Exemple d'algorithme d'escalade en Java

1. Vue d'ensemble

Dans ce tutoriel, nous allons montrer l'algorithme Hill-Climbing et son implémentation. Nous examinerons également ses avantages et ses inconvénients. Avant de vous lancer directement, discutons brièvement de l'approche des algorithmes de génération et de test.

2. Algorithme de génération et de test

C'est une technique très simple qui nous permet d'algorithmiser la recherche de solutions:

  1. Définir l'état actuel comme état initial
  2. Appliquer toute opération possible sur l'état actuel et générer une solution possible
  3. Comparez la solution nouvellement générée avec l'état de l'objectif
  4. Si l'objectif est atteint ou qu'aucun nouvel état ne peut être créé, quittez. Sinon, revenez à l'étape 2

Cela fonctionne très bien avec des problèmes simples. Comme il s'agit d'une recherche exhaustive, il n'est pas possible de la considérer tout en traitant de grands espaces à problèmes. Il est également connu sous le nom d'algorithme du British Museum (en essayant de trouver un artefact au British Museum en l'explorant au hasard).

C'est également l'idée principale derrière l'attaque d'escalade dans le monde de la biométrie. Cette approche peut être utilisée pour générer des données biométriques synthétiques.

3. Introduction à l'algorithme simple d'escalade

En technique d'escalade, en partant du pied d'une colline, nous montons jusqu'à atteindre le sommet de la colline. En d'autres termes, nous commençons par l'état initial et nous continuons à améliorer la solution jusqu'à ce qu'elle soit optimale.

C'est une variante d'un algorithme de génération et de test qui rejette tous les états qui ne semblent pas prometteurs ou qui semblent peu susceptibles de nous conduire à l'état cible. Pour prendre de telles décisions, il utilise une heuristique (une fonction d'évaluation) qui indique à quel point l'état actuel est proche de l'état de l'objectif.

En termes simples, Hill-Climbing = générer-et-tester + heuristique

Regardons l'algorithme d'escalade Simple Hill:

  1. Définir l'état actuel comme état initial
  2. Boucle jusqu'à ce que l'état de l'objectif soit atteint ou qu'aucun autre opérateur ne puisse être appliqué à l'état actuel:
    1. Appliquer une opération à l'état actuel et obtenir un nouvel état
    2. Comparez le nouvel état avec l'objectif
    3. Quitter si l'état de l'objectif est atteint
    4. Évaluer le nouvel état avec une fonction heuristique et le comparer avec l'état actuel
    5. Si l'état le plus récent est plus proche de l'objectif par rapport à l'état actuel, mettez à jour l'état actuel

Comme nous pouvons le voir, il atteint l'état de l'objectif avec des améliorations itératives. Dans l'algorithme Hill-Climbing, trouver un objectif équivaut à atteindre le sommet de la colline.

4. Exemple

L'algorithme d'escalade de colline peut être classé comme une recherche informée. Nous pouvons donc implémenter n'importe quelle recherche basée sur les nœuds ou des problèmes comme le problème des n-reines en l'utilisant. Pour comprendre facilement le concept, nous prendrons un exemple très simple.

Regardons l'image ci-dessous:

Le point clé lors de la résolution de tout problème d'escalade est de choisir une fonction heuristique appropriée.

Définissons une telle fonction h:

h (x) = +1 pour tous les blocs de la structure de support si le bloc est correctement positionné sinon -1 pour tous les blocs de la structure de support.

Ici, nous appellerons tout bloc correctement positionné s'il a la même structure de support que l'état de l'objectif. Selon la procédure d'escalade discutée précédemment, examinons toutes les itérations et leurs heuristiques pour atteindre l'état cible:

5. Mise en œuvre

Maintenant, implémentons le même exemple en utilisant l'algorithme Hill-Climbing.

Tout d'abord, nous avons besoin d'une classe State qui stockera la liste des piles représentant les positions des blocs à chaque état. Il stockera également des heuristiques pour cet état particulier:

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

Nous avons également besoin d'une méthode qui calculera la valeur heuristique de l'état.

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.

Nous pouvons toujours encoder des informations globales en fonctions heuristiques pour prendre des décisions plus intelligentes, mais la complexité de calcul sera alors beaucoup plus élevée qu'elle ne l'était auparavant.

L'algorithme d'escalade peut être très bénéfique lorsqu'il est matraqué avec d'autres techniques. Comme toujours, le code complet de tous les exemples est disponible à l'adresse over sur GitHub.