Tema 4

Optimización II

Algoritmos de adaptación
social. Colonia de
hormigas
 Índice
Esquema 3

Ideas clave 4
4.1. Introducción y objetivos 4
© Universidad Internacional de La Rioja (UNIR)

4.2. Concepto de adaptación social 5

4.3. Computación inspirada en colonia de hormigas 9
4.4. Variantes de los algoritmos de colonias de
hormigas 31
4.5. Cuaderno de ejercicios 46
4.6. Referencias bibliográficas 53
 © Universidad Internacional de La Rioja (UNIR)

Tema 4. Esquema
Optimización II
Esquema

3
 Ideas clave

4.1. Introducción y objetivos

En este tema estudiaremos cómo funcionan los algoritmos de computación

bioinspirada referentes a la adaptación social. En concreto, estudiaremos los
algoritmos de colonias de hormigas (ACO, del inglés ant colony optimization) que
forman parte de la familia de métodos metaheurísticos inspirados por la tesis
doctoral de Marco Dorigo en 1992 (Dorigo, Maniezzo y Colorni, 1996), además de
algunas variantes. La inspiración de los algoritmos de colonia de hormigas se basa en
cómo una colonia de hormigas real realiza la detección de alimento. En particular,
estos algoritmos son muy útiles para resolver problemas como el viajante de
comercio o TSP.

El objetivo de este tema es que se comprendan y afiancen los siguientes puntos:

Comprensión del concepto de algoritmo de adaptación social:

¿Qué son?
¿Cómo funcionan?
¿Para qué sirven?

Definición y estructura de los algoritmos de colonias de hormigas.

Aplicación de los algoritmos de colonias de hormigas para resolver problemas de

grafos.

Variantes de los algoritmos de colonias de hormigas. ¿Es posible realizar

modificaciones sobre los algoritmos de colonias de hormigas originales para
mejorar su funcionamiento?

Optimización II
4
Tema 4. Ideas clave
Respecto a este último punto, veremos que sí es posible, estudiando tres variantes:

El sistema de colonia de hormigas.

El sistema de colonia de hormigas max − min.
El sistema de colonia de hormigas mejor − peor.

4.2. Concepto de adaptación social

Hay muchos tipos de algoritmos de computación bioinspirada. Cada uno de estos

tipos de algoritmos trata de modelar el funcionamiento de un suceso observable en
la naturaleza. Como se afirmó antes, nos centraremos en estudiar los algoritmos de
computación bioinspirada basados en adaptación social.

Definición de adaptación social: consideramos como algoritmos basados en

adaptación social a todos aquellos que tratan de imitar el comportamiento
colaborativo que tienen algunas especies de animales en concreto.

Al igual que los humanos, hay muchas especies de animales que colaboran entre sí
con el objetivo de cumplir ciertas tareas que los benefician mutuamente. A
continuación, exponemos algunos ejemplos:

Los avestruces, que poseen una vista muy desarrollada, colaboran con las cebras, que
tienen un fino oído, para alertarse mutuamente de los ataques de posibles
depredadores.

Las garcillas bueyeras y las vacas también colaboran entre sí. Las garcillas comen
pulgas, garrapatas y otros parásitos que se encuentran en la piel de las vacas.
Estas, a su vez, quedan limpias de este tipo de parásitos que, de otra manera, sería
imposible para ellas de eliminar.

Optimización II
5
Tema 4. Ideas clave
No obstante, el ejemplo más claro de colaboración animal se da entre animales de la
misma especie. El más destacado es el de aquellos que viven en colonias de
enjambre, como las hormigas, las abejas o las avispas. La característica más
notoria de estos animales es esta organización en colonias y la especialización de
sus miembros.

De esta manera, es posible observar cómo cada miembro de la colonia cumple una
función asignada y, todas juntas, hacen que la vida en el hormiguero funcione. Es
muy importante, en consecuencia, entender la gran importancia y dependencia que
para estos animales supone la colaboración y la vida en sociedad. Por sí solos serían
incapaces incluso de subsistir, pero juntos son capaces de conseguir grandes cosas.

Los algoritmos de computación bioinspirada basados en adaptación social se nutren

de esa misma idea. A saber:

Una única entidad es incapaz, por sí sola, de conseguir el objetivo planteado,

pero varias entidades colaborando entre sí y compartiendo información
pueden llegar a realizar grandes hallazgos.

Los modelos de las colonias/sociedades de insectos por medio de sistemas

autoorganizativos puede ayudar al diseño de sistemas artificiales distribuidos para la
resolución de problemas.

Comunicación en sociedades de enjambre

Es muy importante comprender que las sociedades de enjambre son sociedades

autoorganizadas, es decir, no hay un coordinador general que le diga a cada
individuo qué debe hacer, por lo que estos se organizan comunicándose entre ellos.
Por ello, esta comunicación entre los distintos miembros que conforman la sociedad
es muy importante.

Optimización II
6
Tema 4. Ideas clave
Podemos distinguir dos tipos de comunicación:

Comunicación directa: se refiere a la comunicación directa entre dos miembros

concretos de la sociedad. Esta puede realizarse mediante intercambio de líquidos,
sonidos, químico (feromonas), etc. Este tipo de mensajes están destinados a
modificar el comportamiento de un único miembro de la sociedad de enjambre.

Comunicación indirecta: se refiere a la comunicación mediante mensajes que

pueden ser recibidos por uno o varios miembros de la sociedad de enjambre. Un
único miembro de la sociedad deja dichos mensajes sobre el entorno en el que se
encuentra, los cuales pueden ser recibidos y entendidos por cualquiera que sea
capaz de interpretarlos. Por lo general, están destinados a modificar el
comportamiento general de la colmena/colonia. Un ejemplo de comunicación
indirecta es el rastro de feromonas que las hormigas dejan al caminar y que
proporcionan información al resto de hormigas del entorno sobre el camino que
se ha tomado desde la salida del hormiguero.

Características de las sociedades de enjambre

Las características más importantes que cumplen este tipo de sociedades en

enjambre son las siguientes:

Comportamiento emergente: este tipo de sociedades no tienen un líder claro y, sin

embargo, cada miembro de la sociedad sabe qué debe hacer y es capaz de llevar
a cabo su labor, haciendo que la sociedad funcione perfectamente. En otras
palabras, no existe la figura de un coordinador general que deba organizarlo todo
y, aun así, todo el enjambre es capaz de organizarse.

Simplicidad en la actuación: cada miembro del enjambre lleva a cabo tareas muy
simples que apenas pueden considerarse inteligentes. Sin embargo, todas estas
acciones simples combinadas generan comportamientos que pueden llegar a ser
muy complejos.

Optimización II
7
Tema 4. Ideas clave
Robustez: las sociedades organizadas en enjambre son muy robustas. Parte de esta
robustez viene dada debido, principalmente, a dos factores:

No existe un líder que organice el funcionamiento de la colmena. Además, al no

haber un líder claro, no hay tampoco posibilidad de que dicho líder falle y haga
que la sociedad en enjambre deje de funcionar.

Hay varios miembros de la colmena dedicados a la misma tarea. De esta manera,

si uno de los miembros de la colmena falla, la sociedad en enjambre puede
seguir su funcionamiento de forma normal, ya que la acción de un único
miembro no es vital.

Flexibilidad: las colonias de enjambre son flexibles y, por tanto, capaces de adaptarse
a los cambios que se produzcan en el entorno. De esta forma, las colonias de
enjambre pueden adaptarse y continuar su funcionamiento normal a pesar de que
ocurran hechos externos que modifiquen el espacio con el que hasta entonces
estaban tratando. Al producirse un cambio, cada miembro individual modifica su
comportamiento en consonancia y, así, se produce un cambio global. De nuevo,
esto es posible gracias a la ausencia de un coordinador general que tome todas las
decisiones.

Un ejemplo de la flexibilidad de la colmena lo vemos en las hormigas a la hora de

buscar comida. Si la ruta que hasta ese momento se estaba siguiendo para
acceder a la fuente de alimento se ve bloqueada, estas son capaces de
modificar su ruta actual y encontrar otra por la que acceder a esa misma fuente
de alimento.

Optimización II
8
Tema 4. Ideas clave
En síntesis, podemos destacar que las colonias de insectos llevan a cabo actuaciones
de nivel complejo de forma inteligente, flexible y fiable, actuaciones que no serían
factibles si tuviesen que ser realizadas por un insecto de forma individual (estos son
no inteligentes, no fiables, simples). Además, los insectos siguen reglas simples y
utilizan comunicación local simple, donde la estructura global (nido) emerge desde
las acciones de los insectos (las cuales son no fiables atendidas individualmente).

