metode inteligente de rezolvare a problemelor...
Post on 27-Sep-2019
18 Views
Preview:
TRANSCRIPT
METODE INTELIGENTE DE REZOLVARE
A PROBLEMELOR REALE
Laura DioşanTema 2
Conţinut Probleme de optimizare combinatorială
Problema rucsacului şi problema comisului voiajor Formularea problemei şi exemple Algoritmi de rezolvare
Exacţi Euristici Inspiraţi de natură
De citit: S.J. Russell, P. Norvig – Artificial Intelligence - A Modern
Approach capitolul 3 şi 4 H.F. Pop, G. Şerban – Inteligenţă artificială capitolul 3 Documentele din directorul KP şi TSP
Probleme de optimizare combinatorială (POC) Definire
O problemă P de optimizare (minimizare sau maximizare) care presupune un set de instanţe DP
un set finit de soluţii candidat Sp(I) pentru fiecare instanţă I є DP
o funcţie mp care asignează unei instanţe I şi unei soluţii candidat x є SP(I) un număr raţional pozitiv mP(I,x), numit valoarea soluţiei
Soluţia optimă pentru o instanţă I є DP este o soluţie candidat x* є SP(I) a.î. mP(I,x*) ≥ mP(I,x) pentru orice x є SP(I)
Probleme de optimizare combinatorială (POC)
Exemple
Problema comisului voiajor (Travelling Salesman Problem – TSP)
Problema rucsacului Partiţionări în grafe Probleme de atribuiri quadratice Vehicle routing Scheduling
Probleme de optimizare combinatorială (POC)
Metode de rezolvare Exacte
Branch and bound Branch and cut
Euristice
Clasificare Probleme de atribuiri Probleme de aranjare Probleme de partiţionare Probleme de alegere a unor submulţimi
Problema rucsacului Formularea problemei şi exemple
Tipologie
Algoritmi de rezolvare
Complexităţi
Problema rucsaculuiFormularea problemei şi exemple Se dau
un rucsac de o anumită capacitate G şi n obiecte, fiecare obiect având o anumită greutate şi un anumit cost (valoare)
Să se găsească o modalitate cât mia bună de umplere a rucsacului astfel încât valoare obiectelor
alese să fie cât mai mare
Dificultate NP-dificilă
Interes: Problemă de referinţă pentru testarea ideilor
Denumiri Knapsack problem (KP) Alocarea resurselor Submulţimi de sumă dată Cutting stock problem
Problema rucsacului – De ce?
Problemă conceptual simplă
Problemă dificil de rezolvat
Problemă intens cercetată
Problemă care apare în diverse aplicaţii
Problema rucsaculuiInstanţe de referinţă Consideraţii generale
Se dau n obiecte, fiecare având o valoare vi şi o greutate gi, i = 1, 2, ..., n greutatea suportată de rucsac G
Să se aleagă obiecte astfel încât max∑i=1,2, ..., nvixi a.î. ∑i=1,2, .., ngixi ≤ G, unde
xi є {0,1} sau xi є {0,1, ..., ci} sau xi є (0,1]
Instanţe http://www.cs.cmu.edu/afs/cs/project/ai-
repository/ai/areas/genetic/ga/test/sac/0.html http://homepage.ntlworld.com/walter.barker2/Knapsack%20Problem.htm http://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html
Problema rucsacului – Tipologie Numărul de copii ale unui obiect care este depus în rucsac
Problema 0-1 a rucsacului Fiecare obiect poate apare cel mult o dată în rucsac
Problema mărginită a rucsacului Fiecare obiect poate apare cel mult ci ori în rucsac (i=1, 2, ..., n)
Problema ne-mărginită a rucsacului Fiecare obiect poate apare de ori câte ori în rucsac
Numărul de rucsaci Un singur rucsac Mai mulţi rucsaci bin packing problem
Tipul obiectelor Problema discretă a rucsacului
Fiecare obiect ales trebuie pus în întregime în rucsac Problema continuă (fracţionată) a rucsacului
Fiecare obiect ales poate fi pus doar parţial în rucsac
Problema rucsacului – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound
Euristici Constructive De îmbunătăţire
Problema rucsacului – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound
Euristici Constructive De îmbunătăţire
Forţa brută Alte denumiri
Căutare exhaustivă Generează şi testează
Mod de lucru1. Se generează o potenţială soluţie2. Se evaluează această potenţială soluţie3. Se verifică dacă costul curent este mai bun decât costul
precedent• Dacă da, se reţine această soluţie
4. Se revine la pasul 1
Forţa brută – KP Alegerea submulţimii optime
Algoritm1. Se generează o sumbulţime de obiecte2. Dacă obiectele alese încap în rucsac atunci
– Se dermină costul (valoarea) asociat(ă) sumbulţimii– Se verifică dacă costul curent este mai bun decât
costul precedent• Dacă da, se reţine această soluţie
3. Se revine la pasul 1
Problema rucsacului – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound
Euristici Constructive De îmbunătăţire
Programare dinamică Principii
Principiul optimalităţii Optimul general implică optimele parţiale Optimul parţial nu implică optimul general
Mod de lucru Descompunerea problemei în subprobleme
Se rezolvă mai întâi subproblemele care pot fisoluţionate imediat
Se combină aceste soluţii parţiale, obţinând astfelsoluţii la problemele de pe niveluri superioare (din arborele de descompunere)
Programare dinamică KP Descompunerea
Se construieşte o matrice m, unde m[i,g] = valoarea maximă care poate fi obţinută prin
alegerea unor obiecte din primle i şi cu o greutate totală a obiectelor mai mică decât g
Definiţia recursivă a soluţiei m[0,g] = 0 (nici un obiect nu a fost ales) m[i,0] = 0 (nici o greutate) m[i,g] = m[i-1,g], dacă gi > g m[i,g] = maxim(m[i-1,g], vi+m[i-1,g-gi])), dacă gi ≤ g
Programare dinamică KPfunction algorithmKP(G, n)
for g = 0 to G m[0,g] :=0
for i = 1 to n dofor g = 0 to G
if ((gi≤g) and (vi+m[i-1,g-gi] > m[i-1, g])m[i,g] = vi + m[i-1,g-gi]alese[i,g] = 1
elsem[i,g] = m[i-1,g]alese[i,g] = 0
k := Gfor i = n downto 1
if (alese[i,k] == 1)output ik = k – gi
return m[n,G]End
Programare dinamică KP G= 10
3645gi
50304010vi
4321i
90
50
50
10
0
9
90909050505050000i=4
7040404040400000i=3
5040404040400000i=2
101010101000000i=1
0000000000i=0
10876543210m[i,g]
1
0
1
1
0
9
1111111000i=4
1000000000i=3
1111110000i=2
1111100000i=1
0000000000i=0
10876543210alese[i,g]
Problema rucsacului – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound
Euristici Constructive De îmbunătăţire
Branch-and-bound Principii
Căutare ramificată expandarea “inteligentă” a unui nod din arborele de căutare
Căutare mărginită căutarea se realizează între anumite limite
Parcuregerea nodurilor mod special Nodurile se adaugă într-o coadă de priorităţi Criteriul de ordine pt un nod curent n
f(n) = g(n) + h(n), unde g(n) – “distanţa” de la rădăcina arborelui de căutare la nodul
curent n cât a avansat căutarea h(n) – o aproximare a distanţei de la nodul curent n până la
soluţia finală cât mai trebuie căutat Margine inferioară (lower bound) Margine superioară (upper bound)
Branch-and-bound KP G = 10
V – valoarea obiectelor încărcate deja în rucsac G – greutatea obiectelor încărcate deja în rucsac B – limita (marginea) superioară a profitului care poate fi obţinut (bound)
Valoarea obiectelor care ar putea fi încărcate în rucsac Valaorea obiectelor deja încărcate + valoarea obiectelor care ar mai putea fi
încărcate în rucsac în paşii ulteriori PM* – profitul maxim care se poate obţine cu o anumită încărcătură
=maxim(min(Vcrt, Bcrt), PManterior)
3645gi
50304010vi
4321i
5643gi
10304050vi
4(1)321(4)iOrdonare crescătoare
vi/gi
ob1+ob2+ob3(parţial)
v1+v2+(G-g1-g2)*v3/g3
Branch-and-bound KP
pm*=pm=50
Branch-and-bound KP
pm*=pm=90
pm*=pm=50
pm=50
pm*=90
Branch-and-bound KP
pm=40
pm*=90
Branch-and-bound KP
pm=90
pm*=90
Branch-and-bound KP
pm=80
pm*=90
pm=50
pm*=90
Branch-and-bound KP
pm=70
pm*=90
pm=40
pm*=90
Branch-and-bound KP
pm=30
pm*=90
Branch-and-bound KP Soluţia
ob1 şi ob2
pm=90
pm*=90
Problema rucsacului – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound
Euristici Constructive De îmbunătăţire
Căutare euristică Metodele de căutare deterministe (exacte)
metode cu elemente aleatoare pt. evitarea blocării în optime locale euristici
Avantaj Simplitate Funcţia obiectiv nu mai trebuie să respecte anumite
proprietăţi (ex. diferenţiabilă)
Dezavantaj Convergenţa spre soluţie este probabilistică
Căutare euristică Schema unui algoritm simplu (hill climbing)
1. Se porneşte cu o aproximare a soluţiei2. Se generează o potenţială soluţie vecină cu vechea soluţie3. Dacă se obţine o soluţie potenţială mai bună, aceasta se
reţine şi se reptă pasul 2
Iniţializare x(0)K := 0Repetă
generare vecin x’ al lui x(k)Dacă f(x’) < f(x(k))
atunci x(k+1) := x’altfel x(k+1) := x(k)
k := k + 1Până când este satisfăcută o condiţie de oprirex* := x(k -1)
Euristici – KP Euristici constructive
Greedy
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs
Euristici – KP Euristici constructive
Greedy
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs
Greedy KP Alegerea obiectelor într-o anumită ordine
G= 9 ob1, ob2, ob4 valoare totală = 100
Nu generează întotdeauna o soluţie G = 10
ob1, ob2 50 ob4, ob2 903645gi
50304010vi
4321i
5643gi
10304050vi
4(1)321(4)iOrdonare crescătoare
vi/gi
3642gi
50304010vi
4321i
Euristici – KP Euristici constructive
Greedy
Euristici de îmbunătăţire (improved heuristics) Simulated annealing Tabu search EAs
Simulated annealing Ideea de bază:
Acceptarea noii ponteţiale soluţii se face cu o anumită probabilitate
Sursa de inspiraţie: Procesul de reorganizare a structurii unui solid supus unui tratament
termic Când solidul se încălzeşte (prin topire) particulele se distribuie aleator Când solidul se răceşte particulele se reorganizează ajungând în configuraţii
cu energii tot mai mici
Alte denumiri: Tratament termic simulat, călire simulată
Metodă propusă de Kirkpatrick, Gelatt, Vecchi (1983), Cerny (1985)
Simulated annealing - algoritm Iniţializare x(0) K := 0
Repetăgenerare vecin x’ al lui x(k)Dacă f(x’) < f(x(k))
atunci x(k+1) := x’altfel x(k+1) := x’ cu probabilitatea exp(-(f(x’)-f(x(k))/T)
recalculează Tk := k + 1
Până când este satisfăcută o condiţie de opriresoluţie x* := x(k -1)
Unde T (temperatura) este un parametru de control al procesului de optimizare
Simulated annealing - algoritm Iniţializare x(0) K := 0
Repetăgenerare vecin x’ al lui x(k)Dacă f(x’) < f(x(k))
atunci x(k+1) := x’altfel
u := random(0, 1)dacă u < P(x(k+1)=x’)=1/(1+exp(-(f(x’)-f(x(k))/T))
atunci x(k+1) := x’ altfel x(k+1) := x(k)
recalculează T k := k + 1
Până când este satisfăcută o condiţie de oprireSoluţie x* := x(k -1)
Simulated annealingT – mare probabilitate mare de acceptare a unei
configuraţii noi (căutare aleatoare)T – mică probabilitate mare de acceptare doar a
configuraţiilor care îmbunătăţesc funcţia obiectiv
Scheme de răcire:T(k) = T(0) / (k + 1)T(k) = T(0) / ln(k + c)T(k) = a T(k-1), cu a < 1
T(0) – de obicei se alege mare
Simulated annealing – KP Soluţia iniţială
Alegerea unui nr oarecare de obiecte
Vecinătate Alegerea încă a unui obiect
Funcţia obiectiv Valoarea obiectelor alese
Schema de răcire a temperaturii T(k) = T(0) / (1 + log(k))
Euristici – KP Euristici constructive
Greedy
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs
Tabu search O căutare locală ghidată printr-o memorie
flexibilă Soluţia următoare este cea mai bună vecină a soluţiei
curente Chiar dacă s-a găsit un optim local se permite căutarea
unei noi soluţii ciclarea soluţiilor – rezolvată prin folosirea unei liste
tabu Previne re-explorarea unei soluţii anterioare Previne execuţia unei mutări de 2 ori
Nu există elemente stochastice (ca la Simulated Annealing)
Tabu search Iniţializare x(0) x*=x(0) K = 0 T =Ø
Repetădacă există vecini ai lui x(k) care nu sunt tabu
atunci x’ = cel mai bun vecin al lui x(k) care nu e tabux(k+1) := x’Dacă f(x’) < f(x*)
atunci x* := x’k := k + 1update tabu list T
altfel stopPână când este satisfăcută o condiţie de oprireSoluţie x*
Tabu search – KP Soluţia iniţială
Reprezentată ca un vector de n biţi 0 – obiect neales 1 – obiect ales
Nici un obiect ales
Vecinătate alegerea/renunţarea la un obiect x(k) = 001101 011100= x’
Funcţia obiectiv Valoarea asociată obiectelor alese
Lista tabu Soluţiile deja generate !!! Spaţiu mare!!!!
Euristici – KP Euristici constructive
Greedy
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search Algoritmi evolutivi
Algoritmi evolutivi Algoritmi
Inspiraţi din natură (biologie) Iterativi Bazaţi pe
populaţii de potenţiale soluţii căutare aleatoare ghidată de
Operaţii de selecţie naturală Operaţii de încrucişare şi mutaţie
Care procesează în paralel mai multe soluţii Metafora evolutivă
Calitate Fitness (măsură de adaptare)
Operatori de căutareÎncrucişare şi mutaţie
Spaţiul de căutare al problemeiMediu
Parte a reprezentăriiGenă
Codarea (reprezentarea) unei soluţiiCromozom
Mulţime de soluţiiPopulaţie
Soluţie potenţială (candidat)Individ
Rezolvarea problemelorEvoluţie naturală
Algoritmi evolutiviInitializare populaţie P(0)Evaluare P(0)g := 0; //generaţiaCâtTimp (not condiţie_stop) execută
RepetăSelectează 2 părinţi p1 şi p2 din P(g)Încrucişare(p1,p2) =>o1 şi o2Mutaţie(o1) => o1*Mutaţie(o2) => o2*Evaluare(o1*)Evaluare(o2*)adăugare o1* şi o* în P(g+1)
Până când P(g+1) este completăg := g + 1
Sf CâtTimpPopulaţie (părinţi)
Sel
ecţie p
entr
u
per
turb
are
Încrucişare
Muta
ţie
Populaţie (urmaşi)
Selecţie de
supravieţuire
Algoritmi evolutivi KP Reprezentare
Cromozomul = un şir de n biţi 1 – obiectul a fost ales 0 – obiectul nu a fost ales
Fitness Valoarea obiectelor alese max Greutatea rucsacului – greutatea obiectelor alese min
Iniţializare Generare aleatoare de n biţi
Încrucişare Cu punct de tăietură
Mutaţie Negarea unui (unor) bit/biţi Tare sau slabă
Problema comisului voiajor Formularea problemei şi exemple
Tipologie
Algoritmi de rezolvare
Complexităţi
Problema comisului voiajorFormularea problemei şi exemple Se dă
un graf (neorientat) (complet), în care cele n vârfuri (V) sunt considerate oraşe, iar muchiile (E) drumuri între oraşe (fiecare muchie are asociat un cost).
Să se găsească cel mai scurt drum care vizitează o singură dată toate oraşele şi se întoarce în
oraşul de start ciclu Hamiltonian
Dificultate NP-dificilă
Interes: Problemă de referinţă pentru testarea ideilor
Denumiri Travelling Salesman Problem (TSP) Canadian Traveller Problem Vehicle routing problem Route inspection problem
Problema comisului voiajor – De ce?
Problemă conceptual simplă
Problemă dificil de rezolvat
Problemă intens cercetată
Problemă care apare în diverse aplicaţii
Problema comisului voiajor Instanţe de referinţă Consideraţii generale
Metrica frecvent folosită – distanţa Euclideană Distanţele - numere întregi
Instanţe TSPLIB http://comopt.ifi.uni-
heidelberg.de/software/TSPLIB95/ Peste 100 instanţe cu până la 85900 de oraşe Anumite instanţe sunt preluate din aplicaţii practice
Instanţe din proiectarea circuitelor VLSI (Very Large Scale Integration) Împachetarea a cât mai multe dispozitive logice pe
suprafeţe cât mai mici Instanţe generate aleator (grupate şi uniforme)
8th DIMACS challenge http://www2.research.att.com/~dsj/chtsp/
Problema comisului voiajor – Tipologie Tipul grafului
problema simetrică graf neorientat nr soluţiilor se înjumătăţeşte
problema asimetrică graf orientat
coliziuni în trafic străzi cu sens unic
Tipul distanţelor între 2 noduri metrică inegalitatea triunghiului cij < cik + ckj
distanţă Euclidiană distanţă Manhattan
non-metrică Ex. Traficul aerian
Problema comisului voiajor – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound Programare liniară
Euristici Constructive De îmbunătăţire
Problema comisului voiajor – Algoritmi Exacţi
Forţa brută Programare dinamică Branch-and-bound Programare liniară
Euristici Constructive De îmbunătăţire
Forţa brută Alte denumiri
Căutare exhaustivă Generează şi testează
Mod de lucru1. Se generează o potenţială soluţie2. Se evaluează această potenţială soluţie3. Se verifică dacă costul curent este mai bun decât costul
precedent• Dacă da, se reţine această soluţie
4. Se revine la pasul 1
Forţa brută – TSP alegerea permutării optime
Algoritm1. Se generează o permutare2. Se dermină costul asociat ei3. Se verifică dacă costul curent este mai bun decât costul
precedent• Dacă da, se reţine această soluţie
4. Se revine la pasul 1
Problema comisului voiajor – Algoritmi Exacţi
Forţa brută alegerea permutării optime Programare dinamică Branch-and-bound Programare liniară
Euristici Constructive De îmbunătăţire
Programare dinamică Principii
Principiul optimalităţii Optimul general implică optimele parţiale Optimul parţial nu implică optimul general
Mod de lucru Descompunerea problemei în subprobleme
Se rezolvă mai întâi subproblemele care pot fisoluţionate imediat
Se combină aceste soluţii parţiale, obţinând astfelsoluţii la problemele de pe niveluri superioare (din arborele de descompunere)
Programare dinamică TSP Dându-se o submulţime S de noduri din V cu 1 є S şi j є S, j ≠
1, se consideră C(S, j) lungimea celui mai scurt drum de la nodul 1 la nodul j care trece prin toate nodurile din S
Observaţii Dacă |S| = 2, atunci C(S, k) = d1,k pentru k = 2, 3, . . . , n Dacă |S| > 2, atunci există m є S − {k} a.î. C(S, k) =
lungimea turului optim de la 1 la m + dm,k
Definiţia recusrsivă a soluţiei optime C(S, k) = d1,m dacă S = {1, k}
min m≠k, mєS [C(S − {k},m) + dm, k], altfel
Programare dinamică TSPfunction algorithmTSP(G, n)
for k = 2 to n doC({i, k}, k) := d1,k
end forfor s = 3 to n do
for all S from {1, 2, . . . , n} with |S| = s dofor all k є S do
C(S, k) = minm≠k,m є S[C(S − {k},m) + dm,k]opt := mink≠1[C({1, 2, 3, . . . , n}, k) + d1,k
end forend for
end for;return (opt)
end
Programare dinamică TSP Complexitate:
Temporală
Spaţială
)!()2(~)1(22
)1( 23
1
nnnk
nn n
n
k
)2(~2)1(11
1
2
n
k
nn nnk
nk
Problema comisului voiajor – Algoritmi Exacţi
Forţa brută alegerea permutării optime Programare dinamică Branch-and-bound Programare liniară
Euristici Constructive De îmbunătăţire
Branch-and-bound Principii
Căutare ramificată expandarea “inteligentă” a unui nod din arborele de căutare
Căutare mărginită căutarea se realizează între anumite limite
Parcuregerea nodurilor mod special Nodurile se adaugă într-o coadă de priorităţi Criteriul de ordine pt un nod curent n
f(n) = g(n) + h(n), unde g(n) – “distanţa” de la rădăcina arborelui de căutare la nodul
curent n cât a avansat căutarea h(n) – o aproximare a distanţei de la nodul curent n până la
soluţia finală cât mai trebuie căutat Margine inferioară (lower bound) Margine superioară (upper bound)
Branch-and-bound TSP Configuraţia iniţială
toate muchiile grafului
Expandarea considerarea (includerea sau nu) unei muchii
Configuraţia finală ciclul cel mai scurt
Branch-and-bound TSP Lower bound
½ din lungimea turului format din cei mai apropiaţi 2 vecini ai fiecărui nod
Condiţii la ramificare Dacă excluderea unei muchii determină apariţia unor
noduri cu mai puţin de 2 vecini se renunţă la excludere Dacă adăugarea unei muchii determină apariţia unor
noduri cu mai mult de 2 vecini se renunţă la adăugare Dacă LB-ul unui nod-fiu e ≥ LB-ul nodului-părinte, nodul-
fiu nu mai merită explorat (“pruned”) Dacă avem doi fii de explorat, primul va fi explorat cel
cu LB-ul mai mic (coadă de priorităţi)
Branch-and-bound TSP
-417-185
2-97114
167-53
787--2
2010414-1
54321
Branch-and-bound TSP Se construieşte turul progresiv
LB = lungimea turului parţial + muchia cea mai scurtă care iasă din ultimul nod al turului parţial + cele mai scurte muchii care iasă din restul nodurilor (care nu fac parte din turul parţial)
Turul minim iniţial = ∞
Dacă LB < turul minim curent nod promiţător (se depune în coadă)
Dacă LB ≥ turul minim şi s-a găsit deja un tur potenţial se renunţă la explorarea căii respective (în arborel de căutare prune)
B&B TSP A
Tur parţial 1 LB = 4+(7+4+2+4)=21 LB < Tur minim = ∞
-417-185
2-97114
167-53
787--2
2010414-1
54321
B&B TSP B
Tur parţial 1,2 LB = 14+(7+4+2+4)=31
C Tur parţial 1,3 LB = 21
D Tur parţial 1,4 LB = 27
E Tur parţial 1,5 LB = 37
LB minim = 21 următorul nod explorat: C Coada: AAA(21)(21)(21) C(21) D(27) B(31) E(37)
-417-185
2-97114
167-53
787--2
2010414-1
54321
B&B TSP F
Tur parţial 1,3,2 LB = 22
G Tur parţial 1,3,4 LB = 23
H Tur parţial 1,3,5 LB = 33
LB minim = 22 următorul nod explorat: F Coada: AAA(21)(21)(21) C(21)C(21)C(21) F(22) G(23) D(27) B(31)
H(33) E(37)
-417-185
2-97114
167-53
787--2
2010414-1
54321
B&B TSP
L Tur parţial 1,3,2,4 = 1,3,2,4,5,1 Lungime = 37
M Tur parţial 1,3,2,5=1,3,2,5,4,1 Lungime = 31
LB minim = 23 următorul nod explorat: G Coada: AAA(21)(21)(21) C(21)C(21)C(21) F(22)F(22)F(22) G(23) D(27) B(31) M(31)
H(33) E(37) L(37)
-417-185
2-97114
167-53
787--2
2010414-1
54321
B&B TSP
N Tur parţial 1,3,4,2 = 1,3,4,2,5,1 Lungime = 43
O Tur parţial 1,3,4,5=1,3,4,5,2,1 Lungime = 34
LB minim = 27 următorul nod explorat: D Coada: AAA(21)(21)(21) C(21)C(21)C(21) F(22)F(22)F(22) G(23)G(23)G(23) D(27) B(31) M(31) H(33)
O(34) E(37) L(37) N(43)
-417-185
2-97114
167-53
787--2
2010414-1
54321
B&B TSP I
Tur parţial 1,4,2 LB = 32
J Tur parţial 1,4,3 LB = 34
K Tur parţial 1,4,5 LB = 27
LB minim = 27 următorul nod explorat: K Coada: AAA(21)(21)(21) C(21)C(21)C(21) F(22) G(23) D(27)F(22) G(23) D(27)F(22) G(23) D(27) K(27) B(31) I(32)
M(31) H(33) J(34) E(37) L(37)
-417-185
2-97114
167-53
787--2
2010414-1
54321
B&B TSP P
Tur parţial 1,4,2,5=1,4,2,5,3,1 Lungime = 30
Q Tur parţial 1,4,5,3=1,4,5,3,2,1 Lungime = 48
LB minim = 30 S-a găsit un tur de lungime 30 B nu mai merită explorat (se elimină din coadă) Restul nodurilor nu mai merită cercetate (LB > turul minim) Coada: AAA(21)(21)(21) C(21)C(21)C(21) F(22) G(23) D(27)F(22) G(23) D(27)F(22) G(23) D(27) K(27)K(27)K(27) B(31) I(32) M(31)
H(33) J(34) E(37) L(37)
-417-185
2-97114
167-53
787--2
2010414-1
54321
Problema comisului voiajor – Algoritmi Exacţi
Forţa brută alegerea permutării optime Programare dinamică Branch-and-bound Programare liniară
Euristici Constructive De îmbunătăţire
Programare liniară - TSP http://www.tsp.gatech.edu/methods/dfj/in
dex.html http://www.youtube.com/watch?v=-
cLsEHP0qt0&feature=channel
Algoritmi Exacţi
Forţa brută alegerea permutării optime Programare dinamică Branch-and-bound Programare liniară
Euristici Constructive De îmbunătăţire
Euristici – TSP
Euristici constructive Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Euristici de îmbunătăţire (improved heuristics) Simulated annealing Tabu search EAs ACO
Euristici – TSP
Euristici constructive Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Euristici de îmbunătăţire (improved heuristics) Simulated annealing Tabu search EAs ACO
Cel mai apropiat vecin Ordonarea crescătoare a muchiilor Alegerea celei mai scurte muchii, cu condiţiile
orice vârf să aibă maxim 2 vecini să nu se formeze cicluri cu mai puţin de n muchii
Complexitatea O(n2log n) Folosirea arborilor k dimensionali (kd trees) şi a unei cozi de priorităţi
pentru reţinerea muchiilor O(n log n)
Problemă nu găseşte soluţia optimă întotdeauna
1 2
34
1
5
39
72 1 2
34
1
15
189
72
Euristici – TSP
Euristici constructive Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Euristici de îmbunătăţire (improved heuristics) Simulated annealing Tabu search EAs ACO
Căutare locală Se porneşte cu un ciclu oarecare Se modifică ciclul prin operaţii de
schimbare de noduri ABCDEF AECDBF
inserţie de nod ABCDEF ADBCEF
schimbare de k muchii (k = 2)
în vederea obţinerii unui ciclu mai bun (scurt)
Căutare locală Euristici bazate pe
schimbul a k elemente noduri muchii
Vecinătăţi complexe algoritmul Lin-Kernighan & versiuni
Euristici – TSP Euristici constructive
Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs ACO
Algoritmul lui Christofides TSP în graf complet G şi care respectă
ingealitatea triunghiului Algoritm
Se creează arborele de acoperire minimă (A) al lui G Notând cu I mulţimea nodurilor din A de grad impar, se
găseşte o potrivire perfectă P cu muchii de lungimi minime în graful G peste nodurile din I
Se combină muchiile din P şi A formând un multigraf H Se formează un circuit Eulerian în H (H este Eulerian pt
că este conect şi format doar din noduri de grad par) Se transformă circuitul Eulerian într-unul Hamiltonian
prin “sărirea” nodurilor deja vizitate (shortcutting).
Algoritmul lui Christofides
a
b
c
h
d
e
f g
Algoritmul lui Christofides Presupunem următorul
graf cu distanţe Euclidiene între noduri
a
b
c
h
d
e
f g
Algoritmul lui Christofides Se creează arborele de acoperire minimă (A) al lui G
Algoritmul lui Prim Se pleacă dintr-un nod şi se aleg pe rand cei mai apropiaţi vecini ai
nodurilor deja vizitate a.î. să nu se formeze cicluri până se ajunge la o componentă conexă
Algoritmul lui Kruskal Se aleg pe rând muchiile de cost minim a.î. să nu se formeze
cicluri până se ajunge la o componentă conexă
a
b
c
h
d
e
f g
Algoritmul lui Christofides Notând cu I mulţimea nodurilor din A de
grad impar, se găseşte o potrivire perfectă P cu muchii de lungimi minime în graful G peste nodurile din I
a
b
c
h
d
e
f g b
c
h
e
f g
Algoritmul lui Christofides Se combină muchiile din P şi A formând un multigraf H
a
b
c
h
d
e
f g b
c
h
e
f g
a
b
c
h
d
e
f g
Algoritmul lui Christofides Se formează un circuit Eulerian în H (H
este Eulerian pt că este conect şi format doar din noduri de grad par)
a
b
c
h
d
e
f g
a
b
c
h
d
e
f g
Algoritmul lui Christofides Se transformă circuitul Eulerian într-unul
Hamiltonian prin “sărirea” nodurilor deja vizitate (shortcutting).
a
b
c
h
d
e
f g
a
b
c
h
d
e
f g
Euristici – TSP Euristici constructive
Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs ACO
Euristici – TSP Euristici constructive
Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs ACO
Simulated annealing Ideea de bază:
Acceptarea noii ponteţiale soluţii se face cu o anumită probabilitate
Sursa de inspiraţie: Procesul de reorganizare a structurii unui solid supus
unui tratament termic Când solidul se încălzeşte (prin topire) particulele se
distribuie aleator Când solidul se răceşte particulele se reorganizează
ajungând în configuraţii cu energii tot mai mici
Alte denumiri: Tratament termic simulat, călire simulată
Metodă propusă de Kirkpatrick, Gelatt, Vecchi (1983), Cerny (1985)
Simulated annealing - algoritm Iniţializare x(0) K := 0
Repetăgenerare vecin x’ al lui x(k)Dacă f(x’) < f(x(k))
atunci x(k+1) := x’altfel x(k+1) := x’ cu probabilitatea exp(-(f(x’)-f(x(k))/T)
recalculează Tk := k + 1
Până când este satisfăcută o condiţie de opriresoluţie x* := x(k -1)
Unde T (temperatura) este un parametru de control al procesului de optimizare
Simulated annealing - algoritm Iniţializare x(0) K := 0
Repetăgenerare vecin x’ al lui x(k)Dacă f(x’) < f(x(k))
atunci x(k+1) := x’altfel
u := random(0, 1)dacă u < P(x(k+1)=x’)=1/(1+exp(-(f(x’)-f(x(k))/T))
atunci x(k+1) := x’ altfel x(k+1) := x(k)
recalculează T k := k + 1
Până când este satisfăcută o condiţie de oprireSoluţie x* := x(k -1)
Simulated annealingT – mare probabilitate mare de acceptare a unei
configuraţii noi (căutare aleatoare)T – mică probabilitate mare de acceptare doar a
configuraţiilor care îmbunătăţesc funcţia obiectiv
Scheme de răcire:T(k) = T(0) / (k + 1)T(k) = T(0) / ln(k + c)T(k) = a T(k-1), cu a < 1
T(0) – de obicei se alege mare
Simulated annealing – TSP Soluţia iniţială
un ciclu Hamiltonian (o permutare a celor n oraşe)
Vecinătate Transformare 2-opt a unei permutări x(k) = ABCFEDG ABCFEDG ABCDEFG = x’
Funcţia obiectiv Costul asociat unui ciclu
Schema de răcire a temperaturii T(k) = T(0) / (1 + log(k))
Euristici – TSP Euristici constructive
Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs ACO
Tabu search O căutare locală ghidată printr-o memorie
flexibilă Soluţia următoare este cea mai bună vecină a
soluţiei curente Chiar dacă s-a găsit un optim local se permite
căutarea unei noi soluţii ciclarea soluţiilor – rezolvată prin folosirea unei
liste tabu Previne re-explorarea unei soluţii anterioare Previne execuţia unei mutări de 2 ori
Nu există elemente stochastice (ca la Simulated Annealing)
Tabu search Iniţializare x(0) x*=xbest=x(0) K = 0 T =Ø
Repetădacă există vecini ai lui x(k) care nu sunt tabu
atunci x’ = cel mai bun vecin al lui x(k) care nu e tabux(k+1) := x’Dacă f(x’) < f(x*)
atunci x* := x’k := k + 1update tabu list
altfel stopPână când este satisfăcută o condiţie de oprireSoluţie x*
Tabu search – TSP Soluţia iniţială
un ciclu Hamiltonian (o permutare a celor n oraşe)
Vecinătate Transformare 2-opt a unei permutări x(k) = ABCFEDG ABCFEDG ABCDEFG = x’
Funcţia obiectiv Costul asociat unui ciclu
Lista tabu Muchiile noi (2) care au intrat în soluţie într-o iteraţie Muchiile care au intrat in lista tabu nu pot fi eliminate
din soluţie
Euristici – TSP Euristici constructive
Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs ACO
Algoritmi evolutivi Algoritmi
Inspiraţi din natură (biologie) Iterativi Bazaţi pe
populaţii de potenţiale soluţii căutare aleatoare ghidată de
Operaţii de selecţie naturală Operaţii de încrucişare şi mutaţie
Care procesează în paralel mai multe soluţii Metafora evolutivă
Calitate Fitness (măsură de adaptare)
Operatori de căutareÎncrucişare şi mutaţie
Spaţiul de căutare al problemeiMediu
Parte a reprezentăriiGenă
Codarea (reprezentarea) unei soluţiiCromozom
Mulţime de soluţiiPopulaţie
Soluţie potenţială (candidat)Individ
Rezolvarea problemelorEvoluţie naturală
Algoritmi evolutiviInitializare populaţie P(0)Evaluare P(0)g := 0; //generaţiaCâtTimp (not condiţie_stop) execută
RepetăSelectează 2 părinţi p1 şi p2 din P(g)Încrucişare(p1,p2) =>o1 şi o2Mutaţie(o1) => o1*Mutaţie(o2) => o2*Evaluare(o1*)Evaluare(o2*)adăugare o1* şi o* în P(g+1)
Până când P(g+1) este completăg := g + 1
Sf CâtTimpPopulaţie (părinţi)
Sel
ecţie p
entr
u
per
turb
are
Încrucişare
Muta
ţie
Populaţie (urmaşi)
Selecţie de
supravieţuire
Algoritmi evolutivi TSP Reprezentare
Cromozomul = o permutare de n elemente Fitness
Lumgimea ciclului codat de permutare Iniţializare
Permutarea identică + interschimbări de elemente Încrucişare
Cu punct de tăietură + corecţii Operatorul PMX Goldberg (Alleles, loci, and the TSP)
Mutaţie Interschimbare de elemente
Euristici – TSP Euristici constructive
Cel mai apropiat vecin + greedy caseStudyJohnson.pdf Local search Algoritmul lui Christofides spanning tree
Improved heuristics (euristici de îmbunătăţire) Simulated annealing Tabu search EAs ACO
ACO Preferinţa pentru drumuri cu nivel ridicat de
feromon Pe drumurile scurte feromonul se înmulţeşte Furnicile comunică pe baza urmelor de feromon
ACO TSP Algoritm
m furnicuţe sunt plasate în r oraşe alese aleator La fiecare pas, furnicile se deplasează într-un oraş nou
modificând feromonul de pe drumul (muchia) respectiv(ă) – modificare locală a urmei
memorând oraşele prin care au trecut alegerea noului oraş se bazează pe
cantitatea de feromon de pe drumul care urmează a fi parcurs DP importanţa feromonui de pe drumul care urmează a fi parcurs DP lungimea drumului care urmează a fi parcurs IP
Când toate furnicuţele au trecut prin toate oraşele, furnicuţa care a parcurs cel mai scurt drum mai modifică o dată feromonum de pe drumul ei – modificarea globală a urmei recompensarea ciclurilor scurte
Cursul următor Instruire automata (Machine Learning - ML)
introducere in domeniul ML tipuri de probleme metodologia rezolvării unei probleme cu ajutorul unui
algoritm de ML aprecierea performanţelor unui algoritm de ML
De citit: S.J. Russell, P. Norvig – Artificial Intelligence - A Modern
Approach capitolul 18, 19, 20 Documentele din directoarele: ML, classification,
clustering
top related