Lista de metaheurísticas basadas en metáforas

El recocido simulado es un algoritmo probabilístico inspirado en el recocido térmico , un método de tratamiento térmico en metalurgia . Se utiliza a menudo cuando el espacio de búsqueda es discreto (por ejemplo, todos los recorridos que visitan un conjunto determinado de ciudades). Para problemas en los que encontrar el óptimo global preciso es menos importante que encontrar un óptimo local aceptable en un tiempo fijo, el recocido simulado puede ser preferible a alternativas como el descenso de gradiente .

El análogo del enfriamiento lento del recocido simulado es una disminución gradual de la probabilidad de que este acepte soluciones peores a medida que explora el espacio de soluciones. Aceptar soluciones peores es una propiedad fundamental de las metaheurísticas, ya que permite una búsqueda más exhaustiva de la solución óptima.

El algoritmo de optimización por colonia de hormigas es una técnica probabilística para resolver problemas computacionales que pueden reducirse a encontrar buenos caminos a través de grafos . Inicialmente propuesto por Marco Dorigo en 1992 en su tesis doctoral, ^{[ 1 ] [ 2 ]} el primer algoritmo tenía como objetivo buscar un camino óptimo en un grafo basado en el comportamiento de las hormigas que buscan un camino entre su colonia y una fuente de alimento. La idea original se ha diversificado desde entonces para resolver una clase más amplia de problemas numéricos y, como resultado, han surgido varios problemas, basándose en varios aspectos del comportamiento de las hormigas. Desde una perspectiva más amplia, ACO realiza una búsqueda basada en modelos ^{[ 3 ]} y comparte algunas similitudes con los algoritmos de estimación de distribución .

La optimización por enjambre de partículas es un método computacional que optimiza un problema mediante la mejora iterativa de una solución candidata con respecto a una medida de calidad dada. Resuelve un problema a partir de una población de soluciones candidatas, denominadas partículas , y las mueve en el espacio de búsqueda según fórmulas matemáticas sencillas que dependen de la posición y la velocidad de cada partícula . El movimiento de cada partícula está influenciado por su mejor posición local conocida, pero también se guía hacia las mejores posiciones conocidas en el espacio de búsqueda, las cuales se actualizan a medida que otras partículas encuentran mejores posiciones. Se espera que esto mueva el enjambre hacia las mejores soluciones.

El algoritmo PSO se atribuye originalmente a Kennedy , Eberhart y Shi ^{[ 4 ] [ 5 ]} y se concibió inicialmente para simular el comportamiento social ^{[ 6 ]} como una representación estilizada del movimiento de organismos en una bandada de aves o un cardumen de peces . El algoritmo se simplificó y se observó que realizaba una optimización. El libro de Kennedy y Eberhart ^{[ 7 ]} describe muchos aspectos filosóficos de PSO y la inteligencia de enjambre . Poli realiza un estudio exhaustivo de las aplicaciones de PSO . ^{[ 8 ] [ 9 ]} Bonyadi y Michalewicz han publicado una revisión completa de los trabajos teóricos y experimentales sobre PSO. ^{[ 10 ]}

La búsqueda de armonía es una metaheurística que imita fenómenos introducida en 2001 por Zong Woo Geem, Joong Hoon Kim y GV Loganathan ^{[ 11 ]} y está inspirada en el proceso de improvisación de los músicos de jazz. En el algoritmo HS, se genera aleatoriamente un conjunto de posibles soluciones (llamado memoria de armonía). Se genera una nueva solución utilizando todas las soluciones en la memoria de armonía (en lugar de solo dos como se usa en GA) y si esta nueva solución es mejor que la peor solución en la memoria de armonía, la peor solución se reemplaza por esta nueva solución. La efectividad y las ventajas de HS se han demostrado en varias aplicaciones como el diseño de redes de distribución de agua municipales, ^{[ 12 ]} diseño estructural, ^{[ 13 ]} problema de despacho de carga en ingeniería eléctrica, ^{[ 14 ]} optimización multiobjetivo , ^{[ 15 ]} problemas de programación, ^{[ 16 ]} clustering, ^{[ 17 ]} y clasificación y selección de características . ^{[ 18 ] [ 19 ]} Se puede encontrar un estudio detallado sobre las aplicaciones de HS. ^{[ 20 ] [ 21 ]} y las aplicaciones de HS en minería de datos se pueden encontrar en. ^{[ 22 ]}

Dennis (2015) afirmó que la búsqueda de armonía es un caso especial del algoritmo de estrategias evolutivas . ^{[ 23 ]} Sin embargo, Saka et al. argumentan que la estructura de las estrategias evolutivas es diferente de la de la búsqueda de armonía. ^{[ 24 ]}