4.3. Computación inspirada en colonia de

hormigas

Los algoritmos de colonias de hormigas se basan en el método utilizado por las

hormigas para encontrar alimento y llevarlo a su hormiguero. Está demostrado que
las hormigas, gracias a la comunicación de tipo indirecto que llevan a cabo entre ellas
usando sus feromonas, son capaces de encontrar caminos mínimos entre el
hormiguero y la fuente de alimento.

Figura 1. Etapas del Algoritmo de Colonia de Hormigas. Fuente: adaptado de Archivo:Aco branches.svg, 2006.

Optimización II
9
Tema 4. Ideas clave
De esta forma, son capaces de almacenar en el hormiguero, de forma rápida, toda la
comida localizada en la fuente de alimento. Los algoritmos basados en colonias de
hormigas son ideales para encontrar caminos óptimos dentro de grafos. Son muy
utilizados, sobre todo, en problemas de grafos con gran cantidad de nodos en donde
los métodos tradicionales fallan, debido a que son incapaces de resolver problemas
de grandes dimensiones.

En Ducatelle, Di Caro, Gambardella (2010), se utilizan algoritmos de colonias de

hormigas para encontrar el mejor camino dentro de una red de nodos de
telecomunicación. Debido a la gran aceptación y crecimiento de Internet, es muy
importante encontrar caminos mínimos dentro de las redes de telecomunicaciones
para minimizar el tiempo y ocupación de la red en el envío de paquetes de un nodo
a otro.

Figura 2. Diagrama de una red P2P. Fuente: Botnet, 2010.

Los algoritmos de colonias de hormigas han sido también ampliamente aplicados en

el mundo del automóvil con el objetivo de mejorar los sistemas GPS que ayudan a
los conductores a llegar a su destino en el menor tiempo posible. Por ejemplo, en
Donati, Montemanni, Casagrande, Rizzoli, Gambardella (2008), se describe un
método que tiene en cuenta el momento en el día en el que el conductor está
viajando para intentar trazar rutas que le permitan evitar los recorridos con mayor
tráfico.

Optimización II
10
Tema 4. Ideas clave
 Figura 3. Imagen de GPS con información adicional: velocidad, dirección, etc. Fuente: López, 2020.

Estos son algunos ejemplos que hemos comentado por encima para que, de alguna
manera, se pueda tener una visión de la gran utilidad que tienen este tipo de
algoritmos a la hora de resolver problemas reales con los que un ingeniero
informático debe enfrentarse día a día.

Funcionamiento de las hormigas en la naturaleza

Como ya hemos comentado en el apartado anterior, los algoritmos bioinspirados

basados en colonia de hormigas tratan de imitar el comportamiento seguido por
estos insectos cuando trasladan alimento desde el lugar donde se encuentran al
hormiguero. Dado que las hormigas son ciegas, van dejando a su paso un rastro de
feromonas que luego seguirán cuando vayan a volver al hormiguero. El proceso
seguido por cada una de ellas es el siguiente:

Inicio de la ruta: la hormiga sale del hormiguero y comienza a caminar en busca de

alimento.

Búsqueda del objetivo: durante la travesía, la hormiga detecta si hay rastros de

feromonas de otras hormigas.

Optimización II
11
Tema 4. Ideas clave
 Si lo hay: la hormiga tratará de seguir el camino marcado por el rastro (Figura 4,
imagen A). Esto se debe a que, para vaciar cada fuente de alimento, hace falta
realizar varios viajes. Por tanto, si hay un camino que contiene muchas
feromonas, significa que hay varias hormigas recorriéndolo al mismo tiempo.
Esto puede indicar que alguna ha encontrado una fuente de alimento y que hay
un conjunto de ellas trasladándolo desde esa fuente, lo que hace interesante
seguir ese rastro.

Si no lo hay: la hormiga se moverá por el entorno aleatoriamente buscando una

fuente de alimento de la que obtener recursos.

Figura 4. Búsqueda del objetivo con rastro (A) y sin rastro (B). Fuente: adaptado de Archivo:Aco branches.svg,
2006.

Vuelta al hormiguero: cuando la hormiga ha conseguido localizar la fuente de

alimento, extrae un poco y lo lleva de vuelta al hormiguero. Para ello, sigue su
propio rastro de feromonas o el de otras, en caso de que esta se haya dirigido a
una fuente de comida ya descubierta.

Optimización II
12
Tema 4. Ideas clave
El proceso que acabamos de explicar ha sido ampliamente estudiado, dada su
sencillez y eficiencia para su aplicación, en la resolución de problemas reales. Está
demostrado que colocando el hormiguero en el punto A y la comida en el punto B de
la siguiente Figura 5:

Figura 5. Diagrama de búsqueda de comida. Fuente: elaboración propia

Unas veces, el camino que escogen las hormigas para llegar al alimento es 1 y otras
es 2, por lo que acaban convergiendo a una de las dos opciones. En definitiva, las
hormigas acaban yendo todas hacia B por el mismo sendero. Sin embargo, en la
siguiente Figura 6:

Figura 6. Diagrama de búsqueda de comida. Fuente: elaboración propia.

Está demostrado que las hormigas siempre acaban convergiendo al camino número
2, es decir, al más corto.

En el siguiente ejemplo, denominado de doble arco, el camino que las hormigas

descubren también es el más corto:

Optimización II
13
Tema 4. Ideas clave
 Figura 7. Doble arco. Fuente: adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo, 2007.

La razón principal por la que esto ocurre se encuentra en las feromonas que las
hormigas van soltando en el trayecto. Como ya hemos comentado, en su recorrido,
estos insectos van soltando feromonas. De esta manera, el camino que ha seguido
cada hormiga queda registrado durante un tiempo sobre el terreno. Cuando pasa un
cierto tiempo, el rastro de feromonas desaparece y las demás ya no pueden seguirlo.

En la Figura 8, las hormigas inician su recorrido. Al principio, algunas eligen el camino

1, mientras que otras eligen el camino 2. Al llegar a la fuente de alimento, las
hormigas vuelven, en un principio, por donde han venido. Sin embargo, las que han
seleccionado el camino 2 llegan antes que las que han ido por el camino 1, por lo que
las hormigas del camino 2 hacen más viajes en menos tiempo. Al hacer más viajes, el
camino que siguen contiene más feromona que el camino 1, animando a otras a
escoger el camino 2 en vez del 1.

Figura 8. Caminos elegidos por las hormigas. Fuente: adaptado de Archivo:Aco branches.svg, 2006.

Optimización II
14
Tema 4. Ideas clave
Conforme más hormigas escogen el camino 2, la diferencia entre el nivel de
feromonas de un camino y otro aumenta, hasta que llega un punto en que todas las
escogen el camino 2 en vez del 1 y todo rastro de feromonas desaparece de este
último.

Por supuesto, todo este proceso sucede debido a que las hormigas tienden a escoger
los caminos en donde el nivel de feromonas es mayor. Ellas comprenden que un
camino con un alto nivel de feromonas supone que es muy recorrido por sus
compañeras, lo que implica que lleva hacia un lugar en donde son necesarios sus
servicios. Por este motivo, la probabilidad de la hormiga de tomar ese camino en vez
de otros es mayor.

Estructura de los algoritmos bioinspirados basados en colonias de

hormigas

Basándonos en el proceso previamente explicado, es posible diseñar un algoritmo

que nos permita encontrar caminos mínimos dentro de un grafo, usando el siguiente
pseudocódigo (Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo, 2007):

Optimización II
15
Tema 4. Ideas clave
 Figura 9. Algoritmo: Optimización por colonia de hormigas. Fuente: elaboración propia.

A continuación, iremos analizando, paso por paso, las acciones que van realizando
cada una de las funciones que conforman el pseudocódigo. Como podemos ver, el
pseudocódigo maneja las siguientes variables:

Variable 𝑵: número de hormigas que se dirigen a la fuente de alimento al mismo

tiempo.

Variable 𝑭: indica el nivel de feromonas que cada arco del grafo almacena en un
momento concreto.

Optimización II
16
Tema 4. Ideas clave
Variable 𝑪: establece, en un momento concreto, cuáles son los posibles caminos que
puede seguir una hormiga.

Variable 𝑴: almacena información importante recogida por el conjunto de hormigas

