Tutorial ACOVis 1.0

MANUAL DE USUARIOS

Funcionamiento de ACOVis 1.0

ACOVis 1.0 permite al usuario obtener información, tanto visual como numérica, del comportamiento del algoritmo ACS en la solución de problemas TSP e influenciar con la variación de los parámetros, en tiempo de ejecución, las soluciones tomadas.

La implementación fue realizada en lenguaje Java (multiplataforma), utilizando la biblioteca Java2D para las representaciones visuales y programación multihilos para simular el comportamiento paralelo y asíncrono de las hormigas.

1 Requerimientos

Los requerimientos mínimos para la aplicación son: una computadora con 256MB de memoria y la máquina virtual de Java (jre) instalada. ACOVis puede funcionar tanto en Windows como en Linux.

2 Instalación

Para Windows se ha creado un instalador que le guiará en el proceso de instalación (InstaladorACOVis.exe). En Linux para poder utilizar el programa basta con copiarlo y ejecutar el comando: java -jar "ACOVis.rar"

Ficheros de entrada *.TSP

El fichero de entrada del programa tiene extensión .tsp, en la primera línea un número entero que se corresponde con la cantidad de ciudades o nodos del problema, en las demás líneas tres valores separados por espacios: el primero representa el número que identifica al nodo, los dos restantes las coordenadas cartesianas en el plano XY (Ver Figura 1). Varios problemas TSP de referencia obtenidos de la biblioteca de dominio público TSPLIB, pueden encontrarse en la carpeta tsplib incluida en la herramienta.

Figura 1: Estructura de un fichero TSP para ACOVis.

Interfaz principal de la aplicación

La Figura 2 muestra la apariencia de la interfaz principal de la aplicación. Esta interfaz presenta: un menú con varias opciones, cuatro paneles, algunos botones: dos que permiten intercambiar los paneles izquierdo y derechos, uno para cambiar la hormiga visualizada, otro para activar la ventana que muestra las mejores y peores trayectorias en el momento que es ejecutada y los demás con funcionalidades de movimiento del panel mayor; tres edit para fijar los parámetros: cantidad de hormigas, tiempo de ejecución y cantidad de iteraciones y varios slider. El panel izquierdo de mayores dimensiones es principalmente para visualizar el recorrido de las hormigas, el superior derecho muestra el grafo de rastros de feromona, el inferior derecho visualiza las soluciones encontradas en algunas de las iteraciones del algoritmo y el panel más abajo muestra los resultados numéricos del algoritmo.

Figura 2: Interfaz principal de ACOVis 1.0.

4.1 Visualización del Recorrido de las Hormigas

En el panel de la izquierda (Ver Figura 3 (1)) mientras corre el programa usualmente se va visualizando la trayectoria que sigue la hormiga seleccionada en el edit "Visualizar Hormiga" (Ver Figura 3 (15)). Para cambiar la hormiga a visualizar, basta solo con modificar el valor del edit y presionar el botón correspondiente (Ver Figura 3 (6)), el número de la hormiga siempre debe ser menor que la cantidad total de hormigas. Los nodos o ciudades del problema son representados con círculos negros de 4 píxeles de radio y la trayectoria de las hormigas con una polilínea de color rojo.

Figura 3: Componentes de la Interfaz principal de ACOVis 1.0.

4.2 Visualización de la Matriz de Feromonas

En el panel superior derecho (Ver Figura 3 (2)) se representa la matriz de feromonas en forma de grafo, los arcos son dibujados en tonalidades del color gris y simbolizan el rastro de feromona en ellos. A mayor oscuridad de una arco, mayor cantidad de feromona.

4.3 Visualización de las Soluciones

En el panel inferior derecho (Ver Figura 3 (3)) se muestran las soluciones encontradas en las cuatro últimas iteraciones del algoritmo que arrojen distintos recorridos. Estas soluciones presentan diferentes colores que significan la calidad de las mismas, los valores más cercanos al rojo representan las peores soluciones y las mejores, las próximas al azul.

4.4 Intercambiar Paneles

Los botones de intercambiar (Ver Figura 3 (8)) posibilitan el intercambio de los paneles de la derecha que muestran la matriz de feromonas y las soluciones, hacia el panel de mayores dimensiones de la izquierda, desde el cual se pueden realizar con más precisión las interacciones con la visualización.

4.5 Resultados Numéricos del Algoritmo

Los resultados numérico del algoritmo tales como: número de iteración, mejor solución y tiempo requerido en cada iteración y la mejor solución final encontrada con su costo, se pueden observar en el panel inferior de la ventana principal de la aplicación (Ver Figura 3 (4)).

4.6 Mejores y Peores Trayectorias

Al presionar el botón "Mejor/Peor Trayectoria" (Ver Figura 3 (7)) se activa una ventana como la que ilustra la Figura 4, que visualiza en el panel izquierdo la hormiga con mejor trayectoria en color azul y en el derecho la hormiga con peor trayectoria en color rojo. Con los botones que se encuentran en la parte inferior, pueden mostrarse las siguientes mejores y peores soluciones.

Figura 4: Ventana Mejor/Peor Hormiga.

4.7 Clonar y Eliminar Hormigas

Desde el panel de la izquierda (Figura 3 (1)) cuando visualice las trayectorias de las hormigas o desde los paneles de la ventana de "Mejor/Peor Trayectoria" (Figura 4) pueden clonarse o eliminarse hormigas a través de la opción correspondiente de un PopupMenu similar al de la Figura 5, que aparece al dar clic derecho con el mouse en los paneles mencionados.

