Una domanda dettagliata quando si applica l'algoritmo genetico al venditore ambulante

Question

Ho letto varie cose su questo e capisco il principio ei concetti coinvolti, tuttavia, nessuno della carta menziona i dettagli di come calcolare la forma fisica di un cromosoma (che rappresenta un percorso) coinvolgere le città adiacenti (nel cromosoma) che non sono direttamente collegate 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 si calcola la sua idoneità (es. la somma totale delle distanze percorse) se, per esempio, non esiste un collegamento diretto tra le città 2 e 8. Seguiamo una sorta di algoritmo ingordo per calcolare un percorso tra 2 e 8 e aggiungere la distanza di questo percorso a il totale?

Questo problema sembra piuttosto comune quando si applica GA a TSP. Chiunque lo abbia già fatto, per favore, condividi la tua esperienza. Grazie.

Answer 1

Se non c'è alcun collegamento tra 2 e 8 sul grafico, allora qualsiasi cromosoma con 2 | 8 o 8 | 2 in esso non è valido per il classico problema del commesso viaggiatore. Se trovi qualche altro percorso tra 2 e 8, probabilmente violerai il requisito "visita ogni luogo una volta".

Una soluzione davvero dubbia ma pragmatica consiste nell'includere i bordi tra questi nodi con distanze incredibilmente elevate, o anche in INF se la lingua lo supporta. In questo modo, la tua funzione di minimizzare la forma fisica standard li taglierà naturalmente.

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

Answer 2

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

Answer 3

se il cromosone non rappresenta una soluzione valida, quindi è completamente inadatto a risolvere il problema. Quindi dipende da come ordini la forma fisica. cioè se un numero più basso rappresenta più fitness (probabilmente una buona idea quando il fitness rappresenta il costo totale), allora assegneresti un valore massimo e interromperesti qualsiasi ulteriore calcolo di idoneità su quel cromosone quando arriverai a una sequenza genica che non è valida.

(o viceversa, assegnare una vasca di zero se una palestra alto significa un chromosone è più adatto per il lavoro)

tuttavia come altri hanno fatto notare che potrebbe essere meglio per garantire che chromosones validi dont verifica . Tuttavia, se questo è di per sé un processo eccessivamente complicato, consentire loro e assicurarsi che i cromosomi spezzati non siano in grado di trasformarli in generazioni successive potrebbe essere un approccio accettabile.