Algoritmo hormiga

De Wikipedia, la enciclopedia libre

Tabla de contenidos 1 Algoritmo hormiga 2 Descripción 3 Métodos relacionados 4 Publicaciones

[editar] Algoritmo hormiga

Es el algoritmo de la optimización de la colonia de la hormiga (ACO), introducido por Marco Dorigo [Dor92, DoSt04], es una técnica probabilística para solucionar los problemas de cómputo que se pueden reducir a encontrar las buenas trayectorias a través de gráficos. Está inspirado por el comportamiento de las hormigas para encontrar las trayectorias de la colonia al alimento.

[editar] Descripción

En el del mundo real, las hormigas (inicialmente) vagan aleatoriamente, y en el camino de vuelta a la colonia depositan una hormona denominada feromona. Si otras hormigas encuentran tal trayectoria lo más probable es que sigan esta trayectoria para depositar el alimento en la colonia.

En un cierto plazo, sin embargo, el rastro de la feromona comienza a evaporarse, así se reduce su fuerza atractiva. Cuanto más tiempo sigue una hormiga el recorrido bajo la trayectoria de la feromona, más tiempo tarda este en evaporarse. Cuanto mayor número de hormigas viajan tras esta trayectoria, más intenso es el olor de esta sustancia lo que provoca en las hormigas el estímulo de seguir en esa trayectoria. La evaporación de la feromona tiene también la ventaja de evitar la convergencia a una solución localmente óptima. Si no hubiera evaporación en todas las trayectorias elegidas por las primeras hormigas tenderían a ser excesivamente atractivas para las siguientes. En ese caso, la exploración del espacio de la solución sería muy elevado.

Así, cuando una hormiga encuentra una buena trayectoria de la colonia a una fuente de alimento, es más probable que otras hormigas sigan esa trayectoria, y la regeneración de la feromona provoca que todas las hormigas sigan una sola trayectoria. La idea del algoritmo de la colonia de la hormiga es idéntico al comportamiento de las "hormigas simuladas" que caminan alrededor del gráfico que representa el problema para solucionar.

Los algoritmos de la optimización de la colonia de la hormiga se han utilizado para producir soluciones cercano-óptimas al problema del vendedor que viajaba. El algoritmo de la colonia de la hormiga puede funcionar continuamente y adaptarse a los cambios en tiempo real. Un ejemplo claro lo podemos observar en el encaminamiento de la red y sistemas urbanos del transporte.

Los usos del ACO se utilizan para máquinas de aprendizaje y para problemas con una gran cantidad de datos. Por ejemplo, se ha estudiado que una modificación del ACO básico metaheurístico es crear un modelo del mantenimiento del cementerio en donde las hormigas arraciman los cadáveres de sus semejantes. Esto se ha adaptado a la tarea de supervisión de las maquinas de aprendizaje, encargada de arracimar los grupos de objetos que son similares. De hecho se han demostrado que tales formas modificadas de ACO dan un funcionamiento y una exactitud mejores que los varios métodos clásicos tales como el bien conocido k-means.

[editar] Métodos relacionados

SA es una técnica global relacionada de la optimización que atraviesa el espacio de la búsqueda generando soluciones vecinas de la solución actual. Aceptan a un vecino superior siempre. Aceptan a un vecino inferior probabilistically basó en la diferencia en calidad y un parámetro de la temperatura. Se modifica el parámetro de la temperatura mientras que el algoritmo progresa para alterar la naturaleza de la búsqueda.

TS es similar al recocido simulado, en que ambas atraviesan el espacio de la solución probando mutaciones de una solución individual. Mientras que el recocido simulado genera solamente una solución transformada, la búsqueda del TS genera muchas soluciones transformadas y se mueve a la solución con la aptitud más baja de ésos generados. Para evitar el completar un ciclo y animar el mayor movimiento a través del espacio de la solución, TS se mantiene de soluciones parciales o completas. Se prohíbe para moverse a una solución que contenga los elementos de la lista del tabú, se pone al día mientras que la solución atraviesa el espacio de la solución.

[editar] Publicaciones

• [Dor92] M. Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
• [DMC96] M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26 (1): 29–41.
• [DG97] M. Dorigo & L. M. Gambardella, 1997. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem". IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
• [DDG99] M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.
• [BDT99] E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
• [DS04] M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3