Figura 5: Popup Menú Clonar o Eliminar Hormigas.

4.8 Modificar Matriz de Feromonas

Para poder modificar la matriz de feromona, el grafo que la representa debe estar en el panel de la izquierda (Ver Figura 6) que tiene mayores dimensiones, para lograr la modificación con más precisión. Al presionar con clic izquierdo dicho panel, sobre los nodos que conforman el arco al que se le quiere modificar la huella de feromona, se muestra una pequeña ventana como la de la Figura 7 que especifica el arco seleccionado y la cantidad de feromona que presenta y contiene un edit donde se debe introducir un valor que significa el porciento del valor actual que se le quiere adicionar o disminuir. Si se escribe 100 se mantiene igual la cantidad de feromona en el arco, mayor que 100 aumenta y menor disminuye.

Figura 6: Matriz de feromona en el panel principal. Filtrado según cantidad de feromona.

Figura 7: Modificar feromona.

4.9 Filtrar Matriz de Feromonas

Con filtrar matriz de feromona, nos referimos a mostrar solo los arcos del grafo visualizado que representa la matriz de feromona, que posean una cantidad de feromona menor o igual al valor prefijado en el slider "Cantidad de Feromona" (Ver Figura 3 (13)) asociado a la escala de tonos del color gris con que se dibuja el grafo. Este filtrado puede observarse desde el panel derecho superior o desde el izquierdo, tal como se ilustra en la Figura 6, dependiendo de donde este ubicado el grafo.

4.10 Filtrar Soluciones encontradas

Modificando el valor en el slider "Calidad Soluciones" (Ver Figura 3 (12)) asociado a una escala de colores entre el rojo y el azul, donde rojo significa mala solución y azul buena, podemos filtrar las cuatro últimas soluciones diferentes encontradas según su calidad. Dependiendo del valor del slider se mostrarán solo las soluciones con una calidad igual o menor a dicho valor. Este filtrado puede observarse desde el panel derecho inferior o desde el izquierdo, tal como se ilustra en la Figura 8, dependiendo de donde esté ubicado el grafo.

Figura 8: Soluciones en el panel principal. Filtrado según calidad de los caminos.

4.11 Variar velocidad del algoritmo

La velocidad del algoritmo puede ser variada a través del slider correspondiente (Ver Figura 3 (10)), la velocidad máxima se alcanza cuando está en el límite derecho.

4.12 Mostrar con mayor detalle una región seleccionada

Para mostrar con más detalles una región en el panel de la izquierda utilizamos el slider del Zoom (Ver Figura 3 (11)) y los botones de movimiento en varias direcciones: derecha, izquierda, arriba, abajo y centro (Ver Figura 3 (9)).

Opciones de Menú

La Barra de Menú de la aplicación (Ver Figura 3 (5)) consta de cuatro opciones, con nombres que identifican con palabras breves las funcionalidades de las mismas: Archivo, Parámetros, Visualizaciones y Ayuda.

5.1 Archivo

De Archivo se puede elegir cuatro opciones (Ver Figura 9): "Cargar Problema TSP": muestra una ventana de diálogo similar a la de la Figura 10 para cargar un fichero con extensión tsp y las características explicadas en el epígrafe 3, el nombre del fichero cargado aparecerá en la barra de título de la ventana principal de la aplicación; "Iniciar ACS": comienza a resolver el problema cargado con los parámetros prefijados y el algoritmo Sistema Colonia de Hormigas de la metaheurística ACO; "Salvar resultados": permite guardar en un fichero texto los resultados numéricos del algoritmo para el problema seleccionado, la ventana de diálogo que tramita esta operación es similar a la que ilustra la Figura 11 ; y "Terminar": que brinda la posibilidad de abortar la ejecución de la aplicación, independientemente del estado en que se encuentre la misma.

Figura 9: Opción Archivo de la Barra de Menú.

Figura 10: Ventana de diálogo para Cargar problemas TSP.

Figura 11: Ventana de diálogo para Salvar resultados.

5.2 Parámetros

En la barra de menú la opción Parámetros (Ver Figura 12) permite modificar los parámetros del algoritmo ACS: cantidad de hormigas, tiempo de ejecución, número de iteraciones del algoritmo, factor de escalado de feromona y visibilidad (alpha y beta respectivamente), el parámetro la feromona inicial y la constante de evaporación. La cantidad de hormigas, el tiempo de ejecución y el número de iteraciones del algoritmo, también pueden ser modificados desde la ventana principal en los edit correspondiente, mostrados en la Figura 3 (14), (17), (16) respectivamente. El tiempo de ejecución y el número de iteraciones son condiciones de parada de algoritmo que pueden utilizarse ambas si se les da un valor mayor que cero, o solo una si a la otra se le fija el valor cero o un número negativo.

Figura 12: Opción Parámetros de la Barra de Menú.

5.3 Visualizaciones

La opción Visualizaciones de la barra de menú (Ver Figura 13) posibilita al usuario cargar la ventana "Mejor/Peor Trayectoria" (Ver Figura 4) y observar la visualización de las mejores y peores trayectorias que presentan las hormigas en ese momento; además seleccionar otra hormiga para que se visualice su recorrido en el panel "Trayectoria Hormiga" (Figura 3 (1)).

Figura 13: Opción Visualizar de la Barra de Menú.

5.4 Ayuda

La opción Ayuda brinda una descripción sencilla y detallada de cada una de las funcionalidades del sistema (Ver Figura 14) y los Créditos de la herramienta.

Figura 14: Ventana de Ayuda ACOVis 1.0.

Autor:

Lic. Evelyn Menéndez Alonso.