Inteligenta artificiala: Metode de optimizare. Algoritmi evolutivi

Inteligenţă artificială

4. Metode de optimizare Florin Leon

Universitatea Tehnică „Gheorghe Asachi” din Iaşi

Facultatea de Automatică şi Calculatoare

http://florinleon.byethost24.com/curs_ia.htm

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

2

Metode de optimizare

1. Algoritmi evolutivi 1.1. Întâmplare şi scop

1.2. Codarea problemei

1.3. Operatori: selecţia, încrucişarea, mutaţia

1.4. Optimizări multiobiectiv: NSGA-II

2. Gradientul descendent şi călirea simulată

3. Concluzii


3







3. Concluzii


4

Întâmplarea poate genera lucruri interesante


5

Întâmplarea poate genera lucruri interesante


6

Prezentare generală

Un algoritm evolutiv este o metodă de căutare prin analogie cu selecţia naturală biologică

Un AE are o populaţie de soluţii potenţiale care evoluează prin aplicarea iterativă a unor operatori stohastici

Evoluţia soluţiilor mai bune se realizează pe baza presiunii evolutive (favorizarea soluţiilor mai adaptate)


7

Metafora evolutivă

Natură Algoritm evolutiv

Mediu Problema de optimizare

Indivizii care trăiesc în mediu

Soluţii potenţiale fezabile

Gradul de adaptare al individului la mediu

Calitatea soluţiei (funcţia de adaptare / fitness)


8

Evoluţia naturală

Speciile nu au ca „scop” evoluţia

Evoluţia este doar un efect, o consecinţă

Organismele neadaptate mor sau mor fără să se reproducă

Cele care supravieţuiesc suficient ca să se reproducă reuşesc acest lucru tocmai fiindcă sunt mai adaptate la mediu

Selecţia naturală şi selecţia sexuală


9

Operatori genetici

Selecţia (engl. “selection”)

Alege un individ cu o probabilitate definită de calitatea relativă a acestuia

Încrucişarea (engl. “crossover”)

Combină aleatoriu fragmente din 2 indivizi pentru a forma unii noi

Mutaţia (engl. “mutation”)

Modifică aleatoriu un individ nou creat


10

Componentele şi fazele unui algoritm evolutiv

Problema de rezolvat

Principii de codare: gene, cromozomi

Procedura de iniţializare

Selecţia părinţilor, reproducere

Operatorii genetici: încrucişare, mutaţie

Funcţia de adaptare

Condiţia de terminare

Iniţializare populaţie

Selecţie părinţi pentru reproducere

Încrucişare

Introducere copil în populaţie

Rezultat

Mutaţie

da

nu

Stop?


11

Algoritmii evolutivi şi algoritmii specializaţi

Algoritm evolutiv Algoritm specializat

Viteză

Efort

Aplicabilitate

Performanţă

În general lent În general rapid

Foarte mic De obicei mare

Generală Redusă la o clasă de probleme

Bună,

creşte în timp De obicei foarte bună


12

Teorema “No Free Lunch”

Oricare două euristici sunt echivalente când performanţele lor medii sunt considerate pe mulţimea tuturor problemelor posibile

Nicio euristică nu este mai bună în medie decât căutarea oarbă

Consecinţe

Performanţe excelente, robusteţe mică

Performanţe slabe, robusteţe mare


13

Teorema “No Free Lunch”

Robusteţe x Eficienţă = Constantă

Generalitate x Adâncime = Constantă


14

Tipuri de algoritmi evolutivi

Algoritmi genetici

Codarea soluţiei cu şiruri de numere, de obicei binare

Strategii evolutive

Codarea soluţiei cu vectori de numere reale

Programare genetică

Soluţiile sunt programe (de obicei Lisp)


15







3. Concluzii


16

Codarea

Depinde de problemă

Cele mai utilizate tipuri de codare:

Binară

Reală

Cu permutări


17

Exemplu de codare binară

Problema rucsacului: umplerea unui rucsac cu o mulţime de obiecte astfel încât valoarea totală a articolelor incluse să fie maximizată

Constrângere: capacitatea rucsacului este limitată


18

Problema rucsacului

wi – greutatea articolului i

pi – profitul când articolul i este inclus

C – capacitatea rucsacului

xi – 1 dacă articolul i este inclus, 0 altfel

Obiectiv: maximizarea

