Javaでの山登りアルゴリズムの例

投稿日: 2019-10-18 2022-10-26
タグ: Algorithms

1. 概要

このチュートリアルでは、山登りアルゴリズムとその実装を示します。また、その長所と短所についても見ていきます。直接それに飛び込む前に、生成とテストのアルゴリズムのアプローチについて簡単に説明しましょう。

2. 生成およびテストアルゴリズム

これは非常に単純な手法であり、ソリューションの検索をアルゴリズム化することができます。

現在の状態を初期状態として定義する
現在の状態に可能な操作を適用し、可能な解決策を生成します
新しく生成されたソリューションを目標の状態と比較します
目標が達成された場合、または新しい状態を作成できない場合は、終了します。それ以外の場合は、手順2に戻ります。

単純な問題で非常にうまく機能します。徹底的な検索であるため、大きな問題スペースを処理する際に検討することは現実的ではありません。これは大英博物館アルゴリズムとしても知られています（大英博物館でアーティファクトをランダムに探索して見つけようとします）。

これは、バイオメトリクスの世界における山登り法の背後にある主要なアイデアでもあります。このアプローチは、合成生体認証データを生成するために使用できます。

3. 単純な山登りアルゴリズムの概要

山登り法では、丘のふもとから始めて、丘の頂上に到達するまで上向きに歩きます。つまり、初期状態から始めて、最適になるまでソリューションを改善し続けます。

これは、生成とテストのアルゴリズムのバリエーションであり、有望に見えない、または目標状態につながる可能性が低いと思われるすべての状態を破棄します。このような決定を行うために、現在の状態が目標の状態にどれだけ近いかを示すヒューリスティック（評価関数）を使用します。

簡単に言うと、山登り法=生成とテスト+ヒューリスティック

SimpleHill登りアルゴリズムを見てみましょう。

現在の状態を初期状態として定義します
目標状態が達成されるか、現在の状態にこれ以上演算子を適用できなくなるまでループします。
1. 現在の状態に操作を適用し、新しい状態を取得します
2. 新しい状態を目標と比較
3. 目標状態が達成された場合はを終了します
4. ヒューリスティック関数を使用して新しい状態を評価し、現在の状態と比較します
5. 新しい状態が現在の状態と比較して目標に近い場合、現在の状態を更新します

ご覧のとおり、反復的な改善により目標状態に到達します。山登りアルゴリズムでは、目標を見つけることは丘の頂上に到達することと同じです。

4. 例

山登りアルゴリズムは、情報に基づいた検索として分類できます。したがって、ノードベースの検索や、それを使用したn-queens問題などの問題を実装できます。概念を簡単に理解するために、非常に簡単な例を取り上げます。

下の画像を見てみましょう。

山登り問題を解決する際の重要なポイントは、適切なヒューリスティック関数を選択することです。

そのような関数を定義しましょうh：

h（x） =ブロックが正しく配置されている場合は、サポート構造内のすべてのブロックに対して+1、それ以外の場合は、サポート構造内のすべてのブロックに対して-1。

ここでは、目標状態と同じサポート構造を持っている場合、正しく配置されたブロックを呼び出します。前に説明した山登り法の手順に従って、ターゲット状態に到達するためのすべての反復とそのヒューリスティックを見てみましょう。

5. 実装

それでは、山登りアルゴリズムを使用して同じ例を実装しましょう。

まず、各状態でのブロックの位置を表すスタックのリストを格納するStateクラスが必要です。また、その特定の状態のヒューリスティックを格納します。

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

また、状態のヒューリスティック値を計算するメソッドも必要です。

public int getHeuristicsValue(
  List<Stack<String>> currentState, Stack<String> goalStateStack) {
 
    Integer heuristicValue;
    heuristicValue = currentState.stream()
      .mapToInt(stack -> {
          return getHeuristicsValueForStack(
            stack, currentState, goalStateStack);
    }).sum();
 
    return heuristicValue;
}

public int getHeuristicsValueForStack(
  Stack<String> stack,
  List<Stack<String>> currentState,
  Stack<String> 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;
}

