Sto costruendo un algoritmo genetico per affrontare il problema del commesso viaggiatore. Sfortunatamente, ho raggiunto picchi che possono durare per oltre un migliaio di generazioni prima di mutare e ottenere risultati migliori. Quali operatori di crossover e mutazione generalmente funzionano bene in questo caso?Operatori GA consigliati per un problema TSP?
La prego di chiarire
"Purtroppo, mi ha colpito i picchi che possono sostenere per più di mille generazioni prima mutazione di loro e ottenere risultati migliori"?
È possibile controllare gli operatori di crossover, che si assicurano di non avere nodi ripetuti nei cromosomi figli. Un paio di quegli operatori crossover sono gli operatori Order Crossover (OX) e Edge Crossover.
La mutazione può essere semplice come scambiare semplicemente due posizioni in un singolo cromosoma.
BTW, dal momento che hai taggato "python", dai un'occhiata a Pyevolve, ma ha anche un esempio di TSP.
Mutazione ordinata e crossover ordinato (vedere this article). La mutazione standard e le operazioni di crossover generalmente causano soluzioni non valide (ad esempio città duplicate e/o mancanti in una rotta).
C'è stato un similar question di recente.
Ho a Java applet that implements the TSP using ordered cross-over and mutation, se sei interessato a confrontare le prestazioni della tua implementazione.
Se il problema è che i picchi rimangono per oltre mille generazioni, il problema potrebbe non essere con gli operatori di crossover e di mutazione. Potresti non introdurre o mantenere abbastanza variazioni nella tua popolazione: esaminerei le proporzioni dei crossover, delle mutazioni e dei sopravvissuti da una generazione all'altra e probabilmente aumenterei la proporzione delle mutazioni.
http://stackoverflow.com/questions/1544055/rossover-operation-in-genetic-algorithm-for-tsp potrebbe aiutare. –