Tema 4.2

 Colonia de Hormigas

Transparencias                                                                       Página Principal                               

Contenidos

1.-

 Descripción.
2.- Funciones heurísticas.
3.- Estrategias para actualizar el rastro.

4.-

 Variantes
Procedimiento de aprendizaje por refuerzo Ant-Q.
MAX-MIN Ant System.

5.-

 Aplicaciones
Se comienza describiendo brevemente el medio empleado por las hormigas para comunicarse entre sí. Además, se pone de manifiesto que el rastro de feromona usado para la comunicación les permite resolver de forma eficiente una gran variedad de problemas: encontrar comida, determinar caminos mínimos entre dos puntos, establecer buenas estrategias de defensa, etc. A continuación, se explica como puede usarse un proceso análogo a éste para obtener soluciones de alta calidad para un problema particular. Inicialmente, se emplea el problema del Viajante de Comercio para ejemplificar el procedimiento, ya que, aparte de ser el primer problema abordado con esta técnica, la explicación sobre el mismo es particularmente clara y sencilla. Sobre este problema se enumeran y detallan diferentes evaluaciones heurísticas y estrategias de actualización del rastro.

El estudio de algunas de las variantes del anterior procedimiento es otro de los elementos tratados en el tema. Se presta especial atención a la variante Ant-Q por ser un procedimiento de aprendizaje por refuerzo. Otra variante estudiada es el MAX-MIN Ant System.

En la sección de aplicaciones se enumeran otros problemas resueltos con estas técnicas a fin de manifestar la gran aplicabilidad del procedimiento.
Objetivos del tema
1.- Conocer los procedimientos de optimización basados en Colonias de Hormigas.
2.- Conocer diferentes evaluaciones heurísticas para un problema.
3.- Valorar el papel que juega el rastro en el proceso de optimización.
4.- Ser capaz de reconocer diferentes estrategias de actualización del rastro.
5.- Conocer algunas de las variantes propuestas del procedimiento.
6.- Ser capaz de proponer procedimientos de optimización basados en Colonias de Hormigas para un problema arbitrario.
7.- Conocer algunas de las aplicaciones de estos métodos.
Material recomendado

1.-

 Ant System: Optimization by a Colony of Cooperating Agents. Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics Vol. 26 No. 1, pp. 29-41 (1996)
Excelente trabajo dedicado al Sistema Hormiga. En el se introduce, en palabras de los autores, este nuevo paradigma computacional. De manera clara y sencilla se describe el procedimiento y se detallan los diferentes elementos que lo forman. Además, se estudian diversas propiedades del Sistema Hormiga, se analiza su comportamiento y se compara la efectividad del mismo frente a otras técnicas de optimización (Búsqueda Tabú y Recristalización Simulada).

2.-

 Ant Colonies for the Travelling Salesman Problem.  Marco Dorigo, Luca Maria Gambardella. Biosystems Vol. 43 pp. 73-81 (1997)
Buen artículo dedicado a la aplicación de la Optimización a través de Colonias de Hormigas al problema del Viajante de Comercio. La principal diferencia que existe entre el método descrito en este trabajo y el descrito en el trabajo anterior radica en la regla de elección de acción empleada. Se usa una de las reglas descritas en el siguiente trabajo. Además, se compara el comportamiento de este método con otros procedimientos inspirados por procesos naturales: Recristalización Simulada, Redes Neuronales, Algoritmos Genéticos y Programación Evolutiva.

3.-

 Ant-Q: A Reinforcement Learning Approach to the Travelling Salesman Problem. Luca Maria Gambardella, Marco Dorigo. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Morgan Kaufmann, pp. 252-260, (1995)
En este trabajo se introduce la familia de procedimientos Ant-Q, que pueden verse como una generalización del Sistema Hormiga. La familia propuesta emplea muchas ideas presentes en el Q-aprendizaje, un tipo de aprendizaje basado en premios retardados (learning with delayed rewards). Las principales diferencias entre el Sistema Hormiga y el Ant-Q se encuentran en la manera en que se elige el próximo elemento que entra a formar parte de la solución (regla de elección de acción), la expresión mediante la cual se actualiza el rastro y la cantidad de rastro que recibe cada acción posible. Además de exponer estas diferencias, en el trabajo se estudian algunas propiedades de la familia Ant-Q y se suministran los resultados computacionales obtenidos al aplicar esta técnica a la resolución de problemas del Viajante de Comercio difíciles.
4.- Improvements on the Ant-System: Introducing the MAX-MIN Ant System. Thomas Stützle, Holger Hoos. ICANNGA97 - Third International Conference on Artificial Neural Networks and Genetic Algorithms, University of East Anglia, Norwich, UK, Springer Verlag (1997)
Mientras experimentaban con el Sistema Hormiga, los autores observaron que, en muchos casos, se producía un estancamiento prematuro que impedía obtener soluciones óptimas. A fin de subsanar este inconveniente se propone limitar a un intervalo el valor que puede tomar el rastro. Se pretende no descartar precipitadamente elementos que pudieran estar en la solución óptima de un problema. Esta mejora, llamada MAX-MIN Ant System, presenta un mejor comportamiento que el Sistema Hormiga.
5.- MAX-MIN Ant System and Local Search for Combinatorial Optimization Problems. Thomas Stützle, Holger Hoos.  2nd Metaheuristics International Conference (MIC-97), Sophia-Antipolis, France (1997)
Se presenta una descripción más detallada del procedimiento MAX-MIN Ant System. Asimismo, se propone una mejora consistente en aplicar búsquedas locales desde soluciones construidas por algunas de las hormigas. De esta forma, el procedimiento híbrido resultante es un Método Multiarranque con un particular mecanismo de generación de soluciones iniciales. Las propuestas son validadas sobre problemas del Viajante de Comercio y de Asignación Cuadrática.