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.