Algoritmi genetici – Introduzione ed esempi in Matlab

Un algoritmo genetico è un metodo di ricerca globale e stocastico basato sulla metafora dell’evoluzione biologica. Gli Algoritmi Genetici (GA) operano su una popolazione di potenziali soluzioni applicando il principio della sopravvivenza del migliore, evolvendo verso una soluzione che si spera si avvicini quanto più possibile alla reale soluzione del problema.
Ad ogni generazione, un nuovo insieme di soluzioni è creato dal processo di selezione che, basandosi sul livello di adeguatezza (Fitness), seleziona i migliori membri della popolazione e li fa evolvere utilizzando una serie di operatori genetici mutuati dalla genetica naturale. Questo processo porta ad una evoluzione robusta verso individui che meglio si adattano all’ambiente, in altre parole, all’insieme di soluzioni che meglio rispondono al problema posto in principio.
Ogni individuo della popolazione, (o ogni soluzione che dir si voglia) è codificato sotto forma di stringa, detta Cromosoma. Il sistema di codifica più utilizzato è il sistema binario. Ogni soluzione è quindi rappresentata (codificata) come una stringa di 0 ed 1. Ad esempio, una soluzione di un problema a 2 variabili può essere rappresentata come:

0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 1

Dove le prime 10 cifre codificano la prima variabile e le seconde 10 codificano la seconda.
Ogni soluzione, possiede una Fitness, ovvero una misura di quanto la soluzione è in grado di rispondere al problema posto.
Cosi come nella natura solamente gli individui che meglio si adattano all’ambiente sono in grado di sopravvivere e di riprodursi, anche negli algoritmi genetici le soluzioni migliori sono quelle che hanno la maggiore probabilità di trasmettere i propri geni alle generazioni future. Individui con fitness elevata (rispetto alla fitness media della popolazione) probabilmente verranno selezionati come genitori per la futura generazione di soluzioni. Dopo aver selezionato un numero n di individui, l’algoritmo genetico emula la riproduzione sessuata che avviene in natura e ri-combina il materiale genetico dei genitori, dando vita ai figli, ovvero alla futura generazione di soluzioni. La ri-combinazione avviene tramite operatori genetici di Cross Over e Mutazione Puntuale.
La nuova generazione di soluzioni prende il posto della generazione precedente, dalla quale è nata per ri-combinazione.
Il processo viene reiterato per un numero x di volte fino a quando o si raggiunge una approssimazione accettabile della soluzione al problema o si raggiunge il numero massimo di iterazioni prefissato.
Schematizzando, gli elementi costitutivi di un algoritmo genetico sono:

  • Popolazione
    Costituita da un numero n di individui. Ogni individuo rappresenta una possibile soluzione al problema.
  • Funzione Fitness
    La funzione di Fitness è una funzione in grado di valutare quanto una soluzione è adatta a risolvere il problema dato. Ad ogni soluzione corrisponde quindi un valore di fitness.
  • Principio di selezione
    Il principio di selezione ha il compito di selezionare gli individui della popolazione (le soluzioni) che meglio rispondono al problema da risolvere. La selezione si basa sulla fitness degli individui; le soluzioni con fitness maggiore (rispetto alla media della popolazione) avranno maggiori possibilità di partecipare alla riproduzione e quindi di trasmettere alle future generazioni i propri geni.
  • Operatori genetici
    Prendendo spunto dalla biologia, gli operatori genetici combinano i geni delle diverse soluzioni al fine di esplorare nuove soluzioni. Una volta che un gruppo di soluzioni viene individuato come idoneo alla riproduzione, l’operatore genetico di cross over, emulando la riproduzione sessuata degli esseri viventi, combina i geni dei genitori e formula una nuova generazione di soluzioni. Un altro operatore genetico largamente utilizzato è la Mutazione puntuale. La mutazione puntuale agisce direttamente sui figli, andando a modificare un gene a caso.

Ecco uno schema che spiega in sintesi il funzionamento di un algoritmo genetico:

Schema algoritmi genetici base

Di seguito, un esempio di un algoritmo genetico base implementato in Matlab. Il problema è la minimizzazione della funzione di De Jong:

minimizzare funzione De Jong

