Metaheurística de optimización mediante colonias de hormigas y aplicaciones

Resumen:

La mayoría de los Problemas de Optimización Combinatoria de interés científico o práctico están incluidos en la clase NP-completos, ya que no existen algoritmos exactos con complejidad polinómica que permitan resolverlos. Debido a su intratabilidad, se han diseñado una gran cantidad de métodos aproximados, los cuales encuentran buenas soluciones en tiempos razonables. Uno de estos métodos es la metaheurística de Optimización mediante Colonias de Hormigas (ACO); que tiene su fuente de inspiración en el comportamiento de las hormigas reales, que minimizan el recorrido entre su colonia y cualquier fuente de abastecimiento, basándose fundamentalmente en los rastros de feromona que van dejando a su paso. Para la metaheurística ACO se han propuesto varios algoritmos, que desde su surgimiento han probado su amplia aplicabilidad y eficiencia en la solución de Problemas de Optimización Combinatoria.

Palabras Claves: Optimización mediante Colonias de Hormigas, Sistema de Hormigas, Sistema Colonia de Hormigas, Sistema de Hormigas Max- Min, Sistema de Hormigas con Ordenación, Sistema Mejor-Peor Hormiga, ACO en Dos Etapas.

I. INTRODUCCIÓN

La existencia de una gran cantidad y variedad de Problemas de Optimización Combinatoria incluidos en la clase NP-completos que necesitan ser resueltos de forma eficiente, impulsó el desarrollo de procedimientos para encontrar buenas soluciones, aunque no fueran óptimas. Estos métodos, en los que la rapidez del proceso es tan importante como la calidad de la solución obtenida, se denominan heurísticos o aproximados. Un método heurístico es un procedimiento para resolver un problema de optimización bien definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución [1]. Luego, con el propósito de obtener mejores resultados que los alcanzados por los heurísticos tradicionales surgen los denominados procedimientos metaheurísticos. Los procedimientos metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son efectivos. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y los mecanismos estadísticos [2, 3].

Se han desarrollado varias metaheurísticas para solucionar problemas de optimización, entre ellas se encuentran: Búsqueda Tabú [4], Recocido Simulado [5], GRASP [6], Algoritmos Genéticos [7], Optimización mediante Mallas Dinámicas o Dynamic Mesh Optimization (MDO) [8], Optimización basada en Enjambre de Partículas o Particle Swarm Optimization (PSO) [9, 10] y Optimización basada en Colonias de Hormigas [11, 12], de esta última incluida en la categoría de los algoritmos bioinspirados o de vida artificial e inteligencia colectiva [13], trataremos el presente trabajo.

II. METAHEURÍSTICA DE OPTIMIZACIÓN MEDIANTE COLONIAS DE HORMIGAS

La metaheurística Optimización mediante Colonias de Hormigas o Ant Colony Optimization [14], propuesta para resolver problemas complejos de optimización combinatoria, tiene su fuente de inspiración en el comportamiento de colonias de hormigas reales. Las hormigas son capaces de seguir la ruta más corta en su camino de ida y vuelta entre la colonia y una fuente de abastecimiento. Al desplazarse cada una va dejando un rastro de una sustancia química llamada feromona a lo largo del camino seguido, "transmitiéndose información" entre ellas de esta forma [15]. Las feromonas forman un sistema indirecto de comunicación química entre animales de una misma especie, que transmiten información acerca del estado fisiológico, reproductivo y social, así como la edad, el sexo y el parentesco del animal emisor, las cuales son recibidas en el sistema olfativo del animal receptor, quien interpreta esas señales, jugando un papel importante en la organización y la supervivencia de muchas especies [16].

Al iniciar la búsqueda de alimento, una hormiga aislada se mueve a ciegas, es decir, sin ninguna señal que pueda guiarla, pero las que le siguen deciden con buena probabilidad seguir el camino con mayor cantidad de feromona. Considere la Figura 1 donde se observa cómo las hormigas establecen el camino más corto. En la figura (a) las hormigas llegan a un punto donde tienen que decidir por uno de los caminos que se les presenta, lo que resuelven de manera aleatoria. En consecuencia, la mitad de las hormigas se dirigirán hacia un extremo y la otra mitad hacia el otro extremo, como ilustra la figura (b). Ya que las hormigas se mueven aproximadamente a una velocidad constante, las que eligieron el camino más corto alcanzarán el otro extremo más rápido que las que tomaron el camino más largo, quedando depositada mayor cantidad de feromona por unidad de longitud, como ilustra la figura (c). La mayor densidad de feromonas depositadas en el trayecto más corto hace que éste sea más deseable para las siguientes hormigas y por lo tanto, la mayoría elige transitar por él. Considerando que la evaporación de la sustancia química hace que los caminos menos transitados sean cada vez menos deseables y la realimentación positiva en el camino con más feromona, resulta claro que al cabo de un tiempo casi todas las hormigas transiten por el camino más corto, como se ilustra en la figura (d) [16].

Figura 1: Comportamiento de las hormigas reales.

En analogía con el ejemplo biológico, ACO se basa en la comunicación indirecta de una colonia de agentes simples, llamados hormigas (artificiales), por medio de la huella de feromona (artificial). La huella de feromona en ACO sirve como información numérica distribuida, que las hormigas usan para la construcción probabilística de soluciones del problema a resolver y la adaptan durante la ejecución del algoritmo para reflejar su experiencia de búsqueda [17]. La estructura de un algoritmo genérico de la metaheurística ACO es la siguiente:

1 procedimiento metaheurística_ACO()

2 inicialización_de_parámetros

3 mientras (criterio_de_terminación_no_satisfecho)

4 programación_de_actividades

5 hormigas_y_actividad()

6 evaporación_de_feromona()

7 acciones_del_demonio() {opcional}

8 fin programación_de_actividades

9 fin mientras

10 fin procedimiento

1 procedimiento hormigas_y_actividad()

2 repetir en paralelo desde k=1 hasta número_hormigas

3 nueva_hormiga(k)

4 fin repetir en paralelo

5 fin procedimiento

1 procedimiento nueva_hormiga(id_hormiga)

2 inicializa_hormiga(id_hormiga)

3 L = actualiza_memoria_hormiga()

4 mientras (estado_actual ? estado_objetivo)

5 P = calcular_probabilidades_de_transición(A,L,W)

6 siguiente_estado = aplicar_política_decisión(P,W)

7 mover_al_siguiente_estado(siguiente_estado) si (actualización_feromona_en_línea_paso_a_paso)

8 depositar_feromona_en_el_arco_vistado() fin si

9 L = actualizar_estado_interno()

10 fin mientras si (actualización_feromona_en_línea_a_posteriori)

11 para cada arco visitado

12 depositar_feromona_en_el_arco_visitado()

13 fin para fin si

14 liberar_recursos_hormiga(id_Hormiga)

15 fin Procedimiento

Las hormigas de la colonia se mueven, concurrentemente y de manera asíncrona, a través de los estados adyacentes de un problema, que puede representarse en forma de grafo con pesos. Este movimiento se realiza siguiendo una regla de transición basada en la información local disponible en las componentes o nodos. Esta información incluye una heurística y una memorística (rastros de feromona) para guiar la búsqueda. La inicialización_de_parámetros depende del algoritmo específico, generalmente deben tenerse en cuenta parámetros como: el rastro inicial de feromona asociado a cada transición o arco, el número de hormigas en la colonia, los pesos que definen la proporción en la que afectarán la información heurística y memorística en la regla de transición probabilística. En programación_de_actividades se controla la planificación de tres componentes: la generación y puesta en funcionamiento de lashormigas artificiales; la evaporación de feromona, que se usa como un mecanismo para evitar el estancamiento en la búsqueda y permitir que la hormigas busquen y exploren nuevas regiones del espacio; y las acciones del demonio, utilizadas para implementar tareas desde una perspectiva global que no pueden llevar a cabo las hormigas, por ejemplo, observar la calidad de todas las soluciones generadas y depositar una nueva cantidad de feromona adicional en las transiciones asociadas a algunas soluciones. El procedimiento actualiza_memoria_hormiga() se encarga de especificar el estado inicial desde el que la hormiga comienza su camino y además almacenar la componente correspondiente en la memoria de la hormiga L. La decisión sobre cuál será el nodo inicial depende del algoritmo específico. En los procedimientos calcular_probabilidades_de_transición y aplicar_política_decisión se tienen en consideración el estado actual de la hormiga y el conjunto de arcos del grafo (A), los valores actuales de la feromona visibles en dicho nodo y las restricciones del problema (W) para establecer el proceso de transición probabilístico hacia otros estados válidos. La actualización_feromona_en_línea_paso_a_paso es el procedimiento donde se actualiza el rastro de feromona asociado a un arco, cuando la hormiga se mueve entre los nodos que este conecta. Una vez que la hormiga ha construido la solución puede reconstruir el camino recorrido y actualizar los rastros de feromona de los arcos visitados mediante el procedimiento llamado actualización_feromona_en_línea_a_posteriori [12, 18].

Se han propuesto varios modelos de la metaheurística ACO, entre ellos se encuentran: Sistema de Hormigas o Ant System (AS) [14], Sistema Colonia de Hormigas o Ant Colony System (ACS) [11], Sistema de Hormigas Max-Min o Max-Min Ant System (MMAS) [19], Sistema de Hormigas con Ordenación o Rank-Based Ant System [20], Sistema Mejor-Peor Hormiga o Best-Worst Ant System [21, 22] y ACO en Dos Etapas o Two-Step Ant Colony Optimization (TS-ACO) [23, 24].

EL PRESENTE TEXTO ES SOLO UNA SELECCION DEL TRABAJO ORIGINAL. PARA CONSULTAR LA MONOGRAFIA COMPLETA SELECCIONAR LA OPCION DESCARGAR DEL MENU SUPERIOR.