PRO:Problema del Viajante TSP

Pincha sobre la imagen para descargar la applet java. Para más información ve al final del artículo

Metodología 

El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés TSP: Travelling Salesman Problem), 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 más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos.

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación

P = {c0,c2,…,cn − 1} tal que  sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay entre la ciudad X y la ciudad Y

La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.

Para disminuir los tiempos de cálculo vamos a definir un Algoritmo Genético que nos ayudará a encontrar una de las mejores soluciones posibles.

Para ello definimos una población aleatoria inicial de individuos.

Cada individuo será un conjunto de ciudades ordenado por preferencia de visita en el recorrido, siendo la última de estas la anterior a la primera, formando así una ruta cíclica.

La función de evaluación será el total de las distancias recorridas en cada ruta, siendo esta mejor cuanto menor sea la distancia a recorrer.

Realizaremos selección de individuos a emparejar permitiendo variar el número máximo de estos, que podrán ser elegidos, determinando dicho conjunto mediante torneo genético.

Posteriormente procedemos a calcular la descendencia derivada del conjunto anterior, realizando sobre los resultados obtenidos una criba mediante torneo genético del número máximo preestablecido de supervivientes. (Los torneos genéticos están implementados en el programa para poder observar las permutaciones al activar la atributo debug de la clase GeneticAlgorithm.class).

Obtendremos la siguiente generación con los resultados obtenidos, posibilitando modificar el porcentaje de crossover y de mutación.

El criterio de parada se establece mediante un número fijo de generaciones a computar, pudiendo detenerse y continuar el cálculo de las mismas antes de este punto. (Implementación de hilos (treath) en java).

Estudio comparativo de resultados

N generaciones=100

p	CIUDADES	POBLACION	%MUTACION	%CROSSOVER	P.SIG GEN	SUP.SIG.G	APTITUD
1	10	100	10	50	5	5	866.2987392781653
2	20	100	10	50	5	5	1298.8326485811754
3	10	200	10	50	5	5	696.997805505715
4	10	100	20	50	5	5	760.2042235938017
5	10	100	10	100	5	5	696.997805505715
6	10	100	10	50	10	5	Min ó 760.2042235938017
7	10	100	10	50	5	10	Min ó 760.2042235938017

En la tabla superior podemos observar un resumen de 7 ejecuciones realizadas sobre el mismo mapa (a excepción de la op 2) en las que hemos ido variando los parámetros del algoritmo de n a n*2 respecto al patrón inicial p=1

p=1 vs p=2 (Ciudades):

Al duplicarse observamos que con el mismo número de generaciones, la función de aptitud es mayor. Si tenemos en cuenta que esta representa la media de distancia total recorrida y que el mapa ha variado aleatoriamente, (sin variar las dimensiones), determinamos que el número de ciudades no es determinante más que para el rendimiento del algoritmo.

p=1 vs p=3 (Población):

Al duplicarse la población usada en el algoritmo observamos que la función de aptitud mejora.

p=1  vs p=4 (%Mutación):

La variación de la mutación nos permite explorar espacios de búsqueda que de otro modo quedarían fuera del alcance.  En este caso el fitness obtenido en p=3 es el mínimo, aumentándose al introducir mutaciones para este caso.

p=1  vs p=5 (%Crossover):

Al duplicar la posibilidad de cruzamiento, (y para este algoritmo con dos puntos de swap), obtenemos más oportunidades de no encontrar un mínimo local.

p=1  vs p=5,6 (Padres y supervivientes de la siguiente generación):

Al modificar estos parámetros influimos en la función de cálculo de individuos de la próxima generación. Para este caso, se obtienen dos valores, el mínimo ya conocido y un valor de aptitud superior.

Manual de aplicación

Pantalla Principal:

En la pantalla principal podemos observar inicialmente 5 secciones: el menú, el cuadro de control, la sección de parámetros del mapa, la de parámetros del AG, y la consola de salida.

Algunas de estas funciones están desactivadas inicialmente hasta que puedan ser usadas.

En el momento en que se produce la llamada a la generación del mapa, se creará una nueva ventana que contiene el mapa generado y donde podremos observar los cálculos de recorridos para el algoritmo TSP.

1. 1.      Menú:
   1. a.      Archivo:
      1.                                                                i.
         

         Guardar Resultados: Almacena los resultados de Consola en un fichero

      2.                                                              ii.     Salir: Sale de programa liberando la memoria,

1. Algoritmos Genéticos: Da acceso a las funciones de manejo del AG.

1.                                                                i.     Generar Ciudades: Genera un mapa de x*y dimensiones con k ciudades.

1.                                                              ii.     Iniciar/Continuar: llama al AG para resolver el problema con los parámetros indicados, o recupera una operación previamente detenida.

1.                                                             iii.     Parar/Pausa: Detiene la ejecución del AG, pudiéndose reanudar.

