algoritmi genetici - bel.utcluj.ro · adecvati indivizi si combinarea acestora pentru a da nastere...

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

ALGORITMI GENETICI

ALGORITMI GENETICI

Reprezinta tehnici de cautare si optimizare avand

ca punct de pornire o metafora biologica.

Aceasta metafora biologica este cea a mostenirii

genetice si evolutiei naturale [Dum06]


ALGORITMI GENETICI

Introducere

AG sunt metode de cautare stocastice care mimeaza

evolutia naturala biologica

Opereaza pe o populatie de solutii potentiale

aplicand principiul supravietuirii celui mai bun

(teoria evolutionista a lui Darwin) pentru a produce

aproximari din ce in ce mai bune ale solutiei.

Fiecare individ al populatiilor este descris printr-un

singur cromozom

Genotipul fiecarui individ contine un singur

cromozom


ALGORITMI GENETICI

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 genetica

Are loc evolutia populatiei de indivizi care devin maiadecvati (potriviti) mediului decat indivizii din careau fost creati, similar cu adaptarea naturala.

Sunt modelate si implementate procese biologice:

selectie

recombinare

mutatie


ALGORITMI GENETICI

Reprezentarea variabilelor

Specifica AG este notiunea de cromozom, ce contine toate informatiile

necesare reprezentarii unui individ.

Un cromozom este compus din gene – variabile a problemei de optimizat

Cromozom generic - fiecare gena reprezinta o variabila:

“Alfabetul” utilizat in reprezentarea genelor poate fi (teoretic) orice

alfabet, cele mai utilizate fiind:

reprezentarea binara

reprezentarea reala – specifica problemelor ingineresti

reprezentarea cu numere intregi

2 indivizi în reprezentare

reală cu trei variabile:


ALGORITMI GENETICI

Reprezentarea variabilelor - binar De exemplu in cazul unei variabile

cu valori in domeniul (0, 255) se

utilizeaza un sir de 8 biti (lungimea

cromozomului este 8): 11111111:255

10000000:128

01111111:127

00000000:0

• schimbarea tuturor bitilor poate produce cea mai mica schimbare in

valoarea functiei obiectiv (intre 127 si 128) – nu este de dorit !

• solutie: codul Gray – distanta Hamming intre valori reale 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

Incrucisare Cu un singur punct Cu doua puncte

Mutatie

Operatori genetici pentru reprezentarea binară


ALGORITMI GENETICI

Reprezentarea variabilelor – valori reale

De exemplu, in cazul a trei variabile lungimea cromozomului este 3

Doi indivizi ai populatiei ar putea fi:

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

• pe parcursul evolutiei nu va exista interactiune intre variabile diferite

o Provocari la reprezentarea cu valori reale:

• mentinerea domenului dinamic al fiecarei variabile


ALGORITMI GENETICI

Formularea problemei de optimizare

Formularea problemei de optimizare este de tipul

minimizeaza sau maximizeaza (se poate trece de la una la cealalta utilizand

semnul minus in fata functiei sau impartirea)

Găsește vectorul soluțiilor x

care optimizează funcția xf

supus la constrângeri de inegalitate, de egalitate și de mărginire


ALGORITMI GENETICI