Constrângere:


19

Codarea binară

De exemplu 6 articole incluse sau nu

O genă = un bit (xi)

Aléle = valori posibile ale genei (0 şi 1)

Un cromozom – un şir de gene (biţi)

Cromozomul este o soluţie potenţială

011001 articolele 2, 3 şi 6 incluse


20

Decodarea: funcţia de adaptare / fitness

Funcţia de adaptare defineşte problema

Spune cât este de bună o soluţie (cât este de adaptat un cromozom)

Cromozom: 011001

Constrângere: w = 50 + 45 + 5 = 100 C = 100 (ok)

Funcţia de adaptare: p = 35 + 18 + 2 = 55


21

Satisfacerea constrângerilor

Cromozom: 111001

Constrângere: w = 100 + 50 + 45 + 5 = 200 > C = 100 Constrângerea nu este satisfăcută

Modalităţi posibile de rezolvare: Respingerea soluţiei: funcţia de adaptare F = -1000000

Reduce diversitatea genetică

Repararea soluţiei: câte o genă 1 devine 0 până este satisfăcută constrângerea

Optimizarea hibridă: întâi după greutate (-w) apoi după profit Funcţia de adaptare F = -200


22

Reprezentarea întreagă / reală

Multe probleme de optimizare implică numere întregi sau reale De exemplu minimizarea funcţiei f(x,y) = x2 + y2

Valorile întregi sau reale pot fi codate binar n = 6 110

r = 3.14 în domeniul [1, 10], pe 8 biţi, reprezentare în virgulă fixă

1 0000 0000 (0)

10 1111 1111 (255)

r = 3.14 (3.14 – 1) · 255 / (10 – 1) = 60 0011 1100

0011 1100 3.12 (precizia creşte cu numărul de biţi)


23

Faleza Hamming

O problemă a codării binare este aşa-numita „faleză Hamming” (engl. “Hamming cliff”)

01111111 127

10000000 128

Există o breşă în reprezentare care nu există în problema originară


24

Codul Gray reflectat 0 0 0 0 0

1 0 0 0 1

2 0 0 1 1

3 0 0 1 0

4 0 1 1 0

5 0 1 1 1

6 0 1 0 1

7 0 1 0 0

8 1 1 0 0

9 1 1 0 1

10 1 1 1 1

11 1 1 1 0

12 1 0 1 0

13 1 0 1 1

14 1 0 0 1

15 1 0 0 0

0 0 0

1 0 1

2 1 1

3 1 0

0 0 0 0

1 0 0 1

2 0 1 1

3 0 1 0

4 1 1 0

5 1 1 1

6 1 0 1

7 1 0 0


25

Conversia Gray – binară

unsigned short binaryToGray(unsigned short num)

{

return (num>>1) ^ num;

}

unsigned short grayToBinary(unsigned short num)

{

unsigned short temp = num ^ (num>>8);

temp ^= (temp>>4);

temp ^= (temp>>2);

temp ^= (temp>>1);

return temp;

}


26

Faleza Hamming

engl. “Hamming cliff”

Codare binară standard

127 01111111

128 10000000

Codarea Gray

127 01000000

128 11000000


27

Reprezentarea întreagă / reală

Este mai bine să codăm variabilele numerice direct ca: Întregi

Variabile în virgulă mobilă

De exemplu: f(x,y) = x2 + y2

Un cromozom poate fi o pereche (x, y) = (0.12, 0.51)


Exemple: funcţii reale de test

Funcţia sferă

28 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm


Funcţia Rastrigin generalizată



Funcţia Ackley generalizată

Alte funcţii sunt prezentate în suportul de curs sau la adresa: http://en.wikipedia.org/wiki/Test_functions_for_optimization



Funcţia Ackley generalizată


32

Reprezentarea prin permutări

Unele probleme necesită ca obiectele să fie aranjate într-o anumită ordine

Exemple:

Algoritmii de sortare: ce elemente apar înaintea altora

Ordinea

Problema comis-voiajorului (engl. “Travelling Salesman Problem”, TSP): ce elemente apar unul lângă altul

Adiacenţa

Aceste probleme sunt reprezentate mai bine cu ajutorul permutărilor

Dacă avem n variabile, reprezentarea este o listă de n întregi, fiecare apărând o singură dată


33

Exemplu: TSP

