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ó szerkesztés
Az algoritmus megkísérli megkeresni a szélsőértékeit egy függvénynek, ahol diszkrét vagy folytonos értékek egy vektorát jelöli. Minden iterációban az algoritmus megváltoztatja egy elemét, és megnézi, hogy az így kapott vektor javít-e é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. -et ekkor lokális optimumnak hívjuk.
A diszkrét vektorterekben minden lehetséges é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 értékét, a helyi maximum (vagy a helyi minimum) eléréséig.
Problémák szerkesztés
Három komoly probléma van a hegymászó algoritmussal.
Lokális maximumok/minimumok szerkesztés
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 szerkesztés
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 szerkesztés
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 szerkesztés
Az algoritmus például képes megoldani az utazó ügynök problémát a következő lépésekben:
- Kiindulunk egy kezdeti megoldásból (akár véletlenszerűen megválasztva a városok sorrendjét)
- Kiszámoljuk a teljes út hosszát
- Felcseréljük két város sorrendjét, és kiszámoljuk az így kapott hosszt
- 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
- 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 szerkesztés
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 szerkesztés
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 szerkeszté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 szerkesztés
Források szerkesztés
- 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
