implementaciones aco aeb
TRANSCRIPT
Práctica 1 de Algoritmos Evolutivos y Bioinspirados
Eduardo Moreno DíazAlumno Ingeniería Informática Universidad de Huelva
Resumen
El objetivo de este documento es el de presentar los resultados obtenidos en la práctica número uno de la asignatura de Algoritmos Evolutivos y Bioinspirados en el curso 2010/2011. Se trata de implementar los algoritmos conocidos como “hormigas” para resolver el problema del “viajante de comercio” o TSP (Travelling Salesman Problem en inglés). Dichos algoritmos serán el SH o Sistema de Hormigas, el SHE o sistema de Hormigas Elitistas y el SCH o Sistema de Colonia de Hormigas. Se realizará un estudio comparativo entre los resultados obtenidos para varios casos de dicho problema. Al final, se expondrán las conclusiones a las que se ha llegado partiendo desde la premisa de que los resultados han sido obtenido a partir de una parametización proporcionada por el profesor y no ha sido modificada en ningún momento.
1. Introducción
El problema del viajante de comercio es uno de los problemas más famosos y quizás el mejor estudiado en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los problemas más complejos de resolver que se equipara, a veces, con problemas matemáticos mucho más complejos que han retado a los matemáticos desde hace siglos.
En su formulación más general, se trata de que, dado un conjunto de N ciudades, encontrar el circuito más corto que partiendo de una de ellas, pase por todas las demás y retorne a la ciudad origen. Cabe destacar que, en principio, esta formulación no recoge premisas de conexión entre ciudades, sino que el grafo formado por las ciudades es fruto del producto cartesiano de todas las ciudades, formando un grafo completo. Evidentemente, dicho grafo presenta bucles o lazos que el algoritmo de resolución debe controlar.
Son muchos los intentos que los matemáticos han realizado para tratar de dar respuesta a estos problemas, Edsger Dijkstra, Kruskal [1], etc. Dicho algoritmos de resolución son muy eficientes en problemas de poca complejidad ya que cuando se enfrentan a casos muy complejos resultan ineficientes respecto a tiempo y recursos empleados.
Los algoritmos basados en colonias naturales de individuos como las hormigas, se inspiran en la observación de cómo las organizaciones sociales que conforman los animales
en la naturaleza son capaces de resolver problemas complejos [2]. Para el caso que se plantea, las hormigas son capaces de encontrar comida y crear rutas, en principio cortas, que permiten al resto de la colonia llegar hasta ella. Ésta idea ha sido adaptada para resolver el problema del TSP. Las ciudades son zonas de comida y las hormigas tienen que pasar por todas ellas, regresar al origen y con el mínimo recorrido.
Para la realización de este estudio, se han implementado tres versiones de este algoritmo para enfrentarlas a tres casos del TSP, CH130, problema de 130 ciudades con 6110 de coste; A280, 280 ciudades con un camino mínimo de 2579; y P654, formado por 654 ciudades cuya solución óptima es 34643. Dicho casos son de poca complejidad en lo que al que tiempo razonable se entiende en las que se pueden apreciar las diferencias que existen entre las diferentes formas de resolverlos mediante algoritmos de colonia de hormigas.
2. Descripción de problema
En su descripción matemática, el TSP formado por el conjunto finto de ciudades C, trata de encontrar la permutación P = {co, c1, …, cn} tal que
sea mínimo. La distancia entre ciudades viene dada por la matriz D = N x N donde d[x, y] representa la distancia entre las ciudades x e y.
Para dar solución a este problema con los algoritmos de hormigas, se hace necesaria de otra matriz adicional, la matriz F = N x N de Feromonas, cuyo objetivo es el potenciar los caminos más visitados por las hormigas.
La representación que se hará de la solución será la lista de ciudades, ordenada en orden de paso, por las que la hormiga ha realizado el recorrido por el grafo.
Además, para evitar los bucles en el recorrido, cada hormiga tiene una memoria que indica si la siguiente ciudad a la que ha de moverse esta ya en el camino recorrido o no.
3. Ciclo de Vida de los Sistemas de Hormigas
Las tres implementaciones que se ha realizado son muy similares exceptuando algunas particularidades. Básicamente siguen este procedimiento:
Procedure SH
Sf = 0 InicializarFeromonas()
Mientras (¬criterioParada) Hacer Si = ContruirSolucion() ActualizarFeromona() Sf = AlmacenarMejorSolucionSiProcede(Si) Fin
Devolver Sf
Fin
La inicializacion de Feromonas corresponde a asignar un valor a la matriz de feromonas del problema. Normalmente, se le atribuye el valor generado por algún algoritmo que nos de una primera solución a la que le aplicamos la fórmula
siendo n el numero de ciudades del caso de estudio TSP y L el coste de la solución inicial. El valor generado se utiliza además como mínimo valor para la citada matriz, asegurando que dicha matriz conserve un valor distinto de 0 necesario para el procedimiento de transición de la hormiga entre ciudades.
En la construcción de la solución, la hormiga selecciona cuál es la mejor ciudad a la que debe moverse de entre todas las no visitadas aún por ella. Es en este procedimiento donde se tendrán en cuenta ambos factores que condicionan el problema: la distancia y la feromona depositada por otras hormigas. Esta relación es probabilística, potenciando así la aleatoriedad de la implementación en su similitud con la naturaleza
siendo α y β parámetros de control sobre la importancia de la feromona y el la distancia, n la inversa de la distancia entre las ciudades vecinas i y j que aún no han sido visitadas. Esta fórmula aplicada a cada posible ciudad del vecindario retorna una lista de probabilidades entre las cuales se ha de seleccionar una. Para realizar la citada elección se utiliza un algoritmo basado en ruleta,
que asigna porciones de dicha ruleta en función de las probabilidades de elección de las ciudades. La ciudad que resulta elegida pasa a ser la siguiente en el recorrido de la hormiga. Gracias a este sencillo proceso, se mantiene la relación entre explotación y exploración ofreciendo posibilidades a soluciones que no resultan óptimas, escapando así de mínimos locales. Llegado este punto, se hace necesario resaltar la primera diferencia con el Sistema de Colonia de Hormigas. Este algoritmo una regla de transición pseudo-aleatoria tal que
donde s es la siguiente ciudad a elegir, S es la aplicación de la anterior fórmula de transición, u ЄJk el conjunto de ciudades no visitas, q0 la probabilidad de elección entre ambos métodos y q el valor aleatorio generado.
Por último, se encuentra la actualización de las feromonas, parte fundamental de este tipo de algoritmos constructivos. Se trata de modificar la heurística del problema potenciando aquellas rutas que se muestran aconsejables de estudiar. Es sobre dicho apartado donde residen las principales diferencias entre los tres algoritmos resolutorios basados en hormigas. Existen dos formas de realizar dicho proceso:
Actualización, paso a paso . De esta manera las hormigas ponen una cantidad constante de feromona cada vez que van de un nodo a otro. Existen pequeñas variaciones que hacen que pongan más o menos feromona, según la cantidad de feromona presente antes de dar el paso. Es el utilizado en el Sistema de Colonia de Hormigas en la actualización local de feromonas, modificando dicho valor en función del parámetro de evaporación φ
siendo r y s ciudades.
Actualización a posteriori . De este modo las hormigas ponen feromona después de haber encontrado una solución por todas las aristas por donde pasaron para encontrar la solución. Esto puede ser en una cantidad constante por todas las aristas, o dependiendo de la calidad de la solución encontrada, o de parámetros externos determinados por el programador, pueden poner más o menos feromona según el camino encontrado. Este método es empleado por el Sistema de Hormigas, el Sistema de
Hormigas Elitista [3] y el Sistema de Colonias de Hormigas en la actualización global.
Además el Sistema de Hormigas Elitista refuerza el mejor camino obtenido hasta el momento multiplicando el valor de la feromona por un parámetro, consiguiendo así una mayor velocidad de convergencia. Este valor debe ser estudiado cuidadosamente ya que de elegir uno que resulte inapropiado, el sistema puede converger a óptimos locales con mucha facilidad.
4. Experimentación
Se ha realizado una batería de pruebas sobre las implementaciones expuestas con los parámetros indicados por el profesor en el enunciado de la práctica. También se ha realizado un algoritmo comparativo greedy cuya heurística se basa en partir de la ciudad 0 del caso de estudio e ir alcanzado el resto de ciudades en función a la menor distancia entre éstas. Dicho algoritmo sólo se ejecuta una vez y proporciona una comparación perfecta para el resto de métodos.
A continuación, se muestran las tablas de resultados obtenidas.
Tablas de resultados por algoritmo y casos de estudio
Tabla de resultados globales
ch130
0
10000
20000
30000
40000
50000
60000
Iteraciones
Coste SH
SHE
SCH
a280
0
2000
4000
6000
8000
10000
12000
14000
Iteraciones
Coste SH
SHE
SCH
p654
0
20000
40000
60000
80000
100000
120000
140000
Iteraciones
Coste
SH
SHE
SCH
Durante la fase de experimentación, se ha observado que el algoritmo SHE no mejora pasada 50 iteraciones. Así pues, se ha decidido tomar dichas 50 iteraciones como criterio de parada adicional al tiempo de ejecución.
Se ha utilizado 5 semillas diferentes para la inicialización de los objetos random necesarios para la aleatoriedad de los algoritmos y los resultados presentados en las gráficas corresponden a los valores medios obtenidos.
5. Análisis de Resultados
Antes de ofrecer un análisis de los resultados y obtener unas conclusiones, cabe resaltar que la experimentación realizada se ha elaborado sobre unos problemas cuya complejidad es baja, y que por tanto, no puede entenderse como un estudio general de los problemas TSP.
Tomando como primera aproximación el algoritmo determinista greedy, se observa que no existe una gran diferencia entre los costes que éste presenta y el resto. Es por tanto una buena heurística de aproximación a la solución óptima. Se podría haber tomado dicha solución como solución de partida del resto de implementaciones e iterar sobre ella para mejorarla.
También se ha observado que la convergencia de los algoritmos que se han estudiado difiere entre ellas de forma bastante evidente. A medida que el algoritmo es más complejo, se acelera el ritmo de convergencia acercando cada vez más a la solución óptima. Sobre este aspecto cabe destacar el algoritmo SHE sobre el caso de estudio CH130, que hace justo lo contrario. Este fenómeno ocurre cuando el refuerzo elitista de feromonas que se realiza sobre el camino de la mejor solución es desproporcionado con relación al tamaño de la instancia del TSP. Las hormigas tienden a elegir el camino con más feromonas rechazando el camino con menor distancia, cayendo así en mínimos locales de los cuales es imposible salir. Esto ocurre cuando el número de hormigas elitista para la instancia indicada es superior a 5.
Dicha convergencia se ha notado muy rápida. Dependiendo siempre de la instancia, durante el primer 25% de la ejecución se alcanza una solución bastante aceptable. Claro esta que modificando los parámetros que se han marcado, dicha convergencia se puede acelerar aún más y con resultados aún mejores.
Se ha notado que la elección de la ciudad de origen marca también la diferencia entre las soluciones. Al tratarse de algoritmos constructivos, el hecho de tener muchas ciudades cercanas entre las que elegir hace que las probabilidades sean casi parejas, presentando una probabilidad en el algoritmo de selección muy escasa.
Como se ha expuesto al principio de este punto, el tamaño de las instancias es relativamente pequeño, con lo que se puede apreciar una clara diferencia entre las tres implementaciones que se están presentando. El algoritmo SCH nada más empezar su ejecución tiene ya la solución mejor que se puede alcanzar con los parámetros establecidos, por lo que en el resto de iteraciones prácticamente no mejora nada.
Por último, cabe destacar que los tres algoritmos son poco capaces de escapar de mínimos locales. Por tanto, pude plantearse el estudio de técnicas de reinicialización que eviten este tipo de inconvenientes como puede ser una racha de viento que elimine el rastro de feromonas o la introducción de algún obstáculo que fuerce a las hormigas a buscar nuevas rutas.
6. Concluciones
Las presentes conclusiones no pueden ser tomadas como ideas globales ni teoremas empíricos puesto que no están refutadas con el resto de la comunidad. Sólo son el fruto del estudio de los algoritmos expuestos a lo largo del documento para los casos de estudios tomados. Son conclusiones empíricas que sólo se podrán aplicar a lo citado.
Los algoritmos basados en hormigas son métodos de exploración combinatoria muy rápidos, que parametrizados de la forma adecuada, pueden encontrar soluciones aceptables en tiempos muy razonables.
Cabe resaltar que son también incapaces de salir de mínimos locales cuando han caído en ellos. Es por tanto que se hace necesario estudiar estrategias que permitan la búsqueda de nuevas soluciones como puede ser rachas de vientos cuando no se producen mejoras o incorporación de obstáculos al recorrido de ciudades.
Esta conclusión esa muy relacionada con el hecho de la no mejora llegado a un punto de convergencia. Es por tanto, que se hace necesaria la modificación de ciertos parámetros a medida que se avanza en el algoritmo.
La elección de la ciudad de comienzo de la hormiga también debe ser estudiada con detenimiento y no realizar este proceso de forma aleatoria. Si la ciudad elegida está rodeada de otras ciudades cercanas, el algoritmo no toma buenas decisiones de transición entre las ciudades. Para el comienzo del algoritmo es importante elegir ciudades que estén bastante separadas.
7. Referencias
[1] J. B. Kruskal: On the shortest spanning subtree and the traveling salesman problem. En: Proceedings of the
American Mathematical Society. 7 (1956), pp. 48–50
[2] Dorigo M., Maniezzo V. y Colorni A., “The Ant System: Optimization by a colony of cooperating agents”, IEEE Transaction on Systems, Man, & Cybernetics, Vol 26, No. 1, pg.1-13, 1996.
[3] Dorigo, M.; Stützle, T. (2004). Ant Colony Optimization. MIT Press.