Hegymászó algoritmus

A számítástudományban a hegymászó algoritmus egy optimalizációs eljárás, amely a lokális keresőalgoritmusok osztályába tartozik. Az eljárás egy kezdeti - véletlenszerű - megoldásból indul ki, majd iteratívan megkísérel egy mind jobb megoldást találni minden lépésben, mindig egy elemet megváltoztatva az eredményhalmazon, ameddig nem talál jobbat. Az algoritmus relatíve egyszerűsége okán az egyik leggyakrabban elsőnek választott optimizáló eljárás. Széles körben használja a mesterséges intelligencia tudománya, mivel bár fejlettebb algoritmusok (szimulált hűtés, tabukeresés stb.) is léteznek, sok esetben ez is elég jó teljesítményt képes felmutatni.

A hegymászó algoritmus megtalálja az optimális megoldást a konvex problémákhoz – más problémák esetén csak a helyi szélsőértéket fogja megtalálni (azokat a megoldásokat, amelyeken a szomszédos konfigurációk sem képesek javítani), amely nem feltétlenül a legjobb megoldás (a globális szélsőérték) az összes lehetséges megoldás közül. A hegymászó algoritmussal konvex problémákat megoldó algoritmusokra példa a lineáris programozás és a bináris keresés szimplex algoritmusa. Hogy elkerülje a helyi szélsőértéken ragadást, újra is indulhat (azaz ismételt helyi keresés), vagy bonyolultabb sémákat alkalmazhat iterációkon (például iterált helyi keresés), vagy memórián (például reaktív keresésoptimalizálás és tabukeresés), vagy memóriamentes sztochasztikus módosításokon (mint például a szimulált hűtés).

A hegymászó algoritmus gyakran jobb eredményt nyújthat, mint más algoritmusok, ha a keresés elvégzésére álló idő korlátozott, például valósidejű rendszereknél, mindaddig, amíg kis számú lépés elegendő a jó megoldáshoz (az optimális megoldás vagy egy megközelítése). A buborékrendezés hegymászó algoritmusnak tekinthető (minden szomszédos elemcsere csökkenti a rendezetlen elempárok számát), ám ez a megközelítés messze nem hatékony még egyszerű N esetében sem, mivel a cserék száma négyzetesen növekszik.

További előnye, hogy a futtatás bármely pillanatában is szakítjuk meg a működését, a (rész)megoldás mindig elérhető.

Formális definíció

Az algoritmus megkísérli megkeresni a szélsőértékeit egy $f(x)$ függvénynek, ahol $x$ diszkrét vagy folytonos értékek egy vektorát jelöli. Minden iterációban az algoritmus megváltoztatja $x$ egy elemét, és megnézi, hogy az így kapott vektor javít-e $f(x)$ értékén. Minden egyes ilyen lépést elfogad, és onnantól kezdve abból a megoldásból indulunk ki. Az eljárást addig folytatjuk, amíg nem találunk jobb megoldást. $x$-et ekkor lokális optimumnak hívjuk.

A diszkrét vektorterekben minden lehetséges $\mathbf {x}$ érték a gráf csúcsaként jeleníthető meg. A hegymászás csúcsról csúcsra követi a gráfot, mindig helyileg növelve (vagy csökkentve) az $f(\mathbf {x} )$ értékét, a helyi maximum (vagy a helyi minimum) $x_{m}$ eléréséig.

A felület egy maximum esetén. A hegymászók alkalmasak az ilyen felületek feletti optimalizálásra, és a globális maximumhoz tartanak

Problémák

Három komoly probléma van a hegymászó algoritmussal.

Lokális maximumok/minimumok

Ha a heurisztika vagy keresési tér nem konvex, akkor előfordulhat, hogy „szerencsétlenebb” helyről indítva az eljárás csak egy lokális maximumra „mászik fel”, nem találja meg a globális szélsőértéket. Több keresőalgoritmus ezt a hibát kiküszöböli, többek között a sztochasztikus változata a hegymászónak is.

A grafikonban szereplő sok helyi maximum ellenére a globális maximum még mindig megtalálható a szimulált hűtés segítségével. Sajnos a szimulált hűtés alkalmazhatósága probléma-specifikus, mivel a helyzet javítását szolgáló szerencsés ugrások megtalálására épül. Ilyen szélsőséges példákban a hegymászó algoritmus valószínűleg helyi maximumot hoz

Völgyek, és élek

Völgy

Ha a függvényünk rendelkezik egy keskeny éllel, amelynek tengelye szöget zár be a keresési terünk koordinátatengelyeivel, akkor az eljárásunk cikk-cakk alakban fog ugrálni a völgy lejtőjén, és rendkívül lassan fog tudni felérni a tetejére. Ilyen esetben a gradiens módszer sokkal hatékonyabban működik.

Fennsíkok

Ha a keresési terünkön fennsík található, akkor elképzelhető, hogy az algoritmusunk olyan irányokba fog lépni, ahol soha nem ér el javulást, mivel nem tudja megkülönböztetni a jelen pont jóságát a következő pont jóságától.

Alkalmazások, példák

