streamalism.org

1. Oversikt

I denne opplæringen viser vi Hill-Climbing-algoritmen og implementeringen av den. Vi vil også se på fordelene og manglene. Før vi hopper direkte inn i det, la oss diskutere generere-og-test algoritmer tilnærming kort.

2. Generer-og-test algoritme

Det er en veldig enkel teknikk som lar oss algoritmisere å finne løsninger:

1. Definer nåværende tilstand som en starttilstand
2. Bruk enhver mulig operasjon på gjeldende tilstand og generer en mulig løsning
3. Sammenlign nylig generert løsning med måltilstanden
4. Hvis målet er oppnådd eller ingen nye stater kan opprettes, avslutt. Ellers, gå tilbake til trinn 2

Det fungerer veldig bra med enkle problemer. Ettersom det er et uttømmende søk, er det ikke mulig å vurdere det mens du arbeider med store problemområder. Det er også kjent som British Museum algoritme (prøver å finne en gjenstand i British Museum ved å utforske den tilfeldig).

Det er også hovedideen bak Hill-Climbing Attack i biometriens verden. Denne tilnærmingen kan brukes til å generere syntetiske biometriske data.

3. Introduksjon til Simple Hill-Climbing Algorithm

I Hill-Climbing-teknikken, som starter ved foten av en bakke, går vi oppover til vi når toppen av bakken. Med andre ord starter vi med starttilstand, og vi fortsetter å forbedre løsningen til den er optimal.

Det er en variant av en generer-og-test-algoritme som forkaster alle stater som ikke ser lovende ut eller som ikke ser ut til å føre oss til målstaten. For å ta slike avgjørelser bruker den heuristikk (en evalueringsfunksjon) som indikerer hvor nær den nåværende tilstanden er til måltilstanden.

Med enkle ord, Hill-Climbing = generer-og-test + heuristikk

La oss se på klatrealgoritmen Simple Hill:

1. Definer gjeldende tilstand som en starttilstand
2. Sløyfe til måltilstanden er oppnådd eller ikke flere operatører kan brukes på den nåværende tilstanden:
   1. Bruk en operasjon i gjeldende tilstand og få en ny stat
   2. Sammenligne den nye staten med målet
   3. Slutte hvis måltilstanden er oppnådd
   4. Evaluer ny tilstand med heuristisk funksjon og sammenligne den med gjeldende tilstand
   5. Hvis den nyere staten er nærmere til målet sammenlignet med nåværende tilstand, oppdater gjeldende tilstand

Som vi kan se, når den måltilstanden med iterative forbedringer. I Hill-Climbing-algoritmen tilsvarer å finne mål å nå toppen av bakken.

4. Eksempel

Hill Climbing Algorithm kan kategoriseres som et informert søk. Så vi kan implementere ethvert nodebasert søk eller problemer som n-queens-problemet ved å bruke det. For å forstå konseptet enkelt, tar vi opp et veldig enkelt eksempel.

La oss se på bildet nedenfor:

Nøkkelpunktet når du løser problemer med å klatre i bakker, er å velge en passende heuristisk funksjon.

La oss definere en slik funksjon h:

h (x) = +1 for alle blokkene i støttestrukturen hvis blokken er riktig plassert ellers -1 for alle blokkene i støttestrukturen.

Her vil vi kalle en hvilken som helst blokk riktig plassert hvis den har samme støttestruktur som måltilstanden. I henhold til fremgangsmåten som ble diskutert tidligere, la oss se på alle iterasjonene og deres heuristikker for å nå målstaten:

5. Implementering

La oss nå implementere det samme eksemplet ved hjelp av Hill-Climbing-algoritmen.

Først og fremst trenger vi en Stat klasse som vil lagre listen over stabler som representerer posisjoner for blokker i hver stat. Det vil også lagre heuristikker for den aktuelle staten:

offentlig klasse Stat {privat liste stat; privat int heuristikk; // kopi konstruktør, settere og getters}

Vi trenger også en metode som beregner statens heuristiske verdi.

public int getHeuristicsValue (Liste currentState, Stack goalStateStack) {Heltall heuristicValue; heuristicValue = currentState.stream () .mapToInt (stack -> {return getHeuristicsValueForStack (stack, currentState, goalStateStack);}). sum (); return heuristicValue; } public int getHeuristicsValueForStack (Stack stack, List currentState, Stack goalStateStack) {int stackHeuristics = 0; boolsk isPositioneCorrect = true; int goalStartIndex = 0; for (String currentBlock: stack) {if (isPositioneCorrect && currentBlock.equals (goalStateStack.get (goalStartIndex))) {stackHeuristics + = goalStartIndex; } annet {stackHeuristics - = goalStartIndex; isPositioneCorrect = false; } goalStartIndex ++; } return stackHeuristics; } 

Videre må vi definere operatørmetoder som gir oss en ny tilstand. For vårt eksempel vil vi definere to av disse metodene:

1. Popp en blokk fra en bunke og skyv den på en ny bunke
2. Popp en blokk fra en bunke og skyv den inn i en av de andre stakkene

private State pushElementToNewStack (Liste currentStackList, strengblokk, int currentStateHeuristics, Stack goalStateStack) {State newState = null; Stack newStack = new Stack (); newStack.push (blokk); currentStackList.add (newStack); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); hvis (newStateHeuristics> currentStateHeuristics) {newState = new State (currentStackList, newStateHeuristics); } annet {currentStackList.remove (newStack); } returner newState; }

