1
Metode de cǎutare directǎ (MCD)
Sunt utilizate pentru optimzarea sistemelor descrise prin funcţii criteriu y(u), nu
neapǎrat diferenţiabile, mono sau multivariabile fǎrǎ şi cu restricţii.
Aceste metode nu folosesc derivatele funcţiei criteriu şi se bazeazǎ pe ideea înaintǎrii
spre optim prin îmbunǎtǎţiri aduse la fiecare etapǎ, valorilor calculate pentru y(u).
De regulǎ, MCD determinǎ un optim local, aşa cǎ este recomandatǎ pornirea cǎutǎrii
succesiv din mai multe puncte iniţiale alese în mod arbitrar. Pe baza rezultatelor practice
obţinute se apreciazǎ cǎ MCD sunt mai puţin eficiente decât metodele de gradient, datoritǎ
unei convergenţe mai slabe şi a unui control mai puţin riguros asupra procesului de
optimizare, dar sunt apreciate datoritǎ simplitǎţii şi posibilitǎţilor de adaptare la problemele
cu restricţii.
MCD se împart în douǎ clase mari, dupǎ dimensiunea spaţiului variabilei u din
descrierea funcţiei criteriu y(u) :
- MCDU metode de cǎutare directǎ unidimensionalǎ (monovariabilǎ);
- MCDM metode de cǎutare directǎ multivariabile.
Primele se folosesc pentru optimizarea sistemelor descrise de funcţii criteriu
monovariabile, iar celelalte pentru optimizarea sistemelor descrise de funcţii criteriu
multivariabile.
Fundamental, MCD diferǎ prin modul în care se efectueazǎ “cǎutarea”, adicǎ prin
alegerea direcţiilor şi paşilor de înaintare spre optim, iar esenţial este faptul cǎ, la fiecare
etapǎ se calculeazǎ valoarea funcţiei criteriu în punctele noi localizate în vederea detectǎrii
unor eventuale succese sau insuccese.
1. Metode de cǎutare directǎ unidimensionalǎ monovariabilǎ (MCDU).
Sunt folosite pentru calculul optimului funcţiei y(u) monovariabile fǎrǎ şi cu restricţii,
dar în special sunt utilizate avantajos ca proceduri de estimare a pasului optimal de înaintare
pe o direcţie datǎ, în metodele de optimizare pentru funcţii multivariabile.
Aceste metode folosesc, în principal, urmǎtoarele douǎ proceduri de estimare a
optimului:
- interpolarea - procedurǎ care constǎ în aproximarea funcţiei reale y(u) în jurul
punctului de optim printr- un polinom de interpolare şi detectarea în continuare a
optimului acestui polinom.
- Eliminarea intervalelor = procedurǎ care constǎ în împǎrţirea succesivǎ a aunui
inteval dat de pe axa realǎ care conţine optimul în subintervale şi excluderea repetatǎ
a acelora care nu conţin punctul u*.
Faţǎ de aceste precizǎri, MCDU se clasificǎ în:
- MCDUI – metode de cǎutare directǎ unidimensionalǎ (monovariabilǎ) de interpolare
2
- MCDUE - metode de cǎutare directǎ unidimensionalǎ (monovariabilǎ) cu eliminarea
intervalelor
MCDUI se bazeazǎ pe aproximarea evidentǎ a funcţiei criteriu y(u) în jurul optimului u*.
* * 2 *
1
( ) ( ) ( ) ''( )
2
y u y u u u y u
(1)
Relaţia (1) dovedeşte cǎ y(u) se comportǎ în jurul punctului u* ca o veritabilǎ funcţie
pǎtraticǎ şi este posibilǎ o aproximare a lui y(u) printr-un polinom de interpolare, uzual de
gradul doi. În acest fel, optimul u* al funcţiei y(u) poate fi redat prin optimul (extremul)
polinomului de interpolare.
Interpolarea pǎtraticǎ (prin polinom de gradul doi) se executǎ dupǎ ce se efectueazǎ o
deplasare prealabilǎ spre zona optimului unde se reţine un numǎr suficient de puncte de
inperpolare. Apoi se construieşte polinomul şi se calculeazǎ optimul sǎu care urmeazǎ sǎ
aproximeze u*. Dacǎ nu se asigurǎ o precizie bunǎ, procedeul se repetǎ.
MCDUE se bazeazǎ, aşa cum s-a specificat, pe eliminarea succesiva a unor
subintervale care nu conţin punctul de optim al funcţiei y(u). Determinarea comodǎ a acestor
subintervale este posibilǎ din considerente legate de comportarea funcţiilor unimodale.
Funcţia y(u) este unimodalǎ pe un interval [a, b] dacǎ pentru oricare douǎ puncte u1 şi u2, cu
u1<u2, din (a, b) sunt satisfǎcute condiţiile:
*
2 2 1
*
1 1 2
( ) ( )
( ) ( )
u u y u y u
u u y u y u
(2)
unde u* este punctul optim (minim) staţionar al lui y(u) din (a, b). În acest fel, este posibilǎ
reducerea intervalului inicial [a, b] cu care se realizesazǎ reducerea, se construiesc cu ajutorul
şirului de numere al lui Fibonacci, definit astfel:
01
1 2;
1
2
N N N
FF
F F F N
(3)
Sunt prezentate sub formǎ algoritmicǎ cele mai moderne MCDU şi anume:
- din cateforia MCDUI – metoda COGGINS
- din categoria MCDUE – metoda FIBONACCI
Metoda COGGINS – este utilizatǎ pentru optimizrea sistemelor monovariabile, descrise prin
funcţii y(u) neliniare fǎrǎ restricţii şi minimizeazǎ y(u).
Dacǎ se considera trei puncte reţimute pentru interpolare f(u1, u2, u3), punctul care
aproximeazǎ extremul funcţiei se determinǎ dipa relaţia:
2 2 2 2 2 2
*2 3 1 3 1 2 1 2 3
2 3 1 3 1 2 1 2 3
( ) ( ) ( ) ( ) ( ) ( )
1
2 ( ) ( ) ( ) ( ) ( ) ( )
u u y u u u y u u u y u
uu u y u u u y u u u y u
(4)
Punctul de aproximare este extremul polinomului pǎtratic de interpolare.
3
Aproximarea trebuie sǎ asigure o anumitǎ precizie impusǎ. Dacǎ aceasta un este
obţinutǎ, procesal de unterpolare se repetǎ, reţinâcd extremul vechiului polimom printre cele
trei puncte cu cae se realizeazǎ interpolarea urmǎtoare.
Algoritmul metodei Coggins este urmǎtorul:
Pasul 1. Se alege un punct arbitrar de pornire u0 şi se calculeazǎ y(u0).
Pasul 2. Se efectueazǎ o deplasare din uo cu pas Δu şi de calculeazǎ y(u0 + Δu).
Pasul 3. Dupǎ primal pas, se dubleazǎ mǎrimea Δu dupǎ fiecdare îmbunǎtǎţire şi se
înjumǎtǎţeǎte dacǎ se obţine un eşec.
Pasul 4. Dacǎ ultimele cele mai bune puncte din regiunra minimului lui y(u) sunt ui, ui-1, ui-2
(ui fiind ultimul punct în care y(u) realizeazǎ o scǎdere faţǎ de valorile anterioare), se
construieşte punctul adiţional:
11
2
ii u
uu
(5)
unde Δu este mǎrimra curentǎ a pasului.
Pasul 5. Se reţin din punctele (ui, ui-1, ui-2) cele mai bune trei puncte renumerotate (u1, u2, u3)
şi se determinǎ punctul de extrem al polinomului pǎtratic de interpolare care apoximeazǎ
minimul lui y(u):
2 2 2 2 2 2
*2 3 1 3 1 2 1 2 3
2 3 1 3 1 2 1 2 3
( ) ( ) ( ) ( ) ( ) ( )
1
2 ( ) ( ) ( ) ( ) ( ) ( )
u u y u u u y u u u y u
uu u y u u u y u u u y u
(6)
Pasul 6. Se evalueazǎ y în punctul u* şi se comparǎ u* cu cel mai bun punct din cele trei (u1,
u2, u3) spre a se satisface un driteriu de convergenţǎ dfe tipul:
|u* - ui (cel mai bun)| < EPS 1 (i = 1, 2, 3)
Dacǎ criteriul este satisfǎcut se reţine u* ca punct de minim pentru y(u).
Dacǎ criteriul un este satisfǎcut, se reţin cele mai bune trei puncte din cele patru
(u1, u2, u3, u*) şi procesul di interpolare continuǎ pânǎ ce criteriul este satisfǎcut.
Metoda FIBONACCI – este utilizatǎ pentru optimizarea sistemelor monovariabile neliniare,
cu restricţii şi minimizeazǎ y(u) cu a1 < u < b1.
Limitele superuiarǎ şi inferioarǎ b1 şi a1 sunt constante impuse. Dacǎ o funtie y(u) este
unimodalǎ pe intervalul data [a1, b1], atunci, fiind date douǎ valori ale variabilelir situate de
aceeaşi parte a optimului, cea care aste mai aproape de aceasta va furniza pentru funcţie o
valoare mai bunǎ.
Algoritmul metodei Fibonacci este urmǎtorul:
Pasul 1. Se delimitezǎ inicial pentru investigaţie intevalul L1 = [a1, b1] .
4
Pasul 2. Se impune precizia doritǎ, prin valoarea α şi se determinǎ câte numere Fubibaccu vir
fi utilizate pentru atingerea preciziei dorite, din relaţia:
1
N
F
(7)
Pasul 3. Se determinǎ primele douǎ puncte u1 şi u2 (u1 < u2) la disanţa l1 de capetele
intervalului [a1, b1]:
1 1 1
2 1 1
2
11
N
N
u a l
u b l
F
lL
F
(8)
Pasul 4. Se evalueazǎ funcţia y(u) în punctele u1 şi u2 şi se eliminǎ o parte din intervalul
[a1, b1] prin relaţiile (9) :
- pentru y(u1) < y(u2) a1 ≤ u* ≤ u2 (9)
- pentru y(u1) > y(u2) u1 ≤ u* ≤ b1
unde u* este punctul de optim ce trebuie localizat.
Noul interval pentru investigaţie este:
L2 = [a2, b2]
unde
1
2 1 1 1
N
N
F
L L L l
F
(10)
Pasul 5. Se plaseazǎ un al treilea punct u3 în noul subinterval L2, simetric faţǎ de punctul
rǎmas (unul dintre u1 şi u2), la distanţa l2:
3 2 2
3 2 2
u a l
u b l
(11)
unde:
3
22
1
N
N
F
lL
F
(12)
Pasul 6. Se evalueazǎ funcţia y(u) în u3 şi se comparǎ cu valoarea sa în punctul rǎmas în
[a2, b2] , iar pe baza rezultatelor se reduce intervalul la:
5
2
3 1 2 2
N
N
F
L L L l
F
(13)
Pasul 7. Procedeul se continuǎ dupǎ relaţiile generale de la pasul “K”:
1
1
K K K
K K K
u a l
u b l
(14)
unde:
( 1) 1 1 1
[ , ] NK
K K K K K
N
F
L a b L L l
F
(15)
iar
( 1)
( 1)
NK
KK
NK
F
lL
F
(16)
Pasul 8. Dupǎ N-1 evaluǎri şi partiţionarea subintervalelor la fiecare etapǎ, punctul rǎmas va
fi situat în centrul intervalului ultim. Dacǎ punctul uN rezultǎ de asemenea în centrul
intervalului ultim, acesta este înlocuit cu un alt punct deviat faţǎ de centru în
*
NN
uu
.
Aceste douǎ puncte determinǎ intervalul final unde este localizat optimul lui u* cu precizia α
impusǎ.
Metoda SECŢIUNII DE AUR – este utilizatǎ pentru optimizarea sistemelor monovariabile
descrise prin funcţii neliniare, cu sau fǎrǎ restricţii. Metoda este o variantǎ îmbunǎtǎţitǎ a
algoritmului Fibonacci. Din relaţia de recurenţǎ pentru generarea şirului de numere
Fibonacci:
12N N N
F F F
(17)
se poate determina:
11
1 5 1 5
1
22
5
NN
N
F
(18)
Pentru N suficient de mare, relaţia devine:
1
1 1 5
2
2
N
N
F
(19)
6
deoarece termenul
1
15
2
N
tinde la zero.
Dacǎ se noteazǎ:
15 1.618
2
(20)
formula (19) se scrie:
11
10.447(1.618)
5
NN
N
F
(21)
Relaţia (21) genereazǎ cu aproximaţie şirul lui Fibonacci utilizat pentru cǎutarea prin
eliminarea intervalelor ce nu conţin punctul de minim.
Metoda “secţiunii de aur” înainteazǎ spre optim dublând pasul în caz de success, pânǎ
ce încadreazǎ punctul de optim. Din acest moment, începe operaţia de înaintare prin
eliminarea intervalelor, ca la algoritmul Fibonacci. Rezultǎ, deci, o înaintare acceleratǎ spre
optim.
Algoritmul metodei “secţiunea de aur” este urmǎtorul:
Pasul 1. Se alege un puncr arbitrar u0 şi se calculeazǎ funcţia criteriu în acest punct.
Pasul 2. Se evalueazǎ funcţia criteriu în u0+Δu. Dacǎ s-a obţinut o îmbunǎtǎţire, se dubleazǎ
Δu pânǎ se obţine un eşec.
Pasul 3. Dacǎ nu s-a obţinut o îmbunǎtǎţire în prima fazǎ a pasului 2, se schimbǎ sensul de
deplasare. Se calculeazǎ y în u0-Δu. În caz de îmbunǎtǎţire, se dubleazǎ Δu pânǎ se obţine un
eşec.
Pasul 4. Dacǎ în caz cǎ un s-a reuşit sǎ se obţinǎ o îmbunǎtǎţire în prima fazǎ nici la pasul 2,
nici la pasul 3, se face
'2
u
u
şi se reia cu pasul 2.
Pasul 5. Se reţin ultimele douǎ puncte notate a1 şi b1 (eşecul şi succesul anterior eşecului) şi
se ordoneazǎ în ordine crescǎtoare, a1 < b1
Intervalul L1=[a1, b1] reprezintǎ restricţia problemei care minimizeazǎ y(u) cu
11
a u b
.
Pasul 6. Se determinǎ punctele u1 şi u2 din L1 prin relaţiile:
11
1 1 1 1 1 1 1
20.382( )
ba
u a l a a b a
(22)
7
11
2 1 1 1 1 1 1
20.618( )
ba
u b a b a b a
(23)
unde:
1 1 1
122
5
; 1.618
2
L b a
l
(24)
Pasul 7. Se evalueazǎ y(u) în punctele u1 şi u2:
- dacǎ y(u1) < y(u2) atunci
*
12
a u u
- dacǎ y(u1) > y(u2) atunci
*
11
u u b
.
Noul subinterval în care se gǎseşte optimul u* va fi:
1
2 2 2 1 1
[ , ] L
L a b L l
(25)
Pasul 8. În intervalul L2 se plaseazǎ punctul u3, dupǎ realaţia:
3 2 2 3 2 2
u a l sau u b l
(26)
unde:
2
22
L
l
Pasul 9. Procesul de eliminare a intervalelor se continuǎ astfel cǎ la stadiul K de cǎutare:
uK+1 = aK+lK = aK + 0.382(bK-aK) (27)
sau
10.618( )
K K K K K K
u b l a b a
unde:
1
21
K
KK
K
LL
l si L
Pasul 10. Procedura se opreşte când este satisfǎcut un criteriu de convergenţǎ de tipul:
11
KK
u u EPS
(28)
Se observǎ cǎ de la pasul 5 metoda devine de optimizare a unor funcţii cu restricţii de forma:
11
u u b
8
Punctul de optim se obţine ca media aritmeticǎ a punctelor ultimului interval.
