En computación evolutiva , la búsqueda de población mínima ( MPS ) es un método computacional que optimiza un problema al intentar iterativamente mejorar un conjunto de soluciones candidatas con respecto a una medida dada de calidad. Resuelve un problema al desarrollar una pequeña población de soluciones candidatas mediante operaciones aritméticas relativamente simples.
MPS es una metaheurística, ya que hace pocas o ninguna suposición sobre el problema que se está optimizando y puede buscar espacios muy grandes de soluciones candidatas. Para los problemas en los que encontrar el óptimo global preciso es menos importante que encontrar un óptimo local aceptable en una cantidad fija de tiempo, el uso de una metaheurística como MPS puede ser preferible a alternativas como la búsqueda de fuerza bruta o el descenso de gradiente .
MPS se utiliza para funciones multidimensionales de valor real, pero no utiliza el gradiente del problema que se está optimizando, lo que significa que MPS no requiere que el problema de optimización sea diferenciable como lo requieren los métodos de optimización clásicos, como el descenso de gradiente y los métodos cuasi-newton . Por lo tanto, MPS también se puede utilizar en problemas de optimización que ni siquiera son continuos , son ruidosos, cambian con el tiempo, etc.
De manera similar a la evolución diferencial , MPS utiliza vectores de diferencia entre los miembros de la población para generar nuevas soluciones. Intenta proporcionar un uso eficiente de las evaluaciones de funciones manteniendo un tamaño de población pequeño. Si el tamaño de la población es menor que la dimensionalidad del espacio de búsqueda, entonces las soluciones generadas a través de vectores de diferencia estarán restringidas al hiperplano dimensional. Un tamaño de población menor conducirá a un subespacio más restringido. Con un tamaño de población igual a la dimensionalidad del problema , los "puntos de línea/hiperplano" en MPS se generarán dentro de un hiperplano dimensional. Dar un paso ortogonal a este hiperplano permitirá que el proceso de búsqueda cubra todas las dimensiones del espacio de búsqueda. [1]
El tamaño de la población es un parámetro fundamental en el desempeño de las heurísticas basadas en la población. Las poblaciones más grandes promueven la exploración, pero también permiten menos generaciones, y esto puede reducir la posibilidad de convergencia. La búsqueda con una población pequeña puede aumentar las posibilidades de convergencia y el uso eficiente de las evaluaciones de funciones, pero también puede inducir el riesgo de convergencia prematura. Si se puede evitar el riesgo de convergencia prematura, entonces una heurística basada en la población podría beneficiarse de la eficiencia y la tasa de convergencia más rápida de una población más pequeña. Para evitar la convergencia prematura, es importante tener una población diversificada. Al incluir técnicas para aumentar explícitamente la diversidad y la exploración, es posible tener poblaciones más pequeñas con menos riesgo de convergencia prematura. [1]
La convergencia por umbral (TC) es una técnica de diversificación que intenta separar los procesos de exploración y explotación. La TC utiliza una función de “umbral” para establecer un paso de búsqueda mínimo, y la gestión de este paso permite influir en la transición de la exploración a la explotación, por lo que la convergencia se “retiene” hasta las últimas etapas del proceso de búsqueda. [2] El objetivo de una transición controlada es evitar una concentración temprana de la población en torno a unas pocas regiones de búsqueda y evitar la pérdida de diversidad que puede provocar una convergencia prematura. La convergencia por umbral se ha aplicado con éxito a varias metaheurísticas basadas en la población, como la optimización de enjambre de partículas , la evolución diferencial , [3] las estrategias de evolución , [4] el recocido simulado [5] y los algoritmos de estimación de distribución .
El caso ideal para la convergencia de umbral es tener una solución de muestra de cada cuenca de atracción y que cada solución de muestra tenga la misma aptitud relativa con respecto a su óptimo local. La aplicación de un paso mínimo tiene como objetivo lograr este caso ideal. En MPS, la convergencia de umbral se utiliza específicamente para preservar la diversidad y evitar la convergencia prematura mediante el establecimiento de un paso de búsqueda mínimo. Al rechazar nuevas soluciones que estén demasiado cerca de los miembros de la población actual, TC obliga a una exploración intensa durante las primeras etapas de la búsqueda, al tiempo que preserva la diversidad de la (pequeña) población.
Una variante básica del algoritmo MPS funciona teniendo una población de tamaño igual a la dimensión del problema. Las nuevas soluciones se generan explorando el hiperplano definido por las soluciones actuales (por medio de vectores de diferencias) y realizando un paso ortogonal adicional para evitar quedar atrapado en este hiperplano. Los tamaños de paso se controlan mediante la técnica de convergencia por umbral, que reduce gradualmente los tamaños de paso a medida que avanza el proceso de búsqueda.
A continuación se presenta un esquema del algoritmo:
