inteligenţă artificială -...

Inteligenţă artificială

4. Metode de optimizare Florin Leon

Universitatea Tehnică „Gh. Asachi” 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

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 (selection)

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

Încrucişarea (crossover)

Descompune două soluţii şi combină aleatoriu fragmentele rezultate pentru a forma noi soluţii

Mutaţia (mutation)

Modifică aleatoriu o soluţie potenţială


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 Cea mai populară tehnică

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 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 practic 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 Violarea constrângerii

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

Codarea Gray

Problema falezei Hamming

01111111 127

10000000 128

Codarea Gray

01111111 devine 01000000

10000000 devine 11000000


27

Reprezentarea întreagă / reală

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

Variabile în virgulă mobilă

f(x,y) = x2 + y2

De exemplu un cromozom poate fi o pereche (x, y) = (0.12, 0.51)


28

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ă


29

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

permutaţie 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”

Cromozom: 0.12, 0.65, 0.87, 0.02, 0.35

Decodare: 2, 4, 5, 1, 3

Indexul fiecărei gene în şirul sortat

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

31







3. Concluzii


32

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”)

Turnir (engl. “tournament”)


33

Ruleta (I)

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 indivizi

fitness(A) = 3

fitness(B) = 1

fitness(C) = 2

A C

1/6 = 17%

3/6 = 50%

B 2/6 = 33%


34

Ruleta (II)

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


35

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


36

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)

Prea multă explorare, prea puţină exploatare


37

Transpunerea funcţiei de adaptare (I)

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

> 0 poate fi fitness-ul minim în generaţia curentă (sau în ultimele n generaţii) Creşte presiunea selectivă, favorizează indivizii foarte

adaptaţi

Pentru convergenţă lentă

< 0 Scade presiunea selectivă, favorizează indivizii cu

adaptare medie

Pentru convergenţă prematură


38

Efectele scalării fitness-ului


39

Transpunerea funcţiei de adaptare (II)

Scalarea sigma:

f’(i) = max( f(i) - (μf - cf ), 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ă


40

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ă)


41

Selecţia bazată pe ranguri

Populaţie cu N indivizi

Cel mai adaptat individ primeşte rangul N-1, cel mai puţin adaptat primeşte rangul 0

Sortarea populaţiei presupune calcule suplimentare


42

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


43

Selecţia prin turnir (I)

Ruleta şi rangul se bazează pe statisticile globale ale populaţiei Pot apărea probleme la paralelizare

Ideea fundamentală: Se aleg aleatoriu k membri 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 selecţiile prin ruletă şi ranguri


44

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 (mating pool)?

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

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

Turnir determinist sau probabilistic


45

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 ex. k = 4, p = 0.7 p1 = 70%

p2 = 21%

p3 = 6%

p4 = 3%


46

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ă


47

Î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

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

De obicei în intervalul (0.75, 0.95)

Dacă se foloseşte elitismul, poate fi 1


48

Î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ă unul sau doi copii prin unirea extremelor


49

Operatori alternativi de încrucişare

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

Subiectivitatea poziţională (engl. “positional bias”)


50

Î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ă


51

Î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


52

Încrucişarea cu valori reale

Discretă Valoarea fiecărei gene în copilul z vine de la un părinte (x,y)

cu probabilităţi egale: zi = xi sau yi

Se poate folosi încrucişarea cu 1 punct, n puncte sau uniformă

Aritmetică Se creează copii „între” părinţi:

zi = xi + (1 - ) yi , cu 0 1

Parametrul poate fi:

Constant

Aleatoriu


53

Încrucişarea cu permutări (I)

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

S-au descoperit numeroşi operatori care combină 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


54

Încrucişarea cu permutări (II)

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

Se alege un fragment arbitrar din primul părinte

Se copie fragmentul în (primul) copil

Se copie 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


55

Încrucişarea cu permutări (III)

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

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


56

Mutaţia

Se modifică fiecare genă independent cu o probabilitate pm numită rată de mutaţie Între 1 / d şi 1 / lc

d = dimensiunea populaţiei, lc = lungimea cromozomului

De obicei 1-2%

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

Prea multe mutaţii căutare aleatorie


57

Mutaţia reală

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

„Reglarea” valorii unei gene De obicei gaussiană

Media: valoarea veche

Deviaţia standard: definită de utilizator

Liniară Valoarea veche q%


58

Mutaţia pentru 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


59

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


60

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


61

Mutaţia prin distorsionare

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


62

Încrucişare sau mutaţie?

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ă”


63

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 populaţia a convers

Raportul dinte cel mai mare fitness şi fitness-ul mediu (sau cel mai mic) scade sub un prag

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


64

Alegerea parametrilor

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

Euristică: dimensiunea populaţiei trebuie să fie 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


65

Exemplu de convergenţă


66







3. Concluzii


67

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 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

68

Abordarea convenţională

Sumă ponderată f(x) = w1f1(x1) + w2f2(x2) +…+ wnfn(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


69

Algoritmi genetici multiobiectiv

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


70

Exemplu: dominanţa Pareto

Minimizarea costului ş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


71

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


72

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


73

NSGA-II

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

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

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

Reuneşte populaţia veche cu populaţia nouă


74

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


75

NSGA-II: Sortarea

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


76

NSGA-II: Distanţa de aglomerare

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ă)


77

NSGA-II: Distanţa de aglomerare

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ă ∞


78

NGSA-II: Exemplu

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


79

Exemplu: Front Pareto concav


80

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


81

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ţia 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


82







3. Concluzii


83

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ă, pc pv

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

Se alege vecinul cel mai bun (Steepest Ascent HC)


84

Exemplu


85

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


86

Probleme

Optime locale

Creste

Platouri


87

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 m ori cu puncte de start diferite (aleatorii) şi se alege în final soluţia cea mai bună


88

Călirea simulată

Algoritm stohastic inspirat din călirea metalurgică

Încălzirea şi apoi răcirea controlată a unui material

înainte după


89

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)


90

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, 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)


91

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, 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


92

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ă

3. Scăderea mai lentă a temperaturii: T = T / (1 + β) β are o valoare foarte mică E suficientă o singură iteraţie la un nivel de temperatură

4. 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


93

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


94

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


95

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


inteligenţă artificială -...

Documents