Come trovare i parametri migliori per un algoritmo genetico?

Question

Alcuni quadri algoritmo genetico, come http://www.aforgenet.com/ richiede molti parametri, come il tasso di mutazione, le dimensioni della popolazione, ecc

C'è numeri migliori universali per tali parametri? Credo che dipenda dal problema (ritardo della funzione di fitness, ritardo di mutazione, ritardo di ricombinazione, velocità di evoluzione, ecc.). Il mio primo pensiero è stato quello di utilizzare un GA per configurare un altro GA.

Qualche idea migliore?

Answer 1

L'unica volta che ho programmato un algoritmo genetico ho incluso quei valori nei valori da mutare, in pratica come hai detto usando un GA per configurarsi. Ha funzionato sorprendentemente bene, soprattutto perché ho trovato utile per quei valori cambiare nel corso del suo calcolo.

Answer 2

Non c'è davvero un modo automatico per farlo per un dato set di dati. Se ci fossero, non potrebbero esporre quei parametri. Usare un secondo GA per sintonizzare i parametri del primo GA è pericoloso - usi un terzo GA per mettere a punto i parametri del secondo? Anche se l'hai fatto, è comunque una ricetta per il sovraffollamento.

Il mio consiglio sarebbe di giocare con i parametri, e vedere in che modo influiscono sulla distrubuzione della popolazione ad ogni generazione, quante generazioni ci vogliono per ottenere una risposta accettabile, ecc. Se si hanno troppe mutazione la popolazione non sarà mai stabilizzare. Troppo poco e finirai con l'omogeneità.

È un segreto sporco di GA che sintonizzarli è un'arte, non una scienza.

Answer 3

Trovo utile pensare a questi problemi come un paesaggio, in cui si sta cercando di trovare il punto più basso.

I metodi come gli algoritmi genetici vengono utilizzati quando il paesaggio è troppo grande per testare tutti i punti e la "forma" del paesaggio è tale che metodi come la discesa del gradiente ti faranno rimanere bloccati nei minimi locali.

Un buon esempio è la funzione di Rastrigin (image ref): :

Le scelte sono:

dimensioni Generation:

• Troppo grande: si sta andando ad avere una lunga tempo storico, limitando quante probabilità ogni individuo deve esplorare il suo quartiere.
• Troppo piccola: non si ottiene la copertura corretta dello spazio di ricerca.

tasso di mutazione:

• troppo elevato: si rischia l'individui "saltare" su una soluzione erano vicino.
• Troppo basso: avranno tutti bloccati nei minimi locali.

Quindi in realtà dipende dal proprio particolare spazio di ricerca. Sperimenta con i parametri e prova a trovare la combinazione ottimale.Concordo sul fatto che l'utilizzo di un altro GA per ottimizzare i parametri non risolverà il problema.

Answer 4

Non è facile.

Perché? A causa del teorema No Free Lunch. Questo in sostanza afferma che non esiste un algoritmo di ricerca generale che funzioni correttamente per tutti i problemi.

Il meglio che puoi fare è personalizzare la ricerca di uno spazio di problema specifico . Dovrai modificare manualmente i tuoi parametri per adattarli alla tua soluzione. Scusate.

Utilizzare un GA per trovare i parametri GA diventa complicato. Come trovi i parametri ottimali per la tua ricerca su GAGA? Un altro GA ...?

Answer 5

Come tutti hanno detto, non c'è una risposta. Sebbene ci sia una certa tendenza ad usare il tasso di crossover sul livello 0.7-0.9 e la mutazione sullo 0.1-0.3 dipende davvero. Dipende dal problema, può dipendere dalla funzione fitness e dipende sicuramente dall'algoritmo genetico stesso. Esistono molte variazioni di GA, i parametri ottimali per lo stesso problema possono variare.

Per quanto riguarda l'utilizzo di GA per regolare i parametri di GA di destinazione, ci sono approcci come questo, ma, come è stato sottolineato, come regolare i parametri del primo GA? Tieni presente che forse il tasso di mutazione dovrebbe essere più elevato all'inizio e che dovrebbe diminuire mentre il tasso di crossover dovrebbe aumentare. È questione di esplorazione contro sfruttamento. Ci sono approcci per consentire a GA di essere più adattivi e lasciare che modifichi i suoi parametri mentre cerca la soluzione. I controller Fuzzy sono talvolta utilizzati per manipolare i parametri di GA. Ci sono anche altri approcci.

Se vuoi saperne di più, acquista dei libri o consulta i documenti di ricerca accademici.
Se è necessario impostare la propria GA senza ricerche approfondite, provare alcuni valori di altri utenti e sperimentare con essi.

Answer 6

Trovo piuttosto deludente ci siano così tante risposte che presuppongono che non è possibile trovare automaticamente i parametri migliori per l'Algoritmo Genetico. Concordo sul fatto che i parametri dipendono dal problema, tuttavia esistono metodi in cui è possibile trovarli.

Inoltre il No Free Lunch Theorem in nessun modo vi impedisce di trovare i migliori parametri, come ci sono già state discussioni che contesta il fatto:

• Practically it does not hold
• Description length may dispute the theorem
• Coevolution can make the theorem irrelevant

Esistono due tipi di impostazione dei parametri:

• parametri di sintonia (ricerca dei parametri offline - prima che il GA è gestito)
• controllo dei parametri (parametro tweaking on-line - durante la corsa GA)
  • Adaptive
  • Auto Adaptive
  • deterministico

C'è molta letteratura fuori ci che descrive come si possono trovare questi parametri ottimali, dipende se si desidera eseguire la ricerca parametri offline o online. La credenza popolare è che offline è più adatto per la maggior parte dei casi perché i metodi di controllo dei parametri online aggiungerebbero troppa complessità rispetto al offline.

Ecco alcuni esempi per trovare le "migliori" parametri:

parametri di sintonia:

• semplice parametro sweep (provare tutto)
• Meta-GA ontop di un GA
• Racing strategy per trovare i parametri migliori
• Meta-GA and Racing together

controllo parametro:

• Adaptive probabilities for mutation and crossover
• Self adaptive popuation size
• Deterministic Genetic Operators

E molti altri, basta cercare nella letteratura utilizzando parole chiave utilizzate in precedenza. Esistono metodi scientifici per trovare parametri adatti per ogni problema dato!