Inhoudsopgave:
Definitie - Wat betekent Hill Climbing?
Bergbeklimmen is een wiskundige optimalisatieheuristische methode die wordt gebruikt voor het oplossen van computationele uitdagende problemen met meerdere oplossingen. Het is een iteratieve methode die tot de lokale zoekfamilie behoort, die begint met een willekeurige oplossing en vervolgens die oplossing iteratief één element tegelijk verbetert totdat het tot een min of meer geoptimaliseerde oplossing komt.
Techopedia legt Hill Climbing uit
Bergbeklimmen is een optimalisatietechniek die wordt gebruikt om een "lokale optimale" oplossing voor een computerprobleem te vinden. Het begint met een oplossing die erg slecht is in vergelijking met de optimale oplossing en verbetert vervolgens iteratief vanaf daar. Het doet dit door "buur" -oplossingen te genereren die relatief een stap beter zijn dan de huidige oplossing, kiest de beste en herhaalt vervolgens het proces totdat het tot de meest optimale oplossing komt omdat het geen verbeteringen meer kan vinden.
varianten:
- Eenvoudig - De eerste knoop of oplossing die het dichtst in de buurt komt, wordt gekozen.
- Steilste beklimming - Alle beschikbare opvolgeroplossingen worden overwogen en vervolgens wordt de dichtstbijzijnde gekozen.
- Stochastisch - Een naburige oplossing wordt willekeurig gekozen en vervolgens wordt besloten of naar die oplossing wordt overgegaan op basis van de hoeveelheid verbetering ten opzichte van het huidige knooppunt.
Bergbeklimmen gebeurt iteratief - het doorloopt een hele procedure en de uiteindelijke oplossing wordt opgeslagen. Als een andere iteratie een betere uiteindelijke oplossing vindt, wordt de opgeslagen oplossing of status vervangen. Dit wordt ook shotgun hill climbing genoemd, omdat het eenvoudig verschillende paden uitprobeert totdat het de beste raakt, net zoals hoe een shotgun onnauwkeurig is, maar nog steeds zijn doel kan raken vanwege de brede verspreiding van projectielen. Dit werkt in veel gevallen erg goed, omdat het beter blijkt om CPU-middelen te besteden aan het verkennen van verschillende paden dan zorgvuldig te optimaliseren vanuit een initiële toestand.