Problema Se dau n oraşe Să se găsească un tur

complet de lungime minimă

Codarea Oraşele sunt numerotate

1, 2, … , n Un tur complet este o

permutare De ex. dacă n = 5, atunci

[1,2,3,4,5] şi [3,4,5,2,1] sunt valide

Spaţiul de căutare este foarte mare Pentru 30 de oraşe există

30! 1032 tururi posibile


Codarea cu chei aleatorii

engl. “random key encoding”

Indexul fiecărei gene în şirul sortat crescător

Exemplu:

Cromozom: 0.12, 0.65, 0.87, 0.02, 0.35

Decodare: 2, 4, 5, 1, 3


35







3. Concluzii


36

Selecţia

Operatorul de selecţie alege un părinte (cromozom) pentru noua generaţie, pe baza funcţiei de adaptare

Selecţia acţionează la nivel de individ

Este independentă de reprezentare

Tipuri de selecţie:

Ruletă (engl. “roulette-wheel”)

Bazată pe ranguri (engl. “rank”)

Eşantionare universală stohastică (engl. “stochastic universal sampling”)

Turnir (engl. “tournament”)

...şi altele


37

Ruleta

Ideea de bază: indivizii mai adaptaţi au şanse mai mari Şansele sunt proporţionale cu adaptarea

Implementare Se atribuie fiecărui individ o parte a ruletei

Se „învârte” ruleta de n ori pentru a se alege n părinţi

fitness(A) = 3

fitness(B) = 1

fitness(C) = 2

A C

1/6 = 17%

3/6 = 50%

B 2/6 = 33%


38

Implementare

Fie S suma tuturor funcţiilor de adaptare (ale tuturor indivizilor din populaţie)

Se generează un număr aleatoriu N între 1 şi S Se returnează cromozomul a cărui funcţie de adaptare adăugată

la suma parţială este ≥ N

Cromozom: 1 2 3 4 5 6 Fitness: 8 2 17 7 4 11 Suma parţială: 8 10 27 34 38 49 N (1 N 49): 23 Selectat: 3


39

Domeniul funcţiei de adaptare

Convergenţă prematură

Fitness prea mare

Genele unui individ foarte adaptat „cuceresc” populaţia dacă restul indivizilor sunt mai puţin adaptaţi

Algoritmul converge într-un optim local

Prea puţină explorare, prea multă exploatare


40

Domeniul funcţiei de adaptare

Convergenţă lentă

Fitness prea mic

După multe generaţii, fitness-ul mediu a convers, dar nu s-a găsit un optim global

Nu există suficientă diferenţă între fitness-ul maxim şi fitness-ul mediu

Presiune selectivă redusă (necompetitivitate)

Presiunea selectivă variază invers cu şansa de a fi ales

Prea multă explorare, prea puţină exploatare


41

Transpunerea funcţiei de adaptare (I)

Scalarea fitness-ului f’(i) = f(i) –

> 0 Creşte presiunea selectivă, favorizează indivizii

foarte adaptaţi

Soluţie pentru convergenţa lentă

poate fi fitness-ul minim din generaţia curentă (sau din ultimele n generaţii)

< 0 Scade presiunea selectivă, favorizează indivizii cu

adaptare medie

Soluţie pentru convergenţa prematură


42

Efectele scalării fitness-ului


43

Transpunerea funcţiei de adaptare (II)

Scalarea sigma:

f’(i) = max( f(i) – (μf – c f ), 0)

μf este media valorilor funcţiilor de adaptare

f este deviaţia standard a valorilor

c este o constantă, de obicei 2

Regula 3 sigma: 68 – 95 – 99.7

μf – 2f reprezintă fitness-ul minim acceptat pentru ca individul să se poată reproduce

Creşte presiunea selectivă


44

Rangul funcţiei de adaptare

Indivizii sunt numerotaţi în ordinea crescătoare a fitness-ului

Valoarea efectivă a fitness-ului este mai puţin importantă, contează rangul în populaţie

Probabilităţile de selecţie se bazează pe fitness-ul relativ, nu absolut

Numărul de start şi incrementul influenţează rezultatele

1,2,3,4,... (presiune selectivă mai mare)

10,12,14,16,... (presiune selectivă mai mică)


45

Selecţia bazată pe ranguri

Populaţie cu N indivizi

