streamalism.org

1. Oversigt

I denne vejledning viser vi Hill-Climbing-algoritmen og dens implementering. Vi vil også se på fordelene og manglerne. Før vi springer direkte ind i det, lad os diskutere generere-og-test algoritmer tilgang kort.

2. Generer-og-test algoritme

Det er en meget enkel teknik, der giver os mulighed for at algoritme finde løsninger:

1. Definer den aktuelle tilstand som en starttilstand
2. Anvend enhver mulig operation i den aktuelle tilstand, og generer en mulig løsning
3. Sammenlign nyoprettet løsning med måltilstanden
4. Hvis målet nås, eller hvis der ikke kan oprettes nye stater, skal du afslutte. Ellers skal du vende tilbage til trin 2

Det fungerer meget godt med enkle problemer. Da det er en udtømmende søgning, er det ikke muligt at overveje det, når man beskæftiger sig med store problemrum. Det er også kendt som British Museum algoritme (forsøger at finde en artefakt i British Museum ved at udforske det tilfældigt).

Det er også hovedideen bag Hill-Climbing Attack i biometriens verden. Denne tilgang kan bruges til at generere syntetiske biometriske data.

3. Introduktion til den enkle algoritme til bjergbestigning

I Hill-Climbing-teknik, der starter ved bunden af ​​en bakke, går vi opad, indtil vi når toppen af ​​bakken. Med andre ord starter vi med starttilstand, og vi fortsætter med at forbedre løsningen, indtil den er optimal.

Det er en variation af en generer-og-test-algoritme, der kasserer alle stater, der ikke ser lovende ud eller synes usandsynligt at føre os til måltilstanden. For at tage sådanne beslutninger bruger den heuristik (en evalueringsfunktion), der angiver, hvor tæt den aktuelle tilstand er på måltilstanden.

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

Lad os se på Simple Hill klatring algoritme:

1. Definer den aktuelle tilstand som en starttilstand
2. Sløjfe indtil måltilstanden er nået, eller der ikke kan anvendes flere operatører i den aktuelle tilstand:
   1. Anvend en operation i den aktuelle tilstand og få en ny stat
   2. Sammenligne den nye stat med målet
   3. Afslut hvis måltilstanden er nået
   4. Evaluer ny tilstand med heuristisk funktion og sammenlign det med den aktuelle tilstand
   5. Hvis den nyere stat er tættere til målet sammenlignet med den aktuelle tilstand, opdater den aktuelle tilstand

Som vi kan se, når det måltilstanden med iterative forbedringer. I Hill-Climb-algoritmen svarer det til at finde mål at nå toppen af ​​bakken.

4. Eksempel

Hill Climbing Algorithm kan kategoriseres som en informeret søgning. Så vi kan implementere enhver node-baseret søgning eller problemer som n-dronningsproblemet ved hjælp af det. For at forstå konceptet let vil vi tage et meget simpelt eksempel op.

Lad os se på billedet nedenfor:

Nøglepunkt ved løsning af et bjergbestigningsproblem er at vælge en passende heuristisk funktion.

Lad os definere en sådan funktion h:

h (x) = +1 for alle blokke i understøtningsstrukturen, hvis blokken er placeret korrekt ellers -1 for alle blokke i understøtningsstrukturen.

Her kalder vi enhver blok korrekt placeret, hvis den har den samme støttestruktur som måltilstanden. I henhold til den tidligere diskuterede bjergbestigningsprocedure, lad os se på alle iterationer og deres heuristikker for at nå måltilstanden:

5. Implementering

Lad os nu implementere det samme eksempel ved hjælp af Hill-Climbing-algoritmen.

Først og fremmest har vi brug for en Stat klasse, der gemmer listen over stakke, der repræsenterer positioner for blokke i hver stat. Det gemmer også heuristikker til den pågældende tilstand:

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

Vi har også brug for en metode, der beregner statens heuristiske værdi.

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

Desuden er vi nødt til at definere operatørmetoder, der giver os en ny tilstand. For vores eksempel vil vi definere to af disse metoder:

1. Pop en blok fra en stak, og skub den på en ny stak
2. Pop en blok fra en stak og skub den ind i en af ​​de andre stakke

privat stat pushElementToNewStack (liste currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) {State newState = null; Stak newStack = ny stak (); newStack.push (blok); currentStackList.add (newStack); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); hvis (newStateHeuristics> currentStateHeuristics) {newState = new State (currentStackList, newStateHeuristics); } andet {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 (stakstak, strengblok, liste currentStackList, int currentStateHeuristics, Stack goalStateStack) {stack.push (blok); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); hvis (newStateHeuristics> currentStateHeuristics) {return new State (currentStackList, newStateHeuristics); } stack.pop (); returnere null; }

Nu hvor vi har vores hjælpemetoder, lad os skrive en metode til implementering af bjergbestigningsteknik.

Her, vi fortsætter med at beregne nye stater, der er tættere på målene end deres forgængere. Vi fortsætter med at tilføje dem på vores vej, indtil vi når målet.

Hvis vi ikke finder nye tilstande, slutter algoritmen med en fejlmeddelelse:

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

Ud over dette har vi også brug for findNextState metode, der anvender alle mulige operationer i den aktuelle tilstand for at få den næste tilstand:

public State findNextState (State currentState, Stack goalStateStack) {Liste listOfStacks = currentState.getState (); int currentStateHeuristics = currentState.getHeuristics (); return listOfStacks.stream () .map (stack -> {return applyOperationsOnState (listOfStacks, stack, currentStateHeuristics, goalStateStack);}) .filter (Objects :: nonNull) .findFirst () .orElse (null); } public state applyOperationsOnState (Liste listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) {State tempState; Liste tempStackList = ny ArrayList (listOfStacks); Strengblok = 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 (blok); } returner tempState; }

6. Algoritme med stejleste stigning i bjergbestigning

Steepest-Ascent Hill-Climbing algoritme (gradient search) er en variant af Hill Climbing algoritme. Vi kan implementere det med mindre ændringer i vores enkle algoritme. I denne algoritme, vi overveje alle mulige tilstande fra den aktuelle tilstand og derefter vælg den bedste som efterfølger, i modsætning til den enkle bjergbestigningsteknik.

Med andre ord, i tilfælde af bjergbestigningsteknik valgte vi enhver stat som en efterfølger, der var tættere på målet end den nuværende tilstand, mens vi i Steepest-Ascent Hill Climbing-algoritmen vælger den bedste efterfølger blandt alle mulige efterfølgere og derefter opdaterer den aktuelle tilstand.

7. Ulemper

Hill Climbing er en kortsynt teknik, da den kun vurderer øjeblikkelige muligheder. Så det kan ende i få situationer, hvorfra det ikke kan vælge yderligere stater. Lad os se på disse stater og nogle løsninger til dem:

1. Lokalt maksimum: Det er en tilstand, der er bedre end alle naboer, men der findes en bedre tilstand, der er langt fra den nuværende tilstand; hvis lokalt maksimum forekommer inden for synsvidde af løsningen, er det kendt som "foden"
2. Plateau: I denne tilstand har alle nabostater samme heuristiske værdier, så det er uklart at vælge den næste stat ved at foretage lokale sammenligninger
3. Ryg: Det er et område, der er højere end omgivende stater, men det kan ikke nås på et enkelt træk; for eksempel har vi fire mulige retninger til at udforske (N, E, W, S), og der findes et område i NE-retning

Der er få løsninger til at overvinde disse situationer:

1. Vi kan backtrack til en af ​​de tidligere stater og udforsk andre retninger
2. Vi kan springe over få stater og lave en hoppe i nye retninger
3. Vi kan udforske flere retninger for at finde ud af den rigtige sti

8. Konklusion

Selvom bjergbestigningsteknik er meget bedre end udtømmende søgning, er den stadig ikke optimal i store problemrum.

Vi kan altid kode global information i heuristiske funktioner for at træffe smartere beslutninger, men så vil beregningskompleksiteten være meget højere end den var tidligere.

Hill klatring algoritme kan være meget gavnligt, når clubbed med andre teknikker. Som altid kan den komplette kode for alle eksempler findes på GitHub.