Algoritmo de la colonia de hormigas
Inicialmente propuesto por Marco Dorigo en 1992 en su tesis de doctorado,[1][2] el primer algoritmo surgió como método para buscar el camino óptimo en un grafo, basado en el comportamiento de las hormigas cuando estas están buscando un camino entre la colonia y una fuente de alimentos.
La idea original se ha diversificado para resolver una amplia clase de problemas numéricos, y como resultado, han surgido gran cantidad de problemas nuevos, basándose en diversos aspectos del comportamiento de las hormigas.
En nuestro mundo natural, las hormigas (inicialmente) vagan de manera aleatoria, al azar, y una vez encontrada comida regresan a su colonia dejando un rastro de feromonas.
Cuanto más tiempo le tome a una hormiga viajar por el camino y regresar de vuelta otra vez, más tiempo tienen las feromonas para evaporarse.
Un camino corto, en comparación, es marchado más frecuentemente, y por lo tanto la densidad de feromonas se hace más grande en caminos cortos que en los largos.
Por tanto, cuando una hormiga encuentra un buen camino entre la colonia y la fuente de comida, hay más posibilidades de que otras hormigas sigan este camino y con una retroalimentación positiva se conduce finalmente a todas las hormigas a un solo camino.
La idea del algoritmo colonia de hormigas es imitar este comportamiento con "hormigas simuladas" caminando a través de un grafo que representa el problema en cuestión.
[4] [5] El siguiente modelo explica este comportamiento: Las hormigas utilizan el entorno como medio de comunicación.
El mecanismo para resolver un problema demasiado complejo para ser abordado por hormigas solamente es un buen ejemplo de un sistema auto-organizado.
Sin embargo, debido a la retroalimentación, una ligera variación en una arista amplificará y entonces se permitirá elegir una ruta.
El algoritmo se moverá de un estado inestable en el que ninguna arista es más fuerte que otra, a un estado estable donde una ruta está compuesta por las aristas más fuertes.
De esta manera, cada hormiga incrementalmente construye una solución del problema.
Además el algoritmo incluye dos mecanismos más, evaporación del rastro y acciones daemon.
El sistema de hormigas es el primer algoritmo OCH propuesto.
Se corresponde con el funcionamiento descrito en la anterior sección La mejor solución global deposita feromonas en cada iteración junto con todas las otras hormigas.
[7] Todas las soluciones se clasifican de acuerdo su longitud.
La cantidad de feromonas depositadas es ponderada para cada solución, de tal manera que las soluciones con los caminos más cortos depositan más feromonas que las soluciones que con los caminos más largos.
[9] Para algunas variaciones del algoritmo, es posible demostrar que es convergente.
Como muchas metaheurísticas, es bastante difícil estimar la velocidad teórica de convergencia.
En cada iteración del algoritmo, cada hormiga se mueve de un estado
del movimiento, computado por alguna heurística que indica a priori la conveniencia de dicho movimiento y el nivel de rastro
Los rastros son actualizados por lo general cuando todas las hormigas han completado su solución, aumentando o disminuyendo los niveles de los rastros de los movimientos correspondientes que fueron partes de "buenas" o "malas" soluciones respectivamente.
es la cantidad de feromonas depositadas en la transición del estado
Cuando todas las hormigas han completado un solución, los rastros son actualizados por
th hormiga (en la mayoría de los casos es la longitud) y
Muchos métodos derivados han sido adaptados a problemas dinámicos en variables reales, problemas estocásticos, programación paralela y multi-objetivo.
Ellos tienen una ventaja sobre los enfoques: recocido simulado y los algoritmos genéticos en problemas similares cuando el grafo puede cambiar su estructura de manera dinámica, el algoritmo de colonia de hormigas puede seguir corriendo continuamente y adaptar los cambios en tiempo real.
El primer algoritmo de colonia de hormigas, llamado Ant System[11] , tenía como objetivo resolver el problema del viajante, que consiste en encontrar el camino hamiltoniano más corto en un grafo completo.
El algoritmo general es relativamente simple y está basado en un conjunto de hormigas, cada una haciendo una posible ruta entre las ciudades.
De hecho se han demostrado que tales formas modificadas de algoritmos dan un funcionamiento y una exactitud mejores que los métodos clásicos tales como el bien conocido k-means.
