13. tétel - Lokális optimalizálás

Mit értünk lokális optimalizálási módszerek alatt? Mutassa be a hegymászó módszert és annak variánsait (sztochasztikus, steepest ascent)! Ismertesse a Tabu keresés algoritmusát!

Hegymászó módszer

  1. kiválasztja a keresési tér egy véletlen pontját
  2. egy ciklust futtat, ami ezt a pozíciót tudja megváltoztatni, hogy jobb helyre jussunk
    • ha sikerül: ez lesz az új pozíció, a ciklus folytatódik
    • ha nem sikerül: tovább próbálkozik vagy leáll
  • egyik legrégebbi, legegyszerűbb módszer
  • már meglévő kereséseket is lehet vele finomhangolni
  • az elnevezés megtévesztő, a legkisebb fitnesz felé akarunk haladni, nem a legnagyobb felé

A megvalósítások abban különböznek, hogy hogyan vizsgálják az aktuális pont környezetét.

Sztochasztikus hegymászó

Sztohasztikus hegymászó algoritmus

flowchart LR

RAND[Véletlen pont kiválasztása]
STOPCOND{Leállási feltétel igaz?}
SEARCH[Véletlen pont választása ϵ távolságra]
ISBETTER{Jobb az új pont?}
STEP[Lépés az új pontba]
STOP["`Leállás, vissza *gpm(p)*`"]
STOPCOND-- nem -->SEARCH-->ISBETTER--nem-->STOPCOND
ISBETTER--igen-->STEP-->STOPCOND
RAND --> STOPCOND-- igen -->STOP

  • Az algoritmus kiindul egy véletlen pozícióból

  • Egy ciklust futtat addig, amíg a leállási feltétel nem lesz igaz

    A leállási feltétel lehet pl:

    • időkorlát,
    • fitnesz korlát,
    • fitnesz javulás korlát

  • Az aktuális pozíciót p változó tárolja. A cikluson belül választ egy véletlen pozíciót (q) ennek \(ϵ\) sugarú környezetében.

    • Ha az új pont jobb, akkor átlép ide
    • Ha nem, akkor tovább próbálkozik

  • Az algoritmus visszatérési értéke a p által reprezentált megoldás

Megjegyzések

  • Indeterminisztikus módszer (minden indításkor más lehet a pont, de azonos pontból indulva is más lehet az eredmény)
  • Fitnesz vizsgálatnál "\(<\)" helyett "\(\leq\)" használatával a síkságokon is továbblép
  • \(ϵ\) értéke változtatható, pl. megakadásnál

Steepest Ascent

Steepest ascent algoritmus

A q elemet ebben nem véletlenszerűen választjuk, hanem az \(ϵ\) sugarú környezet legjobb eleme lesz kiválasztva.

Fel tudja ismerni, ha globális oprimumba ragad: a sztochasztikus változat abban az esetben, ha a q pont nem volt jobb, mint p, akkor egy újabb véletlen szomszéd felé próbálkozott. Ebben a verzióban ennek nincsen értelme már, mert q biztosan a legjobb a szomszédok közül, a keresés akár le is állítható.

Megjegyzések

  • Ez már determinisztikus (azonos helyről indulva: ugyanaz az út, ugyanaz a megoldás)
  • A gyakorlatban általában nem kivitelezhető a környezet legjobb elemét kiválasztani
    • 1 dimenzióban csak két elem van \(ϵ\) távolságra, 2 vagy több dimenzióban már végtelen
    • így a környezetet általában valamilyen felbontással vizsgáljuk meg
  • Kevesebb lépést tesz meg, de sokkal számításigényesebb a környezet vizsgálata
    • Tehát a teljes algoritmus futásidejére nem várhatjuk, hogy jobb legyen

Tabu keresés

  • A hegymászó egyik hiánya, hogy könnyen beragad a lokális optimumokba
  • Felmerül az ötlet, hogy többször kéne elindítani más kiindulópontokkal
  • A keresések függetlenek, így belefuthatnak ugyanazokba az utakba, ahol várhatóan ugyanahhoz a végeredményhez jutnak
  • Érdemes lenne eltárolni a már megtett utakkal kapcsolatos tudást
  • Minden lépést eltárolni túl memóriaigényes lenne, és nehéz lenne benne keresni

A hegymászót úgy módosítjuk, hogy tabu ponthoz érve hagyja abba a belső ciklus futtatását.

Tabu keresés

Segédfüggvények

  1. SetTabuBarrier():

    • elhelyez egy jelzést a tabu pontok listájába, ami azt jelzi, hogy az ezt követő pontok az aktuális kereséshez tartoznak
    • így a keresés nem akad össze a saját pontjaival

  2. IsTabu(p): keres a tabu tárhelyen, és igaz-at ad vissza, ha a paraméterben megadott pozíció tabu

  3. AddTabu(): felvesz egy új elemet a tabu tárhelyre

  4. PurgeTabu(): tömöríti a tabu tárhelyet

Megjegyzések

  • Nem feltétel, de itt a steepest ascentet használtuk, mert determinisztikus
    • ekkor nyilvánvaló a tabu szerepe, mert egy pontból mindig ugyanoda jut
  • A kereséskor érdemes a pont környezetét keresni a tabu tárhelyen, mert többdimenziós feladatnál kicsi az esélye, hogy az algoritmus többször lép pont ugyanabba a pontba

Tabu tárhely kezelése

  1. Tárolás
    • Végtelen lista
    • Hasító táblák: gyors, de csak teljes egyezésre keres
    • Tulajdonságok tárolása: nem a pontot, hanem valamilyen tulajdonságát tároljuk
    • Változások tárolása: nem a megoldásjelölteket, hanem az azok közötti változásokat tároljuk
  2. Keresés
    • Lineáris keresés
    • Térbeli indexelés: a keresési tér részterekre bontásával, és a részterekben keresünk
  3. Karbantartás
    • FIFO lista: korlátozzuk a tárolt elemek számát, új elem érkezésekor a legrégebbit töröljük, ha tele van
      • nem szerencsés, attól hogy régi még lehet hasznos
    • Klaszterezés: az egymáshoz közeli pontokból úgy törlünk, hogy a lefedett terület ne változzon

Értékelés

  • Többszöri újraindításra jelentősen csökkentheti a futásidőt
  • Főleg determinisztikus kereséseknél hatékony
  • Nem csak hegymászónál használható, más heurisztikák is kiegészíthetőek vele
  • Hátrányok:
    • Csak kis méretű keresési térnél működik hatékonyan
    • A keresés lépés időigényes