a lo largo de la ejecución del algoritmo. En las versiones más complejas de
algoritmos de colonias de hormigas, esta información puede ser conjuntos de
buenas soluciones ya encontradas, soluciones dadas por otra metaheurística o
información heurística relacionada con el problema que se esté tratando. En las
versiones más sencillas, simplemente: 𝑀 = 𝐹. La idea de la variable 𝑀 es
almacenar toda la información útil posible que ayude a la hormiga a decantarse
por ir hacia un nodo u otro dentro de su valor 𝐶 actual.

Variable 𝑷: hace referencia a la probabilidad de que la hormiga se decante por ir

hacia un nodo u otro dentro de las posibilidades dadas por 𝐶.

Variable pos: indica la posición actual de la hormiga sobre la que se está iterando
dentro del algoritmo.

Variable 𝒙: es un conjunto de las soluciones que han ido encontrando las hormigas.
Es muy recomendable tener siempre la mejor solución almacenada para no
perderla.

Variable 𝒙𝐛𝐞𝐬𝐭 : resultado final obtenido tras la ejecución del algoritmo.

Dentro del pseudocódigo distinguimos dos conjuntos de acciones. Las primeras,

incluidas dentro del for, las realizan cada una de las hormigas. Las otras, localizadas
después del for, se realizan sobre la información global que obtenemos tras
almacenar la experiencia de cada una de las hormigas. A continuación, explicaremos,
paso por paso, qué tareas realizan cada una de las funciones del pseudocódigo:

Actualizar memoria.
Movimientos posibles.

Optimización II
17
Tema 4. Ideas clave
Evaluar movimientos.
Movimiento hormiga.
Depositar feromonas.
Añadir componente.
Actualizar soluciones.
Evaporación de feromonas.
Acciones demonio.
Seleccionar mejor.

Actualizar memoria

Esta función actualiza la información almacenada en la variable 𝑀 con información

relevante obtenida durante la iteración. En el caso más simple, en donde 𝑀 = 𝐹, no
se hace nada. Si en 𝑀 almacenamos mejores caminos encontrados entre nodos y
hemos hallado un camino o subcamino óptimo, podemos almacenarlo en 𝑀 para que
las otras hormigas puedan beneficiarse y tener en cuenta esa información a la hora
de seleccionar el camino a seguir.

Movimientos posibles

Calcula, a partir de la posición actual de la hormiga, los nodos a los que la hormiga
puede moverse (variable 𝐶). La hormiga deberá elegir aleatoriamente, mediante la
probabilidad 𝑃 que se calculará con la función evaluar movimientos, el nodo al que
se moverá a continuación.

Optimización II
18
Tema 4. Ideas clave
 Figura 10. Movimientos posibles. Fuente: elaboración propia.

Evaluar movimientos

Calcula, para cada nodo almacenado en 𝐶, la probabilidad de que la hormiga escoja

ese nodo como próximo destino del camino que está recorriendo. El uso de
probabilidades hace que todos los nodos tengan una cierta probabilidad de ser
escogidos, lo que aumenta la capacidad de este algoritmo de explorar nuevos nodos
y encontrar nuevas soluciones.

Para calcular las probabilidades de elección de cada nodo, utilizamos toda la

información que tengamos a nuestro alcance y que, en el caso de este pseudocódigo,
está almacenada en la variable 𝑀. Empleando la información heurística y la matriz de
feromona que, como ya se especificó, indica la cantidad de feromonas almacenada
en cada nodo, podemos calcular la probabilidad para cada nodo usando la siguiente
fórmula:

𝜏 ∙𝛾
𝑝 =
∈ 𝜏 ∙𝛾

Optimización II
19
Tema 4. Ideas clave
Donde 𝑝 indica la probabilidad para la hormiga 𝑘 de ir del nodo 𝑥 al 𝑦. 𝜏 establece
el nivel de feromonas que hay en el arco que va del nodo 𝑥 al 𝑦. 𝛾 indica la
idoneidad del arco referente a una cierta heurística, que puede ser propia del
problema o resultado de la aplicación de una metaheurística. En el caso más simple:
𝛾 = 1 para todos los casos. 𝛼 y 𝛽 son dos valores que nos permiten regular el
impacto que queremos dar al nivel de feromona y al resultado heurístico
respectivamente.

Figura 11. Evaluar movimientos. Fuente: elaboración propia.

Movimiento hormiga

A partir de las probabilidades calculadas en la función Evaluar movimiento, la

hormiga elige aleatoriamente el nodo al que va a trasladarse a continuación. Los
nodos que tengan probabilidades más altas tendrán más posibilidades de salir
escogidos, mientras que aquellos cuyas probabilidades sean cercanas a 0 serán
escogidos en muy raras ocasiones.

Optimización II
20
Tema 4. Ideas clave
Depositar feromonas

Una vez trasladada, la hormiga incrementa el nivel de feromonas asociado al arco

por el que acaba de pasar. De esa forma, indica a las demás que ella ha pasado por
ese arco. Pueden utilizarse muchas fórmulas para realizar esta tarea. Una de las más
comunes es la siguiente:

1
𝜏(𝑡) = 𝜏(𝑡 − 1) +
Coste

Podríamos leer esto como: el nuevo valor de feromonas para el arco recorrido es
igual al valor anterior más un cierto incremento dependiente de un valor Coste. El
valor Coste dependerá del problema que estemos resolviendo, pero, por lo general,
en los casos más simples, puede considerarse dependiente de la distancia entre los
nodos que la hormiga está recorriendo.

Figura 12. Coste de camino. Fuente: adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo, 2007.

Añadir componente

El arco por el que la hormiga se ha desplazado se añade al recorrido que ha llevado a

cabo desde que salió del nodo inicial y que, dentro del pseudocódigo, se almacena
en la variable 𝑥.

Optimización II
21
Tema 4. Ideas clave
De esta forma, cuando la hormiga termine su recorrido, tendremos almacenado el
camino que ha seguido. Así, podremos evaluar su bondad midiendo parámetros tales
como distancia total recorrida o tiempo transcurrido desde la salida. Dichos
parámetros dependen del problema que queramos resolver.

Figura 13. Nuevo camino almacenado. Fuente: elaboración propia.

Actualizar soluciones

Una vez que la hormiga ha terminado su recorrido por el grafo, se almacena la

solución conseguida en el conjunto de soluciones para su posterior evaluación.
Podemos almacenar solo las soluciones de cada iteración e ir desechando las de
iteraciones anteriores. También es posible y recomendable almacenar siempre la
mejor solución encontrada hasta la fecha para evitar la posibilidad de perderla en
posteriores iteraciones del algoritmo.

Optimización II
22
Tema 4. Ideas clave
 Figura 14. Actualización de soluciones. Fuente: elaboración propia.

Evaporación de feromonas

Una vez que todas las hormigas han realizado el recorrido, es necesario llevar a cabo
el proceso de evaporación de feromonas. En el proceso realizado por las hormigas
naturales en su búsqueda de alimento, dichas feromonas dejadas por estas
desaparecen con el tiempo.

En nuestro algoritmo también hemos de simular este proceso ya que, de no hacerlo,

los valores de feromonas se incrementarían con cada paso en cada uno de los arcos.
Esto haría que todos los arcos tuvieran un nivel de transición alto, haciendo difícil la
convergencia a una única solución.

Por tanto, gracias a la evaporación, reducimos las probabilidades en arcos poco

prometedores, haciendo que las hormigas converjan a una única solución. La
evaporación de las feromonas puede hacerse de forma lenta o rápida, dependiendo
de lo rápido que queramos que converja nuestro algoritmo.

Optimización II
23
Tema 4. Ideas clave
 Una evaporación lenta permite la exploración de muchas soluciones, lo que aumenta
la probabilidad de encontrar mejores caminos. Una convergencia rápida hace que
nuestro algoritmo encuentre una solución rápida, pero de menor calidad. Por lo
general, para la evaporación de feromona, se aplica la siguiente función a cada uno
de los arcos:

𝜏(𝑡) = (1 − 𝜌) ∙ 𝜏(𝑡 − 1)

Donde el valor 𝜌 nos permite regular la cantidad de feromonas que vamos a evaporar
en cada iteración para cada uno de los arcos del grafo.

Figura 15. Camino más corto. Fuente: adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo, 2007.

Acciones demonio

Aunque los algoritmos de colonias de hormigas son algoritmos bioinspirados, no