さらに、新しい状態を取得する演算子メソッドを定義する必要があります。この例では、次の2つのメソッドを定義します。

スタックからブロックをポップして、新しいスタックにプッシュします
スタックからブロックをポップし、他のスタックの1つにプッシュします

private State pushElementToNewStack(
  List<Stack<String>> currentStackList,
  String block,
  int currentStateHeuristics,
  Stack<String> goalStateStack) {
 
    State newState = null;
    Stack<String> 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<Stack<String>> currentStackList,
  String block,
  int currentStateHeuristics,
  Stack<String> 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<Stack<String>> currentStackList,
  int currentStateHeuristics,
  Stack<String> goalStateStack) {

    stack.push(block);
    int newStateHeuristics 
      = getHeuristicsValue(currentStackList, goalStateStack);
    if (newStateHeuristics > currentStateHeuristics) {
        return new State(currentStackList, newStateHeuristics);
    }
    stack.pop();
    return null;
}

ヘルパーメソッドができたので、山登り法を実装するメソッドを作成しましょう。

ここでは、前の状態よりも目標に近い新しい状態を計算し続けます。目標に到達するまで、パスにそれらを追加し続けます。

新しい状態が見つからない場合、アルゴリズムはエラーメッセージで終了します。

public List<State> getRouteWithHillClimbing(
  Stack<String> initStateStack, Stack<String> goalStateStack) throws Exception {
    // instantiate initState with initStateStack
    // ...
    List<State> 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;
}

これに加えて、次の状態を取得するために現在の状態で可能なすべての操作を適用するfindNextStateメソッドも必要です。

public State findNextState(State currentState, Stack<String> goalStateStack) {
    List<Stack<String>> 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<Stack<String>> listOfStacks,
  Stack<String> stack,
  int currentStateHeuristics,
  Stack<String> goalStateStack) {

    State tempState;
    List<Stack<String>> 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. 最も急な山登りアルゴリズム

最急降下法の山登りアルゴリズム（勾配検索）は、山登りアルゴリズムの変形です。単純なアルゴリズムを少し変更するだけで実装できます。このアルゴリズムでは、単純な山登り法とは異なり、現在の状態からすべての可能な状態を考慮し、が後継者として最適な状態を選択します。

つまり、山登り法の場合、現在の状態よりも目標に近い後継者として任意の状態を選択しましたが、急勾配の山登りアルゴリズムでは、可能なすべての後継者の中から最良の後継者を選択してから更新します。現在の状態。

7. 短所

山登り法は、当面の可能性のみを評価するため、近視眼的な手法です。そのため、それ以上の状態を選択できないいくつかの状況で終わる可能性があります。これらの状態とそれらのいくつかの解決策を見てみましょう。

ローカル最大値：すべてのネイバーよりも優れた状態ですが、現在の状態からはほど遠い、より優れた状態が存在します。ソリューションの視界内で極大値が発生する場合、それは「フットヒル」として知られています
プラトー：この状態では、隣接するすべての状態のヒューリスティック値が同じであるため、ローカル比較を行って次の状態を選択するかどうかは不明です。
リッジ：周囲の州よりも高いエリアですが、1回の移動で到達することはできません。たとえば、探索する4つの可能な方向（N、E、W、S）があり、NE方向にエリアが存在します

これらの状況を克服するための解決策はいくつかあります。

以前の状態の1つにバックトラックして、他の方向を探索することができます
いくつかの状態をスキップして、新しい方向にジャンプを作成できます
いくつかの方向を探索して正しいパスを見つけることができます

8. 結論

山登り法は全数検索よりもはるかに優れていますが、それでも大きな問題のあるスペースでは最適ではありません。

グローバル情報をヒューリスティック関数にエンコードして、よりスマートな意思決定を行うことができますが、計算の複雑さは以前よりもはるかに高くなります。

山登り法のアルゴリズムは、他の手法でクラブを組むときに非常に役立ちます。いつものように、すべての例の完全なコードは、GitHubのにあります。

getdocs

13036