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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
3
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
4
Întâmplarea poate genera lucruri interesante
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
5
Întâmplarea poate genera lucruri interesante
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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?
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
13
Teorema “No Free Lunch”
Robusteţe x Eficienţă = Constantă
Generalitate x Adâncime = Constantă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
15
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
16
Codarea
Depinde de problemă
Cele mai utilizate tipuri de codare:
Binară
Reală
Cu permutări
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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:
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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;
}
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
26
Codarea Gray
Problema falezei Hamming
01111111 127
10000000 128
Codarea Gray
01111111 devine 01000000
10000000 devine 11000000
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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”)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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%
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
38
Efectele scalării fitness-ului
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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%
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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”)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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%
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
61
Mutaţia prin distorsionare
Se alege o submulţime de gene şi se rearanjează aleatoriu alelele din poziţiile respective
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
65
Exemplu de convergenţă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
66
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
75
NSGA-II: Sortarea
Scopul (incluzând elitismul): selectarea celor mai buni n cromosomi din populaţia de dimensiune 2n
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă ∞
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
78
NGSA-II: Exemplu
Minimizare: f1(x,y) = x f2(x,y) = (1+y) / x
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
79
Exemplu: Front Pareto concav
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
82
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
86
Probleme
Optime locale
Creste
Platouri
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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ă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
88
Călirea simulată
Algoritm stohastic inspirat din călirea metalurgică
Încălzirea şi apoi răcirea controlată a unui material
înainte după
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
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
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm