1概要

このチュートリアルでは、Hill-Climbingアルゴリズムとその実装について説明します。また、その利点と欠点についても説明します。直接説明する前に、生成とテストのアルゴリズムのアプローチについて簡単に説明しましょう。


2テスト生成アルゴリズム

それは私たちが解を見つけることをアルゴリズム化することを可能にする非常に単純なテクニックです:

  1. 初期状態として現在の状態を定義する

  2. 現在の状態に可能な操作を適用して、

考えられる解決策
。新しく生成された解と目標状態を比較する

  1. 目標が達成された場合、または新しい状態を作成できない場合は、終了します.

それ以外の場合は、手順2に戻ります。

単純な問題では非常にうまくいきます。これは徹底的な検索なので、大きな問題空間を扱っている間それを考慮することは現実的ではありません。大英博物館のアルゴリズムとしても知られています(ランダムに探索して、大英博物館で遺物を探そうとしている)。

それはバイオメトリクスの世界におけるヒルクライムアタックの背後にある主なアイデアでもあります。この手法は、合成バイオメトリックデータを生成するために使用することができる。


3単純な山登りアルゴリズムの紹介

ヒルクライムテクニックでは、丘のふもとから丘の頂上に達するまで上に向かって歩きます。言い換えれば、我々は初期状態から始めて、最適になるまで解を改善し続けます。

それは、見込みがないように見えたり、目標状態に導いてしまう可能性が低いと思われるすべての状態を破棄する生成およびテストアルゴリズムのバリエーションです。そのような決定をするために、それは現在の状態がゴール状態にどれほど近いかを示すヒューリスティック(評価関数)を使います。

簡単に言うと、** Hill-Climbing =生成とテストのヒューリスティック

Simple Hillクライミングアルゴリズムを見てみましょう。

  1. 現在の状態を初期状態として定義する

  2. 目標状態が達成されるまで、またはそれ以上オペレータが実行できなくなるまでループします.

現在の状態に適用されます。

.現在の状態に操作を適用して

新しい状態を取得

  1. 新しい状態と目標を比較

.ヒューリスティック関数で新しい状態を評価し、** と比較する

現在の状態

..

新しい状態が現在の状態に比べて目標に近い場合**

  • 現在の状態を更新する**

見ての通り、それは反復的な改善で目標状態に到達します。 Hill-Climbingアルゴリズムでは、目標を見つけることは丘の上に到達することと同じです。


4例

ヒルクライムアルゴリズムはインフォームドサーチとして分類することができます。そのため、ノードベースの検索や、それを使用したnクイーン問題などの問題を実装できます。概念を簡単に理解するために、非常に簡単な例を取り上げます。

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

リンク:/uploads/init__goal.png[]

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

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

h:

  • ブロックが正しく配置されている場合は、サポート構造内のすべてのブロックに対して

    h(x)

    = 1、それ以外の場合はサポート構造内のすべてのブロックに対して-1。

ここでは、ブロックがゴール状態と同じサポート構造を持っていれば、正しい位置にあるブロックを呼び出します。前述の山登り手順に従って、目標の状態に到達するためのすべての反復とそのヒューリスティックを調べてみましょう。

リンク:/uploads/state__iterations-768×422.png%20768w[]

  • 5実装**

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

まず最初に、各状態でのブロックの位置を表すスタックのリストを格納する

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. スタックからブロックをポップして新しいスタックにプッシュする

  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. 最急上昇の登山アルゴリズム

最急上昇ヒルクライミングアルゴリズム(勾配探索)はヒルクライミングアルゴリズムの変形である。私たちの単純なアルゴリズムに少し修正を加えてそれを実装することができます。このアルゴリズムでは、単純な山登り法とは異なり、現在の状態からすべての可能性のある状態を考慮し、次に最良の状態を後続の状態として選択します。

言い換えれば、山登り法の場合、現在の状態よりもゴールに近い状態を後継者として選択しましたが、Steepest-Ascent Hill Climbingアルゴリズムでは、すべての可能な後継者の中から最良の後継者を選択して更新します。現在の状態


7. デメリット

ヒルクライムはただちに可能性を評価するので近視眼的なテクニックです。そのため、それ以上の状態を選択できないような状況になる可能性があります。これらの状態とそれらに対する解決策を見てみましょう。


  1. 極大値:

    それはすべての隣人より良い状態です

現在の状態からかけ離れたより良い状態が存在します。もし
極大値は解の視野内で発生します。
“ふもとの小丘”


高原:

この状態では、すべての近隣州が同じヒューリスティックを持っています

そのため、地域の価値観を
比較


尾根:

周辺の州よりも高い地域ですが、

一回の移動では到達できません。たとえば、探索できる方向は4つ(N、E、W、S)で、NE方向にエリアがあります

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

  1. 以前の状態の1つに

    バックトラック

    し、他の状態を探索する

行き方
。いくつかの状態をスキップして新しい方向に

ジャンプ

することができます。

  1. 正しい道筋を見つけるために

    いくつかの方向性を探る

    ことができます

8.まとめ

山登り法は徹底的な検索よりはるかに優れていますが、それでも大きな問題のある場所では最適ではありません。

グローバルな情報をヒューリスティックな機能に符号化してより賢明な決定を下すことができますが、計算の複雑さは以前よりはるかに高くなります。

山登りアルゴリズムは、他のテクニックと組み合わせたときに非常に有益です。いつものように、すべての例のための完全なコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[GitHubで動く]を見つけることができます。