- Hill Climbing-algoritme is een lokaal zoekalgoritme dat voortdurend in de richting van toenemende hoogte/waarde beweegt om de top van de berg of de beste oplossing voor het probleem te vinden. Het eindigt wanneer het een piekwaarde bereikt waarbij geen enkele buur een hogere waarde heeft.
- Hill Climbing-algoritme is een techniek die wordt gebruikt voor het optimaliseren van wiskundige problemen. Een van de veelbesproken voorbeelden van het Hill Climb-algoritme is het Travelling-salesman-probleem, waarbij we de door de verkoper afgelegde afstand moeten minimaliseren.
- Het wordt ook wel hebzuchtige lokale zoektocht genoemd, omdat het alleen naar de goede directe buurstaat kijkt en niet verder dan dat.
- Een knooppunt van een heuvelklimalgoritme heeft twee componenten: status en waarde.
- Hill Climbing wordt meestal gebruikt als er een goede heuristiek beschikbaar is.
- In dit algoritme hoeven we de zoekboom of grafiek niet te onderhouden en af te handelen, omdat deze slechts één huidige status behoudt.
Kenmerken van heuvelklimmen:
Hieronder volgen enkele belangrijke kenmerken van het Hill Climbing-algoritme:
Toestand-ruimtediagram voor heuvelbeklimmen:
Het toestandsruimtelandschap is een grafische weergave van het heuvelklimalgoritme dat een grafiek toont tussen verschillende toestanden van het algoritme en de doelstellingsfunctie/kosten.
geblokkeerde nummers
Op de Y-as hebben we de functie genomen die een objectieve functie of kostenfunctie kan zijn, en toestandsruimte op de x-as. Als de functie op de Y-as kosten is, is het doel van de zoekopdracht het vinden van het globale minimum en het lokale minimum. Als de functie van de Y-as de Doelfunctie is, is het doel van de zoekopdracht het vinden van het globale maximum en het lokale maximum.
Verschillende regio's in het staatsruimtelandschap:
Lokaal maximum: Lokaal maximum is een staat die beter is dan zijn buurstaten, maar er is ook een andere staat die hoger is dan deze.
Globaal maximum: Mondiaal maximum is het best mogelijke staatsruimtelandschap. Het heeft de hoogste waarde van objectieve functie.
Huidige toestand: Het is een toestand in een landschapsdiagram waarin momenteel een agent aanwezig is.
Java-datum naar tekenreeks
Plat lokaal maximum: Het is een vlakke ruimte in het landschap waar alle buurstaten van de huidige staten dezelfde waarde hebben.
Schouder: Het is een plateaugebied met een opwaartse rand.
Soorten heuvelklimalgoritmen:
- Eenvoudig heuvelklimmen:
- Steilste beklimming van heuvels:
- Stochastisch heuvelklimmen:
1. Eenvoudig heuvelklimmen:
Eenvoudig heuvelklimmen is de eenvoudigste manier om een heuvelklimalgoritme te implementeren. Het evalueert alleen de status van het aangrenzende knooppunt tegelijk en selecteert de eerste die de huidige kosten optimaliseert en deze instelt als een huidige status . Het controleert alleen of het één opvolgende staat is, en als het een betere vindt dan de huidige staat, verplaats dan een andere staat naar dezelfde staat. Dit algoritme heeft de volgende kenmerken:
- Minder tijdrovend
- Minder optimale oplossing en de oplossing is niet gegarandeerd
Algoritme voor eenvoudig heuvelklimmen:
- Als het een doelstatus is, geef dan succes terug en stop.
- Anders, als deze beter is dan de huidige staat, wijs dan de nieuwe staat toe als huidige staat.
- Anders, zo niet beter dan de huidige status, ga dan terug naar stap 2.
2. Heuvelbeklimmen met de steilste klim:
Het steilste klimalgoritme is een variatie op het eenvoudige heuvelklimalgoritme. Dit algoritme onderzoekt alle aangrenzende knooppunten van de huidige status en selecteert één buurknooppunt dat het dichtst bij de doelstatus ligt. Dit algoritme kost meer tijd bij het zoeken naar meerdere buren
Algoritme voor het beklimmen van steile hellingen:
- Laat SUCC een staat zijn zodat elke opvolger van de huidige staat beter zal zijn dan deze.
- Voor elke operator die van toepassing is op de huidige status:
- Pas de nieuwe operator toe en genereer een nieuwe status.
- Evalueer de nieuwe staat.
- Als het een doelstatus is, geef het dan terug en stop, anders vergelijk het met de SUCC.
- Als het beter is dan SUCC, stel dan de nieuwe status in als SUCC.
- Als de SUCC beter is dan de huidige status, stelt u de huidige status in op SUCC.
3. Stochastisch bergbeklimmen:
Stochastisch heuvelklimmen onderzoekt niet al zijn buren voordat ze verder gaan. In plaats daarvan selecteert dit zoekalgoritme willekeurig één buurknooppunt en beslist of het dit als huidige status kiest of een andere status onderzoekt.
gelijkwaardigheid wetten
Problemen met het Hill Climbing-algoritme:
1. Lokaal maximum: Een lokaal maximum is een piektoestand in het landschap die beter is dan elk van de aangrenzende staten, maar er is ook een andere toestand aanwezig die hoger is dan het lokale maximum.
Oplossing: Backtracking-techniek kan een oplossing zijn voor het lokale maximum in het staatsruimtelandschap. Maak een lijst met het veelbelovende pad, zodat het algoritme de zoekruimte kan volgen en ook andere paden kan verkennen.
2. Plateau: Een plateau is het vlakke gebied van de zoekruimte waarin alle aangrenzende staten van de huidige staat dezelfde waarde bevatten, omdat dit algoritme geen beste bewegingsrichting vindt. Een zoektocht tijdens het bergbeklimmen zou in het plateaugebied verloren kunnen gaan.
Oplossing: De oplossing voor het plateau is om tijdens het zoeken grote stappen of hele kleine stappen te zetten om het probleem op te lossen. Selecteer willekeurig een staat die ver verwijderd is van de huidige staat, zodat het mogelijk is dat het algoritme een niet-plateauregio kan vinden.
tekenreeksen java toevoegen
3. Ruggen: Een rug is een bijzondere vorm van het lokale maximum. Het heeft een gebied dat hoger is dan de omliggende gebieden, maar zelf een helling heeft en niet in één beweging kan worden bereikt.
Oplossing: Met het gebruik van bidirectioneel zoeken, of door in verschillende richtingen te bewegen, kunnen we dit probleem verbeteren.
Gesimuleerd gloeien:
Een hill-climbing-algoritme dat nooit een beweging naar een lagere waarde maakt, is gegarandeerd incompleet omdat het kan blijven steken op een lokaal maximum. En als het algoritme een willekeurige wandeling toepast, door een opvolger te verplaatsen, kan het compleet zijn, maar niet efficiënt. Gesimuleerd gloeien is een algoritme dat zowel efficiëntie als volledigheid oplevert.
Op mechanisch gebied Gloeien is een proces waarbij een metaal of glas tot een hoge temperatuur wordt gehard en vervolgens geleidelijk wordt afgekoeld, zodat het metaal een energiezuinige kristallijne toestand kan bereiken. Hetzelfde proces wordt gebruikt bij gesimuleerd uitgloeien, waarbij het algoritme een willekeurige zet kiest in plaats van de beste zet. Als de willekeurige zet de toestand verbetert, volgt deze hetzelfde pad. Anders volgt het algoritme het pad met een waarschijnlijkheid kleiner dan 1, of gaat het bergafwaarts en kiest een ander pad.