14. tétel - Véletlen módszerek

Mutassa be a véletlen optimalizálás módszerét! Miben különbözik ez a lokális optimalizálástól? Ismertesse a szimulált lehűtés algoritmusát! Milyen paraméterei vannak ennek? Mik az előnyei a hegymászó módszerekhez képest?

Véletlen optimalizálás

  • A hegymászó módszer egyes hátrányaira próbál megoldást nyújtani
    • Többdimenziós keresésnél a hegymászó általában egy időben csak egy paraméter értékét változtatja
    • A hegymászónál rögzített a lépési távolság (\(ϵ\))
    • A hegymászó könnyen beragad a lokális optimumokba
  • Az alapelve megegyezik a hegymászónál tanulttal:
    • egy elemet vizsgál
    • egy véletlen pontból indul
    • minden lépésnél próbál jobb fitneszű pozícióba kerülni

Megvalósítás

Véletlen optimalizálás algoritmus

  1. véletlen pontból indítjuk p változót
  2. megállapítjuk a továbblépés irányát
    • több dimenziós tér esetén minden dimenzióban lépünk
    • nem fix távolságot lépünk, hanem ezt egy \((\mu, σ)\) paraméterű normál eloszlással határozzuk meg
  3. a p pozícióhoz hozzáadjuk a kiszámított irányvektort, az így kapott pontot hasonlítjuk össze az aktuális ponttal
  4. ha jobb, akkor átlépünk, különben nem
    • a peremfeltételeket is vizsgáljuk, ha azoknak nem felel meg, akkor sem lépünk át

Megjegyzések

  • A µ értékek a haladási irányt befolyásolják (pozitív vagy negatív)
    • jellemzően \(\mu=0\) egy kiegyensúlyozott érték
  • A σ értékek a véletlen számok méretét befolyásolják
    • általában kicsi, hogy a szomszédságot tudjuk vizsgálni
  • A normál eloszlás nem korlátos, így mindig lesz esély nagyot lépni negatív/pozitív irányba
    • ezáltal ki tud lépni a lokális optimumokból

Véletlen optimalizálás vs. lokális optimalizálás

Különbségek a hegymászóval szemben:

  • Nem csak a tengelyek iránti elmozdulást figyeli
  • A lépés mérete nem fix, hanem egy eloszlás alapján határozzuk meg
  • Rendelkezik a hegymászó előnyeivel
  • Nagyobb eséllyel lép ki a lokális optimumokból
  • Elvben mindig megtalálja a globális optimumot (végtelen idő alatt)

További tulajdonságok

  • Nem determinisztikus módszer
  • Csak \(ℝ^N\) keresési térben használható

Szimulált lehűtés

  • A hegymászó továbbfejlesztésének tekinthető
  • A hegymászó könnyen beleragad a lokális optimumokba, és csak konvex problémáknál ad garantáltan helyes megoldást
  • Alapelve a kohászatból származik: az anyagok minősége jelentősen javítható egy vagy több melegítést és lehűtést végrehajtva
    • lassú lehűtés => jobb eredmény (globális optimum)
    • gyors lehűtés => kevésbé jó eredmény (lokális optimum)
  • Nem kényszerítjük a rendszert túl gyors konvergenciára, mert úgy lokális optimumban ragadhat.
  • Lassabb konvergenciát próbálunk elérni
    • eleinte engedjük a negatív irányú lépéseket is
      • a későbbiekben csökkentjük ennek a szerepét.

Szimulált lehűtés algoritmus

  • elindul egy véletlen pontból
  • innen próbál jobb és jobb helyre átlépni
  • közben figyeli a megállási feltételt
  • a lényeges különbség a hegymászóhoz képest a fitnesz ellenőrzése
    • ha jobb a fitnesz: átlép
    • ha rosszabb: egy bizonyos valószínűséggel ekkor is átlép
      • kiszámolja a hőmérsékletet (T)
      • a valószínűség a annál nagyobb, minél nagyobb a T
  • T folyamatosan csökken a szimuláció során
  • p értéke nem mindig a legjobb talált elemet tárolja, ezért azt külön kell tárolni egy popt változóban.

Paraméterei

  1. T:

    • minél nagyobb, annál megengedőbbek vagyunk a kedvezőtlen változások felé
    • 0 nem lehet az osztás miatt, de ahhoz közeli értékeknél már szinte hegymászóként viselkedik az algoritmus

  2. kB:

  • Boltzmann állandóra utal, tetszőlegesen beállítható konstans
  • minél nagyobb, annál megengedőbb a rendszer
  1. ∆E: minél nagyobb, annál kisebb az esély az elfogadásra

Hőmérséklet meghatározása

flowchart TB
H["Hőmérséklet-meghatározási módok"]
IK[Időkorlátos]
IL[Idővel lassulva csökkenő]
F[Fitneszfüggő]
H --> IK & IL & F

  1. Időkorlátos esetben: \( Temperature(t) = T_{max} \cdot (1-\frac{t}{t_{max}})^{\alpha}\)

    • \(\alpha\) értékével befolyásolható a hőmérsékletet leíró görbe

  2. Idővel lassulva csökkenő: \( Temperature(t+1) = Temperature(t) \cdot (1- \epsilon)\)

  3. Fitneszfüggő: \(Temperature = max(\beta \cdot (f(p_{opt})-f(p)), \gamma)\)

    • a globális optimumhoz közeledve (egyre kisebb fitnesz) egyre szigorúbb a konvergencia
    • \(\beta\) értéke kísérletekkel beállított konstans
    • \(\gamma\) szerepe csak a nullás hőmérséklet értékének elkerülése (\(\gamma > 0\))

A hegymászó módszerhez képest

  • Rendelkezik a hegymászó előnyeivel (egyszerű, hatékony, stb.)

Előnyei

  • Ki tud ugrani a lokális optimumokból
  • Megfelelően választott hűtési karakterisztika esetén biztosan megtalálja a globális optimumot

Hátrányai

  • lépésszáma nagyobb lehet
  • futásideje kedvezőtlenebb
  • több paramétert igényel