debemos olvidar que nuestro objetivo principal es el de la optimización. Por tanto,
todas las acciones y métodos que podamos aplicar sobre los algoritmos de colonias
de hormigas que permitan obtener mejores resultados son bienvenidos. Esto incluye
aquellos métodos que no tienen una base natural.

Optimización II
24
Tema 4. Ideas clave
Dentro del pseudocódigo que estamos describiendo, estas acciones se llevarían a
cabo dentro de la función Acciones demonio. Un ejemplo de este tipo de acciones
puede ser la aplicación de un método de búsqueda local que permita refinar
localmente el camino escogido por las hormigas. De esta forma, podemos llegar a
conseguir resultados óptimos y reducimos, en la medida que el método escogido nos
permita, la distancia final recorrida por cada una de estas.

Seleccionar mejor

Por último, una vez que se han llevado a cabo las iteraciones programadas para el
algoritmo, se almacena en la variable 𝑥 el mejor resultado alcanzado. Como ya
hemos comentado, este resultado puede ser el mejor de la última iteración realizada
o el mejor global, en caso de que hayamos ido guardando el mejor resultado que se
ha ido obteniendo en cada iteración.

Es importante recordar que los algoritmos bioinspirados son algoritmos no

determinísticos, por lo que distintas ejecuciones del mismo algoritmo pueden
conllevar la obtención de distintos resultados. Por tanto, es muy aconsejable realizar
varias ejecuciones del mismo algoritmo. Al irse reinicializando todos los valores que
maneja el algoritmo es muy posible que, en cada ejecución, encontremos soluciones
distintas. De esta forma, permitiendo que las hormigas converjan en distintos
caminos, realizaremos una exploración más profunda de la estructura del grafo y
podremos encontrar mejores soluciones que si solo realizamos una única ejecución.

Optimización II
25
Tema 4. Ideas clave
Aplicación de los algoritmos de colonias de hormigas: el problema del
viajante de comercio

Como ya comentamos, los algoritmos bioinspirados de adaptación social de colonias

de hormigas están principalmente diseñados para encontrar caminos mínimos
dentro de grafos de grandes dimensiones. Uno de los problemas más conocidos es
el del viajante de comercio, al que haremos referencia durante el curso y que puede
ser abordado mediante algoritmos de colonias de hormigas.

En este tenemos un conjunto de ciudades situadas a diferentes distancias unas de

otras, todas ellas conocidas. ¿Cuál es la ruta más corta que pasa por todas las
ciudades y permite volver a la ciudad de origen? Aunque este problema pueda
parecer, en principio, trivial, no lo es en el momento en el que el número de ciudades
disponibles es muy alto. Es, sobre todo, en estos casos cuando los algoritmos de
colonias de hormigas pueden ayudarnos a encontrar soluciones que, aunque no sean
las mejores, sí sean óptimas en el sentido de que la distancia de la solución devuelta
sea bastante buena.

Por lo general, podemos expresar el problema del viajante de comercio mediante un

grafo ponderado no dirigido. Representamos las ciudades en los vértices del grafo y
las distancias entre ellas en los pesos de los arcos que las interconectan. En la Figura
16 podremos ver un pequeño ejemplo de un grafo que representa un problema del
viajante de comercio que contiene cuatro ciudades:

Optimización II
26
Tema 4. Ideas clave
 Figura 16. Grafo no dirigido. Fuente: elaboración propia.

Al seleccionar cualquiera de los nodos del grafo como punto inicial y final es posible
aplicar el algoritmo estudiado para permitir a las hormigas explorar los caminos entre
ellas y llegar a una solución óptima.

A continuación, veremos un ejemplo de aplicación en un problema de viajante de

comercio con treinta nodos que trataremos de resolver con una colonia de treinta
hormigas.

Advertencia: para realizar este ejemplo se ha usado el software: ACO – Ant Colony
Optimization Demonstration, disponible en el enlace:
https://borgelt.net/acopt.html

En la Figura 17 podemos ver la distribución de las ciudades sobre el mapa:

Optimización II
27
Tema 4. Ideas clave
 Figura 17. Distribución de ciudades. Fuente: elaboración propia.

Tras aplicar el algoritmo se puede observar que, después de un par de iteraciones,

las hormigas están muy lejos de alcanzar ninguna solución óptima:

Figura 18. Caminos después de dos iteraciones Fuente: elaboración propia.

Optimización II
28
Tema 4. Ideas clave
Sin embargo, poco a poco, iteración tras iteración, las hormigas van refinando y
convergiendo a una muy buena solución. Esta, además, coincide con la mejor
solución. La solución final obtenida puede ver se en la Figura 19:

Figura 19. Refinamiento. Fuente: elaboración propia.

Observemos ahora el mismo proceso con un ejemplo mucho más complicado, un

problema del viajante de comercio con quinientas ciudades. Usando el mismo
software utilizando en el ejemplo anterior, observemos primero una imagen del
mapa de las ciudades:

Figura 20. Mapa de ciudades. Fuente: elaboración propia.

Optimización II
29
Tema 4. Ideas clave
Como podemos apreciar, encontrar un camino mínimo aquí es mucho más
complicado. Por ello, en este ejemplo hemos utilizado una colonia de sesenta
hormigas en vez de las treinta utilizadas en el ejemplo anterior. Tras seis iteraciones,
obtenemos los siguientes resultados:

Figura 21. Seis iteraciones. Fuente: elaboración propia.

Aquí, el mejor camino encontrado tiene una distancia de 84.4105. Observando el

resultado sobre el mapa, vemos que la solución aportada por la colonia de hormigas
dista mucho de ser óptima. Sin embargo, tras mil iteraciones, obtenemos el siguiente
resultado, cuya distancia es de 20.62.

Sobre el mapa podemos observar, aunque el camino encontrado no es el mínimo,

que hemos conseguido alcanzar un resultado bastante bueno. Por último, tras las
cinco mil iteraciones programadas para la optimización, obtenemos una distancia de
20.0673 y el siguiente resultado sobre el mapa:

Optimización II
30
Tema 4. Ideas clave
 Figura 22. Mil iteraciones. Fuente: elaboración propia.

Es importante entender que cuantas más iteraciones programemos del algoritmo,

más tiempo daremos a las hormigas para que sean capaces de refinar los caminos
encontrados. Sin embargo, al hacer esto, estamos consumiendo un tiempo que,
quizás, estemos desperdiciando si el algoritmo ha convergido a una solución óptima
específica y no es capaz de mejorar. En ese segundo caso, siempre es recomendable
reinicializar y empezar de cero para observar si se converge a una solución mejor.

4.4. Variantes de los algoritmos de colonias de

hormigas

Tal y como hemos visto, los algoritmos de colonias de hormigas nos permiten realizar
una exploración inteligente del espacio de soluciones en problemas relacionados
con grafos. Dicha exploración nos proporciona soluciones óptimas y de forma mucho
más rápida que utilizando únicamente la fuerza bruta. Cuando un problema es
demasiado complejo y las metaheurísticas tradicionales nos fallan, siempre podemos
contar con los algoritmos bioinspirados para encontrar buenas soluciones.

Optimización II
31
Tema 4. Ideas clave
En este apartado veremos algunas modificaciones que pueden realizárseles a los
algoritmos de colonias de hormigas para que estos sean aún más eficaces y devuelvan
soluciones óptimas. Muchas de ellas no están relacionadas con aspectos naturales,
pero, aun así, es importante tener en cuenta que el objetivo principal de los
algoritmos de colonias de hormigas no es el de la simulación de un comportamiento
natural, sino la optimización en grafos. En concreto, describiremos en profundidad
los siguientes métodos:

Algoritmos de colonias de hormigas con búsqueda local: estos algoritmos aplican

métodos de búsqueda local a los caminos recorridos por las hormigas con el fin de
mejorar las soluciones obtenidas.

Sistema de hormigas elitista: los sistemas de hormigas elitistas son algoritmos de

colonia de hormigas tradicionales en los que se premia con un extra de feromonas
a aquellas hormigas que encuentran los caminos óptimos.

Sistemas de colonias de hormigas: estos son algoritmos de colonias de hormigas

modificados para permitir una mayor exploración del espacio y un mayor
refinamiento de la solución óptima.

Sistema de colonia de hormigas 𝐦𝐚𝐱 − 𝐦𝐢𝐧: al igual que los dos algoritmos
anteriores, este es una extensión de los algoritmos de colonias de hormigas que
trata de evitar el estancamiento y, a su vez, refinar las mejores soluciones. Para
ello, establece un valor máximo y mínimo a la cantidad de feromonas que pueden
acumular los arcos.

