Tauon Barcadero

Un semplice algoritmo genetico

with 2 comments


Cosa è un algoritmo genetico?

Un algoritmo genetico è, nella sua definizione più generica, un metodo di ricerca euristico di una soluzione a un dato problema usando tecniche che si ispirano a quelle della selezione naturale e dell’evoluzione darwiniane.

Si parte creando una popolazione di individui, ciascuno di questi rappresenta una soluzione al problema da risolvere codificata in una stringa, detta gene; nella prima generazione i geni vengono generati in modo casuale. A ogni iterazione dell’algoritmo si rimescolano i geni tra i vari individui e definita una funzione detta fitness(), che restituisce la bontà di un certo individuo, ovvero un valore numerico che misura la sua capacità di risolvere il dato problema, si selezionano ad ogni iterazione gli individui migliori ed i loro geni vengono mescolati a quelli di nuovi individui generati dalla funzione che si occupa del crossing-over, ovvero del rimescolamento casuale dei geni di individui già esistenti per crearne di nuovi. Questo procedimento porta, in genere, a ottenere un’individuo con valore di fitness molto alto e quindi capace di risolvere in modo “ottimizzato” il dato problema. Non trattandosi di un procedimento strettamente rigoroso non sempre questo succede, ma si tratta sicuramente di un metodo interessante e potente che rivela le sue capacità soprattutto nell’ottimizzazione per esempio delle interfacce grafiche, dei modelli che operano all’interno di simulazioni fisiche e naturalmente nella programmazione genetica.

Un problema semplice semplice da risolvere

Ora vediamo una mia implementazione in C++ di questo algoritmo per un problema banale come trovare 4 numeri compresi tra 0 e 10 che abbiano somma massima, si lo so, non serve una algoritmo genetico per capirlo, la combinazione giusta è 10 + 10 + 10 + 10 = 40, ma volete mettere il fatto di arrivarci in un modo completamente fuori dal comune?

L’implementazione

Per scarica l’intero sorgente fare click QUI.

Definiamo subito alcune costanti globali dentro a un namespace anonimo, in modo da limitarne la visibilità al solo file in questione:

namespace {
 const int GENE_DIM = 4;                //numero di geni
 const int POPULATION_DIM = 50;        //numero di individui della popolazione
 const int MAX_FITNESS = 40;         //fitness da raggiungere per fermare algoritmo
}

Iniziamo col definire una struttura C++ che rappresenti il singolo individuo:

struct Individuo {

int gene[ GENE_DIM ];

 //costruttore: azzera i geni
 Individuo();

 //assegna valori casuali a gene
 void ramdomize_gene();

 //funzione che misura la bontà di un individuo
 int fitness() const;

 //stampa il gene
 void print() const;

};

I commenti bastano per capire cosa fanno i vari metodi, in particolare quando si crea un Individuo si richiama il costruttore che inizializza a 0 i valori di gene.
La funzione randomize_gene() serve a inserire dei numeri casuali nel gene, verrà utilizzato per creare la prima generazione di individui.

Ora vediamo brevemente i prototipi delle funzioni utilizzate nel codice:

int crossOver( Individuo &parent1, Individuo &parent2, Individuo &child1, Individuo &child2 );
int naturalSelection( Individuo *pop, Individuo *next_pop );

int compareFitness( Individuo i, Individuo j );
int getMaxFitness( Individuo *pop );

int getRandNum( int l );
int order( Individuo *pop );

void swapPopulations( Individuo *pop, Individuo *next_pop );
void printPopulation( Individuo *pop );

Le funzioni più importanti sono crossOver() e naturalSelection(), le altre sono funzioni helper utilizzate per alleggerire la main() del programma.

  • crossOver(Individuo &parent1, Individuo &parent2, Individuo &child1, Individuo &child2): dati in ingresso i due oggetti Individuo parent1 e parent2, genera un numero casuale n compreso tra 1 e GENE_DIM-1, “taglia” i due geni delle strutture di partenza nel punto n dell’array; si ottengono così quattro sequenze di geni, le ultime due metà vengono scambiate tra i due individui, i nuovi individui così generati, con in geni provenienti dalla mescolanza di quelli dei genitori, vengono salvati in child1 e child2.
  • naturalSelection(Individuo *pop, Individuo *next_pop): dati in ingresso la popolazione attuale pop sotto forma di array di oggetti Individuo di dimensione POPULATION_DIM, e un array dello stesso tipo e dimensione next_pop che verrà azzerato, la funzione ordina in base al valore di fitness la popolazione attuale e salva subito i migliori POPULATION_DIM/2 in next_pop.

Diamo ora un’occhiata alla main del programma:

int main() {
 Individuo pop[ POPULATION_DIM ];    //popolazione
 Individuo next_pop[ POPULATION_DIM ];    //prossima popolazione
 int gen = 0;

 //assegna valori casuali del gene a ogni individuo della popolazione
 for( int s = 0; s < POPULATION_DIM; s++ ) pop[s].ramdomize_gene();

 int running = 1;
 while( running ) {

 //decommentare per vedere l'algoritmo in azione passo passo
 /*cout << "generazione " << gen;
 cin.get();
 printPopulation( pop );*/

 //si ferma se ha raggiunto un fitness sufficiente
 if( getMaxFitness( pop ) >= MAX_FITNESS ) {
 cout << "Generazione:   " << gen << endl;
 printPopulation( pop );

 running = 0;
 }
 naturalSelection(pop, next_pop);
 swapPopulations(pop, next_pop);

 gen++;

 }

 return 0;
}

Si parte creando due array di individui: pop e next_pop, il primo contiene la popolazione di una certa iterazione dell’algoritmo, mentre next_pop conterrà i nuovi individui che verranno creati e saranno i genitori nell’iterazione successiva.

All’inizio dell’algoritmo si inizializza la prima popolazione con valori casuali, di questo si occupa la funzione ramdomize_gene(), membre di ciascun individuo.

All’interno del ciclo principale del programma si controlla se è stato raggiunto il livello di fitness specificato in MAX_FITNESS da almeno uno degli individui della popolazione presente nell’attuale iterazione, in caso positivo stampa il numero della generazione e i geni degli individui che ne fanno parte, se il criterio di stop non è stato ancora soddisfatto vengono chiamate le funzioni naturalSelection(Individuo *pop, Individuo *next_pop) e swapPopulation(Individuo *pop, Individuo *next_pop); quest’ultima semplicemente copia in pop gli individui di next_pop, cosi facendo libera next_pop per la successiva iterazione.

Per scaricare l’intero sorgente fare click qui.

Written by barcadero

3 marzo 2011 a 10:44 pm

2 Risposte

Subscribe to comments with RSS.

  1. ciao volevo farti i complimenti per questo programma , e volevo chiederti se sei disponibile a darmi qualche informazione più dettagliata , siccome ho intenzione di utilizzarlo .. cordiali saluti Biagio

    Biagio

    14 dicembre 2012 at 4:13 pm

  2. Ciao volevo avere qualche informazione più dettagliata sul programma .. Grazie in anticipo

    Biagio

    18 dicembre 2012 at 5:53 pm


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: