COLONIA DE HORMIGAS

METAHEURÍSTICA
El término metaheurística fue introducido por Glover, y deriva de la composición de
dos palabras griegas. El sufijo meta significa “más allá de, en un nivel superior”, y
heurística deriva del verbo heuriskein que significa “encontrar, descubrir”. Existen
muchas definiciones de metaheurística, pero en este trabajo se tomará la siguiente
definición.
“Una metaheurística se define formalmente como un proceso de generación
iterativo el cual guía a una heurística subordinada combinando inteligentemente
diferentes conceptos para explorar y explotar el espacio de búsqueda, son utilizadas
estrategias de aprendizaje para estructurar la información con el objetivo de
encontrar eficientemente soluciones casi ´optimas.”
En resumen, se puede decir que las metaheurísticas son estrategias de alto nivel
para explorar espacios de búsqueda usando diferentes métodos. Además, es de
gran importancia que exista un balance dinámico entre diversificación e
intensificación. El término diversificación generalmente se refiere a la exploración
del espacio de búsqueda (promover al proceso de búsqueda a examinar regiones
no visitadas del espacio de búsqueda, para generar soluciones que difieran de
manera significativa de las soluciones ya vistas), mientras que el término
intensificación se refiere a la explotación de la experiencia de búsqueda acumulada
(enfocar la búsqueda en examinar soluciones que pertenezcan a la vecindad de las
mejores soluciones encontradas).
LAS COLONIAS DE HORMIGAS
Las hormigas son insectos sociales, los cuales viven en colonias y cuyo
comportamiento está dirigido más hacia la supervivencia de la colonia como un todo
que al de una simple componente individual de la colonia. Los insectos sociales han
capturado la atención de muchos científicos por el gran nivel de estructuración que
alcanzan sus colonias, especialmente cuando se lo compara con la simplicidad
relativa de los componentes de la colonia.
COMPORTAMIENTO COLECTIVO DE LAS HORMIGAS
Se debe recordar que las hormigas son prácticamente ciegas y, sin embargo,
moviéndose prácticamente al azar, acaban encontrando el camino más corto desde
su nido hasta la fuente de alimentos (y regresar). Es importante hacer algunas
consideraciones:
 Por una parte, una sola hormiga no es capaz de realizar la labor anterior, sino
que termina siendo un resultado del hormiguero completo
  No lo hacen sin "instrumentos", sino que una hormiga, cuando se mueve,
deja una señal química en el suelo, depositando una sustancia denominada
feromona, para que las demás puedan seguirla.
LA HORMIGA ARTIFICIAL
Es un agente que intenta construir posibles soluciones computacionales simples a
diferentes problemas, para lo cual utiliza información heurística y rastros de
feromonas. Es importante tener en cuenta que algunos ejercicios pueden llevar a
soluciones invalidas que tienen que ser revisadas
El método de hormiga artificial tiene las siguientes propiedades:
 Encuentra soluciones válidas con el menor costo.
 Tiene una memoria que almacena información de los caminos recorridos, la
cual puede ser utilizada para construir soluciones válidas, evaluar la solución
generada y reconstruir el camino que ha seguido la hormiga.
 Posee un estado inicial, el cual corresponde a una secuencia unitaria y una
o más condiciones de paradas asociadas.
 Empieza con un estado inicial y se mueve siguiendo estados válidos
construyendo así la solución de forma incremental.
 El movimiento sobre un camino se realiza aplicando una regla de transición,
la cual es función de los rastros de feromona disponibles de manera local,
de los valores heurísticos almacenados en la memoria de la hormiga y de las
restricciones del problema a solucionar.
 En cualquier momento del desarrollo del algoritmo se pueden actualizar los
rastros de feromonas asociados a cada camino.
 El proceso de realización del algoritmo finaliza cuando se encuentra alguna
condición de parada, lo cual ocurre normalmente cuando se alcanzan los
objetivos.