Sistema de hormigas 𝐦𝐞𝐣𝐨𝐫 − 𝐩𝐞𝐨𝐫: este sistema aplica técnicas de computación

evolutiva para mejorar los resultados obtenidos por los algoritmos de colonia de
hormigas básicos.

Optimización II
32
Tema 4. Ideas clave
Algoritmos de colonias de hormigas con búsqueda local

En la función Acciones demonio es posible aplicar métodos de búsqueda local para

refinar las soluciones aportadas por las hormigas y tratar de conseguir mejores
soluciones. Por lo general, la idea consiste en intercambiar, dentro del camino
solución, varias ciudades y comprobar si el resultado obtenido es el mejor. En
problemas como el del viajante de comercio, donde las hormigas deben pasar una
única vez por todos los nodos del grafo y obtener una distancia mínima, dos de las
técnicas de búsqueda local más usadas son las siguientes:

Búsqueda local 2-opt.

Búsqueda local 3-opt.

Búsqueda local 2-opt

Dos ciudades de la solución se intercambian dentro del recorrido y se recalcula la

distancia total. Si dicha distancia es menor que la original, las ciudades se
intercambian definitivamente. Dicho proceso puede hacerse sin tener que sumar la
distancia de todos los nodos mediante la siguiente expresión:

𝐶𝑆 = 𝐶𝑆 − 𝐴(𝑖 − 1, 𝑖) − 𝐴(𝑖, 𝑖 + 1) − 𝐴(𝑗 − 1, 𝑗) − 𝐴(𝑗, 𝑗 + 1)

+ 𝐴(𝑖 − 1, 𝑗) + 𝐴(𝑗, 𝑖 + 1) + 𝐴(𝑗 − 1, 𝑖) + 𝐴(𝑖, 𝑗 + 1)

Donde las ciudades intercambiadas son las de los nodos 𝑖 y 𝑗 y 𝐴 (𝑖, 𝑗) indica la
distancia entre los nodos 𝑖 y 𝑗. El índice 𝑖 − 1 indica el nodo anterior a 𝑖 dentro del
recorrido de la hormiga e 𝑖 + 1 es el nodo siguiente. 𝐶𝑆 es la distancia total del
camino calculado por la hormiga y 𝐶𝑆 es la nueva distancia, tras intercambiar las dos
ciudades dentro de la solución. En el caso de ser 𝐶𝑆 menor que 𝐶𝑆, las ciudades se
intercambian dentro del vector ordenado de nodos por el que ha pasado la hormiga.

Optimización II
33
Tema 4. Ideas clave
Entendamos este proceso mejor con un ejemplo. Imaginemos que tenemos el
siguiente problema del viajante de comercio como el de la Figura 16:

Una de las hormigas ha elegido seguir el camino {𝐶, 𝐷, 𝐵, 𝐴, 𝐶} que, si sumamos la

distancia que hay entre los arcos, nos da un valor de 148. Una iteración de la
búsqueda local cambia las ciudades 𝐴 y 𝐵 dentro del recorrido, con lo que
obtendríamos el siguiente camino: {𝐶, 𝐷, 𝐴, 𝐵, 𝐶} cuya distancia es de 137. Al
tener el camino encontrado tras la iteración de la búsqueda local menor distancia
que el original, se almacena el nuevo camino, {𝐶, 𝐷, 𝐴, 𝐵, 𝐶}, como el encontrado
por la hormiga.

Nótese que, siguiendo la expresión que hemos estudiado de recalculo del coste del
camino, obtenemos el nuevo valor, a partir del antiguo, usando los siguientes
cómputos:

𝐶𝑆 = 𝐶𝑆 − 𝐴(𝐷, 𝐵) − 𝐴(𝐵, 𝐴) − 𝐴(𝐵, 𝐴) − 𝐴(𝐴, 𝐶)

+ 𝐴(𝐷, 𝐴) + 𝐴(𝐴, 𝐵) + 𝐴(𝐴, 𝐵) + 𝐴(𝐵, 𝐶)
137 = 148 − 44 − 30 − 30 − 52 + 45 + 30 + 40 + 30

Búsqueda local 3-opt

Funciona igual que la 2-opt solo que, en vez de dos ciudades, se intercambian tres. La
búsqueda 3-opt da mejores resultados que la 2-opt, ya que explota de forma más
profunda el camino estudiado. A cambio, requiere de un mayor tiempo de ejecución
debido a que deben intercambiarse más ciudades. Dedicar más tiempo a la búsqueda
local implica dedicarle menos tiempo al algoritmo de colonia de hormigas.

Combinando los algoritmos de colonia de hormigas con la búsqueda local,

conseguimos estudiar más a fondo los caminos seguidos por las hormigas, con el
objetivo de mejorar las soluciones, realizando pequeñas modificaciones locales sobre
ellas.

Optimización II
34
Tema 4. Ideas clave
Sistemas de hormigas elitistas

El sistema de hormigas elitista es similar al algoritmo de colonia de hormigas original.

Sus autores (Dorigo, Maniezzo, Colorni, 1996) modificaron la función de actualización
de feromonas con el objetivo de hacer que el algoritmo convergiera de forma más
rápida hacia buenas soluciones. Para conseguirlo, se premia con un refuerzo
adicional de feromonas aquellos caminos que son más prometedores. De esta
manera, conseguimos que las hormigas se centren más en las buenas soluciones y
traten de refinarlas, aunque, a cambio, eliminamos en parte la capacidad inicial que
poseen los algoritmos de colonias de hormigas de explorar diferentes combinaciones
de caminos.

La expresión utilizada para actualizar el valor de feromonas utilizada por este

algoritmo es la siguiente:

⎧ 1
,𝜏 ∉ mejor_solucion
⎪ Coste
𝜏 =
⎨ 1 1
⎪ +𝑒∙ ,𝜏 ∈ mejor_solucion
⎩ Coste Coste

Donde la variable 𝑒 es un valor denominado número de hormigas elitistas, el cual

nos permite regular la cantidad de feromonas que queremos agregar a la mejor
solución encontrada hasta el momento.

Por tanto, lo que esta variación del algoritmo original de la colonia de hormigas hace
es, a cada iteración, reforzar la mejor solución encontrada hasta el momento
simulando que un conjunto ficticio 𝑒 de hormigas ha pasado por allí. De esta forma,
los arcos pertenecientes a la mejor solución encontrada se refuerzan
automáticamente, animando a otras hormigas a utilizarlos.

Optimización II
35
Tema 4. Ideas clave
La ventaja de este sistema es que consigue que las hormigas converjan antes a
buenas soluciones y permite realizar un refinamiento del espacio de esas
soluciones. En otras palabras, se dedica tiempo de cómputo a comprobar caminos
similares a la mejor solución con el objetivo de mejorar aún más el mejor camino
encontrado hasta ese momento. Cuando alguna hormiga encuentra un camino cuya
distancia es mejor a la actual, el camino anterior deja de promoverse y el extra de
feromonas se aplica sobre el nuevo mejor camino encontrado.

El sistema de colonia de hormigas

El sistema de colonia de hormigas es una modificación del algoritmo original que trata
de promover la exploración del espacio y, a su vez, la rápida explotación de soluciones
prometedoras. Incluye, en total, tres modificaciones diferentes sobre el algoritmo
original, las cuales expondremos a continuación.

Modificación de la función que establece la selección del siguiente nodo

La función de selección del siguiente nodo pasa a promover la selección del nodo que
contiene más feromonas. Se establece una probabilidad 𝑞 a partir de la cual se
escogerá, como siguiente nodo, el mejor nodo del vecindario. Para cada
desplazamiento de hormiga, el algoritmo lanza un valor aleatorio 𝑞 :

Si 𝑞 > 𝑞, utiliza el algoritmo de selección de nodo tradicional que ya vimos en la

sección anterior.

Si 𝑞 ≤ 𝑞, escoge directamente como siguiente arco a recorrer el mejor del

vecindario.

Optimización II
36
Tema 4. Ideas clave
De esta manera, la probabilidad de las hormigas de escoger, como siguiente nodo,
aquel que tenga más cantidad de feromonas es mucho más alta que en el algoritmo
de hormigas tradicional. Debemos tener en cuenta que, en la opción dos, también se
genera una probabilidad alta de escoger el arco más prometedor, puesto que este
tendrá siempre más probabilidades que los demás al guardar más feromonas.

Nueva función de actualización de feromona

En el algoritmo tradicional de hormigas, el nivel de feromonas aumentaba cada vez

que una de ella pasaba por un arco. Esto permitía que las otras hormigas supieran
que habían pasado por allí y daba más probabilidad a ese arco de ser transitado. Este
hecho hacía más probables de transitar a aquellos arcos que ya habían sido
transitados, incluso aunque no proporcionaran las mejores soluciones.

Para evitar esto, el sistema de colonia de hormigas solo aumenta las feromonas de
aquellos arcos pertenecientes a la mejor solución encontrada hasta el momento. De
esta manera, conseguimos que las hormigas se centren en trabajar sobre las mejores
soluciones, evitando aquellas que, aunque son buenas, no son óptimas como la
mejor encontrada hasta el momento. Por tanto, se aplica una actualización de
feromonas sobre los arcos pertenecientes a la mejor solución, siguiendo la siguiente
expresión:

1
𝜏 (𝑡) = (1 − 𝜌) ∙ 𝜏 (𝑡 − 1) + 𝜌 ∙
𝐶

Donde el valor 𝜌 nos permite regular el aumento que queremos realizar y 𝐶 es un

valor indicativo del coste o distancia que se ha conseguido con la mejor solución.

Optimización II
37
Tema 4. Ideas clave
Evaporación local de feromonas

Uno de los problemas que tienen los sistemas de hormigas tradicionales es su rápida
convergencia a una solución específica. Dado que las hormigas siempre tienden a
escoger los caminos que ya han seguido otras, llega un momento en que el algoritmo
converge y no se exploran nuevas soluciones, sino que solo se producen pequeñas
modificaciones sobre la solución encontrada actual. Aunque este tipo de pequeñas
modificaciones es bueno y nos permite refinar la solución encontrada, una rápida
convergencia a una solución concreta evita que se exploren nuevas posibilidades y
caminos.

Para evitar esto y permitir que el algoritmo de colonia de hormigas encuentre nuevas
soluciones diferentes a la mejor actual, el sistema de colonia de hormigas
decrementa, en vez de incrementar, el nivel de feromonas cada vez que una hormiga
pasa por un arco. Esto permite que las hormigas sigan distintos caminos y aumenta
las probabilidades de explorar nuevos en vez de seguir los ya encontrados. De esta
forma, el algoritmo tarda mucho más en converger a una única solución y exploramos
muchos más posibles caminos antes de que esto ocurra.

Figura 23. Elección de camino. Fuente: adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo,
2007.

La evaporación local de feromonas, combinada con la función de actualización de

feromonas y la nueva función de selección de arco, permiten una mejor exploración
del espacio, pero también un refinamiento de la mejor solución encontrada hasta el
momento. De esta manera, promovemos una mayor exploración del espacio y una
explotación únicamente de la mejor solución encontrada hasta el momento.

Optimización II
38
Tema 4. Ideas clave
El sistema de colonia de hormigas max-min

El sistema de colonia de hormigas max − min tiene una filosofía similar al del sistema
de colonias de hormigas. Su objetivo es evitar la rápida convergencia del algoritmo
original y realizar, a su vez, un refinamiento sobre la mejor solución encontrada hasta
el momento. Para ello, realiza cinco modificaciones sobre el algoritmo de colonia de
hormigas original, las cuales expondremos a continuación:

Topes mínimo y máximo para el valor de feromona: en los algoritmos tradicionales

de colonias de hormigas es muy típico que, tras una alta cantidad de iteraciones,
los arcos pertenecientes a la mejor solución encontrada hasta el momento tengan
una muy alta cantidad de feromonas y los demás arcos una cantidad muy baja. Es
por esto por lo que, muy rara vez, las hormigas explorarán y pasarán por arcos que
no pertenezcan a la mejor solución encontrada hasta el momento.

Para evitar esta convergencia y estancamiento y promover, con una cierta

probabilidad, que las hormigas investiguen nuevos caminos, el sistema de
colonia de hormigas max − min establece un tope máximo y mínimo de
feromonas en los arcos. De esta forma, todos los arcos tendrán un cierto nivel
de feromonas mínimo y los caminos más transitados no podrán sobrepasar un
tope máximo. Esto permite incrementar la probabilidad de que las hormigas
visiten nuevos arcos sin hacer que la probabilidad de los nuevos arcos sea
mayor que la de la mejor solución, ya que ese hecho implicaría el no
refinamiento de la mejor solución encontrada.

Inicialización del algoritmo con el máximo valor de feromonas: otra de las

características no biológicas de este algoritmo es que, al comienzo de este, los
rastros de feromonas son inicializados al máximo valor posible. Debido a que
podemos controlar la rapidez con que estas se evaporan, este hecho hace que la
exploración del espacio típica producida por este tipo de algoritmos en las
primeras iteraciones sea de una duración mayor. Es muy importante realizar una
buena exploración del espacio de soluciones antes de permitir que el algoritmo

Optimización II
39
Tema 4. Ideas clave
 converja a una buena solución y refinarla ya que, de esta manera, evitamos caer
en caminos óptimos locales que pueden ser de mucha menos calidad que otras
posibles soluciones.

Figura 24. Caminos. Fuente: adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo, 2007.

Reinicialización de la búsqueda: es muy típico de los algoritmos de colonias de

hormigas tradicionales que estos converjan a una única solución antes del final de
las iteraciones programadas. Esto hace que se pierda tiempo de cómputo que
podría dedicarse a la exploración de nuevas soluciones. Es por ello por lo que, en
los algoritmos de colonias de hormigas max − min, si se detecta que durante un
número específico de iteraciones la solución obtenida no mejora, el algoritmo se
reinicializa y se comienza desde cero.

Para ello, se mantiene la mejor solución obtenida hasta el momento, pero se

inicializan todos los valores de feromona de los arcos a su máximo valor.
Empezando desde cero, se da una oportunidad al algoritmo de que encuentre
otras soluciones por otros caminos que puedan incluso superar a la mejor
solución actual. Además, evitamos el estancamiento, aprovechando al máximo
el tiempo que las iteraciones del algoritmo nos proporcionan.

Optimización II
40
Tema 4. Ideas clave
 Figura 25. Camino óptimo. adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego Carrillo, 2007.

Modificación del mecanismo de aporte de feromonas: al igual que ocurría en el

algoritmo de colonia de hormigas, solo se aumenta las feromonas de la mejor
solución, ya sea de la iteración actual o la global. Gracias a esta estrategia,
conseguimos que el algoritmo trabaje sobre la mejor solución encontrada en vez
de refinar soluciones que son menos prometedoras.

Cuando escogemos trabajar sobre la mejor solución global, solo nos centramos
en esa solución específica debido a que es la mejor encontrada hasta el
momento y tratamos de sacarle el máximo partido.

Si escogemos la mejor solución de la iteración, permitimos al algoritmo que refine

y trabaje sobre soluciones prometedoras que, aunque no sean la mejor global,
podrían aspirar a obtener mejores resultados que la mejor solución encontrada
hasta el momento.

Optimización II
41
Tema 4. Ideas clave
 Es importante destacar que es muy complicado saber cuál de las dos opciones
es mejor. En unos casos funcionará mejor la primera y en otros, la segunda.
Dado que los algoritmos de colonias de hormigas son no determinísticos, en la
bondad de la solución obtenida interfiere, muchas veces, la suerte que el
algoritmo tenga en la exploración y explotación del espacio más que el
refinamiento que realicemos de una solución prometedora u otra.

Evaporación de feromonas: en el algoritmo de sistema de colonias de hormigas no

se tocaba el valor de feromonas de los arcos que no habían sido transitados por
ninguna hormiga. Sin embargo, en el algoritmo de sistemas de colonias max −
min, sí realizamos un proceso de evaporación de los rastros de feromonas de
todos los arcos del grafo. Es importante recordar que, dado que hay un tope
máximo y mínimo de feromonas, las feromonas de los arcos nunca llegarán a valer
cero y siempre habrá una posibilidad determinada de que ese arco sea visitado
por una hormiga.

Gracias a las modificaciones propuestas, el sistema de colonia de hormigas max −

min permite un mayor aprovechamiento de las iteraciones del algoritmo. Sus
modificaciones van encaminadas a realizar una mayor exploración inicial del espacio
de soluciones y a un refinamiento de, únicamente, la mejor o mejores soluciones
encontradas.

