Continua lo studio degli algoritmi genetici. In questo articolo Andremo ad implementare lato codice il nostro algoritmo.

In molti casi il numero degli elementi della popolazione può essere fisso, in questo caso si andrà ad utilizzare un array. Nel caso in cui il numero dei membri aumenti o decresca, si userà un ArrayList. Ma un arrau di cosa? Abbiamo bisogno di un oggetto che archivi le informazini genetiche di un membro della popolazione. Il suo DNA, per intenderci.

class DNA {

}

La popolazione sarà poi un array di oggetti DNA.

Ma cosa va nella classe del DNA? Tornando al nostro esempio della scimmia che digita sulla tastiera, il DNA è la frase casuale che digita, una stringa di caratteri.

class DNA {

String phrase;

}

Anche se questo è perfettamente ragionevole per questo particolare esempio, non useremo un vero oggetto String come codice genetico. Invece, useremo una serie di caratteri.

Utilizzando un array, saremo in grado di estendere tutto il codice che scriviamo in altri esempi. Ad esempio, il DNA di una creatura in un sistema fisico potrebbe essere un array di PVectors o, per un’immagine, un array di numeri interi (colori RGB). Possiamo descrivere qualsiasi insieme di proprietà in un array e, anche se una stringa è conveniente per questo particolare schizzo, un array servirà come base migliore per futuri esempi evolutivi.

Il nostro algoritmo genetico impone di creare una popolazione di N elementi, ciascuno con DNA generato casualmente. Pertanto, nel costruttore dell’oggetto, creiamo casualmente ogni carattere dell’array.

Ora che abbiamo il costruttore, possiamo tornare a setup() e inizializzare ogni oggetto DNA nell’array di popolazione.

La nostra Classe DNA non è ancora completa. Abbiamo bisogno di aggiungere una funzione per imolementare poi tutte le altre, come vedremo nel punto 2 e 3.

Step 2. SELECTION

Lo Step 2 dice “Valutare il fitness di ogni elemento della popolazione e costruire un mating pool”. Quindi, come prima cosa valuteremo il fitness di ogni oggetto. Nel nostro, caso, un possibile valore di fitness è la correttezza di caratteri della frase, rispetto alla frase target. Nello specifico andremo a dividere il numero dei caratteri corretti, per il numero totale dei caratteri, ottenendo così il valore fitness dell'”individuo”.

FITNESS = TOTAL # CHARACHTER CORRECT / TOTAL # CHARACTER

La domanda che sorge spontanea…Dove potremmo ora calcolare il fitness? Se il DNA contiene le informazioni genetiche, possiamo scrivere la funzione all’interno della classe DNA, per registrare il valore del fitness. Prendiamo per esempio questa frase:

String target = “to be or not to be”;

Noi possiamo comparare ogni gene con il carattere corrispondente della frase target, incrementando un contatore ogni volta che troviamo un carattere corretto i.e. combaciante.

Nella sezione Draw(), il primo vero Step, sarà richiamare la funzione fitness per ogni membro della popolazione.

Dopo aver registrato tutti i valori di fitness, possiamo costruire il “mating pool” di cui abbiamo bisogno per lo step della riproduzione. Il mating pool è una struttura dati,in cui continueremo amettere due genitori. Recuperando la descrizione del processo di selezione, mettremo genitori con probabilità di riproduzione (valore di fitness) adeguato. In altre parole, i membro della popolazione con valore di fitness più alto, saranno con più probabilità, quelli ad essere selezionati per la riproduzione.  Nell’introduzione a questa serie dia rticoli, abbiamo definito le basi della probabilità e generato una distribuzione base di numeri causali. Ora, andremo ad utilizzare quella tecnica, per assegnare ad ogni membro della popolazione, la sua probabilità. Si veda l’immagine sotto della “ruota della fortuna :)”.

Esempio. Sceglieremo da 5 opzioni (ABCDE), in base alle loro probabilità riempiendo un ArrayList con più istanze di ciascun genitore. In altre parole, supponiamo che voi abbiate un secchio di lettere di legno: 30 A, 40 B, 5 C, 15 D e 10 Es.
Se scegliete una lettera a caso da quel secchio, c’è una probabilità del 30% di ottenere una A, una probabilità del 5% di ottenere una C e così via. Per noi, quel secchio è un ArrayList e ogni lettera di legno è un potenzialmente un genitore. Aggiungiamo ora ogni genitore all’ArrayList N per un numero di volte in cui N è uguale al suo punteggio percentuale. Quidi inseriremo 30 lettere A, 40 lettere B e così via.

Step 3. Riproduzione

Con il mating pool pronto per l’uso, è ora di fare dei “figli” 🙂 Il primo passo è scegliere due genitori. Ancora una volta, scegliere due genitori è in qualche modo una decisione arbitraria. Certamente rispecchia la riproduzione umana ed è il mezzo standard nel tradizionale GA, ma in termini di lavoro, qui non ci sono davvero restrizioni. Potreste scegliere di eseguire la riproduzione “asessuale” con un genitore o escogitare uno schema per scegliere tre o quattro genitori da cui generare il DNA del bambino. Per questa dimostrazione del codice, ci atterremo a due genitori e li chiameremo genitoreA e genitoreB.
La prima cosa di cui abbiamo bisogno sono due indici casuali nel pool di accoppiamento: numeri casuali compresi tra 0 e la dimensione di ArrayList.

int a = int (random(matingPool.get(a)));

int b = int (random(matingPool.get(b)));

Possiamo usare questi indici per recuperare un’istanza di DNA reale dal pool di accoppiamento.

DNA parentA = matingPool.get(a);

DNA parentB = matingPool.get(b);

Poiché abbiamo più istanze degli stessi oggetti DNA nel pool di accoppiamento (per non parlare del fatto che potremmo scegliere lo stesso numero casuale due volte), è possibile che genitoreA e genitoreB possano essere lo stesso oggetto DNA. Se volessimo essere severi, potremmo scrivere del codice per assicurarci di non aver scelto lo stesso genitore due volte, ma guadagneremmo pochissima efficienza per tutto quel codice extra. 

Una volta che abbiamo i due genitori, possiamo procedere con il crossover per generare il DNA del figlio, seguito dallo step mutazione.

Naturalmente, le funzioni crossover() e mutate() non esistono magicamente nella nostra classe DNA; dobbiamo scriverle. Il modo in cui abbiamo chiamato crossover() sopra indica che la funzione riceve un’istanza di DNA come argomento e restituisce una nuova istanza di DNA, il figlio.

La funzione di crossover di cui sopra utilizza il metodo di crossover “punto medio casuale”, in cui la prima sezione dei geni viene prelevata dal genitore A e la seconda sezione dal genitore B.

La funzione mutate() è ancora più semplice da scrivere rispetto a crossover(). Tutto quello che dobbiamo fare è scorrere l’array di geni e per ciascuno scegliere casualmente un nuovo carattere in base al tasso di mutazione. Con un tasso di mutazione dell’1%, ad esempio, sceglieremmo un nuovo personaggio una volta su cento.

L’intera funzione quindi diventa: