8/14/2019 Curs 2 - Algoritmi genetici.txt

1/6

Obtinerea unei noi generatii plecand de la precedenta, are loc in 3 etape:

1. EVALUAREA

Algoritmul genetic calculeaza valoarea functiei de adecvare pentru fiecare individ al vechii populatii.

2.SELECTIA

Algoritmul genetic selectioneaza indivizii unei populatii P(t) in functie de performantele lor. Indivizii selectionati vor reprezenta o populatie intermediara denumita p la 1. Cromozomii pop. p la 1 devin parintii noii generatii P(t+1).

3.RECOMBINAREA SI MODIFICAREA

Algoritmul genetic recombina si modifica indivizii selectionati in acest scop se utilizeaza operatorii genetici de incrucisarea ( recombinare), mutatie, inversie, etc. Din punct de vedere algoritmic operatorii genetici reprezinta metode de a schimba local solutiile reprezentate de parinti (mutatia si inversia)sau de a combina aceste solutii (incrucisarea), aceasta din urma constand intr-un transfer de gene intre 2 cromozomi. Fiecarui operator genetic ii corespunde o

probabilitate de aplicare. Aceste probabilitati sunt parametri ai algoritmului.Operatorii genetici de recombinare si modificare se aplica cu probabilit

atile respective asupra populatiei intermediare. Aplicand operatorul de incrucisare asupra populatiei p la 1 se obtine o populatie p la 2. Asupra indivizilor din p la 2 se aplica operatorii de mutatie, inversie, etc. Astfel indivizii din pla 2 impreuna cu acei indivizi din p la 1 care nu au suferit recombinarea vor constitui noua generatie P(t+1).Sunt posibile numeroase alte modalitati de a selecta cromozomii populatiei p(t) sau/si p(t+1).

2.3.3 Algoritmul genetic fundamental (clasic)

Etapele implementarii si utilizarii unui algoritm genetic sunt urmatoarele:

- Definirea elementelor algoritmului (reprezentarea, functia de performanta, mecanismul de selectie, operatorii genetici si parametri) ;

- Proiectarea experimentului;- Executia experimentului;- Interpertarea rezultatelor;

Analiza unui algoritm evolutiv se face empiric pe baza rezultatelor unor experimente ce urmaresc fie performanta absoluta de calcul a algoritmului studi

at, fie compararea algoritmului genetic cu un alt algoritm ce rezolva aceeasi problema (studiu relativ). De aceea ,in faza de proiectare a experimentului, trebuie avut in vedere optimizarea algoritmului genetic si pentru cel de al doilea caz se considera alte tipuri de algoritmi decat cei genetici pentru efectuarea decomparatii.

In algoritmul genetic clasic functia de evaluare trebuie sa fie strict pozitiva iar asupra ei sa se realizeze o maximizare. Ambele conditii sunt usor de satisfacut atunci cand functia de performanta este data de o functie reala. Astfel functia de evaluare poate fi usor modificata prin translarea cu o constanta.

8/14/2019 Curs 2 - Algoritmi genetici.txt

2/6

Iar daca este cazul, problema de minimizare poate fi exprimata ca problema de maximizare prin inmultirea cu -1 a functiei de performanta.

Nu orice problema poate fi exprimata ca problema de optimizare a unei functii reale. Pentru situatii in care functia de performanta nu are o expresie algoritmica sau este necunoscuta se poate folosi o evaluare interactiva in care utilizatorul stabileste performanta fiecarui individ in ierarhia generatiei.

Algoritmii genetici clasici sunt formati pentru optimizarea unicriteriala. In practica, insa, sunt numeroase probleme in care trebuie urmarite mai multe obiective. Un exemplu clasic il reprezinta problema orarului in care inafara constrangerilor de natura materiala care trebuie satisfacute ( suprapunerea salilor, resurse materiale, etc.) sunt necesare si optimizari din punct de vedere al timpului alocat (cat mai putine "ferestre"). Solutia preferata in rezolvarea unei astfel de probleme este construirea unui criteriu global (modele liniare sau neliniare) in care fiecarui subcriteriu i se acorda mai multa sau mai putina importanta. Algoritmii genetici sunt algoritmi care imbunatatesc solutia pas cu pas de-a lungul mai multor generatii.

