Tauon Barcadero

Posts Tagged ‘genetich algorythm

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;

};

Leggi il seguito di questo post »

Written by barcadero

3 marzo 2011 at 10:44 pm