Ejemplo de algoritmo de escalada en Java

1. Información general

En este tutorial, mostraremos el algoritmo Hill-Climbing y su implementación. También veremos sus beneficios y deficiencias. Antes de saltar directamente a él, analicemos brevemente el enfoque de generar y probar algoritmos.

2. Algoritmo de generación y prueba

Es una técnica muy sencilla que nos permite algoritmos de búsqueda de soluciones:

  1. Definir el estado actual como estado inicial
  2. Aplicar cualquier operación posible sobre el estado actual y generar una posible solución
  3. Compare la solución recién generada con el estado objetivo
  4. Si se logra el objetivo o no se pueden crear nuevos estados, abandone. De lo contrario, vuelva al paso 2

Funciona muy bien con problemas sencillos. Al tratarse de una búsqueda exhaustiva, no es factible considerarla cuando se trata de grandes espacios problemáticos. También se lo conoce como algoritmo del Museo Británico (intentar encontrar un artefacto en el Museo Británico explorándolo al azar).

También es la idea principal detrás del ataque de escalada en el mundo de la biometría. Este enfoque se puede utilizar para generar datos biométricos sintéticos.

3. Introducción al algoritmo simple de escalada

En la técnica Hill-Climbing, comenzando en la base de una colina, caminamos hacia arriba hasta llegar a la cima de la colina. En otras palabras, partimos del estado inicial y seguimos mejorando la solución hasta su óptima.

Es una variación de un algoritmo de generación y prueba que descarta todos los estados que no parecen prometedores o que no parecen llevarnos al estado objetivo. Para tomar tales decisiones, utiliza heurística (una función de evaluación) que indica qué tan cerca está el estado actual del estado objetivo.

En palabras simples, Hill-Climbing = generar-y-probar + heurísticas

Veamos el algoritmo de escalada Simple Hill:

  1. Definir el estado actual como estado inicial
  2. Repita hasta que se alcance el estado objetivo o no se puedan aplicar más operadores en el estado actual:
    1. Aplicar una operación al estado actual y obtener un nuevo estado
    2. Compare el nuevo estado con el objetivo
    3. Salir si se alcanza el estado objetivo
    4. Evaluar el nuevo estado con la función heurística y compararlo con el estado actual
    5. Si el estado más nuevo está más cerca del objetivo en comparación con el estado actual, actualice el estado actual

Como podemos ver, alcanza el estado objetivo con mejoras iterativas. En el algoritmo Hill-Climbing, encontrar una meta equivale a llegar a la cima de la colina.

4. Ejemplo

El algoritmo de escalada de colinas se puede clasificar como una búsqueda informada. Entonces podemos implementar cualquier búsqueda basada en nodos o problemas como el problema de las n-reinas usándolo. Para entender el concepto fácilmente, tomaremos un ejemplo muy simple.

Veamos la siguiente imagen:

El punto clave al resolver cualquier problema de escalada es elegir una función heurística adecuada.

Definamos dicha función h:

h (x) = +1 para todos los bloques de la estructura de soporte si el bloque está correctamente posicionado; de lo contrario, -1 para todos los bloques de la estructura de soporte.

Aquí, llamaremos a cualquier bloque colocado correctamente si tiene la misma estructura de soporte que el estado objetivo. Según el procedimiento de escalada de colinas discutido anteriormente, veamos todas las iteraciones y sus heurísticas para alcanzar el estado objetivo:

5. Implementación

Ahora, implementemos el mismo ejemplo usando el algoritmo Hill-Climbing.

En primer lugar, necesitamos una clase State que almacenará la lista de pilas que representan las posiciones de los bloques en cada estado. También almacenará heurísticas para ese estado en particular:

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

También necesitamos un método que calcule el valor heurístico del estado.

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

Además, necesitamos definir métodos de operador que nos darán un nuevo estado. Para nuestro ejemplo, definiremos dos de estos métodos:

  1. Saque un bloque de una pila y empújelo a una nueva pila
  2. Saque un bloque de una pila y empújelo hacia una de las otras pilas
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; }
     
    

Ahora que tenemos nuestros métodos de ayuda, escribamos un método para implementar la técnica de escalada.

Aquí, seguimos calculando nuevos estados que están más cerca de los objetivos que sus predecesores. Seguimos añadiéndolos en nuestro camino hasta llegar a la meta.

Si no encontramos ningún estado nuevo, el algoritmo termina con un mensaje de error:

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

Además de esto, también necesitamos el método findNextState que aplica todas las operaciones posibles en el estado actual para obtener el siguiente estado:

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. Algoritmo de escalada de pendiente más empinada

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.

Siempre podemos codificar información global en funciones heurísticas para tomar decisiones más inteligentes, pero entonces la complejidad computacional será mucho mayor que antes.

El algoritmo de escalada puede ser muy beneficioso cuando se golpea con otras técnicas. Como siempre, el código completo para todos los ejemplos se puede encontrar en GitHub.