Come trovare i migliori parametri per un algoritmo genetico?

StackOverflow https://stackoverflow.com/questions/1075628

  •  21-08-2019
  •  | 
  •  

Domanda

Alcuni quadri normativi algoritmo genetico, come http://www.aforgenet.com/ richiede molti parametri , come ad esempio tasso di mutazione, le dimensioni della popolazione, etc

C'è numeri migliori universali per questi parametri? Credo che dipende dal problema (fitness ritardo funzione di ritardo mutazione, la ricombinazione di ritardo, il tasso di evoluzione, ecc). Il mio primo pensiero è stato quello di utilizzare un GA per configurare un altro GA.

Tutte le idee migliori?

È stato utile?

Soluzione

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

Altri suggerimenti

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

Metodi come algoritmi genetici vengono utilizzati quando il paesaggio è troppo grande per testare solo tutti i punti, e la "forma" del paesaggio è tale che metodi come il gradiente di discesa si arriva bloccati in minimi locali.

Un buon esempio è la funzione di Rastrigin ( immagine ref ): alt text
(fonte: scientific-computing.com )
:

Le scelte sono:

dimensione Generation:

  • Troppo grande: si sta andando ad avere un tempo di lunga epoca, limitando il numero di le probabilità di ogni individuo deve esplorare è quartiere.
  • Troppo piccolo: non si ottiene una buona la copertura dello spazio di ricerca.

tasso di mutazione:

  • Troppo alto: si rischia gli individui "Saltare" su una soluzione che erano vicino a.
  • Troppo basso: sono tutti andando ottenere bloccati in minimi locali.

Quindi in realtà non dipende dal proprio particolare spazio di ricerca. Esperimento con i parametri e cercare di trovare la combinazione ottimale. Sono d'accordo che l'utilizzo di un altro GA a ottimizzare i parametri non ha intenzione di risolvere il problema.

Lo trovo piuttosto deludente ci sono tante risposte che assumere non è possibile trovare i migliori parametri per l'algoritmo genetico automaticamente. Sono d'accordo che i parametri non dipende il problema ma ci sono metodi in cui è possibile trovarli.

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

Ci sono due tipi di impostazione dei parametri:

  • Il parametro di sintonia (ricerca offline parametro - prima che il GA è gestito)
  • Controllo dei parametri (in linea parametro tweaking - durante la corsa GA)
    • Adaptive
    • Auto Adaptive
    • deterministici

Ci sono un sacco di letteratura là fuori che descrivono come si può trovare questi parametri ottimali, dipende se si vogliono fare la ricerca offline parametro o on-line. La credenza popolare è che la linea è più adatto per la maggior parte dei casi, perché i metodi di controllo dei parametri online sarebbe aggiungere troppa complessità nel corso offline.

Ecco alcuni esempi per trovare i parametri di "migliori":

Parametro di sintonia :

Parametro di controllo :

E molti altri, basta cercare nella letteratura utilizzando parole chiave utilizzate in precedenza. Ci sono metodi scientifici per la ricerca di parametri adatti per ogni problema!

Non è facile.

Perché? A causa della No Free Lunch teorema. Questo afferma in sostanza che non v'è alcuna Generale algoritmo di ricerca che funziona bene per tutti problemi.

Il meglio che puoi fare è su misura la ricerca di una specifica problema di spazio. Dovrete modificare manualmente i parametri per adattare la vostra soluzione. Siamo spiacenti.

Utilizzo di un GA per trovare i parametri GA si complica. Come si fa a trovare i parametri ottimali per la ricerca GAGA? Un altro GA ...?

In realtà non c'è un modo automatico per farlo per un determinato insieme di dati. Se ci fossero, non avrebbero esporre tali parametri. Utilizzando un secondo GA a regolare i parametri della prima GA è pericolosa - si usa un terzo GA per regolare i parametri del secondo? Anche se avete fatto questo, è una ricetta per overfitting comunque.

Il mio consiglio sarebbe quello di giocare con i parametri, e vedere come influenzano la tua distrubuzione popolazione ad ogni generazione, quante generazioni ci vuole per arrivare a una risposta accettabile, ecc Se avete troppo mutazione vostra popolazione sarà mai stabilizzarsi . Troppo poco e vi ritroverete con omogeneità.

E 'un segreto sporco di gas che sintonizzando loro è un'arte, non una scienza.

Come tutti gli altri, ha detto, non c'è una risposta. Anche se v'è una certa tendenza ad utilizzare tasso di crossover a livello 0,7-0,9 e 0,1-0,3 mutazione dipende davvero. Dipende problema, può dipendere funzione di fitness, e sicuramente dipende Algoritmo Genetico stessa. Ci sono molte variazioni GA, parametri ottimali per lo stesso problema può variare.

Come per l'utilizzo GA ai parametri sintonizzare di destinazione GA ci sono approcci del genere, ma, come è stato sottolineato, come ai parametri sintonizzare di primo GA? Tenete a mente, che forse tasso di mutazione dovrebbe essere più elevata all'inizio, e di quello che dovrebbe diminuire mentre cross over tasso dovrebbe essere in aumento. E 'questione di esplorazione contro lo sfruttamento. Ci sono approcci per lasciare GA essere più adattabile e lasciarlo cambiare i suoi parametri come sembra per soluzione. controllori fuzzy vengono talvolta utilizzati per manipolare i parametri di GA. Ci sono anche altri approcci.

Se volete sapere di più, acquistare alcuni libri, o guardare attraverso documenti di ricerca accademica.
Se è necessario configurare il proprio GA, senza approfondite ricerche, provare alcuni valori da altri lavorano, e sperimentare con loro.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top