Slide 1

Componentele unui EAAlgoritmi genetici. Reprezentri cromozomiale.

Componentele EA1. Reprezentarea (definirea membrilor populaiei) - stabilirea unei conexiuni ntre contextul problemei particulare de rezolvat i spaiul n care evolueaz tehnica PS considerat. Fenotipuri : soluiile posibile n contextul problemei de rezolvatGenotipuri (cromozomi): reprezentarea fenotipurilor n context EA; conin valori (alele), plasate n poziii numite variabile sau gene. 2. Funcia de evaluare (fitness) - msoar gradul de adaptabilitate a fiecrui individ la mediul n care triete. St la baza proceselor de selecie i este derivat pe baza unei funcii de tip calitate definit pe spaiul fenotipurilor. 3. Populaia multiset de genotipuri; menine o mulime de genotipuri, n general de dimensiune constant, corespunztoare unor soluii posibileOperatorii de selecie: definii la nivel de populaie. Variaia n cadrul unei populaii individ, calitate, entropie etc.4. Mecanismul de selectare a prinilor - permite celor mai buni indivizi s se reproduc, fr a-i exclude pe cei mai slabi. Selecia este probabilist i depinde de calitatea indivizilorRolul: foreaz mbuntirea calitii globale a populaiei de la o generaie la alta.

5. Operatorii de variaie stochastici: rezultatul este funcie de alegeri aleatoare. Recombinarea: produce unul sau dou genotipuri copil prin combinarea informaiei din dou genotipuri printe i este stochasticMutaia: produce o variant mutant a unui genotip, numit progenitur sau copil6. Mecanismul de selectare a membrilor generaiei urmtoare - este aplicat fiecrui individ aparinnd populaiei curente sau mulimii progeniturilor pe baza unei fucii de decizie. Supravieuire generaionalSupravieuire bazat pe calitate7. Definirea modulului de iniializare (determinarea populaiei iniiale) sunt generate aleator fenotipurile i apoi este obinut reprezentarea prin genotipuri8. Definirea condiiei terminaleatingerea unui numr maxim de iteraii (generaii);atingerea unui numr maxim de evaluri ale calitii indivizilor;pentru o anumit perioad de timp calitatea populaiei curente nu este semnificativ mbuntit (este sub un prag dat);diversitatea populaiei scade sub un prag dat.

ALGORITMI GENETICI (GA)

Respect structura unui EA

Reprezentarea soluiilor. Reprezentarea binar

Alegerea unei anumite reprezentri depinde de problema particular de rezolvat i este foarte important pentru ca GA s furnizeze soluii apropiate de cele optime. Cele mai utilizate tipuri de reprezentri n GA: secvene binare;secvene de numere ntregi;secvene de numere reale;permutri.

Reprezentarea binar: prima ca istoric

n cazul unor clase de probleme care conin variabile de tip decizie boolean, reprezentarea binar este cea mai natural. Altfel, pot fi obinui GA superiori ca performane prin utilizarea reprezentrilor directe

Reprezentarea binar. ExempluReprezentarea binar. Codificarea GrayNumr01234567Cod binar std.0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 1Cod Gray0 0 0 00 0 0 10 0 1 10 0 1 00 1 1 00 1 1 10 1 0 10 1 0 0Numr89101112131415Cod binar std.1 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1Cod Gray1 1 0 01 1 0 11 1 1 11 1 1 01 0 1 01 0 1 11 0 0 11 0 0 0Reprezentarea prin numere ntregiReprezentarea prin numere realeReprezentarea prin permutriPermutrile sunt utilizate pentru reprezentri cromozomiale n probleme n care trebuie stabilit ordinea apariiei unor secvene de evenimente. n acest caz operatorii de variaie trebuie definii astfel nct rezultatul aplicrii acestora s corespund unor soluii admisibile.

Clase de probleme: probleme n care ordinea apariiei evenimentelor este important. Aceast situaie apare, de exemplu, cnd evenimentele utilizeaz resurse limitate sau se desfoar ntr-o anumit perioad de timp. Exemplu: problema planificrii activitilor;probleme n care apare dependena de adiacen. Exemplu: problema comis-voiajorului, n care, pentru n orae interconectate date, trebuie determinat un drum de lungime (distan) minim care s treac prin toate cele n orae, cu revenire n oraul de start. Diferena dintre cele dou clase de probleme este dat de faptul c, evident, n cazul celei de-a doua clase, punctul de start (n cazul problemei comis-voiajorului oraul de plecare) nu este important.