El sistema de colonia de hormigas mejor − peor

El sistema de colonia de hormigas mejor − peor, al igual que el max − min y el

sistema de colonia de hormigas, trata de aplicar técnicas que permitan una mayor
exploración del espacio. Además, este algoritmo tiene como objetivo conseguir un
refinamiento mayor de las mejores soluciones y un aprovechamiento máximo del
número de iteraciones del algoritmo. Los cambios propuestos por el sistema de
colonia de hormigas mejor − peor sobre el algoritmo de colonia de hormigas original
son los siguientes:

Optimización II
42
Tema 4. Ideas clave
Actualización de feromonas de la mejor y la peor hormiga.
Mutación sobre los rastros de feromona de los arcos.
Mecanismo de reinicialización.

Actualización de feromonas de la mejor y la peor hormiga

En el sistema de colonia de hormigas mejor − peor se realiza la evaporación e

incremento de feromonas siguiendo tres pasos:

Evaporación de todos los rastros de feromona: evaporamos feromonas en todos los

arcos del grafo. Esto incluye a la mejor solución tanto de la iteración como la
global.

Incremento de la feromona de la mejor solución: al igual que en el sistema de colonia

de hormigas, realizamos un incremento de feromonas únicamente en la mejor
solución encontrada hasta el momento. De esta forma, todos los arcos pierden
feromonas en cada iteración menos aquellos pertenecientes a la mejor solución.

Decremento extra en la peor solución encontrada: el sistema de colonia de hormigas

mejor − peor aplica una evaporación extra en los arcos pertenecientes a la peor
solución encontrada hasta el momento. De esta forma, evitamos que las hormigas
sigan explorando esos arcos y se concentren en otros que proporcionen mejores
resultados. De esta forma, cuando algún arco que sea especialmente malo
aparezca en muchas soluciones, este algoritmo reduce su nivel de feromonas
asociado y evita que las hormigas lo frecuenten.

Optimización II
43
Tema 4. Ideas clave
Mutación sobre los rastros de feromona de los arcos

Con el objetivo de explorar nuevas soluciones, se aplica un operador de mutación

sobre el nivel de feromona de los arcos del grafo. Este proceso se lleva a cabo con
una probabilidad muy baja y su objetivo es incrementar o decrementar
aleatoriamente el valor de feromonas de los arcos del grafo con el fin de permitir a
las hormigas explorar nuevas soluciones.

El cambio en el valor de feromonas nunca es drástico y se mueve dentro del rango

[−𝜏, … ,0, … , 𝜏], donde el valor 𝜏 indica el máximo incremento o decremento que
puede realizarse sobre la feromona. La probabilidad de aplicar este operador debe
ser muy baja ya que, de ser alta, podría interrumpir el proceso normal de
convergencia, evitando el refinamiento de buenas soluciones. Esto podría conllevar,
incluso, a la obtención de soluciones mucho peores que las del algoritmo de colonia
de hormigas original.

Es muy aconsejable ir variando el valor de probabilidad del operador de mutación

de menos a más. De esta forma, en iteraciones tempranas del algoritmo, dejamos
que las hormigas exploren y converjan a una buena solución. Posteriormente, tras la
convergencia, un valor de probabilidad algo más elevado del operador de mutación
permitiría a las hormigas explorar nuevos arcos. De esta manera, podemos encontrar
otras soluciones prometedoras o, incluso, mejorar la mejor solución encontrada en
ese momento.

Optimización II
44
Tema 4. Ideas clave
 Figura 26. Soluciones momentáneas. Fuente: adaptado de Duarte Muñoz, Pantrigo Fernández y Gallego
Carrillo, 2007.

Mecanismo de reinicialización

Al igual que en el sistema de colonia de hormigas max − min, cuando se detecta que
no se ha mejorado la mejor solución encontrada durante un número determinado de
iteraciones, se realiza un proceso de reinicialización, en este proceso se ponen todos
los parámetros a cero, se almacena la mejor solución encontrada y el algoritmo
empieza a buscar una nueva mejor solución. El motivo de esta modificación, como ya
comentamos, es evitar perder el tiempo iterando sobre la misma solución y
aprovechar para explorar nuevos caminos.

Mediante estas modificaciones, podemos observar cómo el algoritmo de colonia de

hormigas mejor − peor mejora tanto la exploración de nuevas soluciones como el
refinamiento de las soluciones prometedoras encontradas. Con el objetivo de
mejorar la exploración de nuevas soluciones, se utilizan el mecanismo de
reinicialización y la mutación sobre el nivel de feromonas de los arcos. Para mejorar
el refinamiento de las buenas soluciones, se utiliza el mecanismo de aumento y
decremento de feromona expuestos.

Optimización II
45
Tema 4. Ideas clave
Algoritmo de colonia de hormigas para problemas en el continuo

Para finalizar con la descripción que se ha hecho de algunas variantes del algoritmo
de colonia de hormigas, cabe mencionar el caso particular de una variante dirigida,
más que a problemas combinatorios, a optimización sobre el continuo, es decir, un
algoritmo de colonia de hormigas para optimización sobre el continuo. En el
siguiente vídeo, se habla un poco más al respecto.

4.5. Cuaderno de ejercicios

Ejercicio 1

El problema del viajero consiste en encontrar el tour de menor distancia de

recorrido, pasando una sola vez entre 𝑀 ciudades. Si la distancia asociada al viaje de
la ciudad 𝑖 a la 𝑗 es 𝑑 , y si 𝑥 vale cero o uno dependiendo si el tránsito de la ciudad
𝑖 a la 𝑗 se excluye o incluye, respectivamente, la función objetivo se puede escribir
como:

𝑓(𝑠) = 𝑑 𝑥
, ∈{ ,…, }

Establezca los parámetros del algoritmo de colonia de hormigas para este problema.

Optimización II
46
Tema 4. Ideas clave
Solución

Los parámetros que hay que definir son:

Las probabilidades de transición de los arcos.

El incremento de feromonas.

Para establecer las probabilidades de transición es necesario conocer la cantidad de

feromonas por arco 𝜏 , la idoneidad por arco 𝛾 y los índices de relevancia, 𝛼 y 𝛽,
de estas cantidades, respectivamente. La cantidad de feromonas inicial se puede
considerar como uno para todos los arcos, si no se cuenta con información previa.
Después, a medida que avanzan las iteraciones, estas cantidades se sabe que
incrementarán con ayuda de la fórmula de refuerzo.

La aproximación más simple, la idoneidad, puede ser uno para todos los arcos de
manera constante y dejar que la probabilidad solo dependa de las feromonas en el
camino, con lo cual automáticamente es innecesario establecer el parámetro 𝛽,
mientras que el parámetro 𝛼 no tiene mayor relevancia y puede ser uno.

En una versión más sofisticada, la idoneidad puede ser el recíproco de la distancia o

también un costo asociado a cada arco. Por último, el incremento en feromonas,
cuando se ha pasado por determinado arco, se puede establecer, para este caso,
como una función de la distancia. De hecho, puede ser tan simple como hacer
Coste = 𝑑 . La fórmula de refuerzo de feromonas quedaría como:

1
𝜏 =𝜏 +
𝑑

Mientras que la fórmula de transición de probabilidades sería:

𝑃 =∑

Optimización II
47
Tema 4. Ideas clave
Ejercicio 2

Para el caso del Ejercicio 1, siendo 𝜏 la cantidad de feromonas en el arco del nodo 𝑖
al 𝑗, y si para 𝑗 = 1, 2, 3, 4, 5, 6, las cantidades de feromonas son 1, 2, 4, 3, 5, 2,
respectivamente. Obtenga el posible arco que escogería una hormiga en el nodo 𝑖,
bajo una elección por ruleta utilizando el valor 𝑟 = 0.4921, generado de una
distribución uniforme en [0,1].

Solución

Con la información de feromonas se puede construir la siguiente tabla, donde se

calcularon las probabilidades de acuerdo con la cantidad de feromonas en cada
transición para determinar los intervalos de la distribución discreta de probabilidad.

Tabla 1. Feromonas en transición. Fuente: elaboración propia.

Los intervalos de la última columna sirven para que, dado un número aleatorio en
[0,1], se pueda obtener, a su vez, un número aleatorio de la distribución de
probabilidades de la columna de 𝑝 . Dado que el valor 𝑟 = 0.4921 cae en el intervalo
de la fila 𝑗 = 4, este sería el nodo de transición o nueva posición.