Abordarea tipică: cel mai adaptat individ primeşte rangul N – 1, cel mai puţin adaptat primeşte rangul 0

Sortarea populaţiei presupune calcule suplimentare


46

Ordonarea liniară

Σ P(i) = 1 α = 2 – β şi 1 β 2

De exemplu: α = 0, β = 2

α determină numărul de urmaşi ai celui mai puţin adaptat individ


Eşantionarea universală stohastică

Selecţia prin ruletă alege indivizi prin eşantionări repetate

EUS utilizează o singură valoare aleatorie r pentru alegerea tuturor indivizilor, la intervale echidistante

Dacă trebuie aleşi N indivizi, se folosesc N intervale

În figură: N = 4, i = 0 .. N – 1


48

Selecţia prin turnir (I)

Ruleta şi rangul se bazează pe statisticile globale ale populaţiei

Paralelizarea este mai dificilă

Ideea de bază a selecţiei prin turnir:

Se aleg aleatoriu k indivizi din populaţie şi se determină cel mai adaptat dintre aceştia

Se repetă procedura pentru a selecta mai mulţi părinţi

Mai rapidă decât metodele de selecţie prin ruletă sau ranguri


49

Selecţia prin turnir (II)

Probabilitatea selectării individului i depinde de:

Rangul lui i

Dimensiunea eşantionului k

Un k mai mare creşte presiunea selectivă

Participanţii selectaţi rămân în bazinul de împerechere (engl. “mating pool”)?

Dacă nu rămân, creşte presiunea selectivă

Cel mai adaptat individ din turnir câştigă întotdeauna?

Turnir determinist sau probabilistic


50

Turnirul probabilistic

Se alege cel mai adaptat individ cu probabilitatea p

Se alege al doilea cel mai adaptat individ cu probabilitatea p (1 – p)

Se alege al treilea cel mai adaptat individ cu probabilitatea p (1 – p)2

… şi aşa mai departe

De exemplu: k = 4, p = 0.7 p1 = 70%

p2 = 21%

p3 = 6%

p4 = 3%


51

Elitismul

Cel mai adaptat individ este copiat direct în noua populaţie

Sau primii cei mai adaptaţi (mai rar)

Asigură faptul că niciodată nu se va pierde soluţia cea mai bună


52

Încrucişarea

Încrucişarea combină 2 cromozomi părinţi pentru a produce un nou cromozom fiu

Noul cromozom poate fi mai bun decât ambii părinţi dacă ia cele mai bune caracteristici de la fiecare părinte

Se pot produce 1 sau 2 indivizi noi

Încrucişarea are loc cu o probabilitate definită de programator: rata de încrucişare

Trebuie să fie mare, de obicei în intervalul (0.75, 0.95)

Dacă se foloseşte elitismul, poate fi 1


53

Încrucişarea cu un punct

Se alege un punct aleatoriu în cei doi părinţi

Se divid părinţii la punctul de încrucişare

Se creează 1 sau 2 copii prin unirea extremelor


54

Subiectivitatea poziţională

engl. “positional bias”

Performanţele încrucişării cu un punct depind de ordinea în care sunt reprezentate variabilele

Este mai probabil să se menţină împreună genele alăturate

Nu se pot menţine împreună genele de la capetele diferite ale şirului


55

Încrucişarea cu n puncte

Generalizarea încrucişării cu 1 punct

Se aleg aleatoriu n puncte de încrucişare

Se divid părinţii conform acestor puncte

Se reunesc fragmentele, alternativ

Tot mai există o subiectivitate poziţională


56

Încrucişarea uniformă

Se generează o mască uniformă Masca determină ce biţi sunt copiaţi de la fiecare

părinte Densitatea biţilor din mască determină cantitatea de

material genetic luat de la fiecare părinte


57

Încrucişarea reală

Aritmetică: se creează copíi „între” părinţi: zi = xi + (1 – ) yi , cu 0 1

este o variabilă aleatorie

Euristică: dă mai multe şanse părintelui mai adaptat z = x2 + (x2 – x1)

x2 este părintele mai adaptat: F(x2) ≥ F(x1)


58

Încrucişarea cu permutări

Încrucişarea „normală” va crea de obicei soluţii invalide

Operatorul de încrucişare trebuie să combine informaţiile de ordine sau adiacenţă de la părinţi

1 2 3 4 5

5 4 3 2 1

1 2 3 2 1