Exista, insa, si probleme de tipul "acul in carul cu fan" care prin formulare nu permit o imbunatatire pas cu pas. Un exemplu in acest sens este problema satisfiabilitatii in care data o formula in logica booleana. Peste un nr k devariabile boolene se cere o asignare a acestora astfel incat intreaga formula sa fie satisfiabila (rezultatul evaluarii sa fie 1 ca echivalent al valorii booleene adevr poate fi imaginat un algoritm genetic clasic in care reprezentarea solu

tiilor se face sub forma unui sir de k biti iar operatorii genetici sunt cei standard.

Functia de performanta da valoarea de adevar a expresiei booleene sub asignarile date de cromozomi. Dificultatea rezida in faptul ca evaluand cromozomii cu o functie de performanta ce are doar doua valori nu se poate face imbunatatirea pas cu pas iar "invatarea" devine imposibila. Astfel trebuie gasita o modalitatea de a ierarhiza indivizii nesatisfiabili, iar acest lucru este posibil doar utilizand cunostinte suplimentare din domeniul problemei.

Structura unui algoritm genetic clasic fundamental este indentica in esenta cu cea a unei proceduri evolutive. In acest caz, cromozomii utilizati au lungime constanta. Populatia P(t+1) la momentul t+1 se obtine retinand toti descend

entii populatiei P(t) si stergand apoi complet cromozomii generatiei precedente. Numarul cromozomilor in fiecare generatie este constant, principalii operatorigenetici utilizati sunt cei de mutatie, incrucisare si inversie.

Algoritmul genetic clasic are ca operatori principali incrucisarea si mutatia. Structura unui astfel de algoritm putandu-se reprezenta astfel:

P1 - se stabileste t=0;

P2 - se initializeaza aleator populatia P(t);

P3 - se evalueaza cromozomii populatiei P(t);in acest scop se utilizeaza o functie de performanta ce depinde de problema data;

P4 - cat timp se intruneste conditia C executa:

P4(1) - selecteaza cromozomii din P(t) care vor contribui la formarea noii generatii. Fie P la 1 - multimea cromozomilor selectati (P la 1(P1) reprezinta o populatie intermediara)

P4(2) - se aplica cromozomilor din p la 1 operatorii genetici. Cei mai utilizati sunt operatorii de mutatie, si incrucisare. In functie de problema se pot alege si alti operatori (inversie,

8/14/2019 Curs 2 - Algoritmi genetici.txt

3/6

reordonare, operatori speciali). Fie P la 2 (P2) - populatia astfel obtinuta (descendentii populatiei P(t)), se elimina din P la 1parintii noilor indivizi obtinuti. Cromozomii ramasi in P la 1 sunt atribuiti populatiei P la 2. Se construieste noua generatie ( P la 2 = P(t+1) - se elimina toti cromozomii din P(t), se modifica t= t+1, se evalueaza P(t);

OBSERVATII:

1. Conditia de oprire C se refera, de regula, la atingerea numarului degeneratii specificate. Daca numarul maxim atins, de generatii, este N atunci conditia de oprire este t

8/14/2019 Curs 2 - Algoritmi genetici.txt

4/6

- dimensiunea populatiei (n1);

- numarul maxim de generatii (n2);

Modulul EVALUARE:

- functiile de evaluare.

Modulul RECOMBINARE MODIFICARE

- operatorii genetici utilizati : mutatia, incrucisarea, inversia;

- parametrii algoritmului:

* probabilitatea de mutatie - Pm;* probabilitatea de comunicare - Pc;* probabilitatea de inversie - Pi;

2.3.5 SCHEME SI BLOCURI CONSTRUCTIVE

Algoritmii genetici utilizeaza operatori continand copierea cromozomilor, schimbarea unor subsiruri si modificarea unor pozitii. Astfel se poate realiza o cautare eficienta.

Modelul descris in continuare se bazeaza pe observarea anumitor similaritati intre cromozomii care reprezinta doua populatii succesive obtinute prin aplicarea unui algoritm genetic. In general este de asteptat ca performanta medie a populatiei sa creasca de la o generatie la alta. Similaritatile intalnite ar putea fi corelate cu aceasta crestere a performantei. Aceste similaritati dintre cromozomi sunt cunoscute sub numele de SCHEME, mai precis, o schema reprezinta omultime de cromozomi care au anumite pozitii identice.

In codificarea binara, o schema poate fi reprezentata de un sir cu urmatoarele simboluri: 0,1,*.

Simbolul * intr-o anumita pozitie a sirului semnifica ca acea pozitie po

ate fi ocupata de orice simbol al alfabetului binar. Ex 1: S=(1**0). Aceasta schema reprezinta 4 cromozomi.

Ex 2 : Pornind de la o solutie cunoscuta x=1,0. Aceasta a fi reprezentata de 2 la 2 ( 2 patrat) scheme. S1= * */ S2= * 0/ S3= 1 * .

Cromozomul x este considerat o instanta sau un reprezentant al fiecareia dintre schemele S1 - S4. Pentru notiunile descrise pot fi enuntate urmatoareledefinitii:

8/14/2019 Curs 2 - Algoritmi genetici.txt

5/6

- O schema de lungime r este un element al multimii {0,1,*} la r;

- Fie S o schema de lungime r. Spunem ca un cromozom x apartine multimii {0,1} la r este o instanta a schemei S daca oricarei pozitii diferite de * dinS ii corespunde o pozitie din x avand aceeasi valoare;

- Se numeste pozitie specifica a schemei S orice pozitie din S diferitade *. Simbolul * are semnificatia indiferent adica pozitia respectiva poate fi 0 sau 1;

- O schema S reprezinta toti acei cromozomi x pentru care toate pozitiile specifice ale lui S coincid cu pozitiile corespunzatoare din x. Astfel cromozomul x este un reprezentant (o instanta) a schemei S.

EXEMPLE:

S1 = (* * *) - o schema de lungime 3;

S2 = (1 0 1) - reprezinta un singur cromozom x = 1 0 1;

Deoarece o schema reprezinta anumiti cromozomi similari rezulta ca o schema poate fi identificata cu o anumita regiune a spatiului X al cromozomilor delungime r. Asadar schemele reprezinta submultimi ale spatiului de cautare.

2.3.6 TEOREMA SCHEMELOR

ORDINUL unei scheme este dat de numarul de pozitii specifice iar LUNGIME

A UTILA este diferenta dintre ultima si prima pozitie specifica a schemei.Adecvarea (performanta, calitatea) unei scheme intr-o populatie poate de

finita ca fiind adecvarea medie a reprezentantilor (instantelor) ei in acea populatie. Teorema schemelor indica tocmai faptul ca evolutia generatiilor are loc in sensul cresterii performantei iar rezultatul stabilit de teorema schemelor are un caracter probabilistic.

2.3.7 BLOCURI CONSTRUCTIVE SI PARALELISMUL INTRINSEC

Un algoritm genetic manipuleaza simultan un numar mare de scheme. Aceasta caracteristica reprezinta paralelismul intrinsec al algoritmilor genetici. Teorema schemelor ne asigura ca paralelismul intrinsec este asociat cu cresterea adecvarii in generatiile succesive.

O categorie speciala de scheme o reprezinta blocurile constructive. Astfel o schema ce are o calitate peste medie dar are ordin si lungime utila mici se numeste bloc constructiv. Conform teoremei schemelor prin actiunea operatorilor genetici blocurile constructive se compila dand nastere la blocuri constructive

8/14/2019 Curs 2 - Algoritmi genetici.txt

6/6

tot mai performante. Acestea vor converge spre solutia optima.

2.3.8 CONCLUZII

Algoritmii genetici reprezinta o clasa importanta de metode de cautare si optimizare. Aceste metode se bazeaza pe principiile geneticii si a selectiei naturale. Din consideratiile expuse anterior se pot desprinde principalele caracteristici. Acestea referindu-se , mai ales, la particularitatile acestora in raport cu alte metode de cautare si optimizare.

1. Algoritmii genetici sunt o clasa de algoritmi probabilistici care combina elemente de cautare dirijata si cautare aleatorie. Ei realizeaza un echilibru aproape optim intre explorarea spatiului starilor si exploatarea celor mai bune solutii gasite

2. Algoritmii genetici sunt mai robusti decat alete metode existente cautare dirijata si decat oricare dintre algoritmii clasici de optimizare.

3. Metodele de cautare bazate pe algoritmi genetici sunt caracterizate de faptul ca ele mentin o populatie de solutii potentiale. Metodele clasicce actioneaza la un moment dat asupra unui singur punct din spatiul de cautare.

4. De regula algoritmii genetici lucreaza cu o codificare a elementelordin spatiul starilor problemei si nu actioneaza direct asupra elementelor acestui spatiu.

5. Algoritmii genetici folosesc functii de performanta obtinute prin transformari simple ale functiei obiectiv.

6. Algoritmii genetici sunt mult mai simplu de folosit.

7. Algoritmii genetici pot gasi solutiile optime cu o foarte mare probabilitate.