Algoritmi Genetici

Algoritmii genetici fac parte din categoria algoritmilor euristici, ei aplicandu-se cu succes in cazul problemelor ce nu admit algoritmi in timp polinomial.

Algoritmii genetici, dupa cum sugereaza si numele, sunt inspirati din natura, mai precis din felul in care prin recombinari genetice se imbunatateste o specie.

Pasii care trebuie parcursi intr-un astfel de algoritm pot fi descrisi astfel:

//Algoritm genetic general

P = InitPopulatie ( );

Cat timp nu s-a epuizat timpul de executie stabilit

{

Evalueaza ( P );

P’ = SelectParinti ( P );

Recombina ( P’ );

Mutatii ( P’ );

P = P’;

}

Afiseaza ( P );

Ideea algoritmilor genetici este de a reprezenta solutiile posibile ale problemei sub forma unor cromozomi, si de a lucra la fiecare pas cu un numar fix de cromozomi, care formeaza o populatie. In algoritmul de mai sus, P este o populatie de cromozomi care reprezinta solutia problemei gasita la pasul respectiv, iar P’ este o populatie intermediara, generata din P prin metode specifice geneticii (incrucisari intre cromozomi si mutatii spontane). Astfel, se incearca imbunatatirea populatiei de cromozomi in limita timpului disponibil, in sensul apropierii cat mai mult de solutia optima.

Generatia 0 se alege complet aleator, iar restul operatiilor folosesc si ele generarea de numere aleatoare. In consecinta, rezultatul executiei unui astfel de algoritm va depinde si de sansa, si, in plus, va fi altul la fiecare rulare.

Pentru a putea explica mai bine felul in care functioneaza algoritmul, vom alege o problema concreta, si anume “Determinarea maximului unei functii f(x) pe intervalul [a,b]”. Aceasta problema are avantajul ca ne permite sa evaluam foarte usor daca algoritmul ne conduce sau nu la solutie, desi nu este un exemplu semnificativ pentru folosirea algoritmilor genetici.

In mod evident, pentru rezultate cat mai bune, trebuie sa consideram cat mai multe valori pentru variabila x in intervalul [a,b]. Am notat cu NR numarul acestor valori.

Toate valorile pe care le vom alege vor fi cuantificate sub forma de cromozomi. Cromozomul reprezinta o succesiune de k pozitii binare, fiecare pozitie fiind o gena. In consecinta vom avea NR cromozomi cu cate k gene fiecare.

La primul pas se aleg aleator cei NR cromozomi, generand cate o succesiune aleatoare de k gene (valori de 0 sau 1). Pentru a converti un cromozom intr-o variabila reala din domeniul [a,b], se va face o divizare a domeniului in 2k intervale si se aloca pentru a cromozomul 000…00 si pentru b cromozomul 111…111, restul valorilor fiind distribuite proportional.

Pentru obtinerea solutiei sa consideram intai cei NR cromozomi ca fiind c1,c2…,cNR.

Pentru evaluarea populatiei de cromozomi, se vor calcula urmatoarele valori:

- In primul rand, functia obiectiv ; prin aceasta convertim fiecare cromozom intr-o valoare reala, si anume valoarea functiei al carei maxim il dorim, in punctul reprezentat de cromozomul ci ;

- Calculam suma valorilor functiilor obiectiv ;

- Pentru fiecare cromozom calculam probabilitatea de selectie