EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Paradigme ale CE

➢ Calculul evolutiv contine paradigmele optimizarii si

clasificarii cu masini instruibile (machine learning), care

se bazeaza pe mecanisme evolutive:

❖ genetica biologica

❖ selectia naturala

❖ comportament adaptiv

➢ Paradigmele calculului evolutiv furnizeaza instrumente

pentru a construi sisteme inteligente care modeleaza

comportamentul inteligent.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Specificul CE

➢ Mecanisme de cautare in spatiul solutiilor bazate pe principiile

evolutiei naturale principiul supravietuirii celui mai bun (teoria

evolutionista - Darwin).

➢ Pentru gasirea solutiei se utilizeaza o populaţie de soluţii

potentiale care evolueaza (căutători).

✓ Evolutia indivizilor din populatie: indivizii din noua generatie

devin mai adaptati mediului dacat indivizii din care au fost creati -

similar cu adaptarea naturala.

✓ Furnizeaza aproximari din ce in ce mai bune ale solutiei.

➢ Pentru a ghida cautarea solutiei, asupra populatiei se utilizeaza

transformari specifice evolutiei naturale: selectie, recombinare

(crossover, incrucisare), mutatie, reinsertie, etc

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Transformari specifice CE➢ Selecție (Selection)

❖ Indivizii populatiei mai apropiati de solutia problemei (o

masura de tip eroare) sunt considerati mai adecvati (potriviti)

si sunt favorizati, adica au mai multe sanse de a fi selectati

pentru crearea generatiei urmatoare.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Transformari specifice CE

➢ Recombinare (Crossover, Incrucisare)

❖ Pornind de la doi indivizi ai populatiei curente (parinti) se

genereaza noi indivizi (urmasi, copii). In functie de calitatea

acestora (adecvare, potrivire) urmasii isi inlocuiesc (pot inlocui)

parintii.

➢ Mutatie (Mutation)

❖ Pentru a asigura variabilitatea (diversitatea) populatiei, se

aplica, la fel ca in natura, transformari cu caracter aleator

(stocastic) asupra indivizilor populatiei, permitand astfel

aparitia unor noi trasaturi (gene) – indivizi, care doar prin

selectie si incrucisare nu ar fi aparut in cadrul populatiei.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Paradigmele EC sunt unice

➢ Paradigmele CE difera de paradigmele metodelor

traditionale de cautare si optimizare deoarece in CE:

❖ in cautare se utilizeaza o populatie de solutii candidate

(indivizi)

❖ utilizeaza în mod direct informatii privind “potrivirea”

(adecvarea) in loc de informatii de gradient, derivate, etc.

❖ utilizeaza reguli de tranzitie (determinarea variabilelor in

iteratia urmatoare) aleatoare (stocastice, ne-deterministe)

nu deterministe.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Subdomenii ale CE

➢ In functie de modul in care este construita populatia si de

modul in care este implementata evolutia, sistemele de

calcul evolutiv pot fi incadrate in mai multe categorii[Eberhart, Shi07]:

❖ Algoritmi genetici (genetic algorithms)

❖ Programare evolutiva (evolutionary programming)

❖ Strategii evolutive (evolution strategies)

❖ Programare genetica (genetic programming)

❑ Optimizare cu roiuri de particule (particle swarm

optimization)

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Subdomenii ale CE - AG➢ Algoritmi genetici (genetic algorithms)

❖ Reprezinta tehnici de cautare si optimizare avand ca punct de

pornire o metafora biologica, bazata pe mostenirea genetica si

evolutia naturala

❖ Se folosesc in special pentru rezolvarea unor probleme complexe de

optimizare - prin minimizarea (maximizarea) unei functii obiectiv).

❖ Populatia este reprezentata de stari din spatiul problemei codificate

binar (un element al populatiei este un sir de biti) sau cu variabile reale.

❖ Principalii operatori sunt cei de selectie si incrucisare, cel de mutatie

are o probabilitate mai mica de aplicare.

❑ Algoritmii genetici au fost propusi de catre Holland in perioada anilor

1960, initial ca modele ale evolutiei si adaptarii la mediu a sistemelor

naturale.

❑ Ulterior s-a observat ca algoritmii genetici pot fi utilizati si ca

instrumente eficace in rezolvarea problemelor de optimizare.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Subdomenii ale CE - PE

➢ Programare evolutiva (evolutionary programming)

❖ Initial programarea evolutiva a avut ca obiectiv dezvoltarea unor

structuri de calcul (automate) printr-un proces de evolutie in care se

utilizeaza doar selectia si mutatia; nu se utilizeaza incrucisarea.

❖ Fiecare punct in populatie reprezinta o intreaga specie, speciile fiind

in competitie

