XII. Problema del viajante de comercio
Sobre el problema
El problema del viajante de comercio (TSP) ya se menciono en uno de los capitulos anteriores. Para repetirlo: hay ciudades y distancias dadas entre ellas. El viajante de comercio tiene que visitar todas, recorriendo la menor distancia posible. La tarea es encontrar una secuencia de ciudades que minimice la distancia total recorrida. En otras palabras, queremos encontrar un recorrido hamiltoniano minimo en un grafo completo de N nodos.
Implementacion
Se utiliza una poblacion de 16 cromosomas. Estos cromosomas usan codificacion de permutacion; en el capitulo sobre codificacion puede ver como codificar una permutacion de ciudades para el TSP. El TSP se resuelve sobre un grafo completo (es decir, cada nodo esta conectado con todos los demas) con distancias euclidianas. Observe que despues de agregar o eliminar una ciudad, es necesario crear nuevos cromosomas y reiniciar todo el algoritmo genetico.
Puede seleccionar los tipos de cruce y mutacion. Sus significados se describen a continuacion.
Cruce
- Un punto - se copia parte del primer progenitor y el resto se toma en el mismo orden que en el segundo progenitor
- Dos puntos - se copian dos partes del primer progenitor y la seccion entre ellas se toma en el mismo orden que en el segundo progenitor
- Ninguno - no hay cruce; la descendencia es una copia exacta de los progenitores
Mutacion
- Aleatoria normal - se eligen unas pocas ciudades y se intercambian
- Aleatoria, solo mejorando - se eligen e intercambian aleatoriamente unas pocas ciudades solo si mejoran la solucion (aumentan la aptitud)
- Sistematica, solo mejorando - las ciudades se eligen e intercambian de forma sistematica solo si mejoran la solucion (aumentan la aptitud)
- Mejora aleatoria - lo mismo que "aleatoria, solo mejorando", pero primero se realiza una mutacion "aleatoria normal"
- Mejora sistematica - lo mismo que "sistematica, solo mejorando", pero primero se realiza una mutacion "aleatoria normal"
- Ninguna - no hay mutacion
Ejemplo
La siguiente demostracion muestra un AG resolviendo el TSP. El
boton "Change View" cambia entre la poblacion completa y la mejor solucion.
Puede agregar y eliminar ciudades haciendo clic sobre la grafica. Despues de agregar o eliminar
una ciudad aparecera un recorrido aleatorio, porque debe crearse una nueva poblacion con nuevos cromosomas.
Observe tambien que estamos resolviendo el TSP sobre un grafo completo.
Pruebe ejecutar el AG con diferentes configuraciones de cruce y mutacion, y observe como
cambia su rendimiento (y su velocidad; agregue mas ciudades para ver la diferencia).
·