- Hill climbing algoritme er en lokal søkealgoritme som kontinuerlig beveger seg i retning av økende høyde/verdi for å finne toppen av fjellet eller beste løsning på problemet. Den avsluttes når den når en toppverdi der ingen nabo har en høyere verdi.
- Bakkebestigningsalgoritme er en teknikk som brukes for å optimalisere de matematiske problemene. Et av de mye omtalte eksemplene på bakkeklatringsalgoritmer er Traveling-salesman Problem der vi må minimere avstanden som selgeren har tilbakelagt.
- Det kalles også grådig lokalsøk da det kun ser til sin gode umiddelbare nabostat og ikke utover det.
- En node med bakkeklatringsalgoritme har to komponenter som er tilstand og verdi.
- Bakkeklatring brukes mest når en god heuristikk er tilgjengelig.
- I denne algoritmen trenger vi ikke å vedlikeholde og håndtere søketreet eller grafen, da den bare beholder en enkelt gjeldende tilstand.
Funksjoner ved bakkeklatring:
Følgende er noen hovedtrekk ved Hill Climbing Algorithm:
State-space-diagram for bakkeklatring:
Staten-rom-landskapet er en grafisk representasjon av bakkeklatringsalgoritmen som viser en graf mellom ulike tilstander av algoritme og målfunksjon/kostnad.
På Y-aksen har vi tatt funksjonen som kan være en objektiv funksjon eller kostnadsfunksjon, og tilstandsrom på x-aksen. Hvis funksjonen på Y-aksen er kostnad, er målet med søket å finne det globale minimum og lokale minimum. Hvis funksjonen til Y-aksen er Objektiv funksjon, så er målet med søket å finne det globale maksimum og lokale maksimum.
Ulike regioner i det statlige romlandskapet:
Lokalt maksimum: Lokalt maksimum er en stat som er bedre enn nabostatene, men det er også en annen stat som er høyere enn den.
Globalt maksimum: Globalt maksimum er den best mulige tilstanden til statens romlandskap. Den har den høyeste verdien av objektiv funksjon.
Nåværende situasjon: Det er en tilstand i et landskapsdiagram der en agent for øyeblikket er til stede.
Flatt lokalt maksimum: Det er et flatt rom i landskapet der alle nabostatene til nåværende stater har samme verdi.
Skulder: Det er en platåregion som har en oppoverbakke.
Typer bakkeklatringalgoritmer:
- Enkel bakkeklatring:
- Bratteste stigning i bakkeklatring:
- Stokastisk bakkeklatring:
1. Enkel bakkeklatring:
Enkel bakkeklatring er den enkleste måten å implementere en bakkeklatringalgoritme. Den evaluerer bare nabonodens tilstand om gangen og velger den første som optimerer gjeldende kostnad og setter den som gjeldende tilstand . Den sjekker bare at den er en etterfølgertilstand, og hvis den finner bedre enn den nåværende tilstanden, så flytt ellers i samme tilstand. Denne algoritmen har følgende funksjoner:
- Mindre tidkrevende
- Mindre optimal løsning og løsningen er ikke garantert
Algoritme for enkel bakkeklatring:
- Hvis det er måltilstand, så returner suksess og avslutt.
- Ellers hvis den er bedre enn den nåværende tilstanden, tilordne ny tilstand som en nåværende tilstand.
- Hvis ikke bedre enn den nåværende tilstanden, gå tilbake til trinn 2.
2. Bratteste stigning i bakkeklatring:
Den bratteste oppstigningsalgoritmen er en variant av enkel bakkeklatringsalgoritme. Denne algoritmen undersøker alle nabonodene i gjeldende tilstand og velger en nabonode som er nærmest måltilstanden. Denne algoritmen bruker mer tid når den søker etter flere naboer
Algoritme for bakkeklatring med bratteste stigning:
- La SUCC være en stat slik at enhver etterfølger av den nåværende staten vil være bedre enn den.
- For hver operatør som gjelder for gjeldende tilstand:
- Bruk den nye operatøren og generer en ny tilstand.
- Evaluer den nye staten.
- Hvis det er måltilstand, returner det og avslutt, ellers sammenligne det med SUCC.
- Hvis den er bedre enn SUCC, setter du ny tilstand som SUCC.
- Hvis SUCC er bedre enn gjeldende tilstand, sett nåværende tilstand til SUCC.
3. Stokastisk bakkeklatring:
Stokastisk bakkeklatring undersøker ikke for alle sine naboer før de flytter. Snarere velger denne søkealgoritmen en nabonode tilfeldig og bestemmer om den skal velges som gjeldende tilstand eller undersøke en annen tilstand.
Problemer i Hill Climbing Algorithm:
1. Lokalt maksimum: Et lokalt maksimum er en topptilstand i landskapet som er bedre enn hver av nabostatene, men det er også en annen stat som er høyere enn det lokale maksimum.
Løsning: Tilbakesporingsteknikk kan være en løsning av det lokale maksimum i statlig romlandskap. Lag en liste over den lovende banen slik at algoritmen kan spore søkeområdet tilbake og utforske andre stier også.
2. Platå: Et platå er det flate området av søkerommet der alle nabostatene til den nåværende tilstanden inneholder samme verdi, på grunn av denne algoritmen finner ikke den beste retningen å bevege seg. Et bakkesøk kan gå tapt i platåområdet.
Løsning: Løsningen for platået er å ta store skritt eller veldig små skritt mens du søker, for å løse problemet. Velg tilfeldig en tilstand som er langt unna den nåværende tilstanden, slik at det er mulig at algoritmen kan finne en region som ikke er platå.
3. Kanter: En ås er en spesiell form for det lokale maksimum. Den har et område som er høyere enn de omkringliggende områdene, men har i seg selv en skråning og kan ikke nås i et enkelt trekk.
Løsning: Med bruk av toveissøk, eller ved å bevege oss i forskjellige retninger, kan vi forbedre dette problemet.
Simulert gløding:
En bakkeklatringsalgoritme som aldri beveger seg mot en lavere verdi, er garantert ufullstendig fordi den kan sette seg fast på et lokalt maksimum. Og hvis algoritmen bruker en tilfeldig tur, ved å flytte en etterfølger, kan den fullføre, men ikke effektiv. Simulert gløding er en algoritme som gir både effektivitet og fullstendighet.
På mekanisk sikt Gløding er en prosess med å herde et metall eller glass til en høy temperatur og deretter avkjøles gradvis, slik at dette lar metallet nå en lavenergi-krystallinsk tilstand. Den samme prosessen brukes i simulert annealing der algoritmen velger et tilfeldig trekk, i stedet for å velge det beste trekket. Hvis det tilfeldige trekket forbedrer tilstanden, følger det samme vei. Ellers følger algoritmen banen som har en sannsynlighet på mindre enn 1 eller den beveger seg nedover og velger en annen vei.