Una domanda di dettaglio quando si applica algoritmo genetico al venditore di viaggi

Question

Ho letto varie cose su questo e capisco il principio e i concetti coinvolti, tuttavia, nessuno dei documenti menziona i dettagli su come calcolare l'idoneità di un cromosoma (che rappresenta una via) che coinvolge città adiacenti (nel cromosoma) che non sono direttamente connesse da un bordo (nel grafico).

Ad esempio, dato un cromosoma 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, in cui ogni gene rappresenta l'indice di una città sul grafico/mappa, come calcoliamo la sua forma fisica (cioè la somma totale distanze percorse) se, diciamo, non esiste un vantaggio/legame diretto tra la città 2 e 8. Seguiamo una sorta di algoritmo avido per elaborare un percorso tra 2 e 8 e aggiungere la distanza di questa rotta al totale?

Questo problema sembra abbastanza comune quando si applica GA a TSP. Chiunque lo abbia fatto prima, condividi la tua esperienza. Grazie.

Answer 1

Se non esiste un collegamento tra 2 e 8 sul grafico, allora qualsiasi cromosoma con 2 | 8 o 8 | 2 in esso non è valido Per il problema del venditore di viaggi classico. Se trovi qualche altro percorso tra 2 e 8, probabilmente violi il requisito "Visita ogni posizione una volta".

Una soluzione davvero ingannevole ma pragmatica è quella di includere bordi tra quei nodi con distanze incredibilmente alte o addirittura +INF se la tua lingua lo supporta. In questo modo, la tua funzione di fitness di minimizzazione standard li polerà naturalmente.

Penso che la formulazione originale del problema includa bordi tra tutti i nodi, quindi questo non è un problema.

Answer 2

Questo è il tipo esatto di problema, sono stati applicati metodi di crossover e mutazione specializzati per soluzioni basate su GA ai problemi di TSP. Guarda questo domanda.

Answer 3

Se il cromosone non rappresenta una soluzione valida, è completamente inadatto risolvere il problema. Quindi, a seconda di come ordini il fitness. cioè se un numero inferiore rappresenta più fitness (forse una buona idea quando l'idoneità rappresenta il costo totale), lo assegneresti un valore massimo e spezzeresti qualsiasi ulteriore calcolo di fitness su quella cromosone quando si arriva a una sequenza genica non valida.

(o viceversa, assegnarlo una forma fisica zero se una forma fisica superiore significa che un cromosone è più adatto al lavoro)

Tuttavia, come altri hanno sottolineato, potrebbe essere meglio garantire che i cromosoni non validi non si verifichino. Tuttavia, se questo è esso stesso un processo eccessivamente composto, consentire loro e garantire che è improbabile che i cromosoni rotti trasformino in generazioni successive potrebbe essere un approccio accettabile.