Optimalizációs algoritmusok PDF

Optimalizációs algoritmusok PDF 1-2 Mi az optimalizálás Gyakorlatilag szinte minden a minket körülvevő világban felfogható egy opti- mizációs problémaként. A lehető legjobb eredményt elérni bizonyos körülmények között. Egy optimalizációs problémát a következőképpen írhatunk le: P = (X, f, ω)...

Optimalizációs algoritmusok PDF 1-2 Mi az optimalizálás Gyakorlatilag szinte minden a minket körülvevő világban felfogható egy opti- mizációs problémaként. A lehető legjobb eredményt elérni bizonyos körülmények között. Egy optimalizációs problémát a következőképpen írhatunk le: P = (X, f, ω) P az optimalizációs probléma X a keresési tér f a célfüggvény ω a megszorítások halmaza Célfüggvény A célfüggvény az az f : X → Y függvény amit optimalizálni szeretnénk, ahol Y ⊆ R X pedig a probléma terének nevezzük Globális minimum Az x∗ ∈ X globális minimum az f : X → R esetén, ha f (x∗ ) ≤ f (x), ∀x ∈ X Globális maximum Az x∗ ∈ X globális maximum az f : X → R esetén, ha f (x∗ ) ≥ f (x), ∀x ∈ X Lokális minimum Az x∗ ∈ X lokális minimum az f : X → R esetén, ha f (x∗ ) ≤ f (x), ∀x ∈ V (x∗ ), ahol V (x∗ ) az x∗ szomszédsága. Az x∗ ∈ X erős lokális minimum az f : X → R esetén, ha f (x∗ ) < f (x), ∀x ∈ V (x∗ ) ahol V (x∗ ) az x∗ szomszédsága. Lokális maximum Az x∗ ∈ X lokális maximum az f : X → R esetén, ha f (x∗ ) ≥ f (x), ∀x ∈ V (x∗ ), ahol V (x∗ ) az x∗ szomszédsága. Az x∗ ∈ X erős lokális maximum az f : X → R esetén, ha f (x∗ ) > f (x), ∀x ∈ V (x∗ ) ahol V (x∗ ) az x∗ szomszédsága. Típusok diszkrét vs folytonos egycélű vs többcélű megszorításos vs nem-megszorításos biztos vs bizonytalan statikus vs dinamikus lokális vs globális 1 Egycélú minimalizálási feladat Az általános megfogalmazás: minn f (x) x∈R hj (x) = 0, j = 1,...., J, gk (x) ≤ 0, k = 1,....., K, x = (x1,...., xn ) ahol hj (x) és gk (x) függvények megszorítások Egycélú maximalizálási feladat Az általános megfogalmazás: maxn f (x) x∈R hj (x) = 0, j = 1,...., J, gk (x) ≤ 0, k = 1,....., K, x = (x1,...., xn ) ahol hj (x) és gk (x) függvények megszorítások Multi-modális optimalizáció Az összes vagy a lehető legtöbb lokális optimumot meg szeretnénk egyszerre találni Dinamikus optimalizáció Adott egy ft dinamikus probléma, egy G optimalizációs algoritmus és egy op- timalizációs perioódus [tbegin , tend ], ft dinamikus optimalizációs algoritmusnak nevezzük a [tbegin , tend ] periódusban, ha a G által használt fitneszértékek változ- nak, és G-nek reagálnia kell erre a változásra Metaheurisztikák Görög szóból ered, és azt jelenti találni, mig a meta előtag ‘mögé’, ‘egy másik szintet’, jelent. A sztohasztikus optimalizáció egy részének is tekinthetjük, mely az algoritmusok egy olyan osztálya, melyben a véletlen faktor is szerepet játszik. A metaheurisztikus algoritmusokat több szempont szerint csoportosíthatjuk: - lokális vagy globális megoldásokat keres - egy elemet vagy egy populációt használ az algoritmus Hegymászó algoritmus Az egyik legrégibb és legegyszerűbb algoritmus, eredetileg egycélú függvény optimalizálása (létezik változat többcélúra is) Az alapötlet a következő - kiindulunk egy véletlen megoldásból - változtatunk rajta egy kicsit - ha a változás jobb, mint az elődje volt, akkor megtartjuk - ismételjük ezt a lépést, amíg egy leállási feltétel nem teljesül 2 Könnyen beragadhat lokális optimumokba, de ennek kiküszöbölésére léteznek különböző változatai. Változatok: - Legmeredekebb emelkedős hegymászó algoritmus - több szomszédot is megvizsgálunk, és azokból választjuk a legjobbat - Véletlenszerűen újra induló hegymászó algoritmus - ebben a változatban többször egymás után futtatjuk le a hegymászó algoritmust, és az összes közül a legjobb megoldást tartjuk meg. Tabu keresés A tabu keresés egy memóriát használ, amelyben a már kiértékelt, de nem megfelelő megoldásokat tesszük, és amelyekre nem szeretnénk visszatérni, ez lesz a tabu lista, általában diszkrét feladatok esetén használjuk. Paraméterek: - a tabu lista hossza - iterációk száma - az elemek száma, amit keg kell vizsgáljunk Előnyök: - használható folytonos és nem folytonos esetben is - néha elfogad olyan megoldást is, ami nem feltétlenül javít, amiatt, hogy kerüljön ki a lokális optimumból Hátrányok: - túl sok paraméter - sok iterációt igényel Szimulált lehűtés 1980-as években jelent meg, az alapelve, hogy valamilyen kicsi valószínűséggel a rosszabb keresési irányba elinduljon, ezáltal nem ragad be lokális optimumba Az algoritmus a fémek edzési folyamatát idézi, egy lassú hűtés során a fém egy optimális szerkezetbe jut. Az algoritmus paramétere a hőmérséklet, mely a keresés során folyamatosan csökken. A kohászatban a lehűtés a fémeket, illetve az üveget edző keményítő folyamat, amikor azokat magas hőmérsékletre felmelegítjök, majd fokozatosan lehűtjűk, lehetővé téve, hogy az anyag alacsony energiáju kristályos állapotba kerüljön. A legjobb lépés megtétele helyett véletlen lépést tesz, ha a lépés javít akkor mindig végrehajtásra kerül, különben pedig a lépést csak valamilyen 1-nél kisebb valószinűséggel teszi meg. Az emlitett valószínűség exponenciálisan csökken a lépés rosszságával és a hőmérséklet csökkenésével. Lehűtési mechanizmusok Fontos tudni való, hogy az algoritmus eredménye rendkívűl függ a lehűtési mechanizmustól is, hisz ez fogja a hőmérsékletet csökkenteni. exponenciális: Tk = T0 ∗ αk , 0.8 < α < 0.9 logaritmikus: Tk = 1+α∗log(1+k) T0 ,1 Paraméterek: rajméret - hány részecskét használunk, ha túl nagy a szám, az algoritmus lassú 5  α - mennyire fontos az eredeti sebesseg β - az adott részecske legjobb értékének a fontossága, ha a β értéke túl nagy, akkor legnkább csak a saját legjobb értékeket vesszük figyelembe γ - az informátor legjobb értékének a fontossága, fontos az is, hogy hány informátor van, minél több, annál közelebb leszünk a globaális optimumhoz δ - a globális legjobb érték fontossága, ha az érték túl nagy, akkor leginkább már a felfedezett terület felé irányul a keresés ϵ - milyen gyorsan mozogjanak a részecskék, ha az értéke nagy, nagyobb ugrások lesznek a térben Négy fontos csoport a paraméterek alapján teljes modell: γ, δ > 0 csak megismerés: γ > 0, δ = 0 csak szociális: δ > 0, γ = 0 önzetlen: δ > 0, γ = 0 és a globális legjobb különbözik az informátortól Raj topológia gyűrű topológia - néhányan kommunikálnak egymással egy gyűrűn, pl. két szomszéddal csillag topológia Részecskék frissítése szinkron - egyszerre történik az összes részecske változtatása aszinkron - az adott lépésben azonnal megváltozik a részecske poziciója és sebessége Evolúciós algoritmusok 4 fő evolúciós algoritmus: - genetikus algoritmusok - evoluciós algoritmusok - evoluciós programozás - genetikus programozás - differenciál evolúció Differenciál evolúciós algoritmus Mutáció - DE/rand/1 - vi = xr1 + F1 (xr2 − xr3 ) - DE/best/1 - vi = xbest + F1 (xr2 − xr3 ) - DE/rand to best/1 - vi = xr1 + F1 (xr2 − xr3 ) + F2 (xbest − xr1 ) - DE/curr to best/1 - vi = xi + F1 (xr2 − xr3 )F2 (xbest − xi ) - DE/rand/2 - vi = xr1 +F1 (xr2 −xr3 +xr4 −xr5 ) - DE/best/2 - vi = xbest +F1 (xr2 −xr3 +xr4 −xr5 ) PDF 4 Genetikus algoritmusok egy algoritmus család, az evolúciós algoritmusok részét képezik egy lehetséges megoldást kromószóma-szerű adatstruktúrában tárolnak 6  természetből inspirált fogalmakat használ, mint amilyen azö öröklődés, mutáció, kiválasztás és keresztezés Megoldások kódolása Bináris: minden kromoszóma egy 0-ásokból és 1-esekből álló lista Permutációs: minden kromószóma ugyanazon értékeket tartalmazza per- mutálva Egész érték alapú: minden kromószóma egész értékeket tartalmaz Valós érték alapú: minden kromószóma valós értékeket tartalmaz Genetikus operátorok - kiválasztás - keresztezés - mutáció Mutáció Előnyei - új értékeket hozhat be, olyanokat amelyek még nincsenek a populációban - véletlenszerűség megakadályozza, hogy lokális optimumba akadjunk Operátorok - leggyakrabban használt a FlipBit - egyéb lehetőségek például a Határolt, Uniform vagy Gaussian - az operátorokat a kódolás alapján válasszuk ki Flip Bit Bit reprezentáció esetén kiválasztunk egy gént és invertáljuk: - 0-t 1-re állit - 1-t 0-ra állit Egész esetben random új érték választás a lehetséges értékek közül creep mutáció: +- érték hozzáadása egy gén értékéhez Valós esetben random változtatás – x1 , x2 ,...., xn → x′1 , x′1 ,....., x′n , ahol xi , x′i ∈ [Li , Ui ] ∗ egyenletes mutáció ∗ nem-egyenletes mutáció Permutációs esetben swap mutáció: két index véletlen kiválsztása és cseréje insert mutáció: két index véletlen kiválsztása, a második első után való másolása, a többi arrébb tolása scramble mutáció: egy rész kiválsztása és felcserélése véletlenszerűen inversion mutáció: egy rész kiválasztása és fordított sorrendbe helyezése 7 Keresztezés Bit reprezentáció és egész reprezentáció Egy pont alapú – A keresztezési ponton elvágjuk a két listát és felcseréljük azokat Két pont alapú – Választunk két pontot a kromoszómán belül, majd a szülök génjeit cseréljük fel a pont között N pont alapú N darab vágási pontunk van Egyenletes – Egy kereszteződési ráta megmondja az egyes szülők hozzájárulását az udótok génjeihez – Gén alapú keresztezést tesz lehetőve Valós reprezentáció Diszkrét keresztezés - ugyanaz mint a bitesnél Aritmetikai keresztezés – két szülő: x és y – a leszármazott: zi = α ∗ xi + (1 − α) ∗ yi , ahol 0 ≤ α ≤ 1. – Az α paraméter lehet ∗ konstans ∗ random ∗ változó a program futása során Egyszerű aritmetikai kereszteződés – k és α szükséges – minden k. kromószóma utáni krómószómát a fenti képlettel keresztezünk – a kereszteződés után két egyed jön létre melynek az első k krómószómája megegyezik egy-egy szülővel s a többi ugyanaz a képlet szerint – Egyes aritmetikai kereszteződés ∗ k és α szükséges ∗ a k. krómószomát keresztezzük a képlet szerint ∗ a kereszteződés után két egyed jön létre melynek a krómószómái megegyeznek egy-egy szülőjével kivéve a k. ami a kereszteződés szerint van – Teljes aritmetikai kereszteződés: ∗ a kereszteződés után két egyed jön létre, melyeknek az összes krómószómái keresztezve vannak Permutációs reprezentáció esetén Partially Mapped Crossover Edge Crossover 8  Order Crossover Cycle Crossover Keresztezés vs mutáció Keresztezés - explorative - nagyobb ugrások a térben Mutáció - exploitative - kisebb finomítások Kiválasztás Ki kell választani azokat a kromoszómákat amelyek utódokat készítenek Roulette-kerék alapú kiválsztás az egyedek kiválasztásának valószínűsége arányos az egyedek fitneszével pi = PNfi fj j=1 SUS egy szerencsekerék, egyszerre több nyertes Rang alapú kiválasztás sorrendbe helyezzük az egyedeket, és rangsoroljuk őket a rangsorokhoz rendelhetünk valószínűségeket Elitista kiválasztás a legjobb egyedei az aktuális generációnak, garantáltan továbbjutnak a következő generációba garantálja, hogy a már megtalált jó megoldások ne vesztődjenek el amennyiben nagyon jó megoldásra lelünk, az összes megoldás gyorsan felé fog konvergálni Túlélők kiválasztása lecsökkenti az m populáció méret + l leszármazott számát m-re két megközelítés – kor alapú szelekció, a leszármazott valamennyi ideig benne marad a populációban ∗ FIFO ∗ random - nem ajánlott – fitnesz alapú ∗ elitista ∗ genitor - a legrosszabb törlése 9 Paraméterek keresztezés valószínűsége – ha túl nagy, akkor a jól teljesítő egyedeket hamarabb kiszűrjük, mint hogy az algoritmus újakat készitene – ha túl kicsi akkor stagnálás – általában 80% - 95% között mozog mutáció valószínűsége – ha túl nagy akkor szinte csak véletlen megoldások generálódnak – ha túl kicsi, akkor helyi optimumok felé konvergál a megoldás – általában 0.5% - 1% körül mozog populáció mérete – ha túl nagy akkor lassú az algoritmus – ha túl kicsi akkor kevés lesz a kereszteződés és a keresési tér kis részét járjuk be – egy jó szám 20-30 körül mozog, de egészen 100-ig is lehet találni okés eredményeket PDF 5 Többcélű optimalizálás Többcélú minimalizálási feladat Az általános megfogalmazás: minn fi (x), x∈R i = 1,...... , M, hj (x) = 0, j = 1,...., J, gk (x) ≤ 0, k = 1,....., K, x = (x1,...., xn ) ahol hj (x) és gk (x) függvények megszorítások Többcélú maximalizálási feladat Az általános megfogalmazás: maxn fi (x), x∈R i = 1,...... , M, hj (x) = 0, j = 1,...., J, gk (x) ≤ 0, k = 1,....., K, x = (x1,...., xn ) ahol hj (x) és gk (x) függvények megszorítások Megoldások Dekompoziciós technikák (súlyozott összegek módszere, súlyozott Csebisev) Pareto dominancia alapú algoritmusok Indikátor alapú technikák 10 Súlyozott összegek módszere Az egyik legkézenfekvőbb megoldás, ha a több célfüggvényt átalakítjuk egy célfügvénnye, ezt a súlyozott összegek módszereének nevezzük (f1 (x),...., fm (x)) → W S(x) Pm Pm W S(x) = i=1 wi fi (x), ahol 0 ≤ wi ≤ 1, i=1 wi = 1 Nagyon sok célfüggvény is átalakitható egy célfüggvényre, viszont nehéz meg- találni a megfelelő súlyokat Súlyozott Csebisev módszer Adott egy z = (z1 ,..., zn )ref erenciapont A Csebisev norma: gw (x, z) = maxi=1,m wi |fi (x) − zi , ∀x ∈ S A feladat az átalakítás után: min gw (x, z), úgy hogy gi (x) ≥ 9 es hj (x) = 0 Pareto Pareto optimalitás: Egy megoldás Pareto optimális, ha nem tudunk egyik célfüggvényben sem javítani, anélkül, hogy valamelyik másikban rosszabb eredményt kapjunk Pareto dominancia: ∀x, y ∈ X esetén x dominálja y − t ha fi (x) ≤ fi (y), i = 1...M és ∃j, fj (x) < fj (y) Pareto front: A nem dominált megoldások halmazát Pareto frontnak nevezzük Dominancia: - dominancia rang - hány egyed dominált egy adott egyedet - dominancia számolás - egy egyed hány egyedet dominál - dominancia mélység - melyik fronton találhato egy egyed PDF 6 Evoluciós stratégiák csak egy új pontot hoz létre az új pont koordinátáit úgy kapja meg, hogy a régi ponthoz hozzáad egy 0 várható értékű, σ szórású normális eloszlású véletlen számot ha az új pont jobb, akkor ő lesz a kiindulási pont, ha nem akkor marad a régi, elitista a szórást adaptívan változtatja (1 + 1) - ES inicializálás < x1 , x2 ,..., xn > véletlen értékekkel minőség meghatározása utód létrehozása, x′i − xi + N (0, σ) evaluálás, a minőség meghatározása az útod esetén jobb érték megtartása a kettő között 11 Mutáció típusok 1: - a σ a kromoszóma része - a mutáció: - σ ′ = σ ∗ exp(τ ∗ N (0, 1)) - x′i = xi + σ ′ ∗ N (0, 1) - τ = 11 n2 2: - minden σi , i = 1...n a kromoszóma része - a mutáció - σi′ = sigmai ∗ exp(τ ∗ N (0, 1) + τ ∗ Ni (0, 1)) - x′i = xi + σi′ ∗ N (0, 1) - τ = 1 1 2n 2 Kereszteződés operátorok Az alap változatban nincs kereszteződés - Dis- zkrét keresztezés, amikor egy új tulajdonság megegyezik az egyik szülő tulaj- donságával - Számtani keresztezés: legyen 0 ≤ α ≤ 1, akkor - az egyik utód: αx + (1 − α)y - a masik: (1 − alpha)x + αy - Keverés: Az előbbi α konstans helyett egy véletlen szám lesz Szelekció Az evoluciós stratégiák tipikusan jóval több útodot hoznak létre, majda ezek közül kiválasztják a legjobba. A szelekciós nyomást a két szám hányadása határozza meg, általában 14 vagy 71. Ez a módszer a (µ, λ) Ha a szülök közül is lehet választani akkor (µ + λ) kiválasztásról beszélünk. Alaptípusok (1 + 1) - 1 szülő és 1 utód, megtartjuk a legjobbat (µ + 1) - µ szülő és 1 utód s elhagyunk 1-t kiválasztáskor (µ + λ) - µ szülő és λ utód, elhagyjuk a λ legrosszabbat (µ, λ) - Nem választhatunk szülőkból Genetikus programozás leginkább gépi tanulás problémáira lassú GA, ES, EP esetén a kromoszómák lineáris szerkezetűek a fa reprezentáció nem-lineáris struktúra GA, ES, EP esetén a kromószoma hossza nem változik a fák növekedhetnek mélységben és szélességben is Fa reprezentáció terminal halmaz T függvény halmaz F Rekurzív definició – ∀t ∈ T helyes kifejezés – f (e1 ,...., en ) helyes kifejezés ha f ∈ F, f argumentumainak száma n, e1 ,...en helyes – nincs más formája a helyes kifejezésnek 12 Leszármazott létrejötte GA esetén mutáció és kereszteződés GP esetén mutáció vagy kereszteződés Mutáció az egyik leggyakoribb formája: egy random kigenerált csomópontnál egy random generált fát szúrunk be Kereszteződés a leggyakoribb fajta: két részfa felcserélése két paraméter – a pc valószínűség, mely megmondja, hogy kereszteződést vagy mutációt használunk – egy véletlen belső pont, amely megadja a keresztődés helyét Szelekció szülő kiválasztása: fitnesz arány nagy populáció esetén a kiválasztas: – fitnesz szerint rangsoroljuk a populációt – két csoportra osztjuk ∗ első csoport a populáció legjobb x-a ∗ a második a szemét Inicializálás a fa maximális mélységét beállítjuk Dmax -ra a teljes módszer (minden ág mélysége = Dmax ) növekvő módszer (minden ág mélysége ≤ Dmax ) a kettő kombinilása Genetikus programozás típusai Lineáris genetikus programozás Gráf alapú genetikus programozás Multi expression genetikus programozás Cartesian genetic programming Gene Expression Genetic Programming PDF 7 Evolúciós Programozás legyen intelligens intelligencia alatt adaptivitást értünk 13  az adaptivitás egyik előfeltétetele az előrejelzés előre jelzés véges automatákkal Kiválasztás Minden egyed leszármazottat kreál Túlélők kiválsztaása: P (t)-ben µ darab egyed, P ′ (t)-ben µ darab utod. Bajnok- ság: - minden x egyed a P (t) ∪ P ′ (t)-ből q darab egyeddel hasonúl, az x nyeresége függ a legyőzött egyedek számától - a µ darab legjobb egyed kerül a következő generációba ÖSSZEHASONLITAS Genetikus algoritmusok – Az evolúciós algoritmusok legáltalánosabb formája – Populáció, fitnessz, kiválasztás, keresztezés, mutáció Evoluciós stratégia – Csak egy pont – Új pont meghatározása σ szórásu, egyenletes eloszlású véletlen szám- mal. A szórás adaptvan váltózik (1/5-ös szabály) – Változó populáció: ∗ 1 + 1 ES ∗ µ + λ ES ∗ µ, λ ES Evoluciós programozás – Eredetileg csak véges állapotú automaták segítségével – µ + µ kiválasztás – Nincs keresztezés de mindig van mutáció – Újabb változatai más kromoszómákat is engednek, ezzel egyre inkább összeolvad az Evoluciós Stratégiával Genetikus programozás – Gépi tanulási proglémákra – Fa reprezentáció – Egy helyes kifejezés rekurzív definiciója – Mutáció VAGY Keresztezés Hibrid evolúciós algoritmusok javítani az evolúciós algoritmus teljesítményét az evolúciós algoritmus beépítése egy nagyobb rendszerbe javítani az evolúciós algoritmusok által megtalált megoldásokat Hibrid architektúrák hibridizáció két evolúciós algoritmus között neurális hálok általi evolúciós algoritmusok fuzzy logika általi evolúciós algoritmusok PSO általi evolúciós algoritmusok 14  ACO általi evolúciós algoritmusok bakteriális táplálkozás általi evolúciós algoritmusok hibridizáció egy evoluciós algoritmus és egy más heurisztika között - memetikus algoritmus Memetikus algoritmusok osztályozása első generációs MA - globális keresés párosítása lokálisa kereséssel második generációs MA - globális keresés párosítása többszörös lokálisa kereséssel harmadik generációs MA - globális keresés párosítása többszörös lokális kereséssel, a lokális kereső algoritmus kiválasztásának megtanulása. PDF 8 Paraméterek beállítása Paraméter tuningolás a tesztelés hagyományos módja és a különböző értékek összehasonlítása az igazi futás előtt – felhasználók hibái a beállítsáokban lehetnek hibaforrások – sok időbe telik – paraméterek kölcsönhatásba lépnek, a teljes keresés nem megval- osítható – a jó értékek rosszá válhatnak futás során Paraméter kontroll értékek beállítása online- tényleges futás közben – előre meghatározott időben változó ütemezés – a keresési folyamatból származó visszajelzések felhasználásval – paraméterek kódolása a kromoszómákban és a természetes kiválasztas közben problémák – az optimális p-t nehéz megtalálni, az optimálist p(t)-t nehezebb megtalálni – mé mindig a felhasználó által definiált visszacsatolási mechanizmus Típusok determinisztikus: valamilyen szabály módosítja a stratégia paraméterét, visszajelzés nélkül a kereséstől adaptív: valamilyen mértéken alapuló visszacsatolási szabály, nyomon követni a keresés folyamatát önadaptív: a paraméterértékek együtt fejlődnek megoldások a kro- moszómákba kódolva 15 PDF 9 Multi-modális optimalizáció Az összes optimum meghatározása Ne csak egy megoldást adjunk a döntéshozónak, hanem az összes lehetséges megoldást Alkalmazási lehetőségek - adatelemzés - optimális design a gépészetben Implicit megközelítés Fitness sharing Az ugyanahoz a régióhoz tartozó pontok büntetést kapnak Clearing - 0-ra állítja a fitneszt abban az esetben, ahol ugyanahoz a régióhoz tartoznak Crowding Explicit megközelítés A populációt több al-populációra osztjuk, mindegyik külön optimumot keres Dinamikus optimalizáció Adott egy ft dinamikus probléma, egy G optimalizációs algoritmus és egy opti- malizációs periódus [tbegin , tend ], f_t$-t dinamikus optimalizációs algoritmusnak nevezzük a [tbegin , tend ], ha a G által használt fitneszértékek változnak, és G-nek reagálnia kell erre a változásra Evolúciós algoritmusok DOP-ra Amint észreveszünk egy változást, inditsuk újra az algoritmust: - könnyen implementálható - nem a legjobb megoldás, mert költséges, a változás előtt és után nagyon változó eredmények Más megközelítés - memória használata: tárolni és újra hasznosítani - sokféleség: konvergencia kezelése - multi-populáció: szubpopulációk használata - adaptív: operátorok adatálása - hipermutáció: a mutáció értéke változik - hiperszelekció: a szelekciós nyomás változtatása - hipertanulása: a tanulási arány növelése - előrejelzés: előrejelzi a változásokat Hiperheurisztikák A hiperheurisztika olyan heurisztikus keresési módszer, amely automatizálni igyekszik, gyakran gépi tanulási technikál beépítésével, több egyszerűbb heurisztika kiválasztásának, kombinálásának, generálásnak vagy adaptálásának foolyamatát a számítási keresési problémák hatékony megoldása érdekében. 16 PDF 10 Large Scale GLobal Optimizazion Az a dimenzió amitől a létező algoritmusok nem mükődnek jól: - bináris: 1 milliárd - egész: 1 milliárd - valós: 1000-5000 Exponenciális növekedése a keresési térnek Célok - minőség javítása - hatékonyság javítása Bilevel optimization Bilevel optimalizáció minx∈X,y F (x, y) úgy, hogy G(x, y) ≥ 0, y ∈ S(x), ahol S(x) az optimális megoldása a következőknek: miny∈Y f (x, y), úgy hogy g(x, y) ≥ 0 Megszorítások kezelése büntető függvények – megszoríásokat beépíteni a célfüggvénybe – a célfüggvényhez hozzáadunk/kivonun a megszorítás megszegésnek megfelelően – típusok ∗ death penalty - rossz megoldást egyből kidobjuk ∗ statikus büntetés - a büntetés mértéke nem változik a futás alatt ∗ dinamikus büntetés - idővel változik a büntetés értéke ∗ adaptív büntetés - felhasznál egy visszajelzést speciális reprezentációk és operátorok javító algoritmusok megszorítások és célfüggvények elkülönítése hibrid módszerek self-adaptive fitness formulation – minden egyed esetén meghatározzuk a megszorítások megszegésének az összegét – a legjobb és legrosszabb egyedek meghatározása – egy büntetés alkalmazása: azon egyedeknek amelyek megsértik a megszorításokat rontjuk a fitnesz értékét másik módszer – két jó egyed közül a jobb, amelyiknek jobb a fitneszértéke – ha egyik jó, a másik sérti a megszorítást, akkor a jó győz – ha mindkettő sérti a megszorítást, az győz aki kevésbé érti a megszorítást 17