private State pushElementToExistingStacks (Stack currentStack, List currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) {return currentStackList.stream () .filter (stack -> stack! = currentStack) .map (stack -> {return pushElementToStack (stack, block, currentStackList, currentStateHeuristics, goalStateStack); }) .filter (Objekter :: nonNull) .findFirst () .orElse (null); } private State pushElementToStack (Stack stack, String block, List currentStackList, int currentStateHeuristics, Stack goalStateStack) {stack.push (blokk); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); if (newStateHeuristics> currentStateHeuristics) {return new State (currentStackList, newStateHeuristics); } stack.pop (); return null; }

Nå som vi har hjelpermetodene, la oss skrive en metode for å implementere teknikker for å klatre i bakker.

Her, vi fortsetter å beregne nye stater som er nærmere mål enn forgjengerne. Vi fortsetter å legge dem på vår vei til vi når målet.

Hvis vi ikke finner noen nye tilstander, avsluttes algoritmen med en feilmelding:

offentlig liste getRouteWithHillClimbing (Stack initStateStack, Stack goalStateStack) kaster Unntak {// instantiate initState med initStateStack // ... List resultPath = new ArrayList (); resultPath.add (ny stat (initState)); State currentState = initState; boolsk noStateFound = false; mens (! currentState.getState (). get (0) .equals (goalStateStack) || noStateFound) {noStateFound = true; Oppgi nextState = findNextState (currentState, goalStateStack); hvis (nextState! = null) {noStateFound = false; gjeldende stat = neste stat; resultPath.add (ny stat (neste stat)); }} returner resultatPath; }

I tillegg til dette trenger vi også findNextState metode som bruker alle mulige operasjoner i nåværende tilstand for å få neste tilstand:

public State findNextState (State currentState, Stack goalStateStack) {List listOfStacks = currentState.getState (); int currentStateHeuristics = currentState.getHeuristics (); return listOfStacks.stream () .map (stack -> {return applyOperationsOnState (listOfStacks, stack, currentStateHeuristics, goalStateStack);}) .filter (Objects :: nonNull) .findFirst () .orElse (null); } offentlig stat gjelderOperationsOnState (List listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) {State tempState; Liste tempStackList = ny ArrayList (listOfStacks); Strengblokk = stack.pop (); hvis (stack.size () == 0) tempStackList.remove (stack); tempState = pushElementToNewStack (tempStackList, block, currentStateHeuristics, goalStateStack); hvis (tempState == null) {tempState = pushElementToExistingStacks (stack, tempStackList, block, currentStateHeuristics, goalStateStack); stack.push (blokk); } returner tempState; }

6. Algoritme med steileste stigningsklatring

Steepest-Ascent Hill-Climbing algoritme (gradient search) er en variant av Hill Climbing algoritme. Vi kan implementere det med små modifikasjoner i vår enkle algoritme. I denne algoritmen, vi vurdere alle mulige tilstander fra dagens tilstand og deretter velg den beste som etterfølger, i motsetning til i den enkle bakkeklatringsteknikken.

Med andre ord, når det gjelder bakkeklatringsteknikk, valgte vi en hvilken som helst stat som en etterfølger som var nærmere målet enn den nåværende tilstanden, mens vi i Steepest-Ascent Hill Climbing-algoritmen velger den beste etterfølgeren blant alle mulige etterfølgere og deretter oppdaterer den nåværende tilstanden.

7. Ulemper

Hill Climbing er en kortsiktig teknikk da den kun evaluerer umiddelbare muligheter. Så det kan havne i noen få situasjoner som det ikke kan velge ytterligere stater. La oss se på disse tilstandene og noen løsninger for dem:

1. Lokalt maksimum: Det er en tilstand som er bedre enn alle naboer, men det eksisterer en bedre tilstand som er langt fra den nåværende tilstanden; hvis lokalt maksimum oppstår innen synet av løsningen, er det kjent som "foten"
2. Platå: I denne tilstanden har alle nabolandene samme heuristiske verdier, så det er uklart å velge neste stat ved å gjøre lokale sammenligninger
3. Møne: Det er et område som er høyere enn omkringliggende stater, men det kan ikke nås på ett eneste trekk; for eksempel har vi fire mulige retninger å utforske (N, E, W, S), og et område eksisterer i retning NE

Det er få løsninger for å overvinne disse situasjonene:

1. Vi kan backtrack til en av de forrige statene og utforske andre retninger
2. Vi kan hoppe over noen stater og lage en hoppe i nye retninger
3. Vi kan utforske flere retninger for å finne ut riktig vei

8. Konklusjon

Selv om bakkeklatringsteknikk er mye bedre enn uttømmende søk, er det fortsatt ikke optimalt i store problemområder.

Vi kan alltid kode global informasjon i heuristiske funksjoner for å ta smartere beslutninger, men da vil beregningskompleksiteten være mye høyere enn den var tidligere.

Hill klatring algoritme kan være veldig gunstig når clubbed med andre teknikker. Som alltid kan den komplette koden for alle eksempler finnes på GitHub.