ALGORITMI GENETICI - bel. · PDF file• Convergenta prematura a cautarii, pierdere a...
Transcript of ALGORITMI GENETICI - bel. · PDF file• Convergenta prematura a cautarii, pierdere a...
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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.
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
4 /24
Structura unui AG
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
+−−
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
14 /24
Atribuirea adecvari bazata pe ordonare
Problema de minimizare
Adecvare = fitness value
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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)(
)(_
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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)(
)(_
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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.
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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 =−+=
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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 =−+=
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
23 /24
Mutatia
Tehnici de inteligenţă computaţională în electronică, G. Oltean
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