Il minimo di questa funzione si ottiene per x=0.
Ecco il listato del programma per Matlab:

NIND = 10;
% Numero di individui

MAXGEN = 1000;
% Numero di generazioni (iterazioni)

NVAR = 20;
% numero di variabili

PRECI = 20;
% Bit utilizzati er decrivere ciascuna variabile, PRECISIONE

GGAP = 0.9;
% Quanti individui vengono sostituiti da nuovi
% individui ad ogni iterazione

FieldD = [rep([PRECI],[1,NVAR]);...
rep([-512;512],[1,NVAR]); rep([1;0;1;1],[1,NVAR])];
% Field Descriptor, ovvero indichiamo che il nostro cromosoma
% è costituito da 20 variabili, rappresentate
% da 20 bit, che possono assumere valori da
% -512 a 512 codificate
% in Gray code.

Chrom = crtbp(NIND, NVAR*PRECI);
% Costruzione del cromosoma, ovvero
% una matrice di righe = NIND (Numero INDividui)
% e colonne = NVAR * PRECI (Numero VARiabili * PRECIsione)

gen = 1;
% Contatore generazioni

ObjV = objfun1(bs2rv(Chrom,FieldD));
% Codifico il Fenotipo corrispondente al Genotipo, sulla base del
% descrittore FieldD
% Dopodichè lo invio alla Funzione oggettiva,
% che nel nostro caso è rappresentata
% dalla fuznione De Jong. Restituisce un vettore colonna
% con il valore obbiettivo
% corrispondente ad ogni individuo

while gen < MAXGEN,

FitnV = ranking(ObjV);
% Calcola il valore di fitness sulla base dei valori obbiettivi.
% Restituisce un vettore colonna contenente i
% valori di fitness di ogni individuo.
% La fitness assume valori da 0 a 2.
% La funzione ranking assume
% che la funzione oggettva sia da MINIMIZZARE

minobjv(gen) = min(ObjV);
totobjv(gen) = mean(ObjV);
% Dati per statistiche finali

SelCh = select('sus', Chrom, FitnV, GGAP);
% Questa funzione seleziona con metodo
% Stochastic Universal Sampling,
% dalla matrice
% Chrom, basandosi sulla Fitness, una quantità di individui
% pari a GGAP*NIND

% La matrice SelCh contiene ora i cromosomi
% dei genitori, selezionati in base alla fitness,
% per la riproduzione.

SelCh = recombin('XOVSP',SelCh,0.7);
% I figli vengono creati ricombinando i geni
% dei cromosomi contenuti in SelCh
% Per la riproduzione viene usato Crossover
% Single Point con possibilità del 70%

SelCh = MUT(SelCh);
% Applica la mutazione ai genitori contenuti
% nella matrice SelCh. Se non specificato diversamente,
% la probabilità d mutazione è pari a
% 0.7/Lunghezza del cromosoma.
% Nel nostro caso, 0.7/20*20

ObjVSel = objfun1(bs2rv(SelCh,FieldD));
% Calcolo il valore della funzione oggettiva relativa ai genitori

[Chrom ObjV]=REINS(Chrom,SelCh,1,1,ObjV,ObjVSel);
% Sostituisco i figli ai genitori.
% La sostituzione avviene all'interno
% della matrice originale Chrom e
% sulla base della Fitness (il quarto
% parametro "1" indica reinserimento in base alla fitness)

gen = gen+1
% Incremento il contatore generazione di 1 e
% continuo fino alla generazione massima indicata

end

figure ('name','Andamento minimo funzione obbiettivo')
plot (minobjv)
figure ('name','Andamento del totale della funzione obbiettivo')
plot (totobjv)
min (ObjV)

Per chi lo desiderasse, è disponibile il file .m per Matlab.
Per l’esecuzione del programma è necessario installare la Genetic Algorithm Toolbox sviluppata dall’università di Sheffield.
Piccola nota finale: durante l’esecuzione del codice potreste incontrare un errore dovuto all’utilizzo del nome Switch per identificare una variabile all’interno della funzione Objfun1. Per risolvere il problema è necessario aprire il file OBJFUN1.M e fare un trova e sostituisci switch con un qualsiasi altro nome.

Print This Page Print This Page