Algoritmi metaeuristici – Curs 2 1 [608162]

Algoritmi metaeuristici – Curs 2 1
Algoritmi de căutare locală și globală

•Motiva ție: optimizare locală vs. optimizare globală
•Structura generală a algoritmilor de optimizare locală
•Metaeuristici deterministe pentru căutare locală:
–alg Pattern Search
–alg Nelder Mead
•Metaeuristici aleatoare pentru căutare locală:
–alg Matyas, Solis -Wets
•Metaeuristici pentru căutare globală:
–Căutare locală cu restartare
–Căutare locală iterată
–Simulated Annealing

Algoritmi metaeuristici – Curs 2 2 Optimizare locală vs. optimizare
globală
Optimizare locală: f(x*)<=f(x) pentru orice x in V(x*)
(V(x*)=vecinătate a lui x);
Obs: e necesară cunoașterea unei aproximații inițiale
Optimizare globală :
•identificarea optimului global al unei funcții: pentru o problem ă de
maximizare se caută x* cu proprietatea că f(x*)<=f(x), pentru orice x
•daca funcția obiectiv are și optime locale atunci metodele de căutare
locală (cum este metoda gradientului) se pot bloca în punctele de optim
local 5 10 15 2012345
Optim global Optim local

Algoritmi metaeuristici – Curs 2 3 Optimizare locală
Spațiu de căutare discret:

-Vecinătatea unui element este o
mulțime finită care poate fi explorată exhaustiv

Caz particular (soluții de tip permutare):
-s=(s
1,s2,…,sn) si din {1,….,n}
-V(s)={ s’|s’ poate fi obținută din s
prin interschimbarea a două elemente}
-Card V(s)=n(n -1)/2

Exemplu (n=4)
s=(2,4,1,3)
s’=(1,4,2,3)
Spațiu de căutare continuu:

a) funcția obiectiv este derivabilă
-Metoda gradientului
-Metode de tip Newton

b) funcția obiectiv nu este
derivabilă
-Metode bazate pe căutare
directă (ex: Nelder Mead)
-Metode bazate pe perturbații aleatoare mici

Algoritmi metaeuristici – Curs 2 4 Căutare locală: structura generală
Notații:
S – spațiul de căutare
f – funcție obiectiv
S* – mulțimea optimelor locale/globale
s=(s1,s2,…, sn) : element din S/
configurație/ soluție candidat
s* = cel mai bun element descoperit
până în etapa curentă
s* = soluție optimă Algoritm de căutare locală:

s = aproximație inițială
repeat
s’=perturbare(s)
if f(s’)<f(s) then
s=s’
until <condiție de oprire>
Observații:
1.Aproximația inițială poate fi selectată aleator sau în baza unei euristici
2.Perturbarea poate fi deterministă (ex: metoda gradientului) sau aleatoare
3.Inlocuirea lui s cu s’ se poate face și când f(s’)<=f(s)
4.Condiția de oprire:
(a)nu se mai obține îmbunătățire in estimarea soluției;
(b)s-a atins numărul maxim de iterații (sau de evaluări ale funcției obiectiv)

Algoritmi metaeuristici – Curs 2 5 Căutare locală: variante (I)
Algoritm de căutare locală:

s = aproximație inițială
repeat
s’=perturbare(s)
if f(s’)<f(s) then
s=s’
until <condiție de oprire>
Observații:
1.căutarea e mai „agresivă” – la fiecare iterație se analizează mai mulți
candidați
2.fiecare evaluare a funcției obiectiv trebuie contorizată (dacă condiția de oprire
folosește nr de evaluări)

Mai mulți candidați:

s = aproximație inițială
repeat
s’=perturbare(s)
for k=1:m
s’’ = perturbare(s)
if f(s’’)<f(s) then s’=s’’
end
if f(s’)<f(s) then
s=s’
until <condiție de oprire>

Algoritmi metaeuristici – Curs 2 6 Căutare locală: variante (II)
Algoritm de căutare locală:

