METODE INTELIGENTE DE REZOLVARE A PROBLEMELOR...

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

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

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

90909050505050000i=4

7040404040400000i=3

5040404040400000i=2

101010101000000i=1

0000000000i=0

10876543210m[i,g]

1111111000i=4

1000000000i=3

1111110000i=2

1111100000i=1

0000000000i=0

10876543210alese[i,g]

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

5643gi

10304050vi

4(1)321(4)iOrdonare crescătoare

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*=90

Branch-and-bound KP

pm*=90

Branch-and-bound KP

pm*=90

Branch-and-bound KP

pm*=90

Branch-and-bound KP

pm*=90

Branch-and-bound KP

pm*=90

Branch-and-bound KP Soluţia

ob1 şi ob2

pm*=90

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

Greedy

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

5643gi

10304050vi

4(1)321(4)iOrdonare crescătoare

3642gi

50304010vi

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

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

Greedy

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

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)

ecţie p

Încrucişare

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ă

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

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

Forţa brută alegerea permutării optime Programare dinamică Branch-and-bound Programare liniară

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)

Programare dinamică TSP Complexitate:

Temporală

Spaţială

)!()2(~)1(22

)1( 23

)2(~2)1(11

nn nnk

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

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

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

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

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

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

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

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

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

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

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

72 1 2

Euristici – TSP

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

Algoritmul lui Christofides Presupunem următorul

graf cu distanţe Euclidiene între noduri

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ă

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

Algoritmul lui Christofides Se combină muchiile din P şi A formând un multigraf H

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)

Algoritmul lui Christofides Se transformă circuitul Eulerian într-unul

Hamiltonian prin “sărirea” nodurilor deja vizitate (shortcutting).

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)

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

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

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

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)

ecţie p

Încrucişare

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

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

METODE INTELIGENTE DE REZOLVARE A PROBLEMELOR...

Documents