Come fa l'algoritmo genetico a sapere quando fermarsi se non si conosce il minimo globale?

Question

Come fa l'algoritmo genetico a sapere quando fermarsi se non si conosce il minimo globale?

#1 da (7 voti)
#2 da (3 voti)

4

Dire che sto scrivendo un GA per risolvere il problema del commesso viaggiatore. Non so in anticipo quale sia il percorso più breve, quindi come fa il mio GA a sapere quando fermarsi?

Se aspetto che la migliore forma fisica non si riduca per alcune generazioni, come faccio a sapere che non sono temporaneamente bloccato in un minimo locale, che qualche mutazione nella prossima generazione può aiutare? Se si migliora la forma fisica migliore, come faccio a sapere che questa non è solo una cosa temporanea che sarà risolta in una futura generazione?

genetic-algorithms

posta Avrohom Yisroel 05.01.2017 - 22:33

fonte

2 risposte

Leggi altre domande sui tag genetic-algorithms

Cosa c'è di nuovo nell'assemblatore PL / I, DB2 e S / 390? Come sono codificati i valori letterali in bytecode?

score 7 · Answer 1

In breve, non lo fai. Se non conosci la migliore risposta globale, non saprai mai se la risposta che hai trovato è la migliore o solo la migliore risposta locale.

Per provare a risolverlo, un'idea è riavviare . Riavviare l'algoritmo con parametri diversi, quindi confrontare Optima localizzato e prendere il migliore. Anche allora, tuttavia, non è garantito che tu abbia trovato la risposta migliore.

Come nota a margine, potresti trovare consigli migliori sul sito Computer Science SE per cose come algoritmi genetici.

score 3 · Answer 2

Questo è un problema non solo per le GA ma per molte tecniche di ottimizzazione, ad es. programmazione lineare.

Una soluzione (che ha i suoi problemi) consiste nell'includere la diversità nella funzione fitness, che garantisce uno spazio di ricerca maggiore e una maggiore probabilità di sfuggire ai minimi locali.

Articolo .