s = aproximație inițială
repeat
s’=perturbare(s)
if f(s’)<f(s) then
s=s’
until <condiție de oprire>
Observații:
1.Cea mai bună dintre cele m soluții candidat este acceptată necondiționat
2.Cea mai bună soluție candidat obținută până în momentul curent al căutării
este reținută (se asigură proprietatea de elitism = nu se pierde o soluție
candidat bună)

Mai mulți candidați:
s = aproximație inițială
best = s
repeat
s’=perturbare(s)
for k=1:m
s’’ = perturbare(s)
if f(s’’)<f(s) then s’=s’’
end
s=s’
if f(s)<f(best) then best=s
until <condiție de oprire>

Algoritmi metaeuristici – Curs 2 7 Căutare locală: variante de
perturbare
•Scopul perturbării: construirea unei noi soluții candidat pornind de la
soluția curentă

•Tipuri de perturbare (în funcție de natura perturbării):
–Deterministă
–Aleatoare

•Tipuri de perturbare (în funcție de intensitatea perturbării)
–Locală
–Globală

•Tipuri de perturbare (în funcție de spațiul de căutare)
–Specifică spațiilor discrete de căutare (înlocuirea uneia sau a mai multor
componente)
–Specifică spațiilor continue de căutare (adăugarea unui termen perturbator)

Algoritmi metaeuristici – Curs 2 8 Căutare locală: variante de
perturbare
Probleme de optimizare combinatorială: noua configurație se alege în
vecinătatea celei curente prin aplicarea unor transformări specifice problemei
de rezolvat

Exemplu 1: TSP (Travelling Salesman Problem)
• Generarea unei noi configuraț ii (transformare 2-opt)

A B C
D
E
F
G
ABCFEDG A B C
D
E
F
G
ABCFED G ABCDEFG Implementare:

1.Se aleg aleator două poziții
2.Se inversează ordinea elementelor din subtabloul delimitat de cele două poziții

Algoritmi metaeuristici – Curs 2 9 Căutare locală: variante de
perturbare
Probleme de optimizare combinatorială: noua configurație se alege în
vecinătatea celei curente prin aplicarea unor transformări specifice problemei
de rezolvat
Exemplu 2: Generarea orarelor
• Eliminarea conflictelor prin mutare sau interschimbare

• Perturbarea unei configuraț ii curente:
–Transferul unui eveniment ce încalc ă
o restricț ie puternic ă într-o zonă liberă E1
E2 E3
E4 E5
E6
E7 E8
E9 S1 S2 S3
T1 E1 E3 E9
T2 E4 E8
T3 E6 E5
T4 E2 E7 S1 S2 S3
T1 E1 E9
T2 E4 E3 E8
T3 E6 E5
T4 E2 E7 Graful conflictelor

Algoritmi metaeuristici – Curs 2 10 Căutare locală: variante de
perturbare
Probleme de optimizare combinatorială: noua configurație se alege în
vecinătatea celei curente prin aplicarea unor transformări specifice problemei
de rezolvat
Exemplu 2: Generarea orarelor
• Eliminarea conflictelor prin mutare sau interschimbare

• Perturbarea unei configuraț ii curente:
–Interschimbarea a două evenimente E1
E2 E3
E4 E5
E6
E7 E8
E9 S1 S2 S3
T1 E1 E9
T2 E4 E3 E8
T3 E2 E5
T4 E6 E7 S1 S2 S3
T1 E1 E9
T2 E4 E3 E8
T3 E6 E5
T4 E2 E7 Graful conflictelor

Algoritmi metaeuristici – Curs 2 11 Căutare locală: variante de
perturbare
Optimizare în domenii continue
Perturbare aleatoare
Perturb(s,p,inf,sup,r)
for i=1:n
if rand(0,1)<=p then
repeat
n=rand( -r,r)
until inf<=si+n<=sup
si=si+n
end
end
return s
Perturbare deterministă prin căutare
directă (nu se folosesc derivate)
•Pattern Search (Hooke -Jeeves)
•Nelder – Mead

Notații:
s=soluția candidat ce va fi perturbată p=probabilitate de perturbare
r=„raza” perturbării
rand(a,b) = valoare aleatoare uniform repartizată în [a,b]

12 Căutare locală: pattern search
Idee: modificare succesivă a
componentelor soluției curente
PatternSearch(s,r)
s=aproximație inițială r=valoare inițială best=s
repeat
s’=s
for i=1:n
if f(s+r*e
i)< f(s’) then s’= s+r*ei end
if f(s -r*ei)< f(s’) then s’= s-r*ei end
end
if s==s’ then r=r/2 else s=s’
end
until <condiție de oprire>

T.G. Kolda et al., Optimization by direct
search: new perspectives on some classical
and modern methods, SIAM Review, 45(3),
385-482, 2003
Obs:
1. ei=(0,0,…,0,1,0,…,0) (1 se află pe poziția i)
2. la fiecare iterație se construiesc 2n candidați
dintre care se alege cel mai bun

Algoritmi metaeuristici – Curs 2 13 Căutare locală: algoritm ul Nelder- Mead
Idee: căutarea se bazează pe utilizarea unui
simplex în Rn (set de (n+1) puncte din Rn) și
aplicarea unor transformări asupra simplexului
care permite „explorarea” domeniului soluțiilor

Transformările se bazează pe:
1.Ordonarea elementelor din simplex crescător
după valoarea funcției obiectiv (pentru o problemă de minimizare)
2.Calculul mediei M(x
1,…,xn) a celor mai bune n
elemente din simplex
3.Construirea succesivă a unor noi elemente prin: reflexie, expandare, contracție (interioară,
exterioară), micșorare simplex

Algoritmi metaeuristici – Curs 2 14 Căutare locală: algoritm ul Nelder- Mead
Selectează (n+1) puncte din Rn: (x1,x2,…, xn+1)
Repeat
calculează valorile funcției (f1,f2,…, fn+1)
sortează (x1,x2,…, xn+1) astfel încât f1<=f2<=…<=fn+1
M=(x1+x2+…+xn)/n

Pas1 (reflexie – R):
xr=M+r(M-xn+1);
if f1<=f(xr)<fn+1 accept xr; continue;
else goto Pas 2
Pas 2 (expandare – E):
if f(xr)< f1 then
xe=M+e(xr-M)
if f(xe)<f(xr) then accept xe; continue
else goto Pas 3

Algoritmi metaeuristici – Curs 2 15 Căutare locală: algoritm ul Nelder- Mead
Pas 4 (contracție exterioară/interioară – Co/Ci ):
if fn<=f(xr)<fn+1 then
xc=M+c(xr-M)
if f(xc)<f(xr) accept xc; continue
else goto Pas 5
if f(xr)>=fn+1 then
xcc=M-c(M-xn+1)
if f(xcc)< fn+1 then accept xcc; continue
else goto Pas 5
Pas 5 (Micșorare – Shrink):
construiește un nou simplex:
x1,v2,…, vn+1 unde vi=xi+s(xi-x1)

Parametrii: r=1, e=2, c=1/2, s=1/2

Algoritmi metaeuristici – Curs 2 16 De la optimizare locală la optimizare
globală
Perturbare: se introduc (ocazional) perturbații aleatoare mari
Exemplu: utilizare distribuție de probabilitate cu suport infinit (de
exemplu repartiția normală sau repartiția Cauchy – algoritm
Matyas , Solis -Wets )

Restartarea algoritmului: se reia procesul de căutare locală pornind
de la altă configurație aleatoare (aleasă aleator)
Exemplu: căutare locală cu restartare (local search with random
restarts)

Explorarea optimelor locale: optimul local curent e perturbat și folosit
ca punct de pornire pentru căutarea altui optim
Exemplu: căutare locală iterată (iterated local search)
Selecție: se acceptă ( ocazional ) și configurații de calitate mai slabă
Exemplu: căutare bazată pe simularea procesului de călire
(simulated annealing)

Algoritmi metaeuristici – Curs 2 17 Exemplu: algoritmul Matyas (1960)
s(0) = configurație inițială
k=0 // contor iteratie
e=0 // numar cazuri de esec
repeat
genereaz ă un vector aleator cu
componente normal repartizate (z1,…zn)
IF f(s(k)+z)< f(s(k)) THEN s(k+1)=s (k)+z
e=0
ELSE s(k+1)=s (k)
e=e+1
k=k+1
UNTIL (k ==kmax ) OR (e= =emax ) Obs. Perturba ția
aleatoare se aplică de
regulă asupra unei
singure componente
(vectorul z are o
singur ă component ă
nenul ă)
Problema: cum se aleg
parametrii reparti ției
folosite pentru
perturbarea valorii
curente ?
Exemplu: N(0,s)

Algoritmi metaeuristici – Curs 2 18 Reminder: generare valori aleatoare cu
repartiție normală
Pentru generarea valorilor aleatoare cu reparti ție normal ă (N(0,1)) se
poate folosi algoritmul Box-Muller

u=rand(0,1) // valoare aleatoare uniform repartizat ă in (0,1)
v=rand(0,1 )
r=sqrt(-2*ln(u));
z1=r*cos(2*PI*v )
z2=r*sin(2*PI*v )
RETURN z1,z2
// valorile z1 si z2 pot fi considerate ca fiind realizări a două variabile
// aleatoare independente

Algoritmi metaeuristici – Curs 2 19 Reminder: generare valori aleatoare cu
repartiție normală
Alta variantă a algoritmul ui Box-Muller :
repeat
u=rand(0,1) // valoare aleatoare uniform repartizat ă in (0,1)
v=rand(0,1 )
w=u2+v2
until 0<w<1
y=sqrt (-2ln(w)/w)
z1=u*y
z2=v*y
RETURN z1,z2
// valorile z1 si z2 pot fi considerate ca fiind realizări a două variabile
// aleatoare independente
Obs: pentru a obține valori corespunzătoare repartiției N(m,s) se aplică
transformarea: m+z*s

Algoritmi metaeuristici – Curs 2 20 Exemplu: algoritmul Solis-Wets (1981)
s(0) = configurație inițială
k=0; m(0 )=0 // media vectorului perturbatie este ajustata in timp
repeat
genereaz ă un vector aleator (z1,…zn) cu componente avand
repartitia N(m(k),1)
IF f(s(k)+z)< f(s(k)) THEN s(k+1)=s (k)+z; m(k+1)=0.4*z+0.2* m(k)

IF f(s(k)-z)<f(s(k)) THEN s(k+1)=s (k)-z; m(k+1)= m(k)-0.4*z

IF f(s(k)-z)>f(s(k)) AND f(s(k)+z)> f(s(k)) THEN
s(k+1):= s(k)
m(k+1):=0.5*m(k)
k:=k+1
UNTIL (k ==kmax )

Algoritmi metaeuristici – Curs 2 21 Căutare locală cu restartare
Idee:
•procesul de căutare se repetă
de mai multe ori pornind de la configurații inițiale diferite
•se alege configurația cea mai
bună

Observații:
•Condiția de oprire a căutării locale se poate baza pe o decizie aleatoare (ex: intervalul de timp alocat poate fi aleator)
•Etapele de căutare aleatoare
sunt independente (noua
configurație inițială este aleasă aleator) – nu se folosește
informația colectată la etapa anterioară
Random Restart
s=configurație inițială
best=s
Repeat
repeat
r=perturb(s)
if f(r)<=f(s) then s=r
until <conditie oprire căutare
locală>
if f(s)<f(best) then best =s
s=altă configurație inițială
until <conditie oprire căutare>
return best

Algoritmi metaeuristici – Curs 2 22 Căutare locală iterată
Idee:
•Configurația inițială de la
următoarea etapă se alege în vecinătatea optimului local
identificat la etapa anterioară
(eventual doar dacă acesta este mai bun decât cel identificat anterior)

Observații:
•Pentru generarea configurației inițiale corespunzătoare fiecărei iterații se utilizează o perturbare mai „agresivă” decât cea
utilizată în etapa de căutare
locală
Iterated Local Search (ILS)
s=configurație inițială
s0=s; best=s
Repeat
repeat
r=perturbSmall(s)
if f(r)<=f(s) then s=r
until <condiție oprire căutare
locală>
if f(s)<f(best) then best =s
s0=alege(s0,s)
s=perturbLarge(s0)
until <conditie oprire căutare>
return best