Formularea problemei de optimizare - exemplificare

]10,10[x]10,10[

;,

];,[

2

2

2

121

21

D

xxxxF

xxx

Functia De Jong – 2 variabile


ALGORITMI GENETICI

Structura unui AG

Criterii de oprire:

• număr maxim de generaţii;

• limita maximă de timp;

• valoarea minimă pentru funcţia obiectiv;

• stagnarea îmbunătăţirii soluţiilor


ALGORITMI GENETICI

Initializarea populatiei Uzual, initializarea se realizeaza stocastic (aleator)

Uneori se introduc in populatia initiala catva indivizi selectati euristic

(indivizi promitatori) si se completeaza cu indivizi alesi aleator

Populatia initiala ar trebui sa conste dintr-o varietate mare a indivizilor

Marimea populatiei: moderata 50 – 500 indivizi

Marimea populatiei ar trebui să creasca liniar cu dimensiunea unui individ

(numar de gene ale cromozomului)

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

Exemplificare

]10,10[x]10,10[

;,

];,[

2

2

2

121

21

D

xxxxF

xxx

Functia De Jong – 2 variabile

6.2945 5.1548

8.1158 4.8626

-7.4603 -2.1555

8.2675 3.1096

2.6472 -6.5763

-8.0492 4.1209

-4.4300 -9.3633

0.9376 -4.4615

9.1501 -9.0766

9.2978 -8.0574

-6.8477 6.4692

9.4119 3.8966

9.1433 -3.6580

-0.2925 9.0044

6.0056 -9.3111

-7.1623 -1.2251

-1.5648 -2.3688

8.3147 5.3103

5.8441 5.9040

9.1898 -6.2625

3.1148 -0.2047

-9.2858 -1.0883

6.9826 2.9263

8.6799 4.1873

3.5747 5.0937

x1 x2

25 de indivizi generați aleator


ALGORITMI GENETICI

Ierarhizarea indivizilor Funcţia obiectiv furnizează o măsură absolută a performanţelor

fiecărui individ.

Se poate utiliza o ierarhizare a indivizilor în concordanţă cu

valoarea funcţiei obiectiv.

Cel mai bun individ are cea mai mică valoare a funcţiei obiectiv

Cel mai slab individ are cea mai mare valoare a funcţiei obiectiv

Utilizarea directă a funcţiei obiectiv pentru ierarhizarea indivizilor

poate crea dificultăţi în diferenţierea, în vederea selecției, a indivizilor

cu valori apropiate ale funcţiei obiectiv

o convergenţă prematură a algoritmului

o pierderea diversităţii populaţiei.


ALGORITMI GENETICI

Ierarhizarea indivizilor – cont

În general se utilizează o funcţie de scalare care

realizează o transformare de domeniu: valoarea funcţiei

obiectiv este transformată într-un alt domeniu mai potrivit

pentru realizarea selecţiei.

În principiu există două categorii de funcţii de

scalare:

scalare folosind explicit valorile funcţiei obiectiv

(scalare liniară, scalare de tip trunchiere sigma,

scalare pe baza funcţiei putere);

scalare pe bază de rang, liniară sau neliniară


ALGORITMI GENETICI

Ierarhizarea indivizilor utilizand functie de scalare bazata pe rang (ranking)

Populatia este ordonata in concordanta cu valoarea functiei obiectiv, fiecare

individ primind o pozitie (Poz)

Valoarea functiei de scalare atribuita fiecarui individ depinde numai de pozitia

individului in urma ordonarii si nu de valoarea functiei obiectiv

Ulterior, fiecare individ primeste o probabilitate de selectie in vederea

recombinarii depinzand de valoarea proprie a functiei de scalare si de valorile

functiei de scalare a celorlalti indivizi

selectie de presiunea -

populatiei adimensiune pozitia; -

1

1122

PS

NindPoz

Nind

PozPSPSPozS

• Cel mai adecvat individ are Poz=Nind

si cea mai mare valoare a functiei de scalare

• Cel mai putin potrivit individ are Poz=1

si cea mai mica valoare a functiei de scalare


ALGORITMI GENETICI

Ierarhizarea indivizilor - ranking– cont.

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

selectie de presiunea -

populatiei adimensiune pozitia; -

1

1122

PS

NindPoz

Nind

PozPSPSPozS


ALGORITMI GENETICI

5,1PS


ALGORITMI GENETICI

Selectia Determinarea populatiei intermediare ce contine parintii care vor fi

supusi operatorilor genetici de recombinare si mutatie - selectareaindivizilor care vor produce urmasi.

Metode:

aleatoare – in procesul de selectie sunt introdusi aleator indivizi, ingeneral prin utilizarea unor probabilitati de selectie care depind degradul de adecvare (potrivire).

Indivizii cu grad mare de adecvare au sanse mai mari de a fiselectați, astfel ca numarul de urmasi ai acestora poate fi mai maredecat al celor cu grad mai mic de adecvare

Selectia tip ruleta (esantionare stocastica cu inlocuire); selectie detip turneu, selectie proportionala.

deterministe – indivizii cu grad mare de adecvare sunt intotdeaunaselectati in defavoarea celor cu grad mai mic de adecvare: selectia printrunchiere

Elitism: supravietuirea celui mai bun dintre indivizii generatiei pana la unmoment dat – prin transferul direct a celui mai bun individ al populatiei curente inpopulatia generatiei urmatoare


ALGORITMI GENETICI

Selectia tip ruleta Algoritm stocastic

Pentru fiecare individ se calculeaza o probabilitate de selectie:

Indivizii sunt atribuiti la segmente contigue a unei linii (sau la sectoare

de cerc) astfel ca lungimea fiecarui segment (sector) sa fie

proportionala cu gradul sau de adecvare, adica cu probabilitatea de

selectie

Se genereaza un numar aleator in intervalul [0, 1] si este selectat

individul al carui segment corespunde valorii aleatoare

Procesul se repeta pana cand este selectat numarul dorit de indivizi

Procesul este asemanator rotii de ruleta in care marimea fiecarui

“sector” este proportionala cu gradul de adecvare

N

j

j

j

j

IS

ISIProb

1


ALGORITMI GENETICI

Selectia tip ruleta - cont

Dorim să selectăm 4 părinţi

pentru a participa la crearea

generaţiei viitoare.

Pentru aceasta se generează

aleator 4 numere în intervalul

[0; 1]:

0,69; 0,34; 0,15 și 0,5.

Indivizii selectati: I4, I3, I1, I3


ALGORITMI GENETICI

Selectia tip ruleta - cont

Dorim să selectăm 4 părinţi pentru a participa la crearea generaţiei

viitoare.

Pentru aceasta se generează aleator 4 numere în intervalul [0; 1]:

0,69; 0,34; 0,15 și 0,5. Indivizii selectati: I4, I3, I1, I3


ALGORITMI GENETICI

Incrucisare (Recombinare )

Produce noi indivizi (urmasi) prin combinarea informatiilor

continute de doi sau mai multi parinti

Combinarea valorilor variabilelor parintilor

Tipuri de recombinari:

discreta

pentru valori reale:

recombinare intermediara

recombinare liniara

recombinare liniara extinsa

pentru valori binare (incrucisare - crossover):

incrucisare cu un singur punct / cu doua puncte / cu puncte multiple

incrucisare uniforma

etc.


ALGORITMI GENETICI

Recombinare intermediara

U

jVar - reprezinta variabila j a urmasului

21, P

j

P

j VarVar - reprezinta variabila j a primului, respectiv a 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 P

jj

P

jj

U

j ...,,2,1,1 21

parinte

posibil urmas


ALGORITMI GENETICI

Recombinare intermediară – cont.

NvarjVaraVaraVar P

jj

P

jj

U

j ...,,2,1,1 21


ALGORITMI GENETICI

Mutatia Indivizii sunt modificati aleator

Mutatie

Pentru variabile reale

Pentru variabile binare

Mutatia pentru variabile reale

Valori create aleator sunt adaugate variabilelor reale

Trebuiesc definite:

Probabilitatea ca o variabila sa sufere o mutatie (rata de mutatie)

• Este invers proportionala cu numarul variabilelor

• O valoare optima se poate considera 1/Nvar - o singura variabila a unui

individ sufera procesul de mutatie

Marimea schimbarii variabilei prin procesul de mutatie


ALGORITMI GENETICI

Mutatia

Mutaţia realizează mici schimbări aleatoare în una sau mai multe variabile

ale individului supus mutaţiei.

Mutaţia gaussiană se poate utiliza la problemele de optimizare fără

constrângeri și constă în adăugarea unui număr ales aleator dintr-o

distribuţie gaussiană cu media 0.

Derivaţia standard a distribuţiei este precizată prin doi parametri:

scale - determină deviaţia standard pentru prima epocă,

shrink - controlează modul în care se micşorează deviaţia standard o dată cu

avansul algoritmului.

În acest fel mutaţia este mai puternică la începutul algoritmului şi tot “mai

slabă” pe măsură ce algoritmul avansează și se creează generaţii noi.


ALGORITMI GENETICI

Mutatia – cont.

În generaţia k, pentru variabila j a părintelui supus mutației:

kjj

P

j

C

j scaledrVarVar

rj - aleator ales dintr-o distribuţie gaussiană normală cu centrul în

zero;

dj - reprezintă mărimea domeniul în care ia valori această variabilă,

adică min,max, jjj VarVard

N

kshrinkscalescalek 1

N - numărul maxim de generaţii ales ca şi condiţie de oprire


ALGORITMI GENETICI

Mutatia – cont.Exemplificare

100N 50k scale=1, shrink=1

5,0100

5011150

scale

domeniul de valori este [-10; 10] 2021 dd

05,01 r

2,02 r

5,2)5,02005,0(31 CVar

1)5,020)2,0((12 CVar

N

kshrinkscalescalek 1

kjj

P

j

C

j scaledrVarVar


ALGORITMI GENETICI

Crearea noii populatii

Există 3 modalităţi de creare a urmasilor:

• supraviețuire de tip elitist;

• încrucișare;

• mutaţie.

Noua generaţie poate să provină din fracţiuni create prin fiecare dintre

cele trei modalităţi, aplicate asupra indivizilor din populația curentă.

În general, cea mai mare pondere o are operatorul de încrucişare.

Operatorii de mutaţie se pot aplica fie asupra unor indivizi din populația

curentă, fie asupra unor indivizilor rezultaţi în urma încrucişarii.

Prin supraviețuire de tip elitist, un număr specificat de indivizi, cei mai

buni din populaţia curentă, trec automat în noua populatie.


ALGORITMI GENETICI

algoritmi genetici - bel.utcluj.ro · adecvati indivizi si combinarea acestora pentru a da nastere...

Documents