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, tabu-keresés, stb.) is léteznek, sok esetben ez is elég jó teljesítményt képes felmutatni. 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.

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.
• Völgyek, és élek: Ha a függvényünk rendelkezik egy keskeny éllel, aminek 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.

Pszeudo-kód

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;
}

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 optimálisabbat
5. A megállási kritérium teljesüléséig (pl. kellő hossz alá érünk, vagy n lépésben elismé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.

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 alap vá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.

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.

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