El algoritmo de colonia de abejas artificiales (ABC) es una metaheurística introducida por Karaboga en 2005 ^{[ 25 ]} que simula el comportamiento de forrajeo de las abejas melíferas . El algoritmo ABC tiene tres fases: abeja obrera, abeja observadora y abeja exploradora. En las fases de abeja obrera y abeja observadora, las abejas explotan las fuentes mediante búsquedas locales en el vecindario de las soluciones seleccionadas con base en la selección determinista en la fase de abeja obrera y la selección probabilística en la fase de abeja observadora. En la fase de abeja exploradora, que es análoga a cuando las abejas abandonan las fuentes de alimento agotadas en el proceso de forrajeo, se descartan las soluciones que ya no son beneficiosas para el progreso de la búsqueda y se insertan nuevas soluciones para explorar nuevas regiones en el espacio de búsqueda. El algoritmo tiene una capacidad de exploración y explotación bien equilibrada .

El algoritmo de las abejas fue formulado por Pham y sus colaboradores en 2005 ^{[ 26 ]} y perfeccionado en 2009 ^{[ 27 ].} Basado en el comportamiento de forrajeo de las abejas melíferas , el algoritmo combina la búsqueda exploratoria global con la búsqueda explotadora local. Un pequeño número de abejas artificiales (exploradoras) explora aleatoriamente el espacio de soluciones (entorno) en busca de soluciones de alta aptitud (fuentes de alimento altamente rentables), mientras que la mayor parte de la población busca (recolecta) en el vecindario de las soluciones más aptas en busca del óptimo de aptitud. Se utiliza un procedimiento de reclutamiento determinista que simula la danza de meneo de las abejas biológicas para comunicar los hallazgos de las exploradoras a las recolectoras y distribuirlas según la aptitud de los vecindarios seleccionados para la búsqueda local. Una vez que la búsqueda en el vecindario de una solución se estanca, se considera que se ha encontrado el óptimo de aptitud local y se abandona el sitio.

El algoritmo competitivo imperialista (ICA), al igual que la mayoría de los métodos en el ámbito de la computación evolutiva , no requiere el gradiente de la función en su proceso de optimización. Desde un punto de vista específico, el ICA puede considerarse la contraparte social de los algoritmos genéticos (AG). El ICA es el modelo matemático y la simulación computacional de la evolución social humana , mientras que los AG se basan en la evolución biológica de las especies.

Este algoritmo comienza generando un conjunto de soluciones candidatas aleatorias en el espacio de búsqueda del problema de optimización. Los puntos aleatorios generados se denominan Países iniciales . En este algoritmo, los Países son el equivalente a los Cromosomas en los AG y a las Partículas en la Optimización por Enjambre de Partículas , y constituyen una matriz de valores de una solución candidata del problema de optimización. La función de coste del problema de optimización determina el poder de cada país. En función de su poder, algunos de los mejores países iniciales (los que tienen el menor valor en la función de coste) se convierten en imperialistas y comienzan a tomar el control de otros países (denominados colonias ), formando así los Imperios iniciales . ^{[ 28 ]}

Los dos operadores principales de este algoritmo son la asimilación y la revolución . La asimilación hace que las colonias de cada imperio se acerquen al estado imperialista en el espacio de características sociopolíticas (espacio de búsqueda de optimización). La revolución provoca cambios aleatorios repentinos en la posición de algunos países en el espacio de búsqueda. Durante la asimilación y la revolución, una colonia puede alcanzar una mejor posición y tener la oportunidad de tomar el control de todo el imperio y reemplazar al estado imperialista actual. ^{[ 29 ]}

La competencia imperialista es otra parte de este algoritmo. Todos los imperios intentan ganar este juego y apoderarse de las colonias de otros imperios. En cada paso del algoritmo, según su poder, todos los imperios tienen la posibilidad de tomar el control de una o más colonias del imperio más débil. ^{[ 28 ]}

El algoritmo continúa con los pasos mencionados (Asimilación, Revolución, Competencia) hasta que se cumpla una condición de parada.

Los pasos anteriores se pueden resumir en el siguiente pseudocódigo : ^{[ 30 ] [ 29 ]}

0) Defina la función objetivo:${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$ 1) Inicialización del algoritmo. Generar alguna solución aleatoria en el espacio de búsqueda y crear imperios iniciales. 2) Asimilación: Las colonias se mueven hacia los estados imperialistas en diferentes direcciones. 3) Revolución: Se producen cambios aleatorios en las características de algunos países. 4) Intercambio de posiciones entre una colonia y el imperialista. Una colonia con una mejor posición que el imperialista, tiene la oportunidad de tomar el control del imperio reemplazando al imperialista actual. 5) Competencia imperialista: Todos los imperialistas compiten por tomar posesión de las colonias de los demás. 6) Eliminar a los imperios sin poder. Los imperios débiles pierden su poder gradualmente y finalmente serán eliminados. 7) Si se cumple la condición de parada, deténgase; si no, vaya al paso 2. 8) Fin

