Introducción
Tema elegido: Optimización mediante Ant Colony
Optimization (ACO)
¿Qué es?
Es una meta heurística que se basa en aplicar la metáfora
del comportamiento en las colonias de hormigas reales para encontrar los
caminos más cortos entre las fuentes de comida y el hormiguero.
Mientras las hormigas se mueven entre el hormiguero y la
fuente de comida, las hormigas van depositando feromonas (sustancia que puede
“olerse”). Entre más restos de feromona se encuentren en el camino, las
hormigas tienden a seguir ese camino más seguido. Las feromonas se van
evaporando al pasar el tiempo, si una hormiga deja de pasar por determinado
camino, el olor a feromona desaparecerá y si no encuentran algún rastro de
feromonas, las hormigas ya no seguirán pasando por el mismo lugar. Cabe aclarar
que las hormigas se mueven de forma aleatoria.
Esta técnica es usada para la resolución de problemas
complejos de optimización
combinatoria y búsqueda.
Objetivo
Desarrollar un algoritmo basado en ACO para la resolución
del problema del viajero.
Justificación
Elegimos este método por que nos pareció una manera muy interesante
para optimizar un resultado (en este caso, el del problema del viajero).
Desarrollo
Tenemos 8 ciudades a las que queremos visitar, las
ciudades con sus costos y distancias son:
|
Ciudad
|
Costo
|
Distancia
|
|
1
|
40
|
60
|
|
2
|
15
|
25
|
|
3
|
30
|
50
|
|
4
|
10
|
20
|
|
5
|
90
|
110
|
|
6
|
140
|
170
|
|
7
|
110
|
95
|
|
8
|
75
|
130
|
Para
determinar cual será la probabilidad de que las hormigas pasen mas por cierto
camino según la cantidad de feromona es, es:
Pkij (t) es la probabilidad con la
que, en una iteración t del algoritmo, la hormiga k, situada actualmente en la
ciudad i, elige a la ciudad j como próxima parada. Nki es el
conjunto de ciudades no visitadas todavía por la hormiga k. tij (t) es la cantidad de
feromona acumulada sobre el arco (i, j) de la red en la iteración tij
es la información heurística para la que, en el caso del TSP, se utiliza la
inversa de la distancia existente entre las ciudades i y j alfa y beta son dos parámetros del
algoritmo, los cuales hay que ajustar.
También
necesitamos una formula que nos diga el tiempo de actualización de la feromona,
la cual es:
tij = (1- P) tij
Donde P es la constante de evaporación. Para
este problema usamos una constante de evaporación de 0.1.
Código
Realizamos el programa en
lenguaje JAVA usando el compilador ECLIPSE, para este problema usamos 3 clases:
*ACO.java: Clase principal del programa, es
donde se desarrolla el mismo:
*Datos.java: Donde tenemos las constantes a
utilizar en el problema
*Gráficos.java: Done se inicializan las
ciudades
Dentro
de la clase ACO tenemos la función calcularprob() donde aplicamos la formula de
probabilidad donde las hormigas eligen el camino según el rastro de feromona.
También
tenemos la función actualizarferomona(), la cual como su nombre lo dice,
actualiza las feromonas, usando la formula mencionada anteriormente.
Resultados
Realizamos con éxito la practica, vemos como funciona
correctamente la implementación de las formulas en el programa, solo tenemos
que arreglar la manera en que se muestran los resultados (los enumera del 0 al
7).
Conclusiones
Es
obvio que podemos mejorar el programa, por ejemplo, dar una opción para que el
usuario pueda ingresar los valores de los costos, distancia entre las ciudades
o cantidad de ciudades a recorrer
Aprendimos
mucho en esta práctica sobre ACO y vimos esta manera de optimizar de forma más
entendible.
