Una pregunta detallada al aplicar algoritmo genético al vendedor viajero

Question

Leí varias cosas sobre esto y entiendo el principio y los conceptos involucrados, sin embargo, ninguno de los documentos menciona los detalles de cómo calcular la aptitud de un cromosoma (que representa una ruta) involucrando ciudades adyacentes (en el cromosoma) que no están directamente conectadas por un borde (en el gráfico).

Por ejemplo, dado un cromosoma 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, en el que cada gen representa el índice de una ciudad en el gráfico/mapa, ¿cómo calculamos su aptitud (es decir, la suma total de distancias recorridas) si, por ejemplo, no hay un borde/enlace directo entre la ciudad 2 y 8. ¿Seguimos algún tipo de algoritmo codicioso para calcular una ruta entre 2 y 8, y agregamos la distancia de esta ruta a ¿el total?

Este problema parece bastante común cuando se aplica GA a TSP. Cualquiera que lo haya hecho antes, por favor comparte tu experiencia. Gracias.

Answer 1

Si no hay un enlace entre 2 y 8 en su gráfico, entonces cualquier cromosoma con 2 | 8 o 8 | 2 no es válido para el problema clásico de vendedor ambulante. Si encuentra alguna otra ruta entre 2 y 8, probablemente viole el requisito de "visitar cada ubicación una vez".

Una solución realmente poco fiable pero pragmática es incluir los bordes entre los nodos con distancias increíblemente altas, o incluso + INF si su idioma lo admite. De esta forma, su función de acondicionamiento físico minimizado estándar los podará naturalmente.

Creo que la formulación original del problema incluye los bordes entre todos los nodos, por lo que esto no es un problema.

Answer 2

Este es el tipo exacto de problema, se han aplicado métodos especializados de Crossover y mutación para soluciones basadas en GA a problemas de TSP. Vea esto question.

Answer 3

si la cromosona no representa una solución válida, entonces es totalmente inadecuada para resolver el problema. Entonces, dependiendo de cómo pidas fitness. es decir, si un número más bajo representa más aptitud física (posiblemente una buena idea cuando la condición física representa el costo total), le asignaría un valor máximo y rompería cualquier cálculo de aptitud adicional en esa cromosona cuando llegue a una secuencia de genes que no sea válida.

(o viceversa, asignarle un gimnasio de cero si una aptitud más alto significa un chromosone es más adecuado para el trabajo)

sin embargo, como otros han señalado que podría ser mejor para asegurar que chromosones no válidos dont ocurrir . Sin embargo, si eso es en sí mismo un proceso excesivamente competitivo, entonces permitirles y garantizar que las cromosomas rotas no lo conviertan en sucesivas generaciones podría ser un enfoque aceptable.