5 4 3 4 5


59

Încrucişarea cu permutări

Ideea este păstrarea ordinii relative în care apar elementele

Se alege un fragment arbitrar din primul părinte

Se copiază fragmentul în (primul) copil

Se copiază numerele care nu există în primul fragment în (primul) copil

Se începe de la punctul de diviziune

Folosind ordinea din al doilea părinte

Analog pentru al doilea copil, dacă este cazul, cu rolurile părinţilor inversate


60

Exemplu

Se copiază fragmentul selectat din primul părinte: 1, 2, 3, 4

Se copiază restul din al doilea părinte în ordine: 9, 7, 8, 6, 5


61

Mutaţia

Se modifică fiecare genă în mod independent cu o probabilitate pm numită rată de mutaţie Trebuie să fie mică, de obicei 1-2%

Poate avea valori între 1 / d şi 1 / lc unde d este dimensiunea populaţiei iar lc este lungimea cromozomului

Compromis: Prea puţine mutaţii convergenţă prematură (optim local)

Prea multe mutaţii căutare aleatorie


62

Mutaţia reală

Resetarea valorii unei gene la un număr aleatoriu din domeniul ei de definiţie

Reglarea valorii unei gene Gaussiană

Media: valoarea veche

Deviaţia standard: definită de utilizator

Liniară Valoarea veche q%


63

Mutaţia cu permutări

Operatorii normali de mutaţie conduc la soluţii invalide

Mutaţia pentru permutări trebuie să modifice cel puţin 2 gene

Rata de mutaţie reflectă aici probabilitatea modificării întregului şir, nu a genelor individuale


64

Mutaţia prin interschimbare

Se aleg aleatoriu 2 gene şi li se interschimbă poziţiile

Păstrează majoritatea informaţiilor de adiacenţă (4 legături rupte), afectează mai mult ordinea


65

Mutaţia prin inversiune

Se aleg aleatoriu 2 gene şi se inversează subşirurile dintre ele

Păstrează majoritatea informaţiilor de adiacenţă (numai 2 legături rupte), afectează foarte mult ordinea


66

Mutaţia prin distorsionare

Se alege o submulţime de gene şi se rearanjează aleatoriu alelele din poziţiile respective


67

Încrucişarea şi mutaţia

Au funcţii diferite

Doar încrucişarea poate combina informaţiile de la părinţi

Doar mutaţia poate introduce noi informaţii (alele) în populaţie

Încrucişarea nu schimbă frecvenţa alelelor din populaţie

Pentru a atinge optimul global, de multe ori este nevoie de o mutaţie „norocoasă”


68

Exemplu de convergenţă


69

Criterii de terminare

Problema finală este de a decide când să se termine execuţia algoritmului

Mai multe soluţii posibile:

După un număr prestabilit de generaţii

Cel mai utilizat criteriu

Când algoritmul a convers

Raportul dintre fitness-ul maxim şi fitness-ul mediu (sau minim) scade sub un prag

Îmbunătăţirea fitness-ului mediu timp de două (sau mai multe) generaţii scade sub un prag


70

Alegerea parametrilor

Dimensiunea populaţiei poate fi în jur de 50, dar pentru probleme dificile poate fi mai mare

Euristică: dimensiunea populaţiei poate fi aproximativ numărul de gene x 10

Prea puţini cromozomi algoritmul nu are diversitatea necesară găsirii soluţiei

Prea mulţi cromozomi algoritmul va fi mai lent, fără a se îmbunătăţi calitatea soluţiei

Numărul maxim de generaţii variază de obicei între 100-1000


71







3. Concluzii


72

Optimizarea multiobiectiv

Multe probleme reale (sau majoritatea) implică optimizarea mai multor obiective, de multe ori contradictorii

De exemplu minimizarea costului unui produs şi maximizarea calităţii sale (simultan)

Cost mai bine

Compromisuri acceptabile


73

Abordarea convenţională

Sumă ponderată f(x) = w1 f1(x1) + w2 f2(x2) +…+ wn fn(xn)

Σ wi = 1

Avantajul principal: simplitatea Se poate aplica un algoritm scalar

Probleme Determinarea ponderilor

Obiectivele diferite măsoară diferite aspecte ale calităţii soluţiei şi deseori este greu de stabilit importanţa lor relativă

Returnează o singură soluţie la un moment dat

