Referat Informatica. Algoritmi genetici

label Referate autorenew 2025-09-29, 16:56 history_edu sebivaduva
Constantinescu Mihail FlorinConstantin-Pau Mihai443A 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 00000 si pentru b cromozomul 111111, 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 ;Pentru fiecare cromozom se calculeaza probabilitatea cumulativa de selectie ; ca observatie, sirul q1,q2qNR va fi crescator, ultima valore fiind 1. Cu cat ci+1 contine o valoare pentru care se obtine o valoare mai mare pentru functia obiectiv, cu atat diferenta intre qi+1 si qi va fi mai mare. Astfel, sirul probabilitatilor cumulative de selectie reprezinta o diviziune a intervalului [0,1].Pentru crearea unei populatii intermediare de cromozomi, selectam NR numere uniform aleatoare in intervalul (0,1]. Daca un numar se gaseste in intervalul (qi , qi+1], atunci cromozomul ci+1 este selectat. Se poate observa ca probabilitatea ca un cromozom sa fie selectat este cu atat mai mare cu cat intervalul (qi , qi+1] este mai mare. Am aratat in paragraful anterior ca lungimea acestui interval este cu atat mai mare cu cat valoarea functiei obiectiv pentru cromozomul respectiv este mai mare. In consecinta, exista o probabilitate mai mare ca un cromozom mai bun sa fie selectat, insa nu se garanteaza selectia acestuia. In plus, un cromozom poate sa fie selectat de mai multe ori in populatia intermediara.Urmatorul pas este imperecherea intre cromozomii din populatia intermediara. Aici apare o problema, si anume cati cromozomi alegem pentru imperechere. In primul rand, daca nu alegem nici unul, nu exista posibilitatea sa obtinem o solutie mai buna decat cea actuala, iar daca ii alegem pe toti riscam prea mult distrugand toata populatia de cromozomi, pentru ca in urma imperecherii populatia rezultata poate fi mai buna sau mai proasta. In programul prezentat mai jos citim de la tastatura o valoare pc, si pentru fiecare cromozom generam un numar aleator in intervalul (0,1]. Daca numarul e mai mic decat pc, acel cromozom va fi supus imperecherii. O valoare acceptabila pentru pc este 0,1 (10% din cromozomi vor fi supusi imperecherii).Tehnica incrucisarii este urmatoarea:Incrucisam primul cromozom selectat pentru imperechere cu al doilea, al treilea cu al patrulea etc. (daca s-a selectat pentru imperechere un numar impar de cromozomi, se renunta la ultimul);Incrucisarea consta in schimbul intre cei doi cromozomi a t gene, unde t este ales aleator in intervalul (0,k). In urma incrucisarii se obtin doi cromozomi noi:?Primul cromozom nou va contine primele t gene ale primului cromozom vechi si ultimele k - t gene ale celui de-al doilea cromozom vechi;?Cel de-al doilea cromozom nou va contine primele t gene ale celui de-al doilea cromozom vechi si ultimele k - t gene ale primului cromozom.In final, populatia intermediara de cromozomi este supusa la mutatii simple. Pentru aceasta, se citeste de la tastatura probabilitatea de aparitie a mutatiilor simple, ps , care trebuie sa aiba o valoare mica (apropiata de 0). Pentru fiecare gena a fiecarui cromozom se alege aleator un numar in intervalul (0,1], iar daca numarul ales este mai mic decat ps , continutul genei se schimba din 0 in 1 sau invers.In urma acestor operatii, se obtine o noua populatie de cromozomi si se revine la etapa de evaluare a populatiei. Algoritmul ruleaza in limita timpului disponibil, care este citit ca parametru de la tastatura.Se observa uriasa asemanare intre algoritmii genetici si viata de toate zilele. Desi cromozomii valorosi au sanse mai mari sa ajunga in noua populatie, exista si posibilitatea ca unii din ei sa se piarda. Important nu este atat cromozomul, ci populatia de cromozomi. Aceasta trebuie sa evolueze.//programul calculeaza valoarea maxima a unei functii f pe un interval//dat [a;b], folosind un algoritm genetic#include #include #include #include #include char gena[5000][30], gena1[5000][30];double v[5000] , q[5000];double f (double x){return (fabs(x*x*x-x));}double trans (double a, double pas, int cromozom, int k){//transforma un cromozom intr-un numar real intre a si bint x = 0;int y = 1;for (int i = 0; i < k ;i++) {x += y * gena[cromozom][i];y *= 2;}return a + x * pas;}double genetic (double a, double b, int NR, int k, double pc, double ps, int tmax){double pas = (b-a) / (pow(2,k)-1);double s, max;int i, j, i1, sem, t;time_t t1, t2;time(&t1);//alegerea cromozomilor initialifor (i = 0; i < NR; i++)for (j = 0; j < k ; j++)gena[i][j] = rand()%2;//obtinerea solutieido{//evaluarea populatieis=0;for (i = 0; i < NR; i++){v[i] = f(trans(a,pas,i,k));s += v[i];q[i] = 0;for (j = 0; j <= i; j++) q[i] += v[j];}for (i = 0; i < NR; i++) q[i] = q[i] / s;//crearea unei populatii intermediare de cromozomifor (i = 0; i < NR; i++){v[i] = rand() / (double)RAND_MAX;if (v[i] > 0 && v[i] <= q[0]) for (i1 = 0; i1 < k; i1++) gena1[i][i1] = gena[0][i1];else for (j = 1; j < NR; j++)if (v[i] > q[j-1] && v[i] <= q[j]) for (i1 = 0; i1 < k; i1++) gena1[i][i1] = gena[j][i1];}for (i = 0; i < NR; i++)for (j = 0; j < k; j++)gena[i][j] = gena1[i][j];//selectia cromozomilor supusi imperecheriisem = 0;for (i = 0; i < NR; i++){v[i] = rand() / (double)RAND_MAX;if (v[i] < pc)if (sem == 0) {sem = 1;i1 = i;}else{sem = 0;//se imperecheaza i1 cu it = rand() % (k+1);for (j = 0; j < t; j++){gena1[0][j] = gena[i1][j];gena1[1][j] = gena[i][j];}for (j = t; j < k; j++){gena1[0][j] = gena[i][j];gena1[1][j] = gena[i1][j];}for (j = 0; j < k; j++){gena[i1][j] = gena1[0][j];gena[i][j] = gena1[1][j];}}}//mutatii simplefor (i = 0; i < NR; i++)for (j = 0; j < k; j++){//se alege o valoare aleatoare intre 0 si 1v[0] = rand() / (double)RAND_MAX;if (v[0] < ps) gena[i][j] = 1 - gena[i][j];}//se verifica timpul de executietime(&t2);}while (t2 - t1 < tmax);//gasirea celei mai bune solutiimax = f(trans(a, pas, 0, k));i1 = 0;for (i = 1; i < NR; i++)if (f(trans(a, pas, i, k)) > max){max = f(trans(a, pas, i, k));i1 = i;}//returneaza punctul in care valoarea este maximareturn trans(a, pas, i1, k);}void main (void){double a,b,pct,pc,ps;int NR,k,tmax;srand((unsigned)time(NULL));cout<<"Introduceti capatul din stanga al intervalului : ";cin>>a;cout<<"Introduceti capatul din dreapta al intervalului : ";cin>>b;cout<<"Introduceti numarul de cromozomi (NR<=5000) : ";cin>>NR;cout<<"Introduceti numarul de gene dintr-un cromozom (k<=30) : ";cin>>k;cout<<"Introduceti probabilitatea de imperechere controlata : ";cin>>pc;cout<<"Introduceti probabilitatea pentru mutatiile simple (nr. apropiat de 0) : ";cin>>ps;cout<<"Introduceti timpul de rulare al programului (in secunde) : ";cin>>tmax;pct = genetic(a,b,NR,k,pc,ps,tmax);cout<<"Valoarea maxima este "<