<< La conservazione delle differenze e variazioni individuali favorevoli e la distruzione di quelle nocive sono state da me chiamate “selezione naturale” o “sopravvivenza del più adatto”. Le variazioni che non sono né utili né nocive non saranno influenzate dalla selezione naturale, e rimarranno allo stato di elementi fluttuanti, come si può osservare in certe specie polimorfe, o infine, si fisseranno, per cause dipendenti dalla natura dell’organismo e da quella delle condizioni >> (Charles Darwin, L’origine delle specie, 1859, p. 147)
Gli algoritmi genetici, d’ora in poi “ga”, costituiscono un sottoinsieme di metodi per risolvere problemi di ottimizzazione. L’ottimizzazione è sempre stato un problema complesso eseguito con grande fatica, utilizzando molte conoscenze facente parte di diversi settori. I ga operano una ricerca di un massimo o di un minimo globale in uno spazio finito sulla base di vincoli sullo spazio delle soluzioni.
A differenza degli algoritmi di ricerca più classici, che impiegano un approccio di tipo analitico, i ga si ispirano a una delle più eminenti teorie della biologia, l’evoluzione per selezione naturale, trasformando questa in un metodo di ricerca non lineare. Oltre a risolvere quei problemi di ottimizzazione per i quali un approccio procedurale è impossibile o troppo complesso, i GA possono produrre risultati competitivi anche per compiti normalmente affrontati nel modo classico.
L’origine delle specie di Charles Darwin (Shrewsbury, 12 febbraio 1809 – Londra, 19 aprile 1882) è un’opera pubblicata nel 1859. Si tratta di una tra le opere cardini nella storia scientifica, ed indubbiamente una delle più eminenti in biologia.
Pubblicata per la prima volta il 24 novembre dello stesso anno, in essa Darwin spiega con “una lunga argomentazione” la sua teoria, secondo cui “gruppi” di organismi di una stessa specie si evolvono gradualmente nel tempo attraverso il processo di selezione naturale, un meccanismo che venne illustrato per la prima volta ad un pubblico generico proprio grazie a questo libro. L’opera contiene dettagliate prove scientifiche che l’autore ebbe il tempo di accumulare sia durante il viaggio del HMS Beagle nel 1830 che al suo ritorno, preparando diligentemente la sua teoria e, contemporaneamente, rifiutando quella più in voga fino a quel tempo, il creazionismo, che ritiene le specie, essendo create da Dio, perfette ed immutabili.
Il libro risultò accessibile anche ai non specialisti, attraendo un grande interesse su vasta scala. Sebbene una parte della teoria sia ora supportata da schiaccianti dimostrazioni scientifiche, esistono ancora forti controversie, soprattutto tra i sostenitori del creazionismo, i quali ritengono che questa teoria contraddica le interpretazioni letterali di vari testi religiosi.
La teoria dell’evoluzione di Darwin si basa su 5 osservazioni-chiave e sulle conclusioni che se ne traggono, come riassunto dal biologo Ernst Mayr (Kempten, 5 luglio 1904 – Bedford, 3 febbraio 2005):
- le specie sono dotate di una grande fertilità e producono numerosi discendenti che possono raggiungere lo stadio adulto.
- le popolazioni rimangono grosso modo delle stesse dimensioni, con modeste fluttuazioni.
- le risorse di cibo sono limitate, ma relativamente costanti per la maggior parte del tempo. Da queste prime tre osservazioni è possibile dedurre che verosimilmente in ogni ambiente ci sarà tra gli individui una lotta per la sopravvivenza.
- con la riproduzione sessuale generalmente non vengono prodotti due individui identici. La variazione è abbondante.
- gran parte di questa variazione è ereditabile.
Per queste ragioni Darwin afferma che: in un mondo di popolazioni stabili, dove ogni individuo deve lottare per sopravvivere, quelli con le “migliori” caratteristiche avranno maggiori possibilità di sopravvivenza e così di trasmettere quei tratti favorevoli ai loro discendenti. Col trascorrere delle generazioni, le caratteristiche vantaggiose diverranno dominanti nella popolazione. Questa è la selezione naturale.
John Henry Holland, nato il 2 Febbraio del 1929, è l’ideatore dei ga. Il primo che pensò di sfruttare la logica dell’evoluzione naturale nel campo dell’informatica.
<< Computer programs that “evolve” in ways that resemble natural selection can solve complex problems even their creators do not fully understand >>. (J. Holland)
Vediamo come Holland è riuscito a “trasporre” la teoria di Darwin;
Oltre al punto di vista “epistemologico” della selezione naturale anche la genetica partecipa a delineare la metodologia dei ga. Il termine “gene” è fondamentale. Che cosa è un gene?
Il gene è l’unità ereditaria fondamentale degli organismi viventi.
I geni corrispondono a porzioni di codice genetico localizzate in precise posizioni all’interno della sequenza (DNA o, più raramente, di RNA) e contengono tutte le informazioni necessarie per la produzione di una proteina. Essi sono contenuti ed organizzati all’interno dei cromosomi, presenti in tutte le cellule di un organismo.
La definizione di gene presenta diverse accezioni a seconda che si considerino organismi procarioti ed eucarioti: nei primi il gene è costituito esclusivamente da sequenze codificanti, negli altri anche da sequenze non codificanti. Noi però trascureremo questi aspetti nella nostra trattazione, ci rifaremo sempre a gene come una sequenza di codice genetico.
L’insieme di tutti i geni costituisce il codice genetico di un organismo e viene denominato genotipo.
Ogni gene, singolarmente e/o in modo cooperativo, contribuisce in maniera diversa allo sviluppo, alla fisiologia e al mantenimento funzionale dell’organismo. L’insieme dei caratteri osservabili viene chiamato fenotipo. Il genotipo, da solo, non definisce il fenotipo, piuttosto interagisce con l’ambiente (esterno o interno) nel determinarlo. Quindi due individui con stesso genotipo (ad esempio gemelli monozigoti) non necessariamente hanno un fenotipo identico: ciò può essere spiegato attraverso i meccanismi dell’epigenetica, ossia quell’ attività di regolazione genica che, attraverso processi chimici, pur non alterando direttamente la sequenza nucleotidica, può modificare il fenotipo dell’individuo o della progenie. Questi fenomeni epigenetici alterano l’accessibilità fisica al genoma da parte di complessi molecolari deputati all’espressione genica e quindi alterano il funzionamento dei geni.
Il termine fenotipo corrisponde all’insieme di tutte le caratteristiche osservabili di un organismo vivente, quindi la sua morfologia, il suo sviluppo, le sue proprietà biochimiche e fisiologiche comprensive del comportamento. Nel caso poi si parli di oggetti la cui esistenza è una conseguenza del comportamento, nel caso dell’uomo la società e i suoi prodotti, si parla di “fenotipo esteso”, (Richard Dawkins, “The Extended Phenotype. The Gene as the Unit of Selection”, 1982) il quale influisce sul genotipo, attivando o disattivando geni.
Abbiamo dunque introdotto una relazione importante: genotipo <-> fenotipo. Dove il primo codifica il secondo e questo può influenzare il primo nel tempo. Questo meccanismo permette l’evoluzione costante di un organismo, selezionando le sue caratteristiche in base alla loro utilità ai fini della sopravvivenza.
I problemi che normalmente si affrontano e si risolvono con i computer e con il software sono problemi “polinomiali”. Tutti quei problemi per i quali il tempo impiegato anche dal miglior algoritmo cresce troppo velocemente rispetto al numero delle variabili in gioco, o al loro quadrato, al loro cubo, ecc., risultano impossibili da risolvere in un tempo ragionevole, tali problemi sono chiamati di tipo “N-P“, non polinomiali. Questo perché la complessità dell’algoritmo non cresce in modo polinomiale rispetto alle variabili in ingresso, ma ben più velocemente.
Facciamo un esempio, ammettiamo che ci venga assegnato un lavoro che prevede la stesura dell’orario scolastico di una grande scuola composta da molte classi, e decine di professori. Ci viene raccomandato inoltre che l’orario deve tenere conto del sovraccarico delle lezioni sugli alunni, in altre parole, è bene evitare di sistemare ore di lezioni troppo impegnative o troppo simili una di seguito all’altra. Ad esempio, non sistemare due ore di matematica subito dopo o subito prima due ore di chimica, oppure non collocare ore di educazione fisica prima di lezioni che pretendono un alto livello di attenzione. Naturalmente il tutto deve funzionare in modo tale che i professori non abbiano ore di lezione nello stesso momento e pause adeguate tra una lezione e l’altra.
Formalizzando il nostro lavoro, ci ritroviamo con i seguenti dati: le 6 ore fornite da ciascun professore, il numero di classi e i vincoli che ci sono stati dati dal datore di lavoro.
Anche solo a livello concettuale è difficile trovare un sistema risolutivo, avremmo la tentazione di scrivere uno schema a blocchi formato da un solo blocco che chiameremo “ottimisticamente” risolutore, con in output la nostra tabella degli orari.
In realtà, contemplando una ricerca iterativa del problema, creeremmo probabilmente dei cicli prima sui professori, poi sulle classi, poi verificheremmo i vincoli, il tutto intriso di asserzioni che verifichino che non vengano commesse assurdità come la sovrapposizione di ore di lezione nello stesso momento.
Se a livello concettuale tutto questo può avere un senso, a livello applicativo, comporterebbe un enorme impiego di tempo ed energia data la complessità delle interazioni fra variabili.
Quella che abbiamo definito è una ricerca dell’orario in modo iterativo, controllando i casi uno ad uno. Ogni caso corrisponde ad una combinazione differente delle variabili in input.
Per risolvere questo tipo di problemi di ottimizzazione combinatoria è più conveniente utilizzare algoritmi non lineari, di norma si usano metodi di approssimazione della migliore soluzione che si basano sul concetto di probabilità.
Sembra paradossale, ma in questi casi la miglior soluzione sembra sia estrarre casualmente una combinazione degli input dall’insieme di tutte le combinazioni possibili e provarla, se non soddisfacente scartarla e proseguire, così fino alla scoperta di una soluzione accettabile.
La seleziona naturale è questo, ed è così che i ga lavorano, operando sull’insieme di tutte le combinazioni o soluzioni e scegliendo euristicamente un insieme di elementi con successo più probabile rispetto le altre.
L’architettura di un ga prende in considerazione diversi concetti legati dalla biologia adattandoli:
GENOTIPO:
(Biologia) Si riferisce all’insieme di geni che compongono il DNA di un organismo o di una popolazione. Ogni gene, singolarmente e/o in modo cooperativo, contribuisce in maniera diversa allo sviluppo, alla fisiologia e al mantenimento funzionale dell’organismo. Il genotipo, da solo, non definisce il fenotipo, piuttosto interagisce con l’ambiente (esterno o interno) nel determinarlo.
(Informatica) Si riferisce alla codifica diretta o indiretta del fenotipo. Non ci sono limiti alla complessità con la quale esso, il fenotipo, può essere codificato. Ad ogni modo, spesso si ricorre ad una codifica diretta.
FENOTIPO:
(Biologia) Si intende l’insieme di tutte le caratteristiche osservabili di un organismo vivente, quindi la sua morfologia, il suo sviluppo, le sue proprietà biochimiche e fisiologiche comprensive del comportamento.
(Informatica) Corrisponde alle caratteristiche peculiari di un sistema risolutivo. Può essere anche inteso come parametri dell’algoritmo risolutivo. (per esempio un’equazione parametrizzata)
FITNESS:
(Biologia) Corrisponde al successo riproduttivo di un individuo o di un certo genotipo. Quando due o più assortimenti di caratteri ereditari conferiscono ai rispettivi organismi un diverso successo riproduttivo, allora si dice che presentano una fitness diversa. La fitness si misura per mezzo del successo riproduttivo, cioè dal numero medio dei figli in grado, a loro volta, di riprodursi.
(Informatica) Corrisponde per lo più al successo del sistema risolutivo rispetto al problema. Più l’algoritmo si è avvicinato al risultato desiderato più il suo valore di fitness sarà alto. Solitamente la fitness è calcolata in rapporto alla precisione e all’efficienza dell’algoritmo.
POPOLAZIONE:
(Biologia) E’ un insieme di organismi o individui che coesistono in uno stesso spazio e tempo, condividendo certe proprietà biologiche (fondamentalmente con esseri della stessa specie), le quali producono un’alta coesione riproduttiva ed ecologica del gruppo. In biologia, un significato speciale della popolazione, impiegato nella genetica ed evoluzione è quello che definisce un gruppo riproduttivo i cui individui si incrociano unicamente fra loro, sebbene biologicamente sarebbe loro possibile riprodursi anche con tutti gli altri membri della specie o sottospecie. Le principali cause per cui le popolazioni risultano delimitate sono l’isolamento fisico e le differenze del comportamento.
(Informatica) Rappresenta un insieme di genotipi simili ma non uguali. In base al sistema riproduttivo, solitamente quelli con fitness più alta vengono selezionati per la riproduzione e andranno a costituire parte della popolazione della generazione successiva. Questa definizione cambia però a seconda del tipo di operatore di riproduzione che viene utilizzato.
CROSSOVER:
(Biologia) Inteso come incrocio di materiale genetico che si attua durante la riproduzione. Il codice genetico dei genitori viene perciò incrociato in uno o più punti.
(Informatica) Incrocio di materiale genetico fra il codice di due elementi preesistenti nella popolazione. I tipi di crossover variano a seconda dell’implementazione e dagli obiettivi per meglio adattarsi al tipo di fenotipo codificato. Si tratta in ogni caso di uno scambio di materiale genetico in punti decisi in modo aleatorio o secondo un criterio spesso di tipo fuzzy.
MUTAZIONE:
(Biologia) si intende ogni modifica stabile ed ereditabile nella sequenza nucleotidica di un genoma o più generalmente di materiale genetico (sia DNA che RNA) dovuta ad agenti esterni o al caso, ma non alla ricombinazione genetica. Una mutazione modifica quindi il genotipo di un individuo e può eventualmente modificarne il fenotipo a seconda delle sue caratteristiche e delle interazioni con l’ambiente.
(Informatica) Si intende la modifica casuale di una parte del codice del genotipo e, di conseguenza, anche del fenotipo. Questa procedura assicura l’introduzione di un fattore casuale nel procedere dell’algoritmo, dunque contribuisce ad aumentare l’area di ricerca nello spazio delle soluzioni.
In genere, un algoritmo genetico prevede i seguenti passi:
1. Generazione pseudo-casuale di una popolazione.
2. Valutazione della fitness di ogni gene.
3. In base alla fitness calcolata si sceglie, secondo una strategia, le coppie di geni destinate all’accoppiamento.
4. Si procede all’incrocio delle sequenze genetiche dei genitori. Per ogni figlio generato esiste una probabilità che il codice genetico muti.
5. I figli generati, sostituiscono o compensano quelli dei genitori a formare la nuova popolazione. Si ripete l’accoppiamento fino ad ottenere un gene con una fitness soddisfacente. (si ripete dal punto 2)
1] Dato il problema da risolvere, dobbiamo cercare un buon compromesso per formalizzare la struttura di una soluzione. Ad esempio, nel caso dell’orario scolastico, abbiamo detto che la combinazione degli input, ovvero ore, classi e vincoli rappresentava già di per se lo schema risolutivo.
Altre volte è necessario invece pensare un algoritmo generale dove a variare saranno dei parametri che ne decideranno il comportamento. Questi parametri rappresentano il fenotipo. Mentre la loro codifica costituisce il genotipo. Questo deve essere adatto per essere manipolato come una stringa binaria o una stringa composta da numeri reali. Come vedremo, operatori come il crossover devono essere in grado di manipolarla.
Spesso si ricorre a stringhe binarie, dove il valore di ciascun bit rappresenta una caratteristica “presente o meno” nel fenotipo, quindi nell’algoritmo di risoluzione. Nel caso di stringe binarie i valori possibili che compongono i genotipi saranno limitati a due, 0 e 1. Non presenza e presenza rispettivamente della caratteristica nel fenotipo.
Altre volte si ricorre a codifiche con numeri reali, per esempio il valore di coefficienti di equazioni. Il fatto interessante è che non esistono limiti per ideare tipi di codifiche, dirette o indirette che siano, l’importante è poi saper implementare operatori genetici in grado di lavorare con essi.
Per prima cosa, si inizializza una popolazione componendola di genotipi, solitamente è bene farlo in modo casuale in modo da iniziare la ricerca da punti disposti nello spazio in modo uniforme. Se volessimo rappresentare questo spazio di ricerca potremmo pensarlo in questo modo:
Figura 1: Rappresentazione grafica dello spazio delle possibili soluzioni algoritmiche
2] viene poi valutata la fitness per ogni genotipo.
La funzione adibita al calcolo di questo valore esegue:
1 decodifica il genotipo in fenotipo,
2 applica il fenotipo, ovvero i parametri per la risoluzione del problema,
3 raccoglierà i risultati ottenuti che corrisponderanno al valore di fitness.
Figura 2: Calcolo della fitness
L’implementazione della funzione di fitness dipenderà dal tipo di problema da risolvere.
3] All’atto della riproduzione il valore della fitness viene assegnato ad ogni genotipo. Vengono selezionati gli elementi più adatti e scartati il resto.
Vi sono molti modi per implementare il metodo di selezione. Quella denominata “probabilistica”, è il metodo più diffuso, e utilizza un approccio denominato “la ruota della fortuna truccata”. Il metodo è il seguente: consideriamo il caso comune dove la popolazione rimane di dimensione costante ad ogni generazione, essa viene ogni volta rimpiazzata completamente dai nuovi geni. La ruota della fortuna ha tante caselle quanti sono i geni del genotipo (elementi della stringa), ma la dimensione di ogni casella sarà proporzionale al valore di fitness di ogni gene. La riproduzione selettiva consiste nel far girare la ruota tante volte quante sono gli individui da generare e nel creare ogni volta una coppia della stringa corrispondente alla casella in cui si ferma la pallina.
Formalmente, ogni gene avrà il proprio valore di fitness ‘f’:
Questo valore viene utilizzato per calcolare la probabilità “P” del gene di essere selezionato per la riproduzione. (Questa probabilità corrisponde all’ampiezza della casella della ruota della fortuna). Dunque la probabilità viene estratta da una normalizzazione di tutti i valori:
Questo significa che i genotipi dei genitori vengono selezionati semplicemente scegliendoli in base alla loro idoneità. Questo viene fatto prima ordinando i genomi per il loro valore di fitness, poi scegliendone un certo numero, partendo dall’alto. Solitamente si applica un tasso. Ad esempio un tasso di elitismo pari a 0.1 selezionerà il 10% della popolazione partendo dal più adatto.
Molto spesso l’elitismo è aggiunto ad altri sistemi di selezione.
4] Una volta selezionata la popolazione che costituirà l’insieme dei “genitori”, si procede all’incrocio dei loro genotipi per formare i genotipi figlio. A seconda del tipo di codifica dovremo implementare un operatore di crossover che scambi in uno o più punti il materiale genetico dei genitori. Supponiamo di aver codificato i fenotipi in stringhe binarie o reali, l’operatore crossover che opera su un punto delle stringhe eseguirà il lavoro seguente:
Figura 3: Crossover su un punto
Soprattutto quando il codice genetico è lungo, può risultare più utile, aumentare la variazione utilizzando un “doppio crossover”.
Il procedimento avviene come per l’incrocio singolo ma in questo caso vengono scelti due punti,
Figura 4: Crossover su due punti
Quando il genoma è molto lungo l’incrocio comincia a divenire contro producente. Infatti questo tenderà ad interrompere gli schemi favorevoli, ad esempio sempre utilizzando stringhe binarie, lo schema: 00110011#####111, dove ‘#’ indica i bit non corretti per la soluzione, (quindi di cui non ci interessa il valore) può venire facilmente interrotto nei primi punti dall’operatore crossover.
I tipi di crossover possono essere vari. Il programmatore dovrà scegliere l’implementazione più opportuna. In molti casi si utilizza la distanza di Hamming, o una delle sue varianti, per calcolare un certo fattore di diversità genica tra i genotipi, poi questo viene utilizzato per determinare in quanti punti l’operatore di crossover lavorerà.
Oltre l’operatore di crossover un’altra importante operazione partecipa attivamente al processo di riproduzione della popolazione, la mutazione.
Infatti, per ogni nuova sequenza genica esiste una probabilità che il suo codice muti. Nel caso di stringhe binarie, spesso si esegue uno scambio di posizione di due elementi della stringa:
Figura 5: Mutazione stringa binaria
5] La riproduzione prosegue fino a quando non si giunge alla completa ricostituzione della popolazione.
Se tra le nuove soluzioni risultanti ne emerge almeno una che soddisfa i requisiti richiesti (verificato attraverso la funzione di fitness) l’algoritmo termina altrimenti si procede ad una nuova riproduzione.
Nell’ambito dell’intelligenza artificiale, i ga trovano applicazione quando occorre addestrare classificatori neurali che lavorano su problemi che si presentano come funzioni con punti di discontinuità. Sfruttando le caratteristiche di un linguaggio “OO” come il C++ possiamo delineare 2 classi in grado di lavorare con stringhe composte da numeri reali. Nel mio caso ho preferito implementare una classe “gene” ed una classe “popolazione”. La seconda incapsula un array di elementi “gene” ed in più fornisce i metodi necessari per il processo di evoluzione.
La definizione delle due classi:
/********************************************************************
* libsann - Artificial neural networks library
* Designed to be reliable and cross-platform.
* C++ 11
*
* Author: Matteo Tosato - tosatz{at}tiscali{dot}it
* 2013
* Version: 0.1
*
* Section genetic algorithms:
* consist of a efficient methods for optimization problems, act
* as support for learning systems.
********************************************************************/
#include "libsann.h"
namespace ga
{
enum crossover_mode { SINGLE_POINT, POINTS_PAIR, HAMMING };
#pragma region Definitions
template<typename T>
class geneBase
{
public:
geneBase();
geneBase(uint len, double mrate = 0);
geneBase(geneBase& other);
// set, get and edit code
vector<T>* GetCode();
void SetCode(vector<T> *_code);
// Operators
bool operator<(geneBase b) { return(fitness < b.GetFitness()); }
geneBase& operator=(const geneBase& obj);
geneBase& operator+(const geneBase& obj);
geneBase& operator-(const geneBase& obj);
geneBase& operator+=(const geneBase& obj);
geneBase& operator-=(const geneBase& obj);
geneBase<bool>& operator+(geneBase<bool>& obj);
geneBase<bool>& operator-(geneBase<bool>& obj);
geneBase<bool>& operator+=(geneBase<bool>& obj);
geneBase<bool>& operator-=(geneBase<bool>& obj);
// Mutation
virtual void mutation();
// Access methods
inline double GetMutationRate() { return mate_rate; }
inline void SetMutationRate(double value) { mutation_rate = value; }
inline double GetFitness() { return fitness; }
inline void SetFitness(double value) { fitness = value; }
// Properties
inline uint lenght() { return code.size(); }
// Hamming distance
static double HammingDistance(geneBase<T>& a, geneBase<T>& b);
// Crossover
static geneBase *crossover(
geneBase<T>& a, geneBase<T>& b, crossover_mode m = crossover_mode::HAMMING, double mH = 0
);
protected:
// The code of gene
vector<T> code;
// The fitness value
double fitness;
// Mutation rate
double mutation_rate;
};
template <typename T>
class populationBase
{
public:
populationBase(double mrate = 0.05, double elitism_r = 0.1);
populationBase(uint size, uint len, double mrate = 0.05, double elitism_r = 0.1); // Auto-initialize population
populationBase(vector<geneBase<T>> _pop, double mrate = 0.05, double elitism_r = 0.1);
populationBase(populationBase& obj);
// Operators
populationBase operator=(populationBase& obj);
populationBase operator+(populationBase& obj);
void join(const populationBase& obj);
// Mate method
void mate(crossover_mode mode = crossover_mode::HAMMING);
// Genetic drift
void BlockgeneticDrift();
// Properties
inline double GetMeanHammingDistance() { return MeanHammingDistance; }
inline uint Size() { return population.size(); }
geneBase<T> BestGene();
// Access methods
vector<geneBase<T>> *PopulationPtr();
geneBase<T> *At(uint index);
protected:
// Population
vector<geneBase<T>> population;
// Maximum Hamming distance
double MeanHammingDistance;
// Elitism rate
double elitism_rate;
// Default mutation rate
double mutation_rate;
uint RunRouletteWheel(double random_fit, double total_fit);
};
#pragma endregion
...
In particolare gli operatori di crossover:
...
#pragma region Crossover
template <typename T>
geneBase<T> *geneBase<T>::crossover(geneBase<T>& a, geneBase<T>& b, crossover_mode m, double mH)
{
_ASSERT(a.GetCode()->size() == b.GetCode()->size());
geneBase<T> *child = new geneBase<T>();
vector<T> seq;
uint p = 0;
switch(m)
{
case crossover_mode::HAMMING:
{
_ASSERT(mH != 0);
// Number of values to swap
int np = int(-log(mH / (double)a.GetCode()->size()) * (double)a.GetCode()->size());
if(np == 0)
np = 1;
else if(np >= int(a.GetCode()->size()))
np = a.GetCode()->size() - 1;
// Copy gene A
seq.assign(a.GetCode()->begin(), a.GetCode()->end());
// Collects 'np' random points
vector<int> ps;
for(int i = 0; i < np; i++)
ps.push_back(rand() % a.GetCode()->size());
for(uint i = 0; i < ps.size(); i++)
seq.at(ps.at(i)) = b.GetCode()->at(ps.at(i));
break;
}
case crossover_mode::SINGLE_POINT:
{
uint pos = rand() % a.GetCode()->size(); // cross position
for(; p < pos; p++)
{
seq.push_back(a.GetCode()->at(p));
}
for(; p < a.GetCode()->size(); p++)
{
seq.push_back(b.GetCode()->at(p));
}
break;
}
case crossover_mode::POINTS_PAIR:
{
uint p2 = rand() % a.GetCode()->size(); // 2nd cross position
uint p1 = rand() % a.GetCode()->size(); // 1nd cross position
uint temp;
if(p2 < p1)
{
temp = p1;
p1 = p2;
p2 = temp;
}
for(; p < p1; p++)
{
seq.push_back(a.GetCode()->at(p));
}
for(; p < p2; p++)
{
seq.push_back(b.GetCode()->at(p));
}
for(; p < a.GetCode()->size(); p++)
{
seq.push_back(a.GetCode()->at(p));
}
break;
}
}
child->SetCode(&seq);
return child;
}
#pragma endregion
...
L’operatore crossover che utilizza la distanza di Hamming necessita di altre routines.
In informatica viene detta distanza di Hamming fra due stringhe binarie di ugual lunghezza il numero di posizioni nelle quali i simboli sono diversi. In altre parole, tale distanza misura il numero di sostituzioni necessarie per convertire una stringa nell’altra. Ad esempio, la distanza di Hamming tra 1011101 e 1001001 è 2.
Nel codice è presente una specializzazione per il typename double dove ho modificato tale definizione, introducendo un parametro di tolleranza sulla differenza, in questo modo il parametro di diversità che si ottiene impiegando Hamming è più elastico e da migliori risultati negli algoritmi di addestramento per reti neurali che utilizzano i ga.
...
#pragma region Hamming distance
/*
* In information theory, the Hamming distance between two strings of equal length is the number
* of positions at which the corresponding symbols are different.
* In another way, it measures the minimum number of substitutions required to change one string
* into the other, or the minimum number of errors that could have transformed one string into the other.
*/
template <typename T>
double geneBase<T>::HammingDistance(geneBase<T>& a, geneBase<T>& b)
{
_ASSERT(a.GetCode()->size() == b.GetCode()->size());
double H = 0;
for(uint i = 0; i < a.GetCode()->size(); i++)
{
if(a.GetCode()->at(i) != b.GetCode()->at(i))
H++;
}
return H;
}
double geneBase<double>::HammingDistance(geneBase<double>& a, geneBase<double>& b)
{
_ASSERT(a.GetCode()->size() == b.GetCode()->size());
double H = 0;
for(uint i = 0; i < a.GetCode()->size(); i++)
{
if((a.GetCode()->at(i) - b.GetCode()->at(i)) > 0.1)
H++;
}
return H;
}
#pragma endregion
...
Nella classe “popolazione”, la routine principale è “mate()”. Responsabile del processo di replicazione:
...
#pragma region Mate
template <typename T>
void populationBase<T>::mate(crossover_mode mode)
{
// Initilize a new genes vector
vector<geneBase<T>> *population_new = new vector<geneBase<T>>();
uint pop_amount = population.size();
// Sorting by fitness
std::sort(population.begin(), population.end());
// If crossover mode is Hamming, computes the average of Hamming distances
if(mode == crossover_mode::HAMMING)
{
double hm = 0;
double c = 0;
for(uint f = 0; f < population.size() - 1; f++)
{
for(uint s = f+1; s < population.size(); s++)
{
hm += geneBase<T>::HammingDistance(population.at(f),population.at(s));
c++;
}
}
MeanHammingDistance = hm/c;
}
else
{
MeanHammingDistance = 0; // Not used
}
// Apply elitism, to creates the parents population
uint elitism_quote = (uint)(elitism_rate * (double)population.size());
for(uint i = 0; i < elitism_quote; i++)
{
population_new->push_back(population.at(population.size() - 1 - i));
vector<geneBase<T>>::iterator it;
it = population.begin();
population.erase(it + (population.size() - 1));
}
random_shuffle(population_new->begin(), population_new->end());
uint elitism_size = population_new->size();
// Mates selected parents
uint i1;
for(uint i = 0; i < elitism_size - 1; i += 2)
{
if((i + 1) == elitism_size)
{
i1 = 0;
}
else
{
i1 = i + 1;
}
// Generation
geneBase<T> *n = geneBase<T>::crossover(
population_new->at(i),
population_new->at(i1),
mode, MeanHammingDistance, pop_amount
);
// Set parameters
n->SetMutationRate(mutation_rate);
// Mutation
n->mutation();
// Add to population
population_new->push_back(*n);
// Delete temporary gene
delete n;
}
double total_fitness = 0;
for(uint i = 0; i < population.size(); i++)
total_fitness += population.at(i).GetFitness();
// Mates population
for(uint i = population_new->size(); i < pop_amount; i++)
{
// Generation
geneBase<T> *n = geneBase<T>::crossover(
population.at(RunRouletteWheel(((double)rand()*(total_fitness)/(double)RAND_MAX), total_fitness)),
population.at(RunRouletteWheel(((double)rand()*(total_fitness)/(double)RAND_MAX), total_fitness)),
mode, MeanHammingDistance, pop_amount
);
// Set parameters
n->SetMutationRate(mutation_rate);
/// Mutation
n->mutation();
// Add to population
population_new->push_back(*n);
// Delete temporary gene
delete n;
}
// Replace population
population = move(*population_new);
}
template <typename T>
uint populationBase<T>::RunRouletteWheel(double random_fit, double total_fit)
{
double c_f = 0;
for(uint i = 0; population.size(); i++)
{
c_f += population.at(i).GetFitness();
if(random_fit <= c_f)
return i;
}
return 0;
}
template <typename T>
void populationBase<T>::BlockgeneticDrift()
{
std::sort(population.begin(), population.end());
// Replaces 1/4 of the entire population
uint new_dimension = population.size() / 4;
vector<geneBase<T>>::iterator it;
for(uint i = 0; i < new_dimension; i++)
{
it = population.begin();
// Erase
population.erase(it);
// New random
population.push_back(geneBase<T>(population.at(0).GetCode()->size(),mutation_rate));
}
}
#pragma endregion
...
In questa routine vengono eseguiti la maggior parte dei passaggi sopra descritti.
In questo breve articolo ho cercato di fare una veloce introduzione agli algoritmi genetici sia dal punto di vista teorico che pratico. Per quanto riguarda il codice sorgente, ho riportato le routines chiave per farsi un’idea di come possono essere impostate le strutture dati che implementano questo tipo di tecnologia.-
Per altre informazioni inerenti all’implementazione potete scrivermi. La mia esperienza con i ga si è limitata al loro impiego negli algoritmi di addestramento per reti neurali nei linguaggi C/C++ e C#.
Bibliografia:
1 – Charles Darwin, L’origine delle specie – 1859
2 – Richard Dawkins, Il gene egoista – 1976
3 – Ernest Mayr, Storia del pensiero biologico – 1982
4 – John Henry Holland, Adaptation in Natural and Artificial Systems – 1975
5 – David Vandevoorde, Nicolai M. Josuttis, C++ Templates: The Complete Guide – 2002
6 – Dolores Barrios Alberto Carrascal, Daniel Manrique Juan Rıos, Cooperative binary-real coded genetic algorithms for generating and adapting artificial neural networks – 2003
7 – Mitchell Melanie, An introduction to Genetic Algorithms, MIT Press – 1999
Pacman
Nostradamus
Magical Cat Adventure
Snake