第10章 Local Search (局所探索法)

ステップは勝利 Move です。局所探索法は、現在の解に多くの Move を試し、最適な Move をステップとして選択します。

図10.1 ステップ 0 で次のステップの決定 (クイーン 4 個の例)

B0 から B3 への Move のスコアが一番高い (-3) ため、これが次のステップとして選択されます。最高スコアの Move が複数ある場合は、そのうちの 1 つがランダムに選択されます (この例では B0 から B3)。(ここには示されていませんが) C0 から C3 への Move もスコアが 3 なので、代わりにこの Move が選択された可能性があります。

このステップが解に適用されたら、次の解に向けて、局所探索法がすべての Move をもう一度繰り返し、次のステップを決定します。これがループして継続していき、以下のような結果となります。

図10.2 全ステップ (クイーン 4 個の例)

局所探索法は、探索木ではなく、探索パスを使用している点に注意してください。探索パスは緑の矢印で示されます。各ステップで、選択された Move はすべて試されますが、次のステップとして選択されない限り、その解をそれ以上調べることはありません。これが、局所探索法が非常にスケーラブルな理由です。

上記の例が示すように、局所探索法は、クイーン 4 個の問題を、最初の解から始め、以下のステップを順次選択します。

org.optaplanner カテゴリーの デバッグ ログを有効 にすると、ログにこのステップが示されます。

INFO  Solving started: time spent (0), best score (-6), random (JDK with seed 0).
DEBUG     LS step (0), time spent (20), score (-3), new best score (-3), accepted/selected move count (12/12), picked move (Queen-1 {Row-0 -> Row-3}).
DEBUG     LS step (1), time spent (31), score (-1), new best score (-1), accepted/selected move count (12/12), picked move (Queen-3 {Row-0 -> Row-2}).
DEBUG     LS step (2), time spent (40), score (0), new best score (0), accepted/selected move count (12/12), picked move (Queen-0 {Row-0 -> Row-1}).
INFO  Local Search phase (0) ended: step total (3), time spent (41), best score (0).
INFO  Solving ended: time spent (41), best score (0), average calculate count per second (1780).

ログメッセージには、Move 実装の toString() メソッドが含まれます。これは、たとえば Queen-1 {Row-0 -> Row-3} を返します。

ネイティブの局所探索法の設定は、クイーン 4 個の問題を 3 つのステップで解きますが、可能解として評価するのは 37 個 (3 ステップで、1 ステップあたり 12 個の Move + 最初の解 1 つ) です。この値は、合計で 256 個となる可能解の一部でしかありません。クイーンが 16 個の場合は 31 ステップとなり、解の合計は 18446744073709551616 個になりますが、評価されるのは、そのうち 7441 個です。さらに、構築ヒューリスティック フェーズを最初に使用することで、効率がはるかに良くなります。

局所探索法は、次の設定可能なコンポーネントを 3 つ用いて、次のステップを決めます。

Solver フェーズ設定は以下のようになります。

  <localSearch>
    <unionMoveSelector>
      ...
    </unionMoveSelector>
    <acceptor>
      ...
    </acceptor>
    <forager>
      ...
    </forager>
  </localSearch>

以下の例では、MoveSelector が、青い線で示される Move を集め、Acceptor がそのすべてを認め、Forager が B0 から B3 への Move を選択します。

トレース のログを有効にすると、ログに意思決定が示されます。

INFO  Solver started: time spent (0), score (-6), new best score (-6), random (JDK with seed 0).
TRACE         Move index (0) not doable, ignoring move (Queen-0 {Row-0 -> Row-0}).
TRACE         Move index (1), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-1}).
TRACE         Move index (2), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-2}).
TRACE         Move index (3), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-3}).
...
TRACE         Move index (6), score (-3), accepted (true), move (Queen-1 {Row-0 -> Row-3}).
...
TRACE         Move index (9), score (-3), accepted (true), move (Queen-2 {Row-0 -> Row-3}).
...
TRACE         Move index (12), score (-4), accepted (true), move (Queen-3 {Row-0 -> Row-3}).
DEBUG     LS step (0), time spent (6), score (-3), new best score (-3), accepted/selected move count (12/12), picked move (Queen-1 {Row-0 -> Row-3}).
...

(たとえばタブー探索で) 最終解のスコアを下げることができるため、 Solver は、探索パス全体で見つけた最適解を記憶します。毎回、その時の解は、前の回の最適解を上回るため、その時点の解の クローンが作成され、新しい最適解として参照されます。

タブー探索、焼きなまし法、レイトアクセプタンスを有効にするために、(Forager とともに) Acceptor が使用されます。Acceptor は、各 Move に対し、それが認められるかどうかを確認します。

設定行をいくつか変更するだけで、タブー探索から、焼きなまし法またはレイトアクセプタンスに簡単に切り替え、元に戻すこともできます。

独自の Acceptor を実装することはできますが、組み込まれているもので大概のニーズに沿うはずです。複数の Acceptor を組み合わせることもできます。

Forager は、認められた Move をすべて集め、次のステップとなる Move を選択します。通常は、認められた Move の中で一番スコアが高いものが選択されます。スコアが一番高いものが複数ある場合は、その中からランダムに選択します。ランダムに選択することがより良い結果につながります。

DEBUG     LS step (0), time spent (20), score (-3), new best score (-3), ...

山登り法は、選択したすべての Move を試し、スコアが一番高い解を生む最適な Move を選択します。最適な Move は、ステップ Move と呼ばれます。その新しい解から、再度選択したすべての Move を試し、最適な Move を選択し、それを繰り返します。最適な Move が複数ある場合は、そのうちの 1 つがランダムに選択されます。

クイーンが動いたら、再度動かせます。NP 完全問題では、プランニング変数に最適な最終値を予測することは不可能なので、これは利点となります。

山登り法は改善する Move を常に取得します。これは利点であるように思われますが、実際は利点ではありません。山登り法は局所最適条件で簡単に行き詰まる可能性があります。これは、すべての Move がスコアを下げる解にたどり着くと発生します。いずれの Move を選択しても、次のステップで元の解に戻り、無限ループとなります。

山登り法における改善 (タブー探索、焼きなまし法、レイトアクセプタンスなど) は、局所最適条件で行き詰まる問題に対応します。したがって、計画問題に局所最適条件がないことが明らかな場合を除いて、山登り法を使用することは推奨されません。

最も簡単な設定方法:

  <localSearch>
    <localSearchType>HILL_CLIMBING</localSearchType>
  </localSearch>

高度な設定方法:

  <localSearch>
    ...
    <acceptor>
      <acceptorType>HILL_CLIMBING</acceptorType>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

タブー探索は、山登り法と同じように機能しますが、局所最適条件で行き詰まらないようにタブーリストを維持します。タブーリストには、直近で使用され、今は使用が禁止されるオブジェクトが保持されています。タブーリストのオブジェクトに関連する Move は容認されません。タブーリストのオブジェクトは、Move に関するもの (プランニングエンティティー、計画値、Move、解など) になります。以下は、クイーン 4 個でエンティティータブーを持つ例で、このクイーンはタブーリストに入っています。

学術論文: Tabu Search - Part 1 and Part 2 by Fred Glover (1989 - 1990)

最も簡単な設定方法:

  <localSearch>
    <localSearchType>TABU_SEARCH</localSearchType>
  </localSearch>

タブー検索がステップを選択していくと、1 つまたは複数のタブーが作成されます。多くのステップでは、その Move がタブーに違反する場合は Move が許可されません。ステップ数がタブーのサイズになります。高度は設定方法は以下のようになります。

  <localSearch>
    ...
    <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
    </forager>
  </localSearch>

Planner には、タブーのタイプが複数あります。

タブーの種類を複数組み合わせると便利な場合があります。

    <acceptor>
      <entityTabuSize>7</entityTabuSize>
      <valueTabuSize>3</valueTabuSize>
    </acceptor>

タブーのサイズが小さすぎると、Solver は局所最適条件で行き詰まる可能性があります。逆に、タブーのサイズが大きすぎると、壁で跳ね返って役に立たない可能性があります。ベンチマーカー を使用して、設定を適切に調整します。

焼きなまし法は、ステップごとに数 Move だけを評価するため、すぐに次に進みます。標準的な実装では、最初に許可された Move が勝利ステップになります。Move は、スコアを減らさない場合は許可されます。スコアを減らした場合は、ランダムチェックを通過します。スコアを減らす Move がランダムチェックを通る可能性は、スコアのデクリメントの大きさと、フェーズが実行している時期 (度合い (temperature) として表現されます) に応じて減ります。

焼きなまし法は、スコアが一番高い Move を常に選択するわけではありません。また、1 ステップに対して Move を多数評価するわけでもありません。少なくても最初はそのように振舞います。改善しない Move が選択される可能性もありますが、これは、その Move のスコアと、終了 の時間勾配によります。最終的には、次第に山登り法になっていき、改善する Move だけを許可します。

まずは、simulatedAnnealingStartingTemperature を、1 つの Move が原因となる最大スコアデルタに設定します。ベンチマーカー で値を調整します。以下は、高度な設定になります。

  <localSearch>
    ...
    <acceptor>
      <simulatedAnnealingStartingTemperature>2hard/100soft</simulatedAnnealingStartingTemperature>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

焼きなまし法では、acceptedCountLimit は低くする必要があります。標準的なアルゴリズムでは、acceptedCountLimit を 1 にしますが、4 にした方がパフォーマンスが高いこともしばしばあります。

焼きなまし法は、タブーアクセプターと一緒に使用することができます。これにより、焼きなまし法が少し良くなります。タブー探索だけを使用する場合と比べて、タブーのサイズを小さくします。

  <localSearch>
    ...
    <acceptor>
      <simulatedAnnealingStartingTemperature>2hard/100soft</simulatedAnnealingStartingTemperature>
      <entityTabuSize>5</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

レイトアクセプタンス (LAHC (Late Acceptance Hill Climbing) とも呼ばれています) は、ステップごとに数 Move だけを評価します。スコアが減らない場合、もしくは最後のスコアと同じスコアになった (一定の前ステップでは勝利スコアだったもの) 場合は、Move が許可されます。

学術論文: The Late Acceptance Hill-Climbing Heuristic by Edmund K. Burke, Yuri Bykov (2012)

最も簡単な設定方法:

  <localSearch>
    <localSearchType>LATE_ACCEPTANCE</localSearchType>
  </localSearch>

レイトアクセプタンスは、何ステップも前に最適スコアだったものよりも高いスコアを持つ Move を許可します。このステップの数は lateAcceptanceSize です。以下は高度な設定になります。

  <localSearch>
    ...
    <acceptor>
      <lateAcceptanceSize>400</lateAcceptanceSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

レイトアクセプタンスでは、acceptedCountLimit を低くする必要があります。

レイトアクセプタンスは、タブアクセプターと一緒に使用することができます。これにより、レイトアクセプタンスが少し良くなります。タブー探索を使用する場合と比べて、タブーのサイズを小さくします。

  <localSearch>
    ...
    <acceptor>
      <lateAcceptanceSize>400</lateAcceptanceSize>
      <entityTabuSize>5</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

SCHC (Step Counting Hill Climbing) も、ステップごとに数 Move だけ評価します。ステップのスコアをしきい値として保持します。スコアが減らない場合、またはスコアがそのしきい値以上になる場合は、Move が許可されます。

学術論文: An initial study of a novel Step Counting Hill Climbing heuristic applied to timetabling problems by Yuri Bykov, Sanja Petrovic (2013)

SCHC (Step Counting Hill Climbing) は、しきい値スコアよりも高いスコアを持つ Move だけを許可します。(stepCountingHillClimbingSize で指定した) すべてのステップで、しきい値はステップのスコアに設定されます。

  <localSearch>
    ...
    <acceptor>
      <stepCountingHillClimbingSize>400</stepCountingHillClimbingSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

SCHC (Step Counting Hill Climbing) では、acceptedCountLimit を低くする必要があります。

SCHC (Step Counting Hill Climbing) は、レイトアクセプタンスセクション で説明しているように、タブーアクセプターと同時に使用することができます。

SO (Strategic Oscillation) は、特に タブー探索 と使用すると効果があるアドオンです。スコアが一番高い、許可された Move を選択するのではなく、別のメカニズムを使用します。改善される Move がある場合は、それを選択しますが、ない場合は、よりハードなスコアを壊すのが少ない Move よりは、よりソフトなスコアレベルを改善する Move を選択します。

以下の例では、タブー探索設定で finalistPodiumType を設定します。

  <localSearch>
    ...
    <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
      <finalistPodiumType>STRATEGIC_OSCILLATION</finalistPodiumType>
    </forager>
  </localSearch>

以下の finalistPodiumTypes がサポートされます。