Come facciamo a sapere che la prossima generazione sarà migliore?

Un algoritmo genetico cerca di migliorare ogni generazione abbattendo la popolazione. Ogni membro viene valutato in base a una funzione di fitness e solo a una parte con punteggio elevato è consentito riprodurlo.

Hai ragione, però: non c'è alcuna garanzia che la prossima generazione migliorerà sul punteggio del suo predecessore.

Considera il programma di donnola di Dawkins : "evolvendo" la stringa "Methinks it is like a weasel" . Partendo da una popolazione di stringhe casuali, la funzione fitness valuta la corrispondenza testuale più vicina, che risulta turbata per produrre la generazione successiva. Con una semplice riproduzione crossover, due stringhe ad alto punteggio che sono combinate potrebbero facilmente produrre prole con un punteggio inferiore. Anche la mutazione casuale "asessuata" di una singola stringa di fitness potrebbe abbassare la forma fisica del bambino.

Vale la pena notare, penso, che questo non è necessariamente un difetto. Con questo tipo di ricerca, c'è l'idea di massimi locali . Un membro della popolazione potrebbe rappresentare una soluzione che non è il risultato ottimale, ma è il migliore che si possa ottenere senza peggiorare sulla strada.

Immagina che la funzione di fitness per il programma di donnola non trovi solo la distanza di modifica, ma abbia qualche nozione di "parola", e verifica se l'ultima parola della stringa è il nome di un animale. Qualsiasi nome di animale ha un buon punteggio, ma "weasel" ottiene un grande bonus.

Ora cosa succede se "Methinks it is like a walrus" è evoluto? Segna bene Non così come la stringa finale di destinazione, ma migliore di "Methinks it is like a walrut" o altre varianti ravvicinate che potrebbero essere raggiunte da un singolo passaggio di mutazione.

La stringa di tricheco è un massimo locale e la ricerca può rimanere bloccata lì a meno che il programma non permetta di peggiorare il punteggio della prossima generazione.

Non sappiamo che migliorerà, sappiamo che non peggiorerà.

In ogni generazione, non consiste solo dell'ospring dei migliori elementi, ma include anche gli elementi migliori stessi - i cloni se vuoi. Dal momento che sono ancora presenti, avranno lo stesso punteggio di prima. Significa che se nessuno dei figli è migliore, i vincitori delle generazioni precedenti vinceranno di nuovo e saranno rimodellati / allevati.

Si consideri: Con un individuo progenitore che è una lettera, ad esempio A Un bambino mutato è definito aggiungendo un numero, ad esempio A1 , soluzioni cross-bread scritte con parentesi attorno al genitore, ad esempio (A1B2) E il nucleo di fitness di ogni scrittura individuale dopo di esso - più alto è meglio [12]

Per la dimostrazione, considera un Pool di 5, dove manteniamo il migliore 2. e riempire con 1 mutante di ciascuno, più un incrocio tra parentesi

Generazione 1

• A [10]
• B [5]
• C [4]
• D [3]
• E [1]

Mantieni A , B , in quanto sono i migliori due e riempi altri 3 slot con i discendenti

Generazione 2

• A [10]
• B [5]
• (AB) [7]
• A1 [12]
• B1 [4]

Mantieni A e (AB) , poiché sono i migliori 2 - Questo significa che nonno A sarà ancora nel pool poiché la maggior parte dei bambini lavora più debole

Generazione 3

• A [10]
• (AB) [12]
• (A(AB)) [14]
• A2 [8]
• (AB)1 [13]

Mantieni (AB)1 e (A(AB)) - questa volta non sono stati mantenuti i nonni, dato che due dei loro figli li hanno battuti. Ma se (AB1) ha avuto risultati leggermente peggiori, avremmo invece mantenuto (AB) .

Questo continua fino a quando il punteggio non si stabilizza. Il che indica che hai colpito qualche tipo di massimi locali (potenzialmente un massimo globale). Uno perché scoprire questo sarebbe se gli stessi individui continuano a essere "clonati" nella prossima generazione. (anche se per problemi di alta dimensione che potrebbero richiedere troppo tempo, forse meglio controllare semplicemente i miglioramenti < una particolare tolleranza)

In generale, gli algoritmi genetici funzionano creando una serie di variazioni (casuali) sui genitori in ogni generazione. Quindi viene applicata una funzione di selezione e sopravvive la prole più adatta a questa funzione. Quindi la progenie non è necessariamente migliore dato che la variazione è casuale, ma combinato con la selezione si ottiene un miglioramento nel tempo.

Quando ho studiato gli algoritmi genetici al college è stato spiegato in questo modo:

Immaginate che una soluzione sia una combinazione di "geni", in cui ogni gene influisce sulla bontà della soluzione nel suo complesso. Quando due soluzioni sono accoppiate, i geni vengono scelti casualmente da ciascun genitore.

Ora, se il gene conduce, generalmente, a una buona soluzione, la sua frequenza nel pool genetico aumenta. In casi estremi, il gene dominerà la popolazione.

Quindi, quando pensi agli algoritmi genetici (e all'evoluzione in generale), non devi pensare alle persone. Dovresti pensare a geni e popolazioni nel loro complesso. Anche se una soluzione "migliore" viene persa, non significa che i suoi geni siano persi.

C'è anche un'idea di elitarismo negli algoritmi genetici. Significa che le migliori soluzioni sono sempre mantenute per generazioni. Ciò potrebbe accelerare la convergenza dell'algoritmo, ma è più facile che l'algoritmo rimanga bloccato nell'ottima locale.

Gli algoritmi GA non sono deterministici, non garantiscono di ottenere un miglioramento in ogni generazione e inoltre non garantiscono di trovare un totale ottimale. Tuttavia, la fase di selezione di un GA, utilizzando una funzione di fitness, rende più probabile che "le buone soluzioni" sopravviveranno.