Algoritmi Genetici

Tehnici de inteligenţă computaţională în electronică, G. Oltean

ALGORITMI GENETICI

1 /24

ALGORITMI GENETICI

Reprezinta tehnici de cautare si optimizare avand ca punct de pornire o

metafora bilogica. Aceasta metafora biologica este cea a mostenirii genetice si evolutiei naturale


ALGORITMI GENETICI

2 /24

IntroducereAG sunt metode de cautare stocastice care mimeazaevolutia naturala biologicaOpereaza pe o populatie de solutii potentialeaplicand principiul supravietuirii celui mai bun (teoria evolutionista Darwin) pentru a produce aproximari din ce in ce mai bune ale solutiei.Fiecare individ al populatiilor se descrie printr-un singur cromozom Genotipul fiecarui individ contine un singur cromozom


ALGORITMI GENETICI

3 /24

Introducere – cont.

In fiecare generatie este creat un nou set de indivizi(aproximatori, cautatori) in urma selectiei celor maiadecvati indivizi si combinarea acestora pentru a danastere la noi indivizi utilizand operatoriimprumutati din geneticaAre loc evolutia populatiei de indivizi care astfeldevin mai adecvati (potriviti) mediului decatindivizii din care au fost creati, similar cu adaptareanaturala.Sunt modelate procese naturale:

selectie, recombinare, mutatie.


ALGORITMI GENETICI

4 /24

Structura unui AG


ALGORITMI GENETICI

5 /24

Reprezentarea variabilelorSpecifica AG este notiunea de cromozom, ce contine toate informatiilenecesare reprezentarii unui individ.Un cromozom este compus din gene – variabila a problemei de optimizatCromozom generic in care fiecare gena reprezinta o variabila:

“Alfabetul” utilizat in reprezentarea genelor poate fi teoretic orice alfabet, cele mai utilizate fiind:

reprezentarea binarareprezentarea reala – specifica problemelor ingineresti


ALGORITMI GENETICI

6 /24

Reprezentarea variabilelor - binarDe exemplu in cazul uneivariabile cu valori in domeniul (0, 255) se utilizeaza un sir de 8 biti: 11111111:255

10000000:12801111111:12700000000:0

• cea mai mica schimbare in valoarea functiei obiectiv (intre 127 si 128) poate solicita schimbarea tuturor bitilor – nu este de dorit !

• solutie: codul Gray – distanta Hamming intre valori adiacente este 1

o Provocari la reprezentarea in binar:• rezolutia• numere zecimale• numere negative • mai multe variabile• ramanerea in domeniul dinamic al fiecarei variabile


ALGORITMI GENETICI

7 /24

Reprezentarea variabilelor – valori reale

De exemplu in cazul a treivariabile putem avea:

• avantaj major, in special pentru implementare: vector cu valori reale

• pe parcursul evolutiei nu exista interactiune intre variabile diferite

o Provocari la reprezentarea cu valori reale:• mentinerea domenului dinamic al fiecarei variabile

47;45,0;43235;56,10;124

+−−


ALGORITMI GENETICI

8 /24

Generarea populatiei initialeUzual initializarea se realizeaza stocastic (aleator)Uneori se introduc in populatia initila catva indivizi selectati euristic(indivizi promitatori) si se completeaza cu indivizi alesi aleatorPopulatia initiala ar trebui sa conste dintr-o varietate mare a indivizilorMarimea populatiei: moderata 50 – 500 indiviziMarimea populatiei tinde sa creasca liniar cu dimensiunea unui individ

POP_INIT=zeros(NumInd, NumVar); for i=1:NumVar

RandVar=(HB(i)-LB(i)).*rand(NumInd,1)+LB(i);POP_INIT(:,i)=RandVar;

end

• Generare aleatoare cu distributie de probabilitate uniforma


ALGORITMI GENETICI

9 /24

Functia de adecvareFunctia de adecvare (fitness) se determina in concordanta cu valoarea functieiobiectiv definita pentru problema de optimizare de rezolvat.Formularea problemei de optimizare este de tipul minimizeaza sau maximizeaza(se poate trece de la una la cealalta utilizand semnul minus in fata functiei)

Exemplu de problema de minimizare

( ) DxxFx ∈∀pentru aminimizeaz care Gaseste

