Pregunta

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) que involucra 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 resolver una ruta entre 2 y 8, y agregar la distancia de esta ruta al total?

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

¿Fue útil?

Solución

Si no hay enlace entre 2 y 8 en su gráfico, entonces cualquier cromosoma con 2 | 8 u 8 | 2 no es válido para el problema del vendedor de viajes clásicos. Si encuentra alguna otra ruta entre 2 y 8, probablemente violará el requisito "Visite cada ubicación una vez".

Una solución realmente dudosa pero pracmática es incluir bordes entre esos nodos con distancias increíblemente altas, o incluso +INF si su lenguaje lo admite. De esa manera, su función estándar de minimización de acondicionamiento físico los podará naturalmente.

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

Otros consejos

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

Si la cromosona no representa una solución válida, entonces no es apto para resolver el problema. Entonces, dependiendo de cómo ordene la aptitud física. es decir, si un número más bajo representa más aptitud física (posiblemente una buena idea cuando la aptitud física representa el costo total), entonces le asignaría un valor máximo y rompería cualquier cálculo de aptitud adicional en esa cromosona cuando llega a una secuencia genética que no es válida.

(o viceversa, asigna una aptitud de cero si una condición física más alta significa que una cromosona es más adecuada para el trabajo)

Sin embargo, como otros han señalado, podría ser mejor asegurarse de que no ocurran cromosonas no válidas. Sin embargo, si ese es en sí mismo un proceso excesivamente complejo, entonces permitirles y garantizar que es poco probable que las cromosas rotas lleguen a generaciones sucesivas podrían ser un enfoque aceptable.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top