1  El problema

1.1  Grafos y problemas de optimización

Como debe ser de conocimiento del lector, muchos problemas de optimización pueden modelizarse y resolverse en términos de grafos.

Los problemas de grafos más populares e instrumentos de solución de problemas de optimización son los siguientes:

1. Camino de mínima distancia total entre un par de nodos.
2. Árbol abarcador mínimo de un grafo.
3. Ciclo hamiltoniano de distancia mínima; es decir, un ciclo que recorra todos los nodos del grafo, sin repetir, cuya distancia total sea mínima.

Para los dos primeros problemas existen algoritmos deterministas eficaces y eficientes.

Para el cálculo de ciclos hamiltonianos no se conoce un algoritmo general eficiente (que exhiba tiempo polinomial) y que garantice una solución óptima. Sin embargo, se conocen algoritmos heurísticos, polinomiales, que descubren hamiltonianos con cotas máximas de error respecto al óptimo.

A los algoritmos deterministas mencionados se le pueden atribuir los siguientes inconvenientes:

• Están concebidos para arquitecturas secuenciales. Consecuentemente, son difíciles de adaptar para arquitecturas paralelas.
• Son difíciles de adaptar al “cambio estructural”; es decir, a la modificación del grafo durante el cálculo. Por lo general, si el grafo se altera, estos algoritmos se comienza desde el inicio.

1.2  Colonias de hormigas

La optimización basada en algoritmos de colonias de hormigas designa una técnica heurística de diseño de algoritmos de optimización combinatoria.

Fundamentalmente, la técnica se basa en la emulación de los comportamientos sociales y mecanismos de comunicación que exhiben las hormigas entre sí para descubrir los caminos más cortos entre pares de nodos. La técnica ha sido aplicada con éxito para calcular “buenos” caminos cortos y hamiltonianos.

A pesar de que por lo “general” otros algoritmos deterministas (en la ocurrencia el de Dijkstra para caminos mínimos y el de Christofides para hamiltonianos) son más precisos y rápidos que la mayoría de los conocidos basados en colonias de hormigas, éstos últimos tienen la enorme ventaja de que son “naturalmente” paralelizables y se adaptan espontáneamente al cambio estructural.

Para una comprensión general de los algoritmos basados en colonias de hormigas consúltese:

• Ant Colony Optimization Artificial Ants as a Computational Intelligence Technique - Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Technical Report No. TR/IRIDIA/2006-023 September 2006
• Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B, vol. 26, no. 1, pp. 29-41, 1996.
• MAX-MIN Ant System. T. Stutzle and H. H. Hoos, Future Generation Computer Systems, vol. 16, no. 8, pp. 889-914, 2000.
• Ant colonies for the traveling salesman problem. M. Dorigo and L. M. Gambardella, BioSystems, vol. 43, no. 2, pp. 73-81, 1997.

En la carpeta dropbox del curso se encuentra una bibliografía más amplia sobre el tema.

EN la biblioteca Aleph se encuentra un TAD llamado Agent_Graph (archivo tpl_agent_graph.H), el cual instrumenta “agentes” circulantes por grafos, que pueden modelizar hormigas, y que aprovechan el paralelismo.

2  El trabajo

La meta de este trabajo es diseñar e instrumentar un sistema programado, operativo, que instrumente al menos dos algoritmos heurísticos (o variantes de), basados en colonias de hormigas, que calculen caminos mínimos y hamiltonianos y que permita cotejar las soluciones con algoritmos deterministas.

A continuación se enumeran algunas de las características esenciales que debe tener el sistema:

1. Edición arbitraria y versátil de grafos. Los grafos pueden ser euclidianos o no.
2. Generación de grafos aleatorios.
3. Almacenamiento y recuperación de grafos, tanto los editados como los generados aleatoriamente. Los grafos deben almacenarse en modo texto mediante la clase IO_Graph de la biblioteca Aleph.
4. Cálculo de caminos mínimos y árboles abarcadores según los algoritmos conocidos e implementados en la biblioteca.
5. Cálculo de hamiltoniano basado en un algoritmo tradicional; por ejemplo en el de Christofides.
6. Cálculo de caminos mínimos y hamiltonianos mediante dos algoritmos (o variantes) basados en colonias de hormigas.
7. Visualización de los grafos en pantalla y de las diversas soluciones según los algoritmos empleados. Las visualizaciones deben mostrar distintas soluciones e independientes de la escala.

3  Material de ayuda

Para la visualización de grafos no euclidianos se recomienda la herramienta Graphviz.

Para la edición de grafos y la visualización de grafos euclidianos se recomiendan los desarrollos del preparador.

4  Condiciones

1. Sistema operativo LINUX, lenguaje de programación C⁺⁺, compilador gnu gcc.
2. Interfaz desarrollada con la biblioteca QT-4.
3. Uso intensivo de la biblioteca Aleph para los grafos y otras estructuras de datos.
4. Productos a entregar:
   • Documentos de diseño donde se especifiquen los módulos y algoritmos.

   • Fuentes del sistema.
   • Demostración de operación.

   • Manual del usuario.
5. Fecha propuesta de entrega: 12 de septiembre de 2011.

Es altamente recomendable el uso de la herramienta de visualización de grafos Graphviz.

5  Bibliografía recomendada

• “C++ GUI Programming with Qt 4”. Jasmin Blanchette, Mark Summerfield.
• Borrador de capítulo 7 sobre grafos de libro en preparación. Leandro León.

This document was translated from L^AT_EX by H^EV^EA.