Unele soluţii sunt imposibil de găsit

Detalii mai târziu


74

Algoritmi genetici multiobiectiv

engl. “Multi-Objective Genetic Algorithms”, MOGA

Se bazează pe conceptul de dominanţă Pareto

O soluţie S1 domină o soluţie S2 dacă şi numai dacă:

S1 nu este inferioară lui S2 în raport cu toate obiectivele

S1 este strict superioară lui S2 în raport cu cel puţin un obiectiv

Mulţimea tuturor soluţiilor nedominate se numeşte frontul Pareto


75

Exemplu: dominanţa Pareto

Minimizarea costului de testare şi a numărului de defecte ale unui produs software

Soluţiile A, B, C sunt nedominate Soluţia X este dominată de A Soluţia Y este dominată de B


76

Estimarea frontului Pareto

În fiecare generaţie, mulţimea indivizilor nedominaţi este o estimare a frontului Pareto real (necunoscut)

MOGA returnează cea mai bună estimare a frontului Pareto

Întrucât mulţimea de soluţii reprezintă diferite compromisuri între obiective, utilizatorul poate alege


77

Ponderarea (continuare)

Prin ponderare, unele soluţii sunt imposibil de găsit Poderarea este sensibilă la forma frontului Pareto De exemplu: F = w1f1 + w2f2

Front convex: fiecare punct de pe frontul Pareto este un minim stabil şi poate fi determinat prin schimbarea ponderilor

Front concav: doar cele 2 capete ale frontului Pareto sunt minime stabile şi pot fi determinate


78

Front Pareto convex

Minimizare: f1(x,y) = x f2(x,y) = (1+y) / x


79

Front Pareto concav


80

NSGA-II

Un algoritm „rapid, elitist, cu sortare nedominată” (Deb et al., 2000)

O meta-euristică: utilizează un algoritm evolutiv simplu la care se adaugă calcularea frontului Pareto

Generează noua populaţie folosind selecţia prin turnir, încrucişări şi mutaţii normale

Reuneşte populaţia veche cu populaţia nouă şi selectează cei mai adaptaţi indivizi


81

NSGA II: Fronturi Pareto

Sortare nedominată a populaţiei pe ranguri, astfel încât membrii de rang n domină toţi membrii de rang > n

Membrii de rang 1 constituie mulţimea nedominată, adică aproximarea curentă a frontului Pareto


82

NSGA-II: Sortarea

Scopul (incluzând elitismul): selectarea celor mai buni n cromozomi din populaţia de dimensiune 2n


83

NSGA-II: Distanţa de aglomerare

engl. “crowding distance” Indivizii care aparţin aceluiaşi front sunt sortaţi pe baza

„aglomerării” Un individ mai bun are o distanţă de aglomerare mai mare Efectul este selecţia indivizilor aflaţi în regiuni mai puţin aglomerate Previne omogenizarea soluţiilor (convergenţa prematură)

suma acestor distanţe este distanţa de aglomerare


84

NSGA-II: Distanţa de aglomerare

engl. “crowding distance” Indivizii care aparţin aceluiaşi front sunt sortaţi pe baza

„aglomerării” Un individ mai bun are o distanţă de aglomerare mai mare Efectul este selecţia indivizilor aflaţi în regiuni mai puţin aglomerate Previne omogenizarea soluţiilor (convergenţa prematură)

pentru extreme, distanţa se consideră ∞


85

Aplicaţii ale AE

Proiectare

Design molecular

Invenţii biomimetice

Hardware evolutiv

Rutare în telecomunicaţii

Rutarea mărfurilor

Analiză cinetică chimică

Criptare

Jocuri

Generator de glume

Strategii financiare

Marketing

http://brainz.org/15-real-world-applications-genetic-algorithms


86

Concluzii - AE

Concept uşor de înţeles

Rezolvă probleme complexe

Acceptă funcţii nediferenţiabile

Găsesc optimul global

Optimizează funcţii multiobiectiv

Prezintă robusteţe (căutare paralelă, populaţie de soluţii)

Uşor de paralelizat şi distribuit

Soluţia se îmbunătăţeşte în timp

Uneori sunt foarte lenţi, mai lenţi decât algoritmii specializaţi

Găsirea unei soluţii bune într-un interval mare de timp înseamnă lipsa unei soluţii bune într-un interval de timp acceptabil


