Proyecto Final

Descripción del proyecto:

Nuestro proyecto consiste en un sistema con el que se puedan crear grafos con sus respectivos nodos y aristas, para después resolver instancias del problema del camino más corto, que podría ser útil para empresas de logística (como DHL, por ejemplo), que buscan minimizar su distancia recorrida.

El proyecto se encuentra funcional y en una fase ya avanzada, pero lamentablemente no está del todo terminado, y  la interacción con el usuario es a través de líneas de comandos, aunque como generador de grafos se procuro visualizar una posible representación del grafo creado, con ayuda de diversas herramientas.

Consideramos la utilzación del algoritmo Ant System (AS) para resolver el problema la parte adaptativa de nuestro sistema, aunque ya la creación de grafos de acuerdo a una serie de nodos y sus respectivas aristas podría considerarse como tal, ya que permite crear "cualquier" grafo siempre y cuando este tenga lógica.

Módulos más relevantes

Para nuestro sistema consideramos que era importante llevar a cabo las siguientes tareas:

1 - Crear el grafo
2 - Visualizar grafo
3 - Iniciar una instancia del problema del camino más corto en base al grafo ya creado
4 - Resolver una instancia utilizando el algoritmo AS
5 - Mostrar resultados
6 - Actualizar la visualización del grafo con la ruta más óptima

Lamentablemente no se llevó a cabo la última parte, pues por falta de tiempo no se pudo implementar un algoritmo con las herramientas disponibles. No obstante, si se llevó a cabo todas las demás, aunque como ya se menciono antes el sistema todavía no está terminado y hay algunas cosas por mejorar, como iterar el paso 3 al 5 tantas veces como quisiera el usuario, pero que se podrían implementar en un futuro.

Como se utilizó el lenguaje de programación Java se creó una clase principal llamada Camino, que describe y llama a las demás clases para crear grafos y resolver dicho problema ya mencionado.

Algo interesante que se implementó, y que Ant System no menciona, es que cuando una hormiga encontraba una ruta infactible castigaba a las aristas recorridas, esto es para que ayudara  a que otras rutas tengan más probabilidades de ser elegidas.

Herramientas y técnicas

Como ya se mencionó antes, se utilizó el lenguaje Java, que bien no podría ser el más óptimo (y tampoco es que nuestra implementación de las técnicas de programación orientada a objeto sean las mejores, todo sea dicho), pero dada a su facilidad de uso, su robustez y las ventajas de la programación orientada a objetos ayudó mucho en la elaboración del sistema. Ya que Java se lleva muy bien con los IDE se decidió usar Eclipse, ya que es muy intuitivo de usar y útil cuando queremos llamar a métodos, inclusive cuando no importamos las librerías necesarias. Al respecto de librerías, para la creación de la feromonasse utilizó la librería Random de Java.

Para visualizar el grafo se utilizó la librería JUNG, que cuenta con subrutinas muy fáciles de implementar para visualizar grafos, aunque sólo se quedó en la implementación de mostrar el grafo, que por cierto, siempre que generaba un grafo "virtual" con las mismas características, el grafo creado con JUNG cambiaba un poco.

También se investigó otra librería, llamada JGraphT, que permite la creación de grafos en estructuras de datos. Para visualizar se necesita JGraph, aunque lamentablemente es un poco más difícil de utilizar en conjunto, sobre todo si no queremos poner las coordenadas de los nodos (algo que JUNG nunca nos pedía, pues en base al grafo, las subrutinas de JUNG creaba el dibujo por si mismo)

Meta heurística del algoritmo de colonización de hormigas: A pesar de que nuestro proyecto no tiene que ver con el problema del viajero, es muy parecido en cuanto su estructura, por lo que ayudará en la elección de nodos cuando se quiere encontrar el más óptimo. No obstante, es claro que se necesitará implementar nuevos algoritmos, que para efectos de conveniencia tendrá que crearse nuevas estructuras de información.

.

Demostración

Creación del grafo introduciendo el número de nodos. Para cada nodo, introducir aristas.

Para este grafo de 4 nodos, no se puede crear un nodo con más de 4 aristas, pues su límite es de 3 aristas. También implementa una subrutina para identificar que la nueva arista no se repita con otra.

Después de definir el grafo, hay que ponderarlo. Al final de ponderar el grafo se muestra la información pertinente (la feromona se genera sola)

NOTA: Todavía falta validar que la ponderación no sea 0, es un error que se nos pasó identificar.

Después de definir el grafo (por cierto, este es otro), se dibuja gracias a JUNG.
En ocasiones se dibujaba los grafos a mano y después se implementaba, aunque a veces no parecían mucho es interesante como en algunas secciones JUNG era parecido a nuestros dibujos.

Otro grafo. Por conveniencia no se muestra como un grafo dirigido, pero para el propósito de nuestro sistema debería mostrarlo como tal.

Este es otro grafo, pero cuando ya se define toda su estructura comienza el algoritmo Ant System.
No obstante, creo que pedir el nodo de inicio y el de destino  debe ser antes de implementar este algoritmo. Error nuestro.

Este grafo era un poco sencillo...

Organización del equipo

Trabajo realizado:

1.- Kevin:

 Aplicación de Ant System en Java y editor del blog.

2- Manuel y Gustavo:

Investigación de librerías y formas de aplicación y editores del blog.

3.-  Esmeralda:
Investigación de librerías y debuggeo de las primeras clases.

Problemas críticos:

• La falta de tiempo, ya que con la entrega de otros proyectos de otras materias nos fue muy difícil terminar el proyecto a tiempo.
• Mostrar grafos en pantalla, aunque ya existen herramientas open-source muy poderosas, aunque una mejor documentación sería bienvenida (ya pedir en español sería bendito)
• Varios bugs en el sistema (no es bonito ver errores críticos cuando una ruta es infactible)

Lecciones aprendidas:

• La confianza en un equipo es lo más importante ya que con ella se pueden realizar mejor los proyectos al saber que tus compañeros también desean trabajar  y dar un buen trabajo.
• El algoritmo original Ant System no es del todo fiable, pues su tardía actualización de feromona ocasiona que las hormigas se queden con óptimos locales y no se exploren nuevos nodos, algo que sería crucial en la resolución del problema. En un futuro se podria implementar otros algoritmos ACO, como Max - Mint Ant System (MMAS) o Ant Colony System (ACS), principalmente este último, pues actualiza la feromona al termino de la ruta de cada hormiga y no cuando todos terminan. Pero eso sería una actualización a futuro, pues el sistema se podría mejorar para crear cosas más importantes.