Algoritmo genetico di nuova generazione in crescita esponenziale

Dopo aver generato la popolazione iniziale (il pool dovrebbe essere abbastanza grande) e si applica la funzione fitness, si selezionano i genitori per la prossima generazione.

Una volta che hai i tuoi genitori, scarti gli altri individui in modo che tu possa sostituirli con la nuova generazione. Questa sostituzione manterrà la tua dimensione della popolazione in controllo, dopo tutto, se il singolo I non si adatta ai criteri di idoneità per contribuire alla prossima generazione, perché hai bisogno di tenerlo?

Nota comunque che nel tuo studio c'è un'alta probabilità che il tuo algoritmo converga molto rapidamente in un massimo / minimo locale. Questo perché solo tieni il primo 20% della popolazione per l'accoppiamento. Di solito questa è una cattiva idea dal momento che farà sì che il tuo GA resti bloccato in un massimo / minimo locale. Per risolvere il problema, includere anche alcune delle soluzioni peggiori, ad esempio, il 20% più alto e il 5-10% peggiore.

EDIT: In alternativa, potresti anche provare qualcosa di simile a ciò che @ Jeff Langemeier propone e invece di selezionare il 10% più povero della popolazione, scegli casualmente una data quantità dal non migliore (in questo caso, i restanti 80 %) individuale.

Scegliere i bambini adatti per la prossima generazione di accoppiamento è lo stesso calcolo di idoneità che ha reso i loro genitori adatti. Inoltre, alla fine della generazione attuale, non dovresti avere più figli della popolazione iniziale. Ricorda, questo non è un free-for-all, ma la sopravvivenza del più adatto.

Stai selezionando un gruppo altamente selezionato adatto per l'accoppiamento; essenzialmente scartando fino al 75-80% o più della popolazione iniziale (spazio di ricerca) o comunque molto necessario per garantire solo il compagno più adatto.

Un algoritmo genetico dovrebbe essere eseguito fino a quando non si è esaurito lo spazio di ricerca o, in altre parole, fino a quando non ci sono più coppie di accoppiamento e, si spera, che l'ultima progenie o un gruppo molto piccolo di figli produca la risposta desiderata.

Ciò richiederà di mettere a punto i fattori fitness, crossover e mutazioni. Ricordo quando scrissi un GA per risolvere il modo in cui gli operatori aritmetici (*, /, +. -) ei valori numerici (0-9) sono combinati per formare un valore generato casualmente come 45. Ho rappresentato i miei cromosomi come x- bit di valori binari che contenevano ogni operatore e il numero 0-9. Sono stati pesantemente randomizzati attraverso un'euristica per garantire il maggior numero possibile di variazioni.

Ho dovuto modificare selezione, crossover e mutazione solo per risolvere il problema ma potrebbe essere risolto. Se vedi che le popolazioni vanno fuori controllo, qualcosa non va nel tuo algoritmo. Ricordo che da una popolazione iniziale di 100.000 ho perso tra 50 e 75k che non erano adatti all'accoppiamento.

Gioca ancora con lui; capisci come dovrebbe funzionare e sono certo che ce la farai.

Prima di rispondere alla tua domanda, devo chiederti. Quando esegui il GA, hai effettivamente notato un guadagno nella tua soluzione? In altre parole, dopo ogni iterazione le nuove generazioni che hai sono effettivamente migliori delle precedenti?

Se lo fai, allora sono sorprendentemente sorpreso perché

1. Come Mushy ha sottolineato molto correttamente: il tuo GA è solo un rivestimento zuccherino di ricottura simulata (o Monte Carlo)

2. Man mano che l'entropia aumenta perché ti basta mescolare e abbinare, lo spazio di ricerca da esplorare continuerà ad aumentare. E come sappiamo bene, dopo alcune generazioni, le tue soluzioni degenereranno, le uniche due cose che posso vedere impediscono che ciò accada, sono

   (a) hai una serie di regole su qualsiasi o le operazioni che hai .. crossover, selezione, mutazione o altro se sei creativo abbastanza ..

   (b) intervento divino, ti infili le mani umane e intervenire su alcune o tutte le iterazioni (fatte attraverso alcune aggiunte euristico nella funzione di fitness, o puoi avere a iterazione 1 fai questo, 2 fallo, ...)

Dichiarazione di non responsabilità: non sono esperto in questo settore, ma anche persone come me sanno che devi mettere l'euristica lì da qualche parte.