87







3. Concluzii


88

Tehnici alternative de optimizare: Gradientul descendent

engl. “hill climbing”

~ gradient ascendent, dacă funcţia este continuă şi este maximizată, gradient descendent dacă este minimizată

Se pleacă dintr-un punct ales aleatoriu din spaţiul de căutare p0

Punctul curent pc p0

Se generează unul sau mai multe puncte vecine pv

Dacă funcţia obiectiv într-un punct vecin este mai bună decât cea curentă, atunci pc pv

Se alege primul vecin mai bun (Greedy, Simple HC)

Se alege vecinul cel mai bun (Steepest Ascent HC)


89

Exemplu


90

Hill climbing cu AE

Pe baza unui cromozom, se generează un număr de n vecini folosind numai mutaţia

Se alege vecinul cu funcţia de adaptare cea mai bună, care devine cromozomul curent

Se repetă paşii până la îndeplinirea condiţiei de oprire


91

Probleme

Optime locale

Creste

Platouri


92

HC cu puncte multiple de start

Rezultatul metodei HC depinde de punctul de start p0

Soluţie: HC cu puncte multiple de start (engl. “multiple-point hill climbing”)

Se repetă procedura de HC de m ori cu puncte de start diferite (aleatorii) şi se alege în final soluţia cea mai bună


93

Călirea simulată

engl. “simulated annealing”

Algoritm stohastic inspirat din călirea metalurgică

Încălzirea şi apoi răcirea controlată a unui material creşte dimensiunea cristalelor şi reduce defectele

înainte după


94

Călirea simulată

Căldura face ca atomii să îşi piardă poziţiile fixe (minimul local al energiei interne) şi să viziteze aleatoriu stări cu energie mai ridicată

Răcirea lentă le dă mai multe şanse să găsească o configuraţie cu o energie internă mai mică decât cea iniţială (corespunzătoare minimului global al problemei de optimizare)


95

Descriere

Procedură asemănătoare cu HC

Dar se poate trece şi într-o stare inferioară cu o anumită probabilitate

Dacă vecinul este mai bun, atunci pc pv

Dacă starea curentă este mai bună decât starea următoare (a vecinului)

Se calculează diferenţa funcţiilor obiectiv: ΔE = Ec – Ev

Se consideră temperatura curentă T, mare la început şi care scade în timp

Probabilitatea de a accepta tranziţia în starea inferioară este: P = exp(–ΔE / T)


96

Programul de călire

Temperatura iniţială este mare (teoretic infinită) şi tinde în timp la 0

Dacă programul de răcire este suficient de lung (teoretic infinit), algoritmul garantează găsirea optimului global

De asemenea, trebuie să existe suficiente iteraţii la fiecare nivel de temperatură

Un număr exponenţial de paşi în raport cu dimensiunea problemei


97

Metode practice de răcire

1. Scăderea liniară a temperaturii

2. Scăderea geometrică: T = T ∙ α

Temperatura iniţială poate fi 1000, 10000

α < 1, de obicei între 0.8 şi 0.99 (mai bine mai mare)

Un număr constant de iteraţii la fiecare temperatură

Dacă α este mare, este suficientă o singură iteraţie la un nivel de temperatură

3. Se începe cu o temperatură foarte mare şi se răceşte rapid până când 60% din soluţiile mai proaste sunt acceptate

Aceasta este temperatura reală de start şi răcirea se face apoi mai lent


98

Comportament

La început, la temperaturi mari, există o probabilitate mai mare de acceptare a unor stări inferioare

Algoritmul poate ieşi din vecinătatea unui optim local

Spre final, algoritmul devine asemănător cu HC

Încearcă găsirea punctului optim din vecinătate, care ar putea fi optimul global


99

Criterii de terminare

1. Când T se apropie de 0

Cu o scădere geometrică, T nu atinge 0 niciodată

2. Când nu se mai fac tranziţii, nici în stări mai bune nici mai rele


100

Concluzii

Algoritmul gradientului descendent este foarte simplu de implementat

Are probleme cu optimele locale

Călirea simulată are ca obiectiv găsirea optimului global

Performanţele depind mult de alegerea parametrilor


Inteligenta artificiala: Metode de optimizare. Algoritmi evolutivi

Documents

Transcript of Inteligenta artificiala: Metode de optimizare. Algoritmi evolutivi