❖ Concentrata pe procese top-down a comportamentului adaptiv;

dezvoltarea de modele comportamentale

❖ Bazele domeniului au fost puse de catre Fogel.

❖ Ulterior, programarea evolutiva a fost orientata catre rezolvarea

problemelor de optimizare avand aceeasi sfera de aplicabilitate ca si

strategiile evolutive.

❖ Se folosesc in special pentru rezolvarea unor probleme de

optimizare.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Subdomenii ale CE - SE

➢ Strategii evolutive (evolution strategies)

❖Se bazeaza pe evolutia evolutiei

❖Au fost concepute initial pentru a rezolva probleme de optimizare, in

tehnica fiind destinate rezolvarii problemelor de optimizare continua.

❖ Supravietuirea celui mai potrivit individ

❖ Operatorul principal este cel de mutatie dar este folosita si

recombinarea

❖ Pentru strategiile evolutive au fost dezvoltate scheme de adaptare a

parametrilor de control (auto-adaptare).

❖ Scopul este de a muta populatia inspre regiunea cea mai buna din

spatiul solutiilor

❖ La dezvoltarea strategiilor evolutive contributii importante au adus

Rechenberg si Schwefel.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Subdomenii ale CE - PG➢ Programare genetica (genetic programming)

❖ Este o directie mai recenta a calculului evolutiv, dezvoltata la sfarsitul

anilor 1980 de catre Koza.

❖ Scopul programarii genetice este dezvoltarea unor "modele" de calcul

(programe simple).

❖ Populatia este reprezentata de programe care candideaza la rezolvarea

problemei.

❖ Exista diferite reprezentari ale elementelor populatiei, una dintre cele

mai utilizate fiind aceea in care se utilizeaza o structura arborescenta

pentru reprezentarea programelor (a populatiei).

❖ Incrucisarea este realizata selectand aleator sub-arbori din arborele

asociat programelor parinte si interschimbandu-le.

❖ Ca si in cazul algoritmilor genetici mutatia are pondere mica.

❖ Programe de calculator care sunt codificate de catre alte programe

proiectate pentru a le optimiza performantele

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Subdomenii ale CE - PSO➢ Particle swarm optimization - PSO

❖ PSO is a population based (stochastic) optimization algorithm

that simulates the social behavior of animals

❖ Optimizes a problem by iteratively trying to improve a candidate

solution regarding a given measure of quality.

❖ PSO optimizes a problem by having a population of candidate

solutions (particles) and moving these particles around in the

search-space according to simple mathematical formulae over the

particle's position and velocity.

❖ Each particle's movement is influenced by its local best-known

position and is also guided toward the best-known positions in the

search-space, which are updated as better positions are found by

other particles. This is expected to move the swarm toward the

best solutions.

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Structura unui algoritm evolutiv

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Bazele biologice ale CE➢ Legatura cu genetica, “ramură a biologiei care studiază

fenomenele şi legile eredităţii şi variabilităţii organismelor”

➢ Cromozom: o structura ordonata (liniara) de elemente numite

gene ale caror valori determina caracteristicile unui individ si

care transmite informatie genetica. In genetica pozitiile pe care se

afla genele in cadrul cromozomului se numesc loci (locus – sg.),

iar valorile pe care le pot lua genele se numesc alele (alel – sg.).

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Bazele biologice ale CE – cont.

➢ Vectorii (sirurile, pattern) individuali utilizati in CE

corespund cromozomilor din sistemele biologice.

➢ In genetica, colectia cromozomilor necesara pentru a

caracteriza complet un organism (individ) se numeste

genotip (structura).

➢ In CE, colectia de vectori necesara pentru a specifica

complet un individ este denumita structura.

➢ In general, in CE un individ este caracterizat printr-un

singur vector (vector de stare, pattern)

cromozom structura.

➢ Un fenotip (phénotype) este setul de valori corespunzand

unui genotip, adica este o structura decodata (o solutie)

EVOLUTIONARY ALGORITHMS

Computational Intelligence in Complex Decision Systems G. Oltean

Cromozomi umani

46 de cromozomi (organizati in perechi) in nucleul fiecarei celule:

▪ 22 perechi de autozomi (numerotati dupa marime, in ordine descrescatoare a taliei lor)

✓ arata la fel pentru ambele sexe (sunt omologi)

▪ 1 pereche de heterozomi (determina sexul)

✓ feminin X,X

✓ masculin X,Y

▪ in fiecare pereche avem un

cromozom de la fiecare parinte)

▪ cromozomii pot fi vazuti ca

siruri lungi de gene

Contin informatia ereditara a organismului

Perechea 23XX - X de la mama, X de la tata

XY – X de la mama, Y de la tata

X : ~ 2000 gene; Y: >200 gene