Algoritmi metaeuristici – Curs 2 23 Simulated Annealing
Idee:
– se accept ă, cu o anumit ă probabilitate, și ajustari ale
configura ției curente care conduc la creșterea funcției obiectiv
Sursa de inspira ție:
– procesul de reorganizare a structurii unui solid supus unui
tratament termic :
•Solidul este încălzit (topit ): particulele sunt distribuite într-o
manier ă aleatoare
•Solidul este răcit lent: particulele se reorganizeaz ă pentru a
se ajunge la configura ții de energie din ce în ce mai mică
Terminologie :
simulated annealing = tratament termic simulat = călire simulat ă
Istoric : Metropolis(1953), Kirkpatrick, Gelatt , Vecchi (1983), Cerny
(1985)

Algoritmi metaeuristici – Curs 2 24 Simulated Annealing
Analogie:

Problemă de minimizare :

Func ție obiectiv

Configura ție (solu ție candidat )

Perturbarea configura ției curente
Parametru de control a procesului de
optimizare
Proces fizic:
•Energia sistemului

•Starea sistemului

•Modificarea stării sistemului

•Temperatura

SA= metoda euristic ă inspirat ă de procese fizice

Algoritmi metaeuristici – Curs 2 25 Simulated Annealing
Puțină fizică:
•fiecare stare a unui sistem este caracterizat ă de o anumit ă
probabilitate de apari ție

•probabilitatea asociat ă unei stări depinde de energia stării și de
temperatura sistemului (ex: distribu ția Boltzmann)