1.                                                            iv.     Reiniciar: Recarga los parámetros del AG sin utilizando el mismo mapa y ciudades generadas previamente. Útil para comparar resultados del AG.

1. c.      Help:

1.                                                                i.
   

   About: Muestra información sobre el programa.

1. 2.      Barra de Control:

Contiene las opciones más habituales para el uso del programa.

	Generar Mapa: Genera un mapa de x*y dimensiones con k ciudades.
	Iniciar/Continuar: llama al AG para resolver el problema con los parámetros indicados, o recupera una operación previamente detenida.
	Parar/Pausa: Detiene la ejecución del AG, pudiéndose reanudar.
	Reiniciar: Recarga los parámetros del AG sin utilizando el mismo mapa y ciudades generadas previamente. Útil para comparar resultados del AG.
	About: Muestra información sobre el programa.
	Salir: Sale del programa.
	Salida por Consola: activa la redirección de salida output del sistema al cuadro Consola para poder guardar los datos en un fichero. (Mejor rendimiento si se redirige la salida mediante operadores >> en la consola al iniciar la aplicación)
	Guardar Resultados: Almacena el contenido de Consola en un fichero.

1. 3.      Parámetros del mapa:

Establecemos el número de ciudades que contendrá el mapa a generar, así como las dimensiones del mismo.

1. 4.      Parámetros del Algoritmo Genético:

Facilitamos los parámetros para el AG, y establecemos una condición de parada basada en un numero de generaciones.

1. 5.      Consola:

Capturamos la salida output del sistema y la mostramos en este campo a fin de ver los datos en tiempo de ejecución del algoritmo. Para más detalle ver el atributo debug de la clase GeneticAlgorithm. Debe estar marcada la opción Salida por consola de la barra de controles.

Si quisiéramos guardar los datos obtenidos en este cuadro de texto, podemos utilizar el botón Guardar Resultados que nos mostrará una ventana de dialogo solicitando los datos necesarios.

1. 6.      Mapa de Representación:

En esta ventana podemos observar en tiempo real los enlaces entre ciudades que va calculando el AG. Así mismo, observamos la generación actual en la que se encuentra, así como el último individuo ganador y su aptitud.

Pasos para reproducir el algoritmo:

1. Generar Mapa: previamente estableceremos unos valores de altura y anchura para el mapa a generar, así como el número de ciudades que contendrá.
2. Iniciar/Continuar: Facilitamos los datos de la sección “Parámetros del Algoritmo Genético:” Si no queremos los visualizar los valores en consola y obtener mayor rendimiento dejaremos sin marcar “Salida por Consola”. Finalmente pinchamos en Iniciar/Continuar.
3. El algoritmo se detendrá automáticamente al llegar al número de generaciones máximo establecido, o al pulsar en parar/pausa. Si decidimos continuar con el proceso pulsando de nuevo en Inicio/Continuar, los datos se mantendrán.
4. Para usar el mismo mapa, recogiendo de nuevo los parámetros del algoritmo, usaremos la función Reiniciar.
5. Para almacenar el contenido del campo Consola debemos pulsar en Guardar Resultados. El programa nos solicitará un nombre y ubicación para guardar los resultados obtenidos en formato de texto.

Para realizar permutaciones con mayor eficiencia leer el archive README_infaar01.TXT.

Algoritmos Genéticos:Alberto Arce Rodríguez

README_infaar01.TXT.———————————————————————-

Notas para la ejecución del TSP
-------------------------------
Autor: Alberto Arce Rodríguez
Fecha ult. mod: 13-06-11
RNAG Universidad de Leon 2011

Es necesario tener la maquina virtual java en el sistema, el librerias utilizadas han sido incrustadas en el jar.

Los ejecutables compilados se encuentran en la carpeta "dist".

El código fuente se encuentra bajo la carpeta "src".

1ª OPCIÓN:
----------
Para extraer los datos de las aptitudes en las generaciones podemos hacerlo en tiempo real ejecutando la aplicación
directamente (archivo .jar) y seleccionando Salida por Consola.
Si queremos guardar estos datos pincharemos en Guardar resultados y nos solicitará una ruta para dejar los resultados
y un nombre para el fichero.

2ª OPCIÓN >> rendimiento:
-------------------------
Como el puenteo de la consola en un JTextField consume bastantes recursos, para iteraciones de un gran numero
de generaciones (por encima de 100) es mejor utilizar el batch AAGG_TSP_RENDIMIENTO.cmd. (o sh para linux)
En este caso no debemos activar la salida por Consola en la interfaz ya que esta es direccionada directamente
 a un fichero llamado OUTPUT.txt, este ha de estar ubicado en la misma carpeta que el fichero por lotes cmd.
------------
FiN Archivo
---------------------------------------------------------

About these ads