ALGORITMO DE OPTIMIZACIÓN POR COLONIAS DE HORMIGAS

Los Algoritmos de Optimización por Colonias de Hormigas (ACO) son una
metodología inspirada en el comportamiento colectivo de las hormigas en su
búsqueda de alimentos. Veamos cómo utilizar estas características comunicativas
de las colonias de hormigas para resolver un problema computacionalmente duro
como es el TSP:
En la solución que presentamos aquí vamos a suponer que las N ciudades están
conectadas entre sí (las N ciudades forman un grafo completo).
Denotaremos estas ciudades por {C0…, CN−1}, y denotaremos por dij la distancia
(el coste de la arista) entre las ciudades Ci y Cj. De forma explícita, las ciudades
pueden verse como puntos de un espacio de 2 dimensiones, y la distancia entre
ellas se calcula por medio de la distancia euclídea habitual (entre las
ciudades Ci=(xi,yi)) y Cj=(xj,yj) el resultado será dij=√(xi−xj)2+(yi−yj)2).

En el caso más habitual, esta distancia es simétrica, es decir, tiene el mismo coste
ir de Ci a Cj que de Cj a Ci. Pero, de todas formas, el algoritmo que vamos a explicar
a continuación requiere muy pocas modificaciones si hay ciudades que no son
accesibles desde otras, si los costes no se corresponden con las distancias
euclídeas entre ellas (por ejemplo, si se considera como coste el precio del billete
de tren entre las ciudades) o si dicho coste no es simétrico.
En esta solución las hormigas van construyendo soluciones al problema TSP
moviéndose por el grafo de una ciudad a otra hasta que completan un ciclo. Durante
cada iteración del algoritmo, cada hormiga construye su recorrido ejecutando una
regla de transición probabilista que indica qué nodo debe añadir al ciclo que está
construyendo. El número de iteraciones máximo que se deja correr al algoritmo
depende de la decisión del usuario.
Para cada hormiga, la transición de la ciudad i a la ciudad j en una iteración del
algoritmo depende de:
 Si la ciudad ha sido ya visitada, o no, en el ciclo que está
construyendo: Cada hormiga mantiene en memoria las ciudades que ya ha
visitado en el recorrido actual, y únicamente considera en cada paso las
ciudades que no ha visitado todavía, que denotaremos por Ji. De esta forma,
aseguramos que al final la hormiga ha construido un recorrido válido. (Este
paso puede traer complicaciones si no están permitidas todas las conexiones
entre ciudades, ya que es probable comenzar a generar un recorrido que no
tiene posibilidades de ser completado; en este caso, una solución podría ser,
por ejemplo, que la hormiga anula el recorrido que está construyendo y
comienza un nuevo).
 La inversa de la distancia a dicha ciudad, νij=1/dij, que es lo que se llama
visibilidad: Esta medida es una información local que mide, de alguna forma,
la bondad de escoger Cj estando en la Ci, y puede ser usada por las hormigas
para que la distancia entre ciudades consecutivas sea una característica que
intervenga en la selección del recorrido que está construyendo.
Normalmente, esta información suele ser estática, ya que las distancias de
las ciudades son invariables a lo largo de la ejecución del algoritmo, pero es
fácil imaginar escenarios en los que los costes de paso de un nodo a otro del
grafo sean cambiantes y el algoritmo podría aplicarse para ir obteniendo
buenas soluciones en este entorno dinámico.
 La cantidad de feromona que hay depositada en la arista que une
ambos nodos, que denotaremos por τij(t): Esta cantidad se actualiza en
cada paso, dependiendo de la cantidad de hormigas que han pasado por ella
 y de que el recorrido final de las hormigas que han usado esta conexión haya
sido bueno (en relación con los demás caminos explorados). De alguna
forma, mide la inteligencia colectiva del hormiguero, ya que es
información que depende del conjunto de hormigas que están ejecutando el
algoritmo. A diferencia de la visibilidad, esta medida proporciona una
información más global, ya que la feromona que tiene una arista indica lo
buena que es esa arista en conjunción con otras para dar una buena
solución.