∑
∈−=− =
S))(exp( )())(exp()(1)(
s BBT
TksETZTksE
TZsP
E(s) = energia stării s
T = temperatura sistemului
kB = constanta Boltzmann
Z(T)=func ția de partiție
(factor de normalizare )

Algoritmi metaeuristici – Curs 2 26 Simulated Annealing
Puțină fizică:
•Valori mari ale lui T (T tinde la infinit ): argumentul lui exp este
aproape 0 => stările sunt echiprobabile

•Valori mici ale lui T (T tinde la 0): vor avea probabilitate nenul ă
doar stările cu energia nulă
∑
∈−=− =
S))(exp( )())(exp()(1)(
s BBT
TksETZTksE
TZsP
E(s) = energia stării s
T = temperatura sistemului
kB = constanta Boltzmann
Z(T)=func ția de partiție
(factor de normalizare )

Algoritmi metaeuristici – Curs 2 27 Simulated Annealing
Cum folosim acest lucru pentru rezolvarea unei probleme de
optimizare ?

•Ar fi suficient să gener ăm configura ții în conformitate cu distribu ția
Boltzmann pentru valori din ce în ce mai mici ale temperaturii

•Problema : dificil de calculat Z(T) ( presupune calculul unei sume
pentru toate stările posibile , adică generarea tuturor configura țiilor
spațiului de căutare – IMPOSIBIL de realizat practic dacă spațiul
configura țiilor este mare)

•Soluție : se aproximeaz ă distribu ția prin simularea evoluț iei unui
proces stohastic (lanț Markov) a c ărui distribu ție staționar ă
coincide cu distribu ția Boltzmann => algoritmul Metropolis

Algoritmi metaeuristici – Curs 2 28 Simulated Annealing
Algoritmul Metropolis (1953)
s(0)=aproximație inițială
k=0
REPEAT
s’=perturb( s(k))
IF f(s’)<f(s (k)) THEN s(k+1)=s ’ (necondi ționat )
ELSE s(k+1)=s ’
cu probabilitatea min{1,exp( -(f(s’)-f(s(k))/T)}

k=k+1
UNTIL “ este indeplinita o conditie de terminare ”

Algoritmi metaeuristici – Curs 2 29 Simulated Annealing
Algoritmul Metropolis – propriet ăți

• Alta probabilitate de acceptare :
P(s(k+1)=s ’) = 1/(1+exp(( f(s’)-f(s(k))/T))
• Implementarea unei reguli de atribuire cu o anumit ă probabilitate
u=rand(0,1 )
IF u<P( s(k+1)=x’) THEN s(k+1)=s ’
ELSE s(k+1)=s (k)

• Valori mari pentru T -> probabilitate mare de acceptare a
oricarei configura ții (similar cu căutare a pur aleatoare)
Valori mici pentru T -> probabilitate mare de acceptare doar
pentru configura țiile care conduc la micșorarea funcției obiectiv
(similar cu o metodă de descre ștere sau căutare de tip greedy )

Algoritmi metaeuristici – Curs 2 30 Simulated Annealing
Algoritmul Metropolis – propriet ăți
• Generarea unor noi configura ții depinde de problema de rezolvat
Optimizare în domenii continue
s’=s+z
s=(z1,…,zn)
zi : generata in cf. cu repartitia

• N(0,T)

• Cauchy(T) (Fast SA)

• altele Optimizare combinatorial ă
Noua configura ție se selecteaz ă
determinist/ aleator din
vecin ătatea configura ției
curente
Exemplu: TSP – transformare de
tip 2-opt

Algoritmi metaeuristici – Curs 2 31 Simulated Annealing
Simulated Annealing = aplicare repetat ă a algoritmului Metropolis
pentru valori din ce în ce mai mici ale temperaturii

Structura general ă
Init s(0), T(0)
i=0
REPEAT
aplică Metropolis (pentru una sau mai multe iteratii)
calcul T(i+1)
i=i+1
UNTIL T( i)<eps
Problema: alegerea schemei de modificare a temperaturii (“cooling
scheme”)

Algoritmi metaeuristici – Curs 2 32 Simulated Annealing
Scheme de r ăcire:

T(k)=T(0)/(k+1)

T(k)=T(0)/ ln(k+c )

T(k)= aT(k-1) (a<1, ex: a=0.995)
Obs. 1. T(0) se alege astfel încât la primele iterații să fie acceptate
aproape toate configura țiile generate ( pentru a asigura o bună
explorare a spa țiului soluțiilor)
2. Pe parcursul procesului iterativ este indicat să se re țină de
fiecare dată cea mai bună valoare întâlnită

Algoritmi metaeuristici – Curs 2 33 Simulated Annealing
Propriet ăți de convergență :

Dacă sunt satisf ăcute propriet ățile:

• Pg(s(k+1)=s ’|s(k)=s)>0 pentru orice s și s’ (probabilitatea de
trecere între oricare două configura ții este nenul ă)
• Pa(s(k+1)=s ’|s(k)=s)=min{1,exp( -(f(s’)-f(s))/T)} (probabilitate de
acceptare de tip Metropolis)
• T(k)=C/ lg(k+c ) (schema logaritmic ă de răcire)

Atunci P(f(s (k))=f(s*)) -> 1 (s(k) tinde în probabilitate la minimul global
s* când k tinde la infinit )

Algoritmi metaeuristici – Curs 2 34 Simulated Annealing
Variante : alte probabilit ăți de acceptare (Tsallis )


>∆>≤∆> ∆−−≤∆
=−
1 10 ,01 10 , )/)1(1(0 ,1
)'()1/(1
f-q), (Δff-q), (Δf Tfqf
sPq
a
)1,0()( )'(
∈−=∆
qsf sff

Algoritmi metaeuristici – Curs 2 35 Simulated Annealing
Exemplu : problema comis voiajorului
(TSPLib : http://comopt.ifi.uni -heidelberg.de/software/TSPLIB95 )
Instanta test: eil51 – 51 orase

Parametrii :
• 5000 iteraț ii cu modificarea parametrului T la fiecare 100 de iteraț ii
• T(k)=T(0)/(1+log(k))
0102030405060010203040506070
Distribuț ia oraselor

Algoritmi metaeuristici – Curs 2 36 Simulated Annealing
Exemplu: problema comis voiajorului
Instanta test: eil51 (TSPlib)
0102030405060010203040506070
0102030405060010203040506070
T(0)=10,cost=478.384 T(0)=1, cost=481.32
0102030405060010203040506070T(0)=5, cost=474.178
Cost minim: 426