1.

Metaheurística: Optimización por Colonia de

Hormigas
1.1. Introducción
Muchos problemas de optimización pueden volverse muy difíciles de
resolver y se les clasifica como NP-difíciles. A estos tipos de problemas no
se les conoce un algoritmo que pueda darles solución en tiempo polinomial
puesto que tienen espacios de búsqueda muy grandes y tratar de encontrar
una solución a nivel computacional implica una complejidad y uso de recursos
de tiempo y tecnología que las hace imposibles de llevarse a cabo. Por tal
motivo muchos investigadores exploran y proponen muchas técnicas para
darles solución; dentro de estas técnicas encontramos las técnicas
aproximadas que suelen ser conocidas como heurísticas.

1.2. Heurísticas
La palabra "heurística" proviene del verbo griego heuriskein que
significa "encontrar" y ha sido utilizada para referirse a técnicas que brindan
soluciones aproximadas. Podemos definirlas como:

“A un proceso que puede resolver un cierto problema, pero que no

ofrece ninguna garantía de lograrlo (Coello, C. 2003)” (Telles, E.
2007)

Con el propósito de encontrar mejores soluciones aparecen un

nuevo grupo de técnicas, denominadas en la actualidad
“Metaheurísticas”.

1.3. Metaheurísticas
El término Metaheurística fue introducido por primera vez por Fred
Glover en 1986 y hace uso del prefijo “meta” que significa "más allá" pero
usado en el sentido de "nivel superior". Entonces podemos decir que las
Metaheurísticas son métodos que emplean heurísticas pero que nos
ofrecen mejores soluciones.

Osman y Laporte (1996), nos dan una definición más detallada de lo

que es una Metaheurística:
 “Una Metaheurística es formalmente definida como un proceso de
generación iterativo que guía una heurística subordinada al combinar de
manera inteligente diferentes conceptos para explorar y explotar el
espacio de búsqueda, las estrategias de aprendizaje se utilizan para
estructurar la información con el fin de encontrar rápidamente soluciones
cercanas al óptimo”

Otra definición la podemos encontrar en la página web

Metaheuristics, (2016) y dice:

“Una Metaheurística es un conjunto de conceptos que se pueden

