Algoritmi Genetici

1 Introducere în calculul evolutiv

În general, orice sarcina abstracta care trebuie îndeplinita, poate fi privita ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi perceputa ca o cautare în spatiul solutiilor potentiale. Deoarece, de obicei, cautam cea mai buna solutie, putem privi acest proces ca fiind unul de optimizare. Pentru spatii mici, metodele clasice,cum ar fi procedura backtracking sunt suficiente; dar pentru spatiile mari, aceste proceduri nu sunt destul de suficiente deoarece rezolvarea problemelor dureaza mult timp, astfel se folosesc tehnici speciale ale inteligentei artificiale.

Metodele calculului evolutiv se numara printre aceste tehnici; ele folosesc algoritmi ale caror metode de cautare au ca model câteva fenomene naturale: mostenirea genetica lupta pentru

supravietuire. Cele mai cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici,

strategiile evolutive, programarea genetica si programarea evolutiva. Exista si alte sisteme hibride care încorporeaza diferite proprietati ale paradigmelor de mai sus; mai mult, structura oricarui algoritm de calcul evolutiv este, în mare masura, aceeasi.

În ultimii 30 de ani, s-a manifestat un mare interes în rezolvarea problemelor de sistem bazate pe principiile evolutiei si ereditatii. Astfel de sisteme mentin o populatie de solutii potentiale, ele au unele procese de selectie bazate pe fitness individual, si câtiva operatori gene-tici. Un astfel de sistem este o clasa a evolutiei strategice i.e, algoritmi care imita principiile evolutiei naturale pentru problemele de optimizare de parametru(Rechemberg, Schwefel). Evolutia programarii lui Fogel este o tehnica de cautare într-un spatiu finit, mic de masini. Tehnologiile de cautare a masinii lui Glover Scatter mentin o populatie de puncte de referinta, generând o stare speciala prin greutatea combinatiilor liniare.

Alte tipuri de sisteme evolutionare sunt Holland.s Genetic Algorithms. În 1990 Koza a propus un astfel de sistem evolutional, genetic programming, pentru a cauta cel mai potrivit program de computer sa rezolve o problema particulara .Folosind un termen comun E.P pentru toate sistemele(incluzând sistemele descrise mai sus). Structura evolutiei programului este aratata mai jos:

Majoritatea algoritmilor evolutivi au un caracter iterativ. Structura generala a unui astfel de

algoritm (algoritm genetic, strategie evolutiv_a etc.) este:

// initializarea indicatorului de iteratie

t := 0;

// initializarea (aleatoare) a populatiei (multime de configuratii a caror structura depinde de problema)

init P(t);

// calculul functiei "fitness" pentru fiecare individ al populatiei evaluate P(t);

// proces iterativ de evolutie repetat

// incrementarea indicatorului de iteratie

t = t + 1

// selectarea unei sub-populatii în scopul reproduceri(parinti)

P1(t) = select P(t)

// încrucisarea "genelor" parintilor având ca rezultat obtinerea unei noi populatii

P2(t) = recombine P1(t)

// perturbarea aleatoare a noii populatii (mutatie)

P3(t) = mutatie P2(t)

// evaluarea noii populatii(calculul functiei "fitness" pentru noua populatie)

evaluare P3(t)

// selectia supravietuitorilor din cele doua populatii (pe baza valorii functiei fitness)

P(t+1) = survive (P(t),P3(t))

until <conditie de stop>

Conditia de oprire se poate referi la numarul de iteratii (generatii) sau la proprietatile populatiei

curente (de exemplu, întreaga populatie converge catre o singura valoare).

Evolutia programului este un algoritm probabilistic ce contine elemente distincte, P(t)={x1t,x2t, ...xnt}. Algoritmii evolutivi mentin o populatie de indivizi la fiecare iteratie t. O populatie poate fi privita ca fiind un vector de valori. Fiecare element distinct reprezinta o solutie potentiala a problemei în cauza si în orice program, este interpretat ca S structura de date. Fiecare solutie x1t, x2t,.., xnt este evaluata pentru a da o oarecare masura a fitness-ului sau.Fiecare individ (element al vectorului) reprezinta o solutie potentiala a problemei si este implementata sub forma unei structuri de date S. Un individ este uneori numit si cromozom. Fiecare solutie este evaluata ca fiind o masura a "fitness-ului" sau(sperantei de viata). Acest fitness reprezinta calitatea individului. De obicei, cu cât individul este mai promitator, cu atât fitness-ul sau este mai mare.

Exista unele probleme în cazul carora fitness-ul trebuie sa fie maximizat. O noua populatie (iteratia t + 1) se formeaza prin selectarea mai multor potriviri individuale, alegând cei mai promitatori indivizi (pasul de selectie) din populatia curenta. O parte din membri populatiei nou formate sufera transformari (pasul de modificare) prin operarea genetica a noilor solutii. Vorbim despre o transformare unica e evolutiei programului.

2 Specificul calculului evolutiv

Calculul evolutiv ofera mecanisme de cautare în spatiul solutiilor bazate pe principiile evolutiei naturale (de tip darwinist). Pentru gasirea solutiei se utilizeaza o populatie de cautatori. Elementele populatiei reprezinta solutii potentiale ale problemei. Pentru a ghida cautarea catre solutia problemei asupra populatiei se transformari specifice evolutiei naturale:

Selectie. Elementele populatiei care se apropie de solutia problemei sunt considerate adecvate si sunt favorizate în sensul ca au mai multe sanse de a supravietui în generatia urmatoare precum si de a participa la generarea de "urmasi".

Încrucisarea. La fel ca în înmultirea din natura pornind de la doua sau mai multe elemente ale populatiei (numite parinti) se genereaza noi elemente (numite urmasi). În functie de calitatea acestora (apropierea de solutia problemei) urmasii îsi pot înlocui parintii.

Mutatia. Pentru a asigura variabilitatea populatiei se aplica, la fel ca în natura, transformari cu caracter aleator asupra elementelor populatiei permitând aparitia unor trasaturi (gene) care doar prin încrucisare si selectie nu ar fi aparut în cadrul populatiei.