Az algoritmus például képes megoldani az utazó ügynök problémát a következő lépésekben:

1. Kiindulunk egy kezdeti megoldásból (akár véletlenszerűen megválasztva a városok sorrendjét)
2. Kiszámoljuk a teljes út hosszát
3. Felcseréljük két város sorrendjét, és kiszámoljuk az így kapott hosszt
4. Ha jobb eredményre jutunk a 3. lépésben, akkor eltároljuk az így kapott megoldást mint az optimálishoz közelebb levőt
5. A megállási kritérium teljesüléséig (pl. kellő hossz alá érünk, vagy n lépésben megismételtük a keresést) folytatjuk a 3. lépéstől az eljárást.

Bár az algoritmus előállít egyfajta megoldást, semmi nem szavatolja, hogy az optimális eredményre (a legrövidebb útra) jut.

Pszeudokódok

algoritmus Diszkrét Teres Hegymászás 
     aktualisPont = startPont;
     do{
     L = Szomszedok(aktualisPont);
     kovErtek = -VEGTELEN;
     kovPont = NIL;
     foreach (x in L){
        if (ERTEK(x) > kovErtek){
           kovPont = x;
           kovErtek = ERTEK(x);
        }
     }
     if (kovErtek <= ERTEK(aktualisPont)) return aktualisPont;
     aktualisPont = kovPont;

algoritmus Folyamatos Teres Hegymászás 
     aktualisPont = startPont    // egy nulla nagyságrendű vektor gyakori
     lepesKoz = startLepesKoz    // egy vektor csupa 1-esekkel gyakori
     gyorsulás:= egyGyorsulas // egy olyan érték, mint az 1.2, gyakori
     jelölt[0] = −acceleration
     jelölt[1] = −1 / acceleration
     jelölt[2] = 0
     jelölt[3] = 1 / acceleration
     jelölt[4] = acceleration
     do{
         elozo = ERTEK(aktualisPont)
         foreach (i in aktualisPont){
             legjobb = −1
             legjobbPont = −VEGTELEN
             for j 0-tól 4-ig     // kipróbálja mind az öt jelölt helyet
                 aktualisPont[i] = aktualisPont[i] + lepesKoz[i] × jelolt[j]
                 atmeneti = ERTEK(aktualisPont)
                 aktualisPont[i] = aktualisPont[i] − lepesKoz[i] × jelolt[j]
                 if atmeneti > legjobbPont then
                    legjobbPont = atmeneti
                    legjobb = j
             if jelolt[legjobb] is 0
                 lepeskoz[i]  = lepeskoz[i] / gyorsulás
             else
                 aktualisPont[i]  = aktualisPont[i] + lepeskoz[i] × jelolt[legjobb]
                 lepeskoz[i]  = lepeskoz[i] × jelolt[best] // gyorsulas
         if (ERTEK(aktualisPont) − elozo) < epsilon
             return aktualisPont  
}

Változatok

Az algoritmusnak különböző javításai láttak napvilágot, amelyek segítségével tovább gyorsítható. Az egyik ilyen a legmeredekebben emelkedő hegymászó, ami abban különbözik az alapváltozattól, hogy megvizsgálja, melyik irányba való lépéstől jutunk a lehető leggyorsabban közelebb a megoldáshoz, és azt a lépést választja minden esetben. Ez valójában csak gyorsítja az eljárást, a problémák (mint például a lokális maximumok, fennsíkok) ugyanúgy meggátolják ezt a fajtát is. A legszigorúbb emelkedő dombmászás hasonló az legjobbat először kereséshez, amely csak az egyik helyett az aktuális pálya minden lehetséges kiterjesztését próbálja ki.

Jelentősebb változtatással működik a sztochasztikus hegymászó. Ez véletlenszerűen választja, hogy melyik irányba lépjen, majd a javulás mértékének függvényében megadható valószínűséggel teszi is meg azt a lépést, vagy keres inkább egy másik lehetőséget. Ez a variáció képes „lemászni” egy lokális szélsőértékről, hogy egy globálisat keressen tovább.

Metaheurisztikus megoldás is létezik az úgynevezett sörétespuska-kereső személyében. Ennél az esetben minden egyes alkalommal egy véletlenszerűen kiválasztott x0 helyről indítja a keresést, majd a legjobb xm megoldást eltárolja. Ha egy következő lefutásnál (újraindítás egy új x1 helyről) jobb eredményt talál ennél, akkor azt ezzel kicseréli. Ez a megoldás meglepően hatékony lehet egyes problémák esetén.

Fordítás

Ez a szócikk részben vagy egészben a Hill climbing című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Összefoglaló a különböző hegymászó-módszerekről

Források

• Jason Brownlee. Clever Algorithms, Nature-Inspired Programming Recipes, 1st. isbn 978-1-4467-8506-5 (2011) 
• Toby Segaran. Programming Collective Intelligence. O'Reilly Media Inc.. isbn 978-0-596-52932-1 (2007) 
• Nem módosítható keresőrendszerek

Kapcsolódó szócikkek

• Keresőalgoritmus