Paláncz Béla - Numerikus Módszerek - 2011 - 4. Optimalizálás
4 Optimalizálás Bevezetés Az optimalizáció, egy függvény szélsőértéke helyének meghatározása, talán a legfontosabb numerikus eljárások közé tartozik. Ha valaki rendelkezik egy hatékony optimalizációs eljárással, akkor több más, első megközelítésben látszólag eltérő numerikus probémát is meg tud oldani. Mivel a szélsőérték feladatok típusai változatosak, így a megoldásukra kidolgozott módszerek is nagyon sokfélék lehetnek.
4-1 A szélsőérték-feladatok típusai A szélsőértéket (minimumot) mindig egy adott tartományban vizsgáljuk. Ha létezik a tartományban egy pont ahol igaz az, hogy ezen pont akármilyen kicsiny környezetében a függvényérték nagyobb, mint ezen pontban, akkor ott a függvénynek lokális minimuma van. Ha a tartományban több ilyen pont létezik és ezekben a függvényérték eltérők, akkor a legkisebb minimumhoz tartozó tartomány pontját globális minimumnak nevezzük, lásd 4.1 ábra.
f(x)
P2 P1
4.1 ábra Az f(x) függvény globális minimuma (P1 ) és egy lokális minimuma (P2 ).
Ha a függvény minimumát úgy keressük, hogy közben a tartománybeli pontnak valamilyen feltételt ki kell elégítenie, akkor feltételes szélsőértékről beszélünk. A feltételeket vagy megkötéseket megkülönböztetik aszerint, hogy az egyenletekkel vagy (és) egyenlőtlenségekkel adott, lásd 4.2 és 4.3 ábrák.
2
Optimalizáció_04_2011.nb
f(x)
P2 g(x)
P1
4.2 ábra Az f(x) függvény minimuma megkötés nélkül (P1 ) és a minimum g(x) = 0 megkötéssel (P2 )
f(x)
P2 P1
g(x)
4.3 ábra Az f(x) függvény minimuma megkötés nélkül (P1 ) és a minimum g(x) < 0 egyenlőtlenséggel adott megkötéssel (P2 )
Megjegyzések Az általunk vizsgált esetekben a keresési tartomány egy vektortér és a minimalizálandó függvény általánosan egy skalár-vektor függvény, a megkötés pedig egyenlet vagy egyenlőtlenség rendszer alakjában vektor-vektor függvénnyel adott. Gyakran előfordul, hogy a keresési tartomány végesszámú és diszkrétértékű elemekből áll, például gráfokkal reprezentálható problémák esetén, amikor a cél lehet egy optimális összefüggő élsorozat (út) megtalálása a gráfban (diszkrétértékű vagy kombinatorikus optimalizáció). Az optimalizáció kiterjeszthető olyan esetekre, amelynél a keresési tartomány a valós függvények tere, a minimalizálandó függvény egy funcionál és a megkötéseket differenciálegyenletek képviselik (variációszámítás). Előfordul, hogy nem csupán egy minimalizálandó függvényünk (célfüggvényünk) van hanem több és ezek "ellenérdekeltek" egymással szemben, azaz az egyik értékének csökkentése egy másik értékének növelését eredményezi (játékelmélet). Az is lehetséges, hogy a tartományt valószínűségi változók alkotják (sztohasztikus optimalizáció). Az optimalizációval legáltalánosabb értelemben az operációkutatás foglakozik, de a mesterséges intelligenciakutatásokban is fontos szerepet kap. A továbbiakban először a megkötés nélküli optimalizációs módszerek közül tekintünk át néhányat.
Optimalizáció_04_2011.nb
3
4-2 Aranymetszés Az f (x) függvény r minimumhelyét gyakran egy [xA , xBD intervallumban keressük. A függvény az intervallumban unimodális, ha a minimumhelyig monoton csökken, attól kezdve pedig monoton nő. Az intervallum módszerek (vágáson alapuló módszerek) ezt a tulajdonságot használják ki. A módszerek alkalmazásánál két belső pontban számítjuk ki a függvény értékét. Legyen a két pont x1 és x2 (xA < x1 < x2 < xB). Ha f (x1 L § f Hx2 ), akkor a minimumhely az [xA , x2 D intervallumban van, hiszen egyébként ellentmodásba kerülnénk azzal, hogy a függvény a minimumhelyig monoton csökkenő (4.4 ábra). Hasonló meggondolásból f (x1 L ¥ f Hx2 ) esetén a minimumhely az [x1 , xBD intervallumban van (4.1 ábra).
4.4 ábra A vágási módszerek alapelve
Célszerűnek tűnik az x1 és x2 pontokat az intervallum középpontjához közel választani, így az egy vágással gyakorlatilag a felére csökkenthető. Egy klasszikus geometriai fogalom azonban jobb stratégiát kínál. Ez az aranymetszés módszere. Ebben az esetben x1 = l xA + H1 - lL xB illetve x2 = H1 - lL xA + l xB ahol l az alábbi egyenlet pozitív megoldása (4.5 ábra)
λ
1- λ
λ
4.5 ábra Az aranymetszés geometriai értelmezése
1 l
=
l
Ø l2 + l - 1 = 0 Ø l =
1-l
5 -1
= 0.61803 ...
2
A módszer hatékonyságát az a speciális tulajdonsága adja, hogy az új [x1 0 , xB0 E =[xA 1 , xB0 E intervallum, x1 1 osztópontja azonos a korábbi x2 0 osztóponttal (4.6 ábra),
4
Optimalizáció_04_2011.nb
f(x)
0 xA0
0.382 0.618
x
1
x10
x20
xB0
xA1
x11 x21
xB1
4.6 ábra Az aranymetszés módszere
Az intervallum módszerek biztonságuk mellett lassúak, hiszen a felhasznált információ csupán a belső pontokban számolt két függvényérték összehasonlításából származik.
4-3 Newton-módszer Ha a függvény deriváltjának számítása nem okoz gondot akkor a Newton módszert most is alkalmazhatjuk, azzal az eltéréssel, hogy nem az f (x) =0 egyenletet, hanem az f '(x) = 0 egyenletet oldjuk meg, azaz az iterációs formula, xk+1 = xk -
f ' HxL f '' HxL
4-4 Többváltozós Newton-módszer A Newton módszer többváltozós esetben is alkalmazható. Ekkor f(x) egy skalár -vektor függvény, ahol xœℜn . Most a Taylor-sor másodrendű tagját is figyelembe vesszük: f Hxk+1 L º f Hxk L + f Hxk LT Hxk+1 - xk L +
1 2
Hxk+1 - xk LT H Hxk L Hxk+1 - xk L
azaz Df = f Hxk LT Dx +
1 2
DxT H Hxk L Dx
ahol f(x) az f(x) függvény gradiens-vektora és H a Hesse- mátrix, az f(x) függvény második parciális deriváltjainak a mátrixa ∑ ∑ x1
H HxLi,j =
∑2 f HxL
J
=
∑ xi ∑ x j ∑ ∑ x1
J
∑f HxL N ∑ x1
. . .
. . .
. . . . . . . . .
∑f HxL N ∑ xn
. . .
∑ ∑ xn
J
∑f HxL N ∑ x1
. . . ∑ ∑ xn
J
∑f HxL N ∑ xn
A minimum szükséges feltétele alapján, azaz Df = f Hxk+1 L - f Hxk L -t deriválva Dx = xk+1 - xk szerint, a derivált zérus, 0 = f HxkLT + H Hxk L Dx azaz xk+1 = xk - HH Hxk LL-1 f Hxk L
Optimalizáció_04_2011.nb
5
4-5 Gradiens módszer A Hesse-mátrix számításától eltekinthetünk, ha az ún. gradiens módszert (legmeredekebb irány módszere) alkalmazzuk, azaz egy xk pontból a legmeredekebb csökkenő irányba mozdulunk el, vagyis dk = -f Hxk L Tehát xk+1 = xk + ak dk ahol ak egy alkalmasan megválasztott pozitív lépéshossz úgy, hogy minden lépésben f Hxk+1 L < f Hxk L.
4.7 ábra A gradiens módszer elve
Ez a választás helyes hiszen a megválasztott irány akkor megfelelő, ha f Hxk+1 L < f Hxk L azaz f Hxk + a k dk L < f Hxk L A baloldalt Taylor sorba fejtve f Hxk L + a k Hõf Hxk LLT dk < f Hxk L azaz a k Hõf Hxk LLT dk < 0 Mivel a k > 0 és véges, a dk irány akkor lejtő irányú, ha Hõf Hxk LLT dk < 0 Az ak értékét úgy határozzuk meg, hogy az minimalizálja az f Hxk+1 L = f Hxk + ak f Hxk LL kifejezést. Ez minden lépésnél egy egyváltozós optimalizálást jelent. Megjegyzés A Newton módszer esetén dk = -HH Hxk LL-1 f Hxk L és ak ª 1
4-6 Nelder-Mead-módszer Ha a deriváltak sem számíthatók könnyen, közvetlen kereső módszereket célszerű használni. Most itt a NelderMead -féle szimplex módszert ismertetjük röviden. Az eljárás indításánál n +1 számú x1 ,...,xn+1 indulópontot választunk úgy, hogy az n- dimenziós térben egy poliéder (szimplex) csúcsait alkossák (n =2 esetén ez egy háromszög). A következő pontokat és műveleteket értelmezzük, lásd 4.8 ábra.
6
Optimalizáció_04_2011.nb
4.8 ábra Egy szimplex alakváltozásai 2D esetén. Az induló szimplex : f (a) < f (b) < f (c)
1) Legyen az induló szimplex (a, b, c) úgy, hogy f(a) < f(b) < f(c). 2) Ha a 3 pont elég közel van egymáshoz, akkor f(a) a minimum. 3) Különben az e pontot képezzük (c tükrözése m pontra és nyújtás) 4) ha f(e) < f(b) akkor e pontot választjuk új a c helyett, azaz az új szimplex (a, b, e), különben képezzük az r pontot (összehúzás) 5) ha f(r) < f(c) akkor az új szimplex (a, b, r) 6) ha f(r) ¥ f(b) képezzük az s1 pontot (zsugorítás) 7) ha f(s1 ) < f(c) akkor az új szimplex (a, s1 , b), különben az új szimplex (a, m, c1 ) 8) az aktuális szimplex csúcsainak átnevezése: (a, b, c) és visszalépés 2)-re Az eljárás során, a fenti műveleteket alkalmazva a szimplex alakja a függvényfelület alakjához igazodik, az árkok mentén megnyúlik és szükség esetén elfordul, végül pedig a minimumhely környezetére zsugorodik. A leállás feltétele, hogy az utolsó két iterációban a szimplex súlypontjának változása egy előre definiált e hibakorlát alatt legyen. Az alábbi ábrákon az induló szimplexet és a végső, minimumot lefedő szimplexet látjuk
4.9 ábra Induló szimplex
4.10 ábra Végső szimplex
Optimalizáció_04_2011.nb
7
4-7 Lagrange-módszer Keressük az f(x) függvény minimumát egy g(x) = 0 feltétel kielégítése mellett, azaz min f HxL x
ha g1 HxL g2 HxL g HxL = =0 . gm HxL A Lagrange-módszer esetén az eredeti feladat helyett tekintsük az alábbi függvény megkötés nélküli minimalizálását, m
L Hx, lL = f HxL + lT g HxL = f HxL + ‚li gi HxL i=1
ahol λi -k a Lagrange- féle multiplikátorok (szorzók). A minimum szükséges feltétele a parciális deriváltak eltűnése, azaz m
x L Hx, lL = x Hf HxLL + lT x Hg HxLL = x H f HxLL + ‚li gi x HHxLL = 0 i=1
és l L Hx, lL = g HxL = 0 ahol L(x, l) egy skalár-vektor függvény, a gradiens-vektorok pedig
x HùL =
∑ Hù L ∑ x1
, ...,
∑ HùL
és
∑ xn
l HùL =
∑ Hù L ∑ l1
, ...,
∑ HùL ∑ lm
A minimum elégséges feltétele, hogy ezen kívül az L (x, l) függvény Hesse-mátrixa pozitív definit legyen, azaz a mátrix sajátértékei pozitívak legyenek a szélsőérték helyén.
4-9 Büntetésfüggvény-módszer A megkötéssel definiált minimalizáció helyett, most tekintsük a következő megkötés nélküli feladatot, F Hx, KL = f HxL + K Hg HxLLT g HxL ahol K egy skalár paraméter. A K paraméter értékének növelésével az új, megkötés nélküli probléma megoldása tart az eredeti egyenlőségi megkötéssel rendelkező probléma megoldásához, hiszen K növekvő értéke miatt a minimalizáló eljárás "kénytelen" csökkenteni g(x) normáját, mivel ennek súlya a célfüggvényben egyre nagyobb és ekkor a Hg HxLLT g(x) skalárszorzat nullától való kis eltérése is nagy értéket jelent a célfüggvényben, amit minimalizálni szeretnénk. Minél nagyobb a K annál nagyobb a "büntetés" a g(x) értékének a nullától történő eltérése miatt. Ezt az egyszerű kvadratikus büntetés-függvényt Courant-féle büntetés függvénynek nevezik. 1. Példa Tekintsünk egy adott V térfogatú kúpot, amelynek magasságát, h és alaplapjának sugarát, r, úgy kell meghatároznunk, hogy a kúp felülete A minimális legyen! A minimalizálandó függvény A Hr, hL = p r A megkötés pedig
r2 + h 2
8
Optimalizáció_04_2011.nb
g Hr, hL =
1
p h r2 - V = 0
3
A minimalizálandó függvény a kvadratikus büntetés - függvénnyel, mint megkötés nélküli feladat,
F Hr, hL = p r
r2 + h 2 + K
1
2
p h r2 - V
3
A megkötés nélküli minimalizálás eredményét V = 150 esetén, növekvő K értékek mellett az alábbi táblázat szemlélteti. Az éles jegyeket kiemeltük. 1. Táblázat
K 10 100 1000 10 000 100 000 1 000 000
r 4.661122 527 454 753 4.661367 492 211 849 4.661392 006 898 920 4.661394463 338 137 4.661394700 467 220 4.661394746 079 536
h 6.591 822 727 173 977 6.592169 226 591 700 6.592203 813 096 156 6.592207257 573 435 6.592207626 102 582 6.592207601 021 399
Az exakt megoldás, amely a Lagrange- módszerrel adódik, r=
21ê6 152ê3 p1ê3
= 4.6613947326646587456
és h=
302ê3 p1ê3
= 6.5922076505088680914
4-10 Karush-Kuhn-Tucker-feltételek Ha a megkötések az egyenlőség mellett egyenlőtlenségi feltételeket is tartalmaznak, azaz keressük az f(x) függvény minimumát, min f HxL x
az alábbi megkötések mellett, g1 HxL g2 HxL g HxL = =0 . gm HxL
és
h1 HxL h2 HxL h HxL = §0 . hp HxL
A feladat Lagrange függvénye L Hx, l, mL = f HxL +lT g HxL + µT h HxL Most a lokális minimum szükséges és elégséges feltételeit az ún. Karush-Kuhn- Tucker feltételek biztosítják. A szükséges feltételek: a) Egyrészt (L (x, l, m)) = 0 vagyis
Optimalizáció_04_2011.nb
m
p
i=1
i=1
9
Hf HxLL + ‚li Hgi HxLL + ‚mi Hhi HxLL azaz a Lagrange függvény gradiens vektorának minden komponense zérus. Továbbá g (x) = 0 és minden i = 1, ..., p esetén mi h i = 0 b) Másrészt h (x) § 0 és m¥0 azaz a m vektor egyik eleme sem negatív. Az elégséges feltétel az x minimum helyén, hogy tetszőleges dx változás esetén igaz, hogy m
dxT H H f HxLL + ‚li H Hgi HxLL + ‚ mA H HhA HxLL dx > 0 i =1
A
ahol hA azok az egyenlőtlenségi megkötések, amelyekre hA (x) = 0. Ezeket ún. aktív egyenlőtlenségi megkötésnek nevezzük. Amennyiben a m
= H Hf HxLL + ‚li H Hgi HxLL + ‚ mA H HhA HxLL i =1
A
mátrix pozitív definit, a fenti elégséges feltétel igaz. (Lehet ettől függetlenül is igaz, de akkor a kérdés eldöntéséhez külön vizsgálat szükséges!) Megjegyzés à Ha az egyenlőségi megkötések lineárisak és a célfüggvény konvex, akkor a minimalizálási probléma konvex, azaz a KKT szükséges feltételelek elégségesek is. Ekkor a lokális minimum globális minimum is egyben. Egy függvény konvex, ha a Hesse mátrixa legalább pozitív szemidefinit. Egy mátrix akkor pozitív szemidefinit, ha nincs negatív sajátértéke. Természetesen ez a függvény egy lokális tulajdonsága. à Ha a célfüggvény és a megkötések egyaránt lineárisak akkor lineáris programozási feladatról beszélünk. 2. Példa Minimalizáljuk az f Hx, y, zL = Hx - yL2 + 5 z függvényt a g1 Hx, y, zL = x + y + z + 5 = 0 g2 Hx, y, zL = y - 3 z - 1 = 0 egyenlőségi és az x ¥0, azaz h1 (x,y,z) = -x § 0 egyenlőtlenségi feltételek mellett. Oldjuk meg a feladatot a KKT feltételek alapján! A Lagrange függvény L Hx, y, z, l1 , l2 , m1 L = f Hx, y, zL + l1 g1 Hx, y, zL + l2 g2 Hx, y, zL - m1 x
10
Optimalizáció_04_2011.nb
Az a) pontbeli szükséges feltételeknek megfelelő egyenletek: ∑L ∑x ∑L ∑y
Hx, y, z, l1 , l2 , m1 L = l1 - m1 + 2 x - 2 y = 0 Hx, y, z, l1 , l2 , m1 L = l1 + l2 - 2 x + 2 y = 0
∑L ∑z
Hx, y, z, l1 , l2 , m1 L = l1 - 3 l2 + 5 = 0
továbbá g1 Hx, y, zL = x + y + z + 5 = 0 g2 Hx, y, zL = y - 3 z - 1 = 0 valamint -m1 x = 0 Ez egy nemlineáris egyenletrendszer az (x, y, z, l1 , l2 , m1 ) változókra. Az egyenletrendszer megoldásai, x
88
- 49
0 7
211 98 103 - 98 5 -7 10 7
y
-2 -
z
-2
l1
4
l2
3
m1
11
3
0
Ellenőrizzük, hogy melyik megoldás elégíti ki a b) pontbeli szükséges KKT feltételeket, azaz -x§ 0 és m1 ¥ 0 Nyilván csak az első! Azt, hogy ez a szélsőérték valóban minimum, az elégséges KKT feltétel alapján döntjük el. Azonban esetünkben a megkötések lineárisak, tehát csak azt kell megnézni, hogy a célfüggvény a szélsőérték helyén konvex-e?! A célfüggvény Hesse-mátrixa, ∑f 2 ∑x2
H (f (x,y,z))=
∑f 2 ∑y ∑x
∑f 2 ∑z ∑x
∑f 2
∑f 2 ∑x ∑y
∑y
∑f 2 ∑z ∑y
∑f 2 ∑x ∑z
∑f 2 ∑y ∑z
∑z2
2
∑f 2
Ennek értéke az x = 0, y = -3.5 és z = -1.5 helyen, 2 -2 0 H = -2 2 0 0 0 0 Ennek sajátértékei, 4 c= 0 0 azaz a Hesse - mátrix szemidefinit, tehát a célfüggvény konvex, így a minimumjelölt valóban minimum!
Optimalizáció_04_2011.nb
11
4-11 Genetikus algoritmus Bár a módszert elsősorban többváltozós esetben alkalmazzuk, az egyszerűség érdekében legyen a feladat egy f (x) egyváltozós függvény globális maximumának meghatározása egy adott xœ[a, b] intervallumban, azaz max f HxL
x œ@a, bD
Az intervallum valós számokból, de mint láttuk az intervallum elég jól lefedhető véges tizedestört alakú számokkal. Minél több jegyet alkalmazunk (minél finomabb a felbontás) annál jobb a lefedés. Most alkalmazzunk kettes számrendszert. Rögzített hosszúságú bitsorozat esetén, elvileg az összes függvényértéket a= 0...00 és b=1...11 közötti értékre kiszámítva kiválaszhatjuk azt a bitsorozatot (x értéket) amelynél a függvénynek maximuma van. Miután a maximum egy jó közelítését szeretnénk megkapni, azaz a felbontás nagy, vagyis a bitsorozat hosszú, így a kiszámítandó függvényértékek száma nagyon nagy. A számítási igény lényegesen csökkenthető ha egy keresési stratégiát alkalmazunk Mutáció A módszer lényege, hogy véletlenszerűen több kiindulási bitsorozatot (egyedet) hozunk létre. Ezek alkotják az induló populációt és egyben az első, kiinduló generációt. A populáció egyedeit aszerint értékeljük, hogy hozzájuk mekkora függvényérték tartozik. Minél nagyobb függvényérték tartozik egy egyedhez, annál nagyob az egyed fittségi indexe. Kiválasztjuk a legfittebb egyedet és belőle mutációval előállítunk egy új populációt, amely a következő generáció lesz. Az egyed mutációja, az egyed (bitsorozat) génjeinek (bit-jeiknek) kis valószínűséggel való megváltoztatását jelenti. Ezt a változtatási valószínűséget rögzítve (általában 0.1~0.3), végighaladunk a biteken és vagy megváltozatjuk őket (0-ról 1-re illetve megfordítva) vagy sem. Akkor választottuk meg helyesen a mutáció valószínűségét, ha ennek az új populációnak az átlagos fittsége nagyobb lesz, mint az előző populációjé volt. Ez módszer azonban még mindig meglehetősen lassú. Így a természet létrehozta a szexualitást. Szexualitás Ebben az esetben a populációból két egyedet választunk ki (szülők). A szülők kiválasztása nem determinisztikus, azaz nem a két legfittebb egyed lesz kiválasztva, de minél nagyobb egy egyed fittsége annál nagyobb valószínűséggel lehet szülő (rulett-módszer, amelynél az egyedet reprezentáló rulettkerék szegmense arányos az egyed fittségével)! Ha kiválasztottuk a szülőket, akkor létrehozzuk ezek utódait (gyerekek). Az utódok létrehozása valamilyen rögzített valószínűséggel (általában 0.5~0.8) a szülők génjeinek keresztezésével (crossing) történik, különben klónozással. A két szülő két gyereket hoz létre. A keresztezés esetén rögzített valószínűséggel kiválasztunk egy bitpozíciót a szülők bitsorozatában, majd ettől a pozíciótól kezdve kicseréljük egymással a bitjeiket (génjeiket). A klónozásnál nincs csere, az utódok egyezőek a szülőkkel. Ezt követően, mindkét esetben még egy mutáció következik. A fenti módszerrel hozzuk létre az új generáció populációját. Az iteráció (generációk váltása) során figyeljük a populáció legfittebb egyede fittségi indexének változását. Ha ez a változás már elhanyagolható akkor befejezzük az iterációt. Biztonságként - arra az esetre ha az eljárás nem lenne konvergens - limitáljuk a generációk számát. A fenti algoritmus a legegyszerűbb BGA (Basic Genetic Algorithm), amelynek számos változata alakult ki az elmúlt 20 év folyamán. A mai rendszerek, pl. a Matlab és a Mathematica egyaránt tartalmazzák a módszert. 3. Példa Legyen a függvény, amelynek globális maximumát keressük a 0§x§1 tartományban, f (x) = -mod (9 x, 1) sin (p x)) A feladat a hagyományos optimalizációs módszerekkel nem oldható meg könnyen, lásd 4.11 ábra.
Optimalizáció_04_2011.nb
1.0
0.8
fHxL
0.6
0.4
0.2
0.0 0.0
0.2
0.4
0.6
0.8
1.0
x
4.11 ábra Az f(x) = -mod(9x, 1) sin(p x)) függvény
Az alábbi ábrákon a genetikus algoritmus eredményét látjuk standard paraméterekkel.
maximális fittségi index
12
0.4445
0.4440
0.4435
0
200
400
600
800
iterációk száma
4.12 ábra A maximális fittségű egyed fittségi indexe az iterációk (generációk) számának függvényében 1.0
0.8
0.6
0.4
0.2
0.0 0.0
0.2
0.4
0.6
0.8
1.0
4.13 ábra A generált generációk legfittebb egyedeinek elhelyezkedése