( )]10,10[x]10,10[

;,

];,[22

2121

21

−−=+=

=

DxxxxF

xxxFunctia De Jong – 2 variabile


ALGORITMI GENETICI

10 /24

Functia de adecvare - contPentru probleme de optimizare multiobiectiv exista doua variante:

Optimizare multiobiectiv reala – multimea solutiilor optime ParetoTransformarea intr-o problema cu un singur obiectiv prin combinareafunctiilor obiectiv individuale intr-o singura functie cost – rezulta o singurasolutie

( ) ( )

)( obiectiv functiile dintre fiecarepentru relativa preferinta arata ce ponderisunt unde

pentru aminimizeaz care Gaseste1

xfw

DxxfwxFx

k

k

N

kkk ∈∀=∑

=

Ca functie de adecvare se poate utiliza direct functia obiectiv dar apareun neajuns:

Dupa un anumit numar de generatii multe dintre valorile functiei de adecvare vor fi foarte apropiate de valoarea optima, ceea ce conduce la dificultati in diferentierea indivizilor in procesul de selectie (convergenta prematura, pirderea diversitati populatiei)Solutie: ordonarea indivizilor in functie de valoarile functiei obiectiv


ALGORITMI GENETICI

11 /24

Atribuirea adecvarii - ordonare

Functie de adecvare proportionalaFunctie de adecvare bazata pe rang (in urma ordonarii)

liniaraneliniara

Functie de adecvare multiobiectivordonare Pareto (multi-ranking)atingerea scopuluiinsumare ponderata


ALGORITMI GENETICI

12 /24

Atribuirea adecvari bazata pe ordonarePopulatia este ordonata in concordanta cu valoarea functiei obiectivValoarea adecvarii atribuita fiecarui individ depinde numai de pozitia sa in urmaordonarii si nu de valoarea functiei obiectivFiecare individ primeste o probabilitate de reproducere depinzand de propriavaloare a functiei obiectiv si de valorile functiilor obiectiv a celorlalti indivizi

( ) ( )

selectie de presiunea - populatiei adimensiune pozitia; -

11122

PSNindPos

NindPosPSPSPosAdecvare

−−−

−+−=

• Cel mai adecvat individ are Pos=Nindsi cea mai mare valoare a functiei de adecvare

• Cel mai putin potrivit individ are Pos=1 si cea mai mica valoare a functiei de adecvare


ALGORITMI GENETICI

13 /24

Atribuirea adecvari bazata pe ordonare – cont.

( ) ( )

selectie de presiunea - populatiei adimensiune pozitia; -

11122

PSNindPos

NindPosPSPSPosAdecvare

−−−

−+−=De regula

2] [1,∈PS

Cresterea presiunii de selectie focalizeaza cautarea asupra celor mai performanti indivizi, exploatand cele mai bune solutii

• Convergenta prematura a cautarii, pierdere a diversitatii genetice, reducerea capacitatii de explorare a spatiului starilor

Reducerea presiunii de selectie poate duce la uniformizarea selectiei, cautarea devenind putin eficienta

• creste capacitatile de explorare, in procesul de selectie fiind inclusi mai multi cromozomi

Trebuie mentinut un echilibru explorare - exploatare


ALGORITMI GENETICI

14 /24

Atribuirea adecvari bazata pe ordonare

Problema de minimizare

Adecvare = fitness value


ALGORITMI GENETICI

15 /24

SelectiaDeterminarea populatiei intermediare ce contine parintii care vor fisupusi operatorilor genetici de recombinare si mutatie - selectareaindivizilor care vor produce urmasi.Metode:

aleatoare – in procesul de selectie sunt introduse elemente aleatoare, in general prin utilizarea unor probabilitati de selectie care depind de gradul de adecvare.

Elementele cu grad mare de adecvare au sanse mai mari de a fiselectate, astfel ca numarul de urmasi ai acestora poate fi mai mare decat al celor cu grad mai mic de adecvareSelectia tip ruleta (esantionare stocastica cu inlocuire); selectie de tip turneu, selectie proportionala.

deterministe – indivizii cu grad mare de adecvare sunt intotdeauna selectati in defavoarea celor cu grad mai mic de adecvare: selectia prin trunchiere

Elitism: supravietuirea celui mai bun dintre indivizii generatiei pana la un moment dat – de exemplu prin amplasarea explicita a celui mai bun individ al populatiei curente in populatia corespunzatoare generatiei urmatoare


ALGORITMI GENETICI

16 /24

Selectia tip ruletaAlgoritm stocasticIndivizii sunt atribuiti la segmente contigue a unei linii astfel ca lungimea fiecarui segmant sa fie proportionala cu gradul sau de adecvare.Se genereaza un numar aleator si este selectat individul al caruisegment corespunde valorii aleatoareProcesul se repeta pana cand este selectat numarul dorit de indiviziProcesul este asemanator rotii de ruleta in care marimea fiecarei “felii”este proportionala cu gradul de adecvarePentru fiecare individ se calculeaza o probabilitate de selectie:

( )∑=

= N

iiFitness

iFitnessiyprobabilitSelection

1)(

)(_


ALGORITMI GENETICI

17 /24

Selectia tip ruletaAlgoritm stocasticIndivizii sunt atribuiti la segmente contigue a unei linii astfel ca lungimea fiecarui segmant sa fie proportionala cu gradul sau de adecvare.Se genereaza un numar aleator si este selectat individul al caruisegment corespunde valorii aleatoareProcesul se repeta pana cand este selectat numarul dorit de indiviziProcesul este asemanator rotii de ruleta in care marimea fiecarei “felii”este proportionala cu gradul de adecvarePentru fiecare individ se calculeaza o probabilitate de selectie:

( )∑=

= N

iiFitness

iFitnessiyprobabilitSelection

1)(

)(_


ALGORITMI GENETICI

18 /24

Au fost selectati indivizii:

6, 2, 9, 1, 5 si 3

Adica 1, 2, 3, 5, 6 si 9

Selectia tip ruleta - cont


ALGORITMI GENETICI

19 /24

RecombinareProduce noi indivizi (urmasi) prin combinarea informatiilorcontinute de doi sau mai multi parintiCombinarea valorilor variabilelor parintilorTipuri de recombinari:

discretapentru valori reale:

recombinare intermediararecombinare liniararecombinare liniara extinsa

pentru valori binare (incrucisare - crossover):incrucisare cu un singur puncte / cu doua puncte / cu puncte multipleincrucisare uniformaetc.


ALGORITMI GENETICI

20 /24

Recombinare intermediara( ) NvarjVaraVaraVar P

jjPjj

Uj ...,,2,1,1 21 =−+=

UjVar - reprezinta variabila j a urmasului

21, Pj

Pj VarVar - reprezinta variabila j a primului, respectiv celui de-al doilea parinte

a - reprezinta factorul de scalare, generat aleator in intervalul[-d, 1+d] uzual d=0,25

Aria posibila a urmasilor

( ) NvarjVaraVaraVar Pjj

Pjj

Uj ...,,2,1,1 21 =−+=


ALGORITMI GENETICI

21 /24

Recombinare intermediara – cont.

Din subpopulatia selectata pentru recombinare, cum sunt alesi cei doi parinti care genereaza urmasi?

( ) NvarjVaraVaraVar Pjj

Pjj

Uj ...,,2,1,1 21 =−+=


ALGORITMI GENETICI

22 /24

MutatiaIndivizii (urmasii) sunt modificati aleatorMutatie

Pentru variabile realePentru variabile binare

Mutatia pentru variabile reale

Valori create aleator sunt adaugate variabilelor realeTrebuiesc definite:

Probabilitatea ca o variabila sa sufere o mutatie (rata de mutatie)• Este invers proportionala cu numarul variabilelor• O valoare optima se pare a fi 1/Nvar - o singura variabila a unui

individ surefa procesul de mutatieValoarea schimbarii variabilei prin procesul de mutatie


ALGORITMI GENETICI

23 /24

Mutatia


ALGORITMI GENETICI

24 /24

ReinsertiaGenerarea noii populatiiReinsertie globala

Numar urmasi > numar parinti: toti parintii sunt inlocuiti de urmasiNumar urmasi < numar parinti: se inlocuiesc parinti in mod aleatorNumar urmasi < numar parinti: se inlocuiesc parintii cu cel mai scazutgrad de adecvareNumar urmasi > numar parinti: se inlocuiesc toti parintii cu cei mai buniurmasi

Reinsertie locala

Algoritmi Genetici

Documents

Transcript of Algoritmi Genetici