Beispiel eines Hill Climbing-Algorithmus in Java

1. Übersicht

In diesem Tutorial zeigen wir den Hill-Climbing-Algorithmus und seine Implementierung. Wir werden auch die Vor- und Nachteile untersuchen. Bevor wir direkt darauf eingehen, wollen wir kurz auf den Ansatz der Generierungs- und Testalgorithmen eingehen.

2. Generieren und Testen des Algorithmus

Es ist eine sehr einfache Technik, mit der wir die Suche nach Lösungen algorithmisieren können:

  1. Definieren Sie den aktuellen Status als Ausgangszustand
  2. Wenden Sie eine mögliche Operation auf den aktuellen Status an und generieren Sie eine mögliche Lösung
  3. Vergleichen Sie die neu generierte Lösung mit dem Zielstatus
  4. Wenn das Ziel erreicht ist oder keine neuen Zustände erstellt werden können, beenden Sie den Vorgang. Andernfalls kehren Sie zu Schritt 2 zurück

Es funktioniert sehr gut mit einfachen Problemen. Da es sich um eine erschöpfende Suche handelt, ist es nicht möglich, sie bei großen Problemräumen zu berücksichtigen. Es ist auch als British Museum-Algorithmus bekannt (der versucht, ein Artefakt im British Museum zu finden, indem er es zufällig untersucht).

Es ist auch die Hauptidee hinter dem Hill-Climbing Attack in der Welt der Biometrie. Dieser Ansatz kann zur Erzeugung synthetischer biometrischer Daten verwendet werden.

3. Einführung in den Simple Hill-Climbing-Algorithmus

In der Hill-Climbing-Technik gehen wir vom Fuß eines Hügels aus nach oben, bis wir die Spitze des Hügels erreichen. Mit anderen Worten, wir beginnen mit dem Ausgangszustand und verbessern die Lösung weiter, bis sie optimal ist.

Es ist eine Variation eines Generierungs- und Testalgorithmus, der alle Zustände verwirft, die nicht vielversprechend aussehen oder uns wahrscheinlich nicht zum Zielzustand führen. Um solche Entscheidungen zu treffen, werden Heuristiken (eine Bewertungsfunktion) verwendet, die angeben, wie nahe der aktuelle Zustand am Zielzustand liegt.

In einfachen Worten, Hill-Climbing = Generieren und Testen + Heuristiken

Schauen wir uns den Simple Hill-Kletteralgorithmus an:

  1. Definieren Sie den aktuellen Status als Ausgangszustand
  2. Schleife, bis der Zielzustand erreicht ist oder keine Operatoren mehr auf den aktuellen Zustand angewendet werden können:
    1. Wenden Sie eine Operation auf den aktuellen Status an und erhalten Sie einen neuen Status
    2. Vergleichen Sie den neuen Zustand mit dem Ziel
    3. Beenden Sie, wenn der Zielzustand erreicht ist
    4. Bewerten Sie den neuen Zustand mit heuristischer Funktion und vergleichen Sie ihn mit dem aktuellen Zustand
    5. Wenn der neuere Status im Vergleich zum aktuellen Status näher am Ziel liegt, aktualisieren Sie den aktuellen Status

Wie wir sehen können, erreicht es den Zielzustand mit iterativen Verbesserungen. Beim Hill-Climbing-Algorithmus entspricht das Finden des Ziels dem Erreichen der Bergspitze.

4. Beispiel

Der Hill Climbing-Algorithmus kann als informierte Suche eingestuft werden. So können wir jede knotenbasierte Suche oder Probleme wie das Problem der n-Königinnen damit implementieren. Um das Konzept leicht zu verstehen, werden wir ein sehr einfaches Beispiel aufgreifen.

Schauen wir uns das Bild unten an:

Der entscheidende Punkt bei der Lösung von Problemen beim Bergsteigen ist die Auswahl einer geeigneten heuristischen Funktion.

Definieren wir eine solche Funktion h:

h (x) = +1 für alle Blöcke in der Stützstruktur, wenn der Block korrekt positioniert ist, andernfalls -1 für alle Blöcke in der Stützstruktur.

Hier rufen wir jeden Block auf, der korrekt positioniert ist, wenn er dieselbe Unterstützungsstruktur wie der Zielstatus hat. Schauen wir uns gemäß dem zuvor beschriebenen Verfahren zum Bergsteigen alle Iterationen und ihre Heuristiken an, um den Zielzustand zu erreichen:

5. Implementierung

Lassen Sie uns nun dasselbe Beispiel mit dem Hill-Climbing-Algorithmus implementieren.

Zunächst benötigen wir eine State- Klasse, in der die Liste der Stapel gespeichert wird, die die Positionen der Blöcke in jedem State darstellen. Es werden auch Heuristiken für diesen bestimmten Zustand gespeichert:

public class State { private List
    
      state; private int heuristics; // copy constructor, setters, and getters }
    

Wir brauchen auch eine Methode, die den heuristischen Wert des Staates berechnet.

public int getHeuristicsValue( List
    
      currentState, Stack goalStateStack) { Integer 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; boolean isPositioneCorrect = true; int goalStartIndex = 0; for (String currentBlock : stack) { if (isPositioneCorrect && currentBlock.equals(goalStateStack.get(goalStartIndex))) { stackHeuristics += goalStartIndex; } else { stackHeuristics -= goalStartIndex; isPositioneCorrect = false; } goalStartIndex++; } return stackHeuristics; } 
     
    

Darüber hinaus müssen wir Operatormethoden definieren, die uns einen neuen Status verschaffen. In unserem Beispiel definieren wir zwei dieser Methoden:

  1. Pop einen Block von einem Stapel und schieben Sie ihn auf einen neuen Stapel
  2. Nehmen Sie einen Block von einem Stapel und schieben Sie ihn in einen der anderen Stapel
private State pushElementToNewStack( List
    
      currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) { State newState = null; Stack newStack = new Stack(); newStack.push(block); currentStackList.add(newStack); int newStateHeuristics = getHeuristicsValue(currentStackList, goalStateStack); if (newStateHeuristics > currentStateHeuristics) { newState = new State(currentStackList, newStateHeuristics); } else { currentStackList.remove(newStack); } return 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(Objects::nonNull) .findFirst() .orElse(null); } private State pushElementToStack( Stack stack, String block, List
     
       currentStackList, int currentStateHeuristics, Stack goalStateStack) { stack.push(block); int newStateHeuristics = getHeuristicsValue(currentStackList, goalStateStack); if (newStateHeuristics > currentStateHeuristics) { return new State(currentStackList, newStateHeuristics); } stack.pop(); return null; }
     
    

Nachdem wir unsere Hilfsmethoden haben, schreiben wir eine Methode zur Implementierung der Bergsteigertechnik.

Hier berechnen wir immer wieder neue Zustände, die näher an den Zielen liegen als ihre Vorgänger. Wir fügen sie unserem Weg hinzu, bis wir das Ziel erreichen.

Wenn wir keine neuen Zustände finden, wird der Algorithmus mit einer Fehlermeldung beendet:

public List getRouteWithHillClimbing( Stack initStateStack, Stack goalStateStack) throws Exception { // instantiate initState with initStateStack // ... List resultPath = new ArrayList(); resultPath.add(new State(initState)); State currentState = initState; boolean noStateFound = false; while ( !currentState.getState().get(0).equals(goalStateStack) || noStateFound) { noStateFound = true; State nextState = findNextState(currentState, goalStateStack); if (nextState != null) { noStateFound = false; currentState = nextState; resultPath.add(new State(nextState)); } } return resultPath; }

Darüber hinaus benötigen wir die findNextState- Methode, die alle möglichen Operationen auf den aktuellen Status anwendet, um den nächsten Status zu erhalten:

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); } public State applyOperationsOnState( List
     
       listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) { State tempState; List
      
        tempStackList = new ArrayList(listOfStacks); String block = stack.pop(); if (stack.size() == 0) tempStackList.remove(stack); tempState = pushElementToNewStack( tempStackList, block, currentStateHeuristics, goalStateStack); if (tempState == null) { tempState = pushElementToExistingStacks( stack, tempStackList, block, currentStateHeuristics, goalStateStack); stack.push(block); } return tempState; }
      
     
    

6. Steigste Aufstiegs-Algorithmus

Steepest-Ascent Hill-Climbing algorithm (gradient search) is a variant of Hill Climbing algorithm. We can implement it with slight modifications in our simple algorithm. In this algorithm, we consider all possible states from the current state and then pick the best one as successor, unlike in the simple hill climbing technique.

In other words, in the case of hill climbing technique we picked any state as a successor which was closer to the goal than the current state whereas, in Steepest-Ascent Hill Climbing algorithm, we choose the best successor among all possible successors and then update the current state.

7. Disadvantages

Hill Climbing is a short sighted technique as it evaluates only immediate possibilities. So it may end up in few situations from which it can not pick any further states. Let's look at these states and some solutions for them:

  1. Local maximum: It's a state which is better than all neighbors, but there exists a better state which is far from the current state; if local maximum occurs within sight of the solution, it is known as “foothills”
  2. Plateau: In this state, all neighboring states have same heuristic values, so it's unclear to choose the next state by making local comparisons
  3. Ridge: It's an area which is higher than surrounding states, but it can not be reached in a single move; for example, we have four possible directions to explore (N, E, W, S) and an area exists in NE direction

There are few solutions to overcome these situations:

  1. We can backtrack to one of the previous states and explore other directions
  2. We can skip few states and make a jump in new directions
  3. We can explore several directions to figure out the correct path

8. Conclusion

Even though hill climbing technique is much better than exhaustive search, it's still not optimal in large problem spaces.

Wir können globale Informationen immer in heuristische Funktionen codieren, um intelligentere Entscheidungen zu treffen, aber dann wird die Komplexität der Berechnungen viel höher sein als früher.

Der Hill Climbing-Algorithmus kann sehr nützlich sein, wenn er mit anderen Techniken zusammengeschlagen wird. Wie immer finden Sie den vollständigen Code für alle Beispiele auf GitHub.