Optimización de Colonia de Hormigas

1.1.1. Optimización de Colonia de Hormigas
La optimización de colonia de hormigas (ant colony optimization o ACO) se inspira en el seguimiento de sustancias segregadas por esta especie de insectos, denominadas feromonas, que le sirve a su vez a las hormigas como medio de comunicación. Así, el ACO se basa en una población para resolver problemas de optimización combinatoria, inspirado en elcomportamiento de las hormigas en la naturaleza . Los algoritmos de ACO se consideran como parte de los algoritmos de inteligencia de enjambres (swarm intelligence), que es el campo de investigación que estudia algoritmos Bioinspirados por la observación del comportamiento de este tipo de estructura social. Estos algoritmos utilizan individuos que cooperan a través de la auto-organización, y carecende un control central que actúe sobre los miembros del enjambre.

La inspiración biológica de los algoritmos basados en la inteligencia de enjambres proviene del interés de los científicos, en estudiar el comportamiento de varios animales sociales como hormigas, abejas, termitas, aves y peces, capaces de crear complejas y grandes comunidades a partir de sutiles interacciones entre los individuosde las mismas. Adicionalmente, en el campo ingenieril se desea aplicar los resultados de estos estudios para solucionar problemas intrincados en las ciencias de la computación, las redes computacionales y la robótica, entre muchas otras áreas.

Los científicos han observado que muchas especies de hormigas que caminan hacia o desde un depósito de comida, van dejando en el suelo una sustanciaconocida como feromona (pheromone). Esta sustancia posee una influencia en otras hormigas al momento de elegir su ruta, es decir, las hormigas tienden a elegir caminos con una alta concentración de feromona. Lo que les permite seguir un camino de feromona que las lleva a encontrar buenas fuentes de alimentos que han sido previamente identificadas por otros individuos de la colonia. Las hormigas sólodetectan la feromona cuando están en contacto directo con ella, es decir, es un contacto local. En un experimento documentado por Goss en 1.989 y posteriormente realizado por otros investigadores de la comunidad científica, se coloca una colonia de hormigas en un ambiente desconocido para la misma y se ubica una fuente de alimento en los alrededores de la colonia, al principio se observa que lashormigas tienen un comportamiento aleatorio por todo el espacio explorado, pero al cabo de cierto tiempo (conociendo que las hormigas se desplazan a una velocidad constante), la cantidad de feromona depositada aumentara drásticamente en los lugares más transitados, evitando de esta manera su rápida evaporación (ver Figura 2.). Además se observa que las rutas más cortas entre el nido y la fuente dealimento tienden a ser transitadas más frecuentemente por las hormigas, fenómeno que ocurre por la cada vez más fuerte concentración de feromona en los caminos más cortos. En contraparte se ve como las hormigas van haciendo a un lado los caminos más largos.

Si luego se posiciona un nuevo obstáculo en la ruta escogida por la colonia nuevamente se observa un comportamiento de aleatoriedad en lashormigas al momento de escoger como sortear el nuevo elemento, sin embargo, ellas no dejan de depositar el feromona en los caminos transitados originando de este modo una nueva convergencia hacia una nueva ruta más corta entre el nido de la colonia y la fuente de alimento.


Figura 2. Comportamiento de una colonia de hormigas.
1.1.2. Algoritmo de Optimización de Colonias de Hormigas
El modode operación de un algoritmo de optimización de colonias de hormigas es como sigue: las m hormigas (artificiales) de la colonia se mueven, concurrentemente y de manera asíncrona, a través de las posiciones1 adyacentes del problema (que son los nodos del grafo). Este movimiento se realiza siguiendo una regla de transición que está basada en la información local disponible en las componentes...