La dinámica de formación de ríos se basa en imitar cómo el agua forma los ríos erosionando el suelo y depositando sedimentos (las gotas actúan como un enjambre). Después de que las gotas transforman el paisaje aumentando o disminuyendo la altitud de los lugares, se dan soluciones en forma de caminos de altitudes decrecientes. Se construyen gradientes decrecientes, y estos gradientes son seguidos por gotas subsiguientes para componer nuevos gradientes y reforzar los mejores. Este método de optimización heurística fue propuesto en 2007 por Rabanal et al. ^{[ 31 ].} Se ha estudiado la aplicabilidad de RFD a otros problemas NP-completos ^{[ 32 ]} , y el algoritmo se ha aplicado a campos como el enrutamiento ^{[ 33 ]} y la navegación robótica ^{[ 34 ]} . Las principales aplicaciones de RFD se pueden encontrar en el estudio realizado por Rabanal et al. en 2017 ^{[ 35 ].}

El algoritmo de búsqueda gravitacional se basa en la ley de la gravedad y la noción de interacciones de masas. El algoritmo GSA utiliza la teoría de la física newtoniana y sus agentes de búsqueda son conjuntos de masas. En GSA, existe un sistema aislado de masas. Mediante la fuerza gravitacional, cada masa del sistema puede observar la situación de las demás. Por lo tanto, la fuerza gravitacional es un medio para transferir información entre diferentes masas. ^{[ 36 ]} En GSA, los agentes se consideran objetos y su rendimiento se mide por sus masas. Todos estos objetos se atraen entre sí mediante una fuerza gravitacional , y esta fuerza provoca el movimiento de todos los objetos hacia los de mayor masa. Las masas más pesadas corresponden a mejores soluciones del problema. La posición del agente corresponde a una solución del problema, y ​​su masa se determina mediante una función de aptitud. Con el paso del tiempo, las masas son atraídas por la masa más pesada, que idealmente presentaría una solución óptima en el espacio de búsqueda. El GSA podría considerarse como un pequeño mundo artificial de masas que obedece las leyes newtonianas de la gravitación y el movimiento. ^{[ 37 ]} Hassanzadeh et al. propusieron en 2010 una variante multiobjetivo de GSA, denominada MOGSA. ^{[ 38 ]}

El algoritmo Bat es un algoritmo basado en inteligencia colectiva, inspirado en el comportamiento de ecolocalización de los micromurciélagos . BA equilibra automáticamente la exploración (saltos de largo alcance alrededor del espacio de búsqueda global para evitar quedarse atascado en un máximo local) con la explotación (búsqueda más detallada alrededor de soluciones buenas conocidas para encontrar máximos locales) controlando el volumen y las tasas de emisión de pulsos de murciélagos simulados en el espacio de búsqueda multidimensional. ^{[ 39 ]}

El algoritmo de optimización en espiral, inspirado en los fenómenos espirales de la naturaleza, es un algoritmo de búsqueda multipunto que no utiliza gradiente de función objetivo. Emplea múltiples modelos espirales que pueden describirse como sistemas dinámicos deterministas. A medida que los puntos de búsqueda siguen trayectorias espirales logarítmicas hacia el centro común, definido como el mejor punto actual, se pueden encontrar mejores soluciones y actualizar el centro común. ^{[ 40 ]}

La inteligencia artificial de enjambre es un sistema de bucle cerrado en tiempo real de usuarios humanos conectados a través de internet y estructurado en un marco modelado a partir de enjambres naturales, de manera que evoca la sabiduría colectiva del grupo como una inteligencia emergente unificada. ^{[ 41 ] [ 42 ]} De esta forma, los enjambres humanos pueden responder preguntas, hacer predicciones, tomar decisiones y resolver problemas explorando colectivamente un conjunto diverso de opciones y convergiendo en soluciones preferidas de forma sincronizada. Inventada por el Dr. Louis Rosenberg en 2014, la metodología ASI se ha destacado por su capacidad para realizar predicciones colectivas precisas que superan a las de los miembros individuales del enjambre. ^{[ 43 ]} En 2016, un grupo de Inteligencia Artificial de Enjambre de Unanimous AI fue desafiado por un periodista a predecir los ganadores del Derby de Kentucky ; acertó con éxito los cuatro primeros caballos, en orden, superando las probabilidades de 540 a 1. ^{[ 44 ] [ 45 ]}