Una vez consideradas las condiciones anteriores, la probabilidad de que la

hormiga k vaya de Ci a Cj en la construcción del recorrido actual, viene dada
por una expresión del tipo siguiente:

Donde α y β son dos parámetros ajustables que controlan el peso relativo de cada
una de las medidas en la heurística resultante. Se puede observar que los valores
anteriores definen una función de probabilidad en cada nodo para cada hormiga, ya
que se ha normalizado para que la suma sea 1. Además, hemos de tener en cuenta
que:
 Si α=0, las ciudades más cercanas en cada paso son las que tienen
mayor probabilidad de ser seleccionadas, lo que se correspondería con
el algoritmo voraz clásico en su versión estocástica (con múltiples puntos
de inicio, ya que, como veremos, las hormigas se colocan inicialmente en
una ciudad al azar). En consecuencia, las hormigas no usan el
conocimiento de la colonia para mejorar su comportamiento, que viene
definido por la cantidad de feromona que hay en las aristas.
 Si β=0 únicamente interviene la feromona, lo que experimentalmente se
comprueba que puede llevar a recorridos no muy buenos y sin posibilidad
de mejora.

Con el fin de mejorar los recorridos más prometedores para el problema, tras
completar un recorrido cada hormiga deposita una cantidad de feromona, Δτ kij(t), en
cada una de las aristas por las que ha pasado. Esta cantidad dependerá de lo bueno
que ha sido ese recorrido en comparación con el del resto de las hormigas.
Por ejemplo, si la hormiga k ha realizado el recorrido T k(t), de longitud total Lk(t),
para cada par (i,j)∈Tk(t), se puede hacer un depósito de feromona de Δτkij(t)=Q/Lk(t),
donde Q es un parámetro del sistema (en la práctica, este parámetro se ajusta para
que la influencia de ambas estrategias sea compensada).

ACTUALIZACION DE FEROMONAS
Para que este método funcione correctamente es necesario además dejar que la
feromona no permanezca indefinidamente, sino que su influencia decaiga en el
tiempo, de manera que aquellas aristas que no vuelvan a ser visitadas por las
hormigas, y que por tanto no son reforzadas, tengan cada vez menos influencia en
la heurística de decisión de cada paso. Esta disminución en el tiempo de la cantidad
de feromona refleja un hecho que ocurre en la realidad, y es que la feromona usada
en este tipo de procesos se evapora con una cierta tasa en cuanto es depositada,
de forma que es útil únicamente si recibe un refuerzo constante en cada tramo.
Para conseguir este efecto, en los algoritmos de hormigas se introduce un nuevo
parámetro, 0≤ρ≤1, junto con una regla de actualización de feromona como sigue:

y se supone que inicialmente en todas las aristas hay una cantidad pequeña de
feromona, τ0.
El número total de hormigas que intervienen, que hemos denotado por m en las
ecuaciones anteriores, es otro parámetro importante a tener en cuenta:
 demasiadas hormigas tenderán rápidamente a reforzar recorridos que no son
óptimos de manera que sea difícil salirse de ellos y diferenciar los buenos,
 mientras que muy pocas hormigas no provocarán el proceso de sinergia
esperado debido a que no pueden contrarrestar el efecto de la evaporación
de feromona, por lo que finalmente la solución que proporcionen sería
equivalente al del algoritmo voraz estocástico.
1. https://pdfs.semanticscholar.org/a34f/9c2ee358ec12386efe61d3242a05cad37cee.pdf
2. https://es.wikipedia.org/wiki/Algoritmo_de_la_colonia_de_hormigas
3. https://pdfs.semanticscholar.org/a34f/9c2ee358ec12386efe61d3242a05cad37cee.pdf
4. http://bibing.us.es/proyectos/abreproy/5760/fichero/PFC_Jesus_Vazquez.pdf