Scopriamo come funziona il codice di un algoritmo genetico: la riproduzione

da | Mar 29, 2021 | Tutorial | 0 commenti

Continua lo studio degli algoritmi genetici. In questo articolo scopriremo come riprodurre una nuova generazione, a partire dai membri selezionati dalla popolazione genitoriale.

Ora che abbiamo una strategia per individuare i genitori, dobbiamo capire come usare la riproduzione, per creare la nuova generazioni di individui, tenendo a mente il principio darwiniano dell’eredità , ossia i figlio ereditano proprietà dai loro genitori. Anche in questo caso, ci sono una serie di tecniche diverse che potremmo utilizzare. Per esempio una ragionevole e semplice da programmare, è una riproduzione asessuale, ossai tenere solo un genitore e creare un figlio che è l’esatta copia del padre..o madre :). Tuttavia, l’approccio standard prevede l’utilizzo di 2 genitori e la generazione di un filgio seconod i seguenti step.

1. Crossover.

 

 Il crossover conduce alla creazione di un figlio con un codice genetico nuovo ripsetto a quello dei due genitori. Si prendando ad esempio due frasi dal mating pool:

Parent A: FORK

Parent B: PLAY

Creiamo un figio da queste due frasi. Forse il metodo più ovvio (50/50 method) è prendere i primi due caratteri di A e i secondi due caratteri di B, come nell’immagine sotto:

Una variazione di questa tecnica è definire un punto medio casuale. In altre parole, non avremo il “taglio” esattamente al centro del codice di ogni genitore. Si veda l’immagine sotto:

Un altra possibilità è la selezine casuale dei caratteri dai genitori. Si veda l’immagine sotto:

2. Mutation.

Una volta che il figlio è sato creato via crossover, si applica un ulteriore processo prima di aggiungere il filgio alla nuova generazione. La mutazione. E’ uno step opzionale, ci sono infatti alcuni casi in cui non è necessario. Comunque esiste in funzione del principio di variazione darwiniano. Creiamo una popolazione iniziale causale, avendo la sicurezza di una varietà di membri diversi. Tuttavia a volte non è sufficiente per assicurare una variazione genetica. La mutazione può essere descritta in termini di percentuale. Un algoritmo genetico può avere un tasso di mutazione del 5%, dell’1% o dello 0,1%.Prendiamo l’esempio a fianco con la stringa di caratteri “FORY”:

Se avessimo un tasso dell 1% significherebbe che ogni carattere generato dal crossover, avrebbe l 1% di possibilità di mutare. In questo caso mutare significa, assumere un nuovo carattere in maniera casuale.

Come si vedrà più avanti, il valore della mutazione, può influire fortemente sul comportamento del sistema. Certamente un valore alto (80% ad esempio) potrebbe essere altrettanto negativo, poiche se la maggioranza dei geni dei figli venisse generata casualemnte, non si avrebbe un valore di fit valido per assicuare il “miglioramento della specie” nella generazione successiva, poiche si rimiscolerebbero i geni, ogni volta.

Il processo di selezione (prendere 2 genitori) e riproduzione (crossover e mutazione) viene applicato N volte, fino a quando non si ha una nuova popolazione di N elementi. A questo punto, la nuova popolazione di figli diventa la popolazione corrente. A questo punto si ripete in loop il tutto il ciclo sino ad ora descritto: