Esempio di algoritmo per l'arrampicata in collina in Java

1. Panoramica

In questo tutorial, mostreremo l'algoritmo Hill-Climbing e la sua implementazione. Vedremo anche i suoi vantaggi e difetti. Prima di addentrarci direttamente, discutiamo brevemente dell'approccio di generazione e test degli algoritmi.

2. Algoritmo di generazione e verifica

È una tecnica molto semplice che ci consente di algoritmizzare la ricerca di soluzioni:

  1. Definisce lo stato corrente come stato iniziale
  2. Applicare ogni possibile operazione allo stato corrente e generare una possibile soluzione
  3. Confronta la soluzione appena generata con lo stato obiettivo
  4. Se l'obiettivo viene raggiunto o non è possibile creare nuovi stati, esci. Altrimenti, torna al passaggio 2

Funziona molto bene con problemi semplici. Trattandosi di una ricerca esaustiva, non è possibile considerarla trattando grandi spazi problematici. È anche noto come algoritmo del British Museum (cercando di trovare un artefatto nel British Museum esplorandolo in modo casuale).

È anche l'idea principale alla base dell'Hill-Climbing Attack nel mondo della biometria. Questo approccio può essere utilizzato per generare dati biometrici sintetici.

3. Introduzione al Simple Hill-Climbing Algorithm

Nella tecnica Hill-Climbing, partendo dalla base di una collina, camminiamo verso l'alto fino a raggiungere la cima della collina. In altre parole, iniziamo con lo stato iniziale e continuiamo a migliorare la soluzione fino a quando non è ottimale.

È una variazione di un algoritmo di generazione e test che scarta tutti gli stati che non sembrano promettenti o sembrano improbabili che ci conducano allo stato obiettivo. Per prendere tali decisioni, utilizza l'euristica (una funzione di valutazione) che indica quanto lo stato corrente è vicino allo stato obiettivo.

In parole semplici, Hill-Climbing = genera-e-prova + euristica

Diamo un'occhiata all'algoritmo di arrampicata su Simple Hill:

  1. Definisci lo stato corrente come stato iniziale
  2. Ripeti il ​​ciclo finché non viene raggiunto lo stato dell'obiettivo o non è possibile applicare più operatori allo stato corrente:
    1. Applica un'operazione allo stato corrente e ottieni un nuovo stato
    2. Confronta il nuovo stato con l'obiettivo
    3. Esci se lo stato obiettivo viene raggiunto
    4. Valuta il nuovo stato con la funzione euristica e confrontalo con lo stato corrente
    5. Se lo stato più recente è più vicino all'obiettivo rispetto allo stato corrente, aggiorna lo stato corrente

Come possiamo vedere, raggiunge lo stato obiettivo con miglioramenti iterativi. Nell'algoritmo Hill-Climbing, trovare l'obiettivo equivale a raggiungere la cima della collina.

4. Esempio

Hill Climbing Algorithm può essere classificato come una ricerca informata. Quindi possiamo implementare qualsiasi ricerca basata sui nodi o problemi come il problema delle n-regine utilizzandolo. Per comprendere facilmente il concetto, prenderemo un esempio molto semplice.

Diamo un'occhiata all'immagine qui sotto:

Il punto chiave durante la risoluzione di qualsiasi problema di arrampicata in collina è scegliere una funzione euristica appropriata.

Definiamo tale funzione h:

h (x) = +1 per tutti i blocchi nella struttura di supporto se il blocco è posizionato correttamente altrimenti -1 per tutti i blocchi nella struttura di supporto.

Qui, chiameremo qualsiasi blocco posizionato correttamente se ha la stessa struttura di supporto dello stato obiettivo. Come per la procedura di salita in collina discussa in precedenza, esaminiamo tutte le iterazioni e le loro euristiche per raggiungere lo stato target:

5. Attuazione

Ora implementiamo lo stesso esempio utilizzando l'algoritmo Hill-Climbing.

Prima di tutto, abbiamo bisogno di una classe State che memorizzerà l'elenco degli stack che rappresentano le posizioni dei blocchi in ogni stato. Memorizzerà anche l'euristica per quel particolare stato:

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

Abbiamo anche bisogno di un metodo che calcoli il valore euristico dello stato.

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; } 
     
    

Furthermore, we need to define operator methods which will get us a new state. For our example we will define two of these methods:

  1. Pop a block from a stack and push it onto a new stack
  2. Pop a block from a stack and push it into one of the other stacks
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; }
     
    

Now that we have our helper methods let's write a method to implement hill climbing technique.

Here, we keep computing new states which are closer to goals than their predecessors. We keep adding them in our path until we reach the goal.

If we don't find any new states, the algorithm terminates with an error message:

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; }

In addition to this, we also need findNextState method which applies all possible operations on current state to get the next state:

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. Steepest-Ascent Hill Climbing Algorithm

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.

Possiamo sempre codificare le informazioni globali in funzioni euristiche per prendere decisioni più intelligenti, ma in tal caso la complessità computazionale sarà molto più elevata di quanto non fosse in precedenza.

L'algoritmo di arrampicata in collina può essere molto utile quando viene eseguito con altre tecniche. Come sempre, il codice completo per tutti gli esempi può essere trovato su GitHub.