utilizar para definir métodos heurísticos que se pueden aplicar a una
amplia serie de problemas diferentes. En otras palabras, una
metaheurística puede ser visto como un marco algorítmico general que
se puede aplicar a diferentes problemas de optimización con
relativamente pocas modificaciones para que sean adaptados a un
problema específico”
(http://www.metaheuristics.org/index.php%3Fmain=1.html)

Las metaheurísticas nos proponen un camino ideal computacional

que nos permite encontrar soluciones muy cercanas al óptimo en un
tiempo computacional aceptable incorporando conceptos de muchos y
diversos campos como las matemáticas, la física, la inteligencia artificial,
la biología, la genética, la neurología, entre otras.

Encontramos así métodos como la Búsqueda Tabú, Búsqueda

Dispersa, Recocido Simulado, Algoritmos Voraces, Algoritmos
Genéticos, Redes Neuronales y muchos otros como la Optimización por
colonia de Hormigas.

1.4. Optimización por Colonia de Hormigas

Optimización por Colonia de Hormigas es una metaheurística
bioinspirada en el comportamiento de recolección de alimentos de las
hormigas y en su capacidad de encontrar una ruta corta entre su nido y una
fuente de alimentos a pesar de que son casi ciegas.
1.4.1. Historia
1.4.1.1. Estigmergía
El entomólogo francés Pierre-Paul Grassé (1959), dedicándose a la
observación del comportamiento de las termitas introdujo el término
estigmergía, la cual deriva de las palabras griegas “stigma” (marca, señal) y
“ergon” (trabajo, acción), para referirse a un tipo de comunicación indirecta
entre las integrantes de una colonia utilizando su medio ambiente y
sustancias químicas, depositadas por ellas, que las estimulaban por el
desempeño logrado.

Este tipo de comunicación se puede observar también en muchas

especies de hormigas que mientras caminan desde el nido hacia una fuente
de comida depositan una sustancia química en el trayecto llamado
feromonas, las cuales pueden “oler” sus compañeras y ser influenciadas a
seguir ese rastro lo que les puede permitir encontrar rutas hacia alimentos
que previamente otra hormiga ha identificado.

Este comportamiento de depositar feromonas sería luego investigado

experimentalmente por otros científicos como Deneubourg (1983) en su
experimento del puente binario.

1.4.1.2. Experimento del Puente Binario

Deneubourg, J. y otros (1983) diseñaron un experimento al que
denominaron “experimento del puente binario”. El experimento consistía en
conectar una fuente de alimentos a un nido de hormigas a través de un
puente que se dividía en dos caminos de igual longitud y que se volvían a
unir al otro extremo, ver Fig 1.
 Figura 1: Imagen del experimento real llevado a cabo por Deneubourg.

Las hormigas en un principio escogieron aleatoriamente

cualquiera de los dos brazos del puente por no existir feromonas en el
camino. Al desplazarse desde el nido hacia la fuente de alimentos las
hormigas empezaron a depositar feromonas en el camino. Por razones
aleatorias uno de los brazos del puente termina presentando mayor
concentración de feromonas llegando un momento en que todas
terminan siguiendo sólo ese brazo del puente influenciadas por la
concentración de feromonas. Al repetir varias veces el experimento
encontraron que las hormigas escogían uno de los brazos del puente en
aproximadamente el 50% de los casos.

Este comportamiento basado en una retroalimentación positiva es

usado por las hormigas para encontrar la ruta más corta entre su nido y
la fuente de alimento como lo demostraría Goss (1989) con su
experimento del puente con brazos dispares.

1.4.1.3. Experimento del Puente de Brazos Dispares

Goss, S. y otros (1989) dirigió otro experimento en el que los brazos del puente
eran esta vez uno más corto que el otro, ver Figura 2.
 Figura 2: Imagen del experimento real llevado a cabo por Goss

En este caso las opciones aleatorias eran más reducidas debido a

que las hormigas que escogían por casualidad el camino más corto eran
las primeras en regresar al nido y al volver hacia la fuente de alimento
eran influenciadas a seguir el camino más corto por presentar un rastro
de feromona más fuerte. Gracias a este mecanismo de retroalimentación
las hormigas terminaban convergiendo hacia el camino más corto.

Estimulados por estos resultados, Goss y compañía desarrollarían

un modelo para explicar el comportamiento observado. Asumiendo que
después de t unidades de tiempo de iniciado el experimento 𝑚1
hormigas han usado el primer brazo del puente y 𝑚2 el segundo, la
probabilidad de escoger el primer puente para la i-esima hormiga (𝑃1 𝑖 )
esta dado por:

(𝑚1 + 𝑘)ℎ
𝑃1 𝑖 =
(𝑚1 + 𝑘)ℎ + (𝑚2 + 𝑘)ℎ
 Donde k y h son parámetros para ajustar el modelo a los datos
experimentales. La probabilidad de que la misma hormiga escoja el
segundo brazo estaría dado por: 𝑃2 𝑖 = 1 − 𝑃1 𝑖 . Simulaciones con Monte
Carlo mostraron un buen ajuste para valores de 𝑘 ≈ 20 𝑦 ℎ ≈ 2. Este
modelo básico inspiraría a Dorigo, M. (1992) a desarrollar los algoritmos
de Optimización basados en Colonias de Hormigas.

1.4.1.4. Dorigo y los algoritmos de optimización basados en colonias

de hormigas
La teoría de optimización por colonia de hormigas fue introducida
y formalizada por Marco Dorigo en su tesis Doctoral en 1992 y desde
entonces ha sido utilizado como herramienta para la solución de
problemas de optimización complejos, como lo es el problema clásico
del agente viajero. El primer algoritmo basado en Colonia de Hormigas
fue presentado por Dorigo y lo llamo Sistema de Hormigas (Ant System)
y posteriormente en 1997 publicaría Sistema de Colonia de Hormigas
(Ant Colony System). Otros autores publicarían años después otras
modificaciones del algoritmo original e introducirían conceptos nuevos.

Todos estos algoritmos basados en colonias de hormigas se

caracterizan por la utilización de hormigas artificiales las cuales
construyen soluciones de forma incremental y su aprendizaje está dado
por el almacenamiento del rastro de feromona de las mejores soluciones
encontradas por estas hormigas artificiales.

1.4.2. Desarrollo de la Metaheurística

1.4.2.1. Del Sistema de Colonia de hormigas naturales, a la
metaheurística

La idea principal del algoritmo consiste en reproducir el

comportamiento de las hormigas en la naturaleza de modo artificial.
Entonces para representar el entorno de las hormigas y sus posibles
 rutas utilizaremos un grafo donde cada arista es parte del camino y cada
nodo representa una bifurcación. Las aristas contienen dos datos:
Información sobre su longitud e información sobre la cantidad de
feromona depositada en él.

La información sobre su longitud nos permitirá inducir a las

hormigas a tomar un camino más corto, esto tiene que ver con la
capacidad de visión de las hormigas. La información sobre la cantidad
de feromona es un valor acumulativo y mientras más alto sea inducirá a
las hormigas a tomar ese camino.

Las hormigas artificiales son entes computacionales

independientes unos de otros y construyen soluciones (crean una ruta)
tomando decisiones estocásticas en cada nodo teniendo en cuenta la
información presente en cada arista. Cada hormiga encontrará una
solución al problema y depositará una cantidad de feromonas siguiendo
un criterio que cambia dependiendo del tipo de algoritmo que estemos
modelando. Luego se analizará las soluciones obtenidas por cada una y
se almacenara en una matriz lo que nos servirá para descartar u
preservar soluciones en los recorridos siguientes. Las feromonas
también sufren un proceso de evaporación que sigue un criterio
dependiendo del tipo de modelo.

1.4.2.2. Estructura Básica de la Metaheurística Optimización por

Colonia de Hormigas
Estructuralmente el algoritmo está basado en una fase de
inicialización y tres procedimientos interrelacionados: Construcción de
Soluciones por hormigas, Actualización de Feromonas y Acciones
Auxiliares. En la figura 3 podemos apreciar el pseudocódigo de esta
algoritmo.
 a. Construcción de Soluciones
Un conjunto de m hormigas artificiales construirán soluciones
moviéndose a través de las aristas de un grafo definido y totalmente
conectado, tomando decisiones estocásticas en cada nodo
influenciadas por los datos contenidos en estas aristas
(concentración de feromonas y distancia) escogiendo una de estas
aristas adyacentes. De este modo, las hormigas construyen
incrementalmente una solución al problema.

b. Actualización de Feromonas
Es el proceso mediante el cual son actualizados los valores de
feromonas presentes en las aristas del grafo. Estos valores pueden
incrementarse debido a que las hormigas depositan feromonas en las
aristas que son parte de su solución o pueden decrementarse por
simulación de evaporación, la que se incluye en el algoritmo para
evitar converger prematuramente en una solución, favoreciendo la
exploración de nuevas áreas.

c. Acciones Auxiliares
Son procedimientos utilizados para implementar acciones que
no pueden ser desarrolladas por las hormigas artificiales como podría
ser la actualización de un parámetro global, la activación de un
procedimiento de búsqueda local, o tomar decisiones que modifiquen
el comportamiento total o parcial del algoritmo.

1.5. Algoritmos de la Metaheuristica Optimización por

Colonia de Hormigas
1.5.1. Algoritmo Sistema de Hormigas
En el algoritmo Sistema de Hormigas se construyen las soluciones de la
siguiente forma: para cada hormiga k en cada paso de construcción se escoge
ir del nodo i al siguiente nodo j, ∀ j , con una probabilidad 𝑃𝑖𝑗𝑘 =
𝛼 𝛽
(𝜏𝑖𝑗 ) ∗(𝜂𝑖𝑗 )
𝛼 𝛽 𝑠𝑖 𝑗 ∈ 𝑁𝑖𝑘
∑ (𝜏 ) ∗(𝜂𝑖𝑗 )
𝑗∈𝑁𝑘 𝑖𝑗
𝑖

donde: 𝑁𝑖𝑘 es el vecindario alcanzable por la hormiga k cuando se encuentra en

el nodo i; α es el factor de escalado de feromona y β el de visibilidad, ambos se
usan para afinar el proceso de búsqueda; 𝜏𝑖𝑗 el valor de feromona en el arco
que une los nodos i y j; 𝜂𝑖𝑗 se denomina función de visibilidad, que depende
totalmente de las características del problema que se va a resolver, por
ejemplo para el TSP es 1/𝑑𝑖𝑗 , donde 𝑑𝑖𝑗 es la distancia entre las ciudades i y j.
Luego se comparan para todas las hormigas sus soluciones encontradas con la
mejor hasta el momento y se modifica esta si alguna de las encontradas la
mejora. En la actualización de la huella de feromona se evapora una proporción
constante de feromona en cada arco y luego cada hormiga una vez que la
solución está completa deposita una cantidad de feromona en dependencia de
la calidad de su solución, o sea, actualización en línea a posteriori.

1.5.2. Algoritmo Sistema Colonia de Hormigas

El algoritmo Sistema Colonia de Hormigas se diferencia del AS en la regla de
transición denominada regla proporcional pseudo-aleatoria, que utiliza el
parámetro 𝑞0 ∈ [0,1] y el valor aleatorio 𝑞 ∈ [0,1] y se calcula 𝑃𝑖𝑗𝑘 como sigue:

Si 𝑞 < 𝑞0

𝛽
1, 𝑠𝑖 𝑗 = 𝑚𝑎𝑥𝑗∈𝑁𝑘 {𝜏𝑖𝑗 ∗ (𝜂𝑖𝑗 ) }
𝑃𝑖𝑗𝑘 = { 𝑖
0, 𝑜𝑡𝑟𝑜𝑠 𝑐𝑎𝑠𝑜𝑠

Si 𝑞 > 𝑞0

𝛼 𝛽
(𝜏𝑖𝑗 ) ∗ (𝜂𝑖𝑗 )
𝑃𝑖𝑗𝑘 = 𝛼 𝛽
𝑠𝑖 𝑗 ∈ 𝑁𝑖𝑘
∑𝑗∈𝑁𝑘(𝜏𝑖𝑗 ) ∗ (𝜂𝑖𝑗 )
𝑖
También existen diferencias en cuanto a la actualización de los rastros de
feromona, pues en ACS las hormigas depositan feromona mientras construyen
sus soluciones, es decir, actualización en línea paso a paso, que incluye
además la evaporación de feromona. Cada vez que una hormiga viaja por un
nodo aplica la regla:

𝑡𝑖𝑗 ← (1 − 𝜑) ∗ 𝑡𝑖𝑗 + 𝑡0

Donde 𝜑 ∈ (0,1] es un parámetro de decremento de feromona. Por otra parte

el demonio actualiza la feromona, o sea, se realiza una actualización de
feromona fuera de la línea de los rastros, para esto el algoritmo sólo considera
la hormiga que generó la mejor solución global Smejor-global. Esta
actualización se hace evaporando primero los rastros de feromona en todas las
conexiones utilizadas por la mejor hormiga global y luego depositando
feromona en las mismas mediante la regla:

𝑡𝑖𝑗 ← 𝜏𝑖𝑗 + ∆𝜏 ∀𝑎𝑖𝑗 ∈ 𝑆𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙

∆𝜏 = 𝑓(𝐶(𝑆𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙 ))

Donde 𝑎𝑖𝑗 es el arco que une los nodos i y j y 𝐶(𝑆𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙 ) es la calidad de

la mejor solución encontrada hasta el momento.

1.5.3. Sistema de hormigas Min-Max (SHMM)

Este sistema di_ere del anterior limitando los niveles de feromona entre _min y
_max,

calculados en una corrida previa del algoritmo. Cuando se alcanza el _max se

reinicia el
algoritmo inicializando las mejores aristas con _max. Esto favorece la
explotaci_on de las

mejores soluciones

1.5.4. Sistema de hormigas con ordenaci_on

Es otra extensi_on del SH propuesto por Bullnheimer, Hartl y Strauss [11]. Se
ordenan

las hormigas para actualizar la feromona, siendo la mejor la m_as privilegiada.

Sistema de la mejor-peor hormiga (SMPH)

Esta versi_on de colonia de hormigas es la que utilizamos en este trabajo.

Detallaremos

a continuaci_on las caracter__sticas esenciales.

Feromona: Se agrega en el mejor camino conocido hasta el momento, y se

resta en el peor.

Adem_as se agrega o resta feromona aleatoriamente, mejorando la diversidad.

Este

concepto proviene de los algoritmos evolutivos [17].

Transici_on: Se usa la misma regla del sistema de hormigas cl_asico.

Evaporaci_on: Se aplica a todas las aristas por igual, tambi_en proveniente del
sistema

cl_asico.

Proceso de mejora: Se realiza una b_usqueda local en las mejores hormigas.

Reinicio: Si no hubo mejoras en cierta cantidad de iteraciones, o cierto tiempo,

se reinicia

la cantidad de feromona.

En la siguiente secci_on describiremos como se aplica esta metaheur__stica a

los problemas

que queremos resolver.

 1.6. Problemas resolubles con OCH.
1.6.1. El problema del vendedor viajero
Este es un caso particular de los problemas de optimizacion

en el cual las variables a controlar son

discretas y las soluciones son un conjunto de permutaciones

o series. La principal caracteristica de

este tipo de problemas es que la funcion objetivo es

compleja, lo cual los hace ideales para trabajar por

och (Bianchi, Gambardella y Dorigo, 2002, p. 2),

(Dorigo y Gambardella, 1996, p. 4).

Dorigo, en su trabajo de tesis, implemento el primer

och aplicado al problema del vendedor viajero

(Travelling Salesman Problem tsp). Este ejercicio

consiste basicamente en un vendedor que inicia su

recorrido en una ciudad aleatoria y quiere encontrar

siempre el camino mas corto para llegar a diferentes

ciudades donde tiene clientes por visitar; finalmente,

termina el recorrido llegando a la ciudad de la que

partio al inicio.

Barcos, Rodríguez y Álvarez (2004, p. 710) y

Reinelt (1994, p. 2) presentan ejemplos prácticos de

como solucionar este tipo de problemas utilizando

och y se muestran resultados y conclusiones que

establecen las ventajas y bondades de este metodo

frente a otros existentes. La ventaja que se obtiene

radica en que se encuentra la distancia total mas

corta que se debe recorrer para visitar las ciudades.

Lo anterior se logra realizando una matriz G=(N,A),

en la que N representa las ciudades y A las distancias

a recorrer. Los rastros de feromona en este caso serian

la deseabilidad de visitar una ciudad x despues

de visitar una ciudad y. De esta forma, se obtiene

una funcion que representa la distancia recorrida y

que se puede optimizar mediante un conjunto de

permutaciones.

1.6.2. El problema de la mochila

El principal fin del problema de la mochila es hallar

un subconjunto de objetos con los cuales se logre

maximizar el beneficio que pueden brindar los objetos

mientras se satisface la condicion de no superar

la capacidad de un contenedor, que en este caso es

la mochila. La solucion a este tipo de problemas

se aplica en la asignacion de procesos en sistemas

distribuidos, en presupuesto de capital, entre otros.

Es importante resaltar que el problema de la

mochila puede ser tratado como un multiobjetivo,

puesto que por una parte se debe minimizar el peso

de los objetos para no sobrepasar la capacidad de la

mochila y por otro se debe maximizar la utilidad

de los objetos.

Ponce, Padilla y Ochoa (2006, p. 2) presentan

un estudio detallado de este tema con simulaciones

y resultados obtenidos.

1.6.3. Problemas de enrutamiento de vehículos

Este problema se convierte en una extension del

hombre viajero (tsp). Consiste en vehiculos estacionados

que tienen que transportar un conjunto

de clientes antes de regresar nuevamente al estacionamiento.

El objetivo es minimizar el numero de

vehiculos utilizados y la distancia total recorrida.

Este planteamiento tiene muchas variaciones que

estan siendo estudiadas y que han permitido obtener

resultados satisfactorios.

1.6.4. Problema de la asignación de horarios

Este es un problema basico que consiste en la

asignacion de horarios a un conjunto de personas.

Para dicha asignación se deben tener en cuenta los

siguientes condicionamientos:

• Los tiempos de cada clase y otras actividades se

conocen con anterioridad.

• Ninguna tarea puede ser interrumpida. Cada tarea

puede ser representada como un mapa por lo que

a cada una le corresponde un nodo. Entonces el

objetivo es obtener una funcion de tareas completas

a partir de la funcion objetivo.

2. Referencias:
Telles, E. (2007). Uso de una Colonia de Hormigas para resolver Problemas de
Programación de Horarios (Tesis de Maestría). Laboratorio Nacional de
Informática Avanzada A. C. Xalapa.

OSMAN, I. H. AND LAPORTE, G. (1996). Metaheuristics: A bibliography. Ann.

Oper. Res. 63, 513–623. Traducción mía.

P.-P. Grassé, La reconstruction du nid et les coordinations inter-individuelles

chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie :
Essai d’interprétation du comportement des termites constructeurs, Insectes
Sociaux, numéro 6, p. 41-80, 1959.

J.L. Denebourg, J.M. Pasteels et J.C. Verhaeghe,Probabilistic Behaviour in

Ants : a Strategy of Errors?, Journal of Theoretical Biology, numéro 105, 1983.

S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, Self-organized shortcuts

in the Argentine ant, Naturwissenschaften, volume 76, pages 579-581, 1989