hill climbing
Főnév
hill climbing (tsz. hill climbings)
A hill climbing (magyarul: hegymászó algoritmus) egy egyszerű, lokális keresési algoritmus, amely optimalizációs problémák megoldására szolgál. Célja, hogy egy kiinduló pontból indulva folyamatosan javító lépéseket tegyen egy megoldás irányába, egészen addig, amíg helyi maximumot (vagy minimumot) nem ér el.
Hogyan működik a hill climbing?
- Kiindul egy kezdőmegoldásból.
- Megvizsgálja a megoldás szomszédait (azaz a lehetséges apró változtatásokat).
- Kiválasztja azt a szomszédot, amely javítja a célfüggvény értékét (pl. növeli a hasznosságot).
- Átáll erre az új megoldásra.
- Ismétli a folyamatot, amíg nem talál jobb szomszédot (helyi maximumhoz érkezik).
Tulajdonságok
- Lokális keresés: Csak a közvetlen környezetet vizsgálja.
- Gyors: Egyszerű és gyors megközelítés.
- Helyi optimum problémája: Elakadhat olyan megoldásnál, ami nem a globális legjobb.
- Egyszerű implementáció.
Példa alkalmazás
- Utazó ügynök probléma közelítő megoldása.
- Paraméterhangolás gépi tanulásban.
- Játékelméleti stratégiák keresése.
Variánsok
- Stochastic hill climbing: Véletlenszerűen választ szomszédokat, hogy elkerülje a lokális csapdákat.
- Random-restart hill climbing: Többször újrakezdi különböző kezdőpontokból.
- Simulated annealing: Véletlenszerűen elfogad rosszabb megoldásokat is, hogy kilépjen helyi optimumokból.
Összefoglalás
| Fogalom | Leírás |
|---|---|
| Hill climbing | Lokális keresési algoritmus, amely helyi optimum felé halad |
| Előnyök | Egyszerű, gyors |
| Hátrányok | Elakadás helyi optimumoknál |
- hill climbing - Szótár.net (en-hu)
- hill climbing - Sztaki (en-hu)
- hill climbing - Merriam–Webster
- hill climbing - Cambridge
- hill climbing - WordNet
- hill climbing - Яндекс (en-ru)
- hill climbing - Google (en-hu)
- hill climbing - Wikidata
- hill climbing - Wikipédia (angol)