Optimización II
48
Tema 4. Ideas clave
Ejercicio 3

Implementa un código en Matlab para resolver el problema del Ejercicio 1,

considerando la red de ciudades que se muestra en el diagrama siguiente:

Figura 27. Nodos y conexiones. Fuente: elaboración propia.

Solución

El código desarrollado fue el siguiente:

%%% COLONIA DE HORMIGAS %%%

N = 10; % número de hormigas
M = 5; % número de nodos o ciudades
I = 20; % número de iteraciones
rho = 0.25; % parámetro de evaporación

rng('shuffle')
ss = zeros([N,M]); % almacen de mejores soluciones
d = [0 4 2 10 5; 4 0 3 5 1; 2 3 0 7 1; 10 5 7 0 4; 5 1 1 4 0]; % matriz de
distancias entre ciudades
tau = ones([M,M]); % declaración de matriz de feromonas
cs = repelem(M*max(d,[],'all'),N,1); % costos de tour por hormiga
for l = 1:I

Optimización II
49
Tema 4. Ideas clave
for n = 1:N
J = 1:M;
s = zeros([1,M]);
s(1) = randi(M); % posición actual (nodo inicial)
c = 0;
for k = 2:M
i = s(k-1); % índice de salida o del nodo actual
J = J(i~=J); % posiciones potenciales (nodos posibles s continuación)
P = tau(i,J)/sum(tau(i,J)); % probabilidades de transición
cumP = cumsum(P); % prbabilidades acumuladas
cumP(end) = 1; % asegura que el redondeo no afecte la acumulación
j = J(find(rand <= cumP,1,"first")); % selección por ruleta del índice de
llegada
tau(i,j) = tau(i,j) + 1/d(i,j); % actualiza el valor de feromonas del arco
s(k) = j; % guarda la posición siguiente
c = c + d(i,j); % actualiza el costo por el tránsito del arco (i,j)
end
tau(s(end),s(1)) = tau(s(end),s(1)) + 1/d(s(end),s(1)); % incluye las
feromonas al regresar al nodo inicial
c = c + d(s(end),s(1)); % calcula el costo de regreso
if cs(n) > c % criterio de minimización
cs(n) = c; % actualiza el mejor costo hasta ahora
ss(n,:) = s; % actualiza el mejor tour
end
end
tau = (1-rho)*tau; % aplica la evaporación
end
% imprime la mejor solución en pantalla
disp('Solución:')
[cmin,imin] = min(cs);
disp('Tour: '+strjoin(string(ss(imin,:))))
disp('Distancia:'+string(cmin))

La solución obtenida es: [1 2 4 5 3] con una distancia de 16.

Optimización II
50
Tema 4. Ideas clave
Ejercicio 4

Un tipo de hormiga en América Central llamada Pachycondyla apicalis basa su

búsqueda de alimento en imágenes de regiones más que en el seguimiento de
caminos de feromonas. Si, ahora, en vez de tener un camino se tiene una región o
dominio continuo entre dos nodos, ¿qué implicaciones podría tener esto sobre el
algoritmo que se ha descrito?

Solución

La idea de que las hormigas de la especie Pachycondyla apicalis basen su búsqueda

de alimento en imágenes de regiones en lugar de seguir el rastro de feromonas es
interesante y sugiere un enfoque diferente en comparación con muchas otras
especies de hormigas. Si consideramos un escenario en el que dichas hormigas
buscan alimento en un dominio continuo entre dos nodos en lugar de seguir un
camino definido por feromonas, hay varias implicaciones potenciales para el
algoritmo que podría estar involucrado en este comportamiento:

Visión y procesamiento de imágenes:

El algoritmo de la hormiga podría requerir habilidades de visión y procesamiento

de imágenes para identificar y reconocer las características relevantes en el
entorno. Esto implicaría la capacidad de distinguir entre diferentes regiones y
evaluar la calidad del entorno en función de esas imágenes.

Aprendizaje espacial:

Las hormigas podrían depender de un sistema de aprendizaje espacial para

recordar características visuales específicas asociadas con fuentes de alimento.
Esto podría incluir la capacidad de recordar la apariencia de ciertas regiones y
utilizar ese conocimiento para encontrar alimentos en el futuro.

Optimización II
51
Tema 4. Ideas clave
Sensibilidad y cambios en el entorno:

El algoritmo debería ser lo suficientemente flexible como para adaptarse a

cambios en el entorno, ya que la apariencia de las regiones podría cambiar
debido a factores como la variabilidad estacional, la presencia de depredadores
u otros elementos perturbadores.

Comunicación visual:

Las hormigas podrían comunicarse visualmente para compartir información sobre

la ubicación de fuentes de alimento o la calidad de diferentes regiones. Esto
podría incluir señales visuales específicas emitidas por las hormigas para guiar
a otras hacia las áreas correctas.

Exploración eficiente:

El algoritmo debería permitir una exploración eficiente del espacio visual para
maximizar la probabilidad de encontrar fuentes de alimento. Esto podría
implicar estrategias como la exploración sistemática de diferentes regiones o la
búsqueda basada en patrones visuales específicos.

Memoria visual a largo plazo:

Las hormigas podrían depender de la memoria visual a largo plazo para recordar
la ubicación de fuentes de alimento y mejorar su eficiencia con el tiempo. En
resumen, si las hormigas de la especie Pachycondyla apicalis utilizan imágenes
de regiones en lugar de feromonas para buscar alimento en un dominio
continuo entre dos nodos, el algoritmo subyacente probablemente involucraría
una combinación de habilidades de visión, aprendizaje espacial, comunicación
visual y adaptabilidad a cambios en el entorno. Este enfoque podría tener
implicaciones interesantes para la comprensión de los algoritmos de búsqueda
y la inteligencia colectiva en el reino animal.

Optimización II
52
Tema 4. Ideas clave
Una región, más que un camino, se podría entender como un continuo de caminos.
Otra posibilidad es que la región sea explorada con un conjunto de nodos virtuales
intermedios, que necesitarían ser recorridos antes para poder llegar a una nueva
región.

Ejercicio 5

De omitirse el paso de evaporación, dé un ejemplo de posible dificultad que esto

acarrearía y un ejemplo donde se vea la utilidad de la evaporación.

Solución

El reescalar los valores de feromonas puede servir como un parámetro que tonifique
la exploración siempre que esté relacionado con el incentivo de feromonas que se
adquiere al cruzar un arco. En efecto, si los incentivos son muy pequeños, los valores
de feromonas tenderán a ser muy semejantes, provocando una exploración más
equitativa. Sin embargo, al elegir una evaporación alta, los incrementos quedarían en
los mismos ordenes de magnitud, notándose mejor los aumentos y propiciando una
convergencia más rápida.

4.6. Referencias bibliográficas

Archivo:Aco branches.svg. (2006, mayo 27). En Wikipedia.

https://es.wikipedia.org/wiki/Archivo:Aco_branches.svg

Archivo:P2P-network.svg. (2010, abril 21). En Wikipedia.

https://es.wikipedia.org/wiki/Archivo:P2P-network.svg

Optimización II
53
Tema 4. Ideas clave
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E. y Gambardella, L. M.
(2008). Time dependent vehicle routing problem with a multi ant colony system.
European Journal of Operational Research, 185(3), 1174-1191.
https://www.academia.edu/416737/Time_Dependent_Vehicle_Routing_Problem_
With_a_Multi_Ant_Colony_System

Dorigo, M., Maniezzo, V. y Colorni, A. (1996). Ant system: optimization by a colony of

cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, 26(1), 29-
41. https://ieeexplore.ieee.org/document/484436

Duarte Muñoz, A., Pantrigo Fernández, J. J. y Gallego Carrillo, M. (2007).

Metaheurísticas. Dykinson.

Ducatelle, F., Di Caro, G. A. y Gambardella, L. M. (2010). Principles and applications

of swarm intelligence for adaptive routing in telecommunications networks. Swarm
Intelligence, 4(3), 173-198. https://ouci.dntb.gov.ua/en/works/7XYw0qZ4/

López, N. (2020, octubre 12). Preguntas tontas: ¿puede instalar tu empresa un GPS
en el coche para controlarte? [Imagen]. Autobild.
https://www.autobild.es/noticias/preguntas-tontas-puede-instalar-empresa-gps-
coche-controlarte-734935

Optimización II
54
Tema 4. Ideas clave