第6章 最適化アルゴリズム

計画問題に対する可能解の数には圧倒されます。たとえば、以下のようになります。

なお、既知の宇宙に存在する原子の数の最小値は 10⁸⁰ です。計画問題が大きくなればなるほど、探索空間は急激に大きくなります。したがって、プランニングエンティティーまたは計画値を 1 つ追加すると、アルゴリズムの実行時間が非常に長くなります。

計算する可能解の数は、ドメインモデルの設定によって異なります。

可能解をすべて確認するアルゴリズム (分枝限定などの枝刈りでさえも) は、現実世界の計画問題を 1 つ実行するのに数億年かかる可能性があります。ここで必要なのは、限られた時間の中で自由に使える最適解を見つけることです。通常は、現実世界の制限を考えると、(International Timetabling Competition などの) 計画コンペティションでは、局所探索の各方法 (タブー探索、焼きなまし、レイトアクセプタンス など) が、能力を最大限に発揮します。

ビジネスでは最適解が必要ですが、必須条件は他にもあります。

Given these requirements, and despite the promises of some salesmen, it’s usually impossible for anyone or anything to find the optimal solution. Therefore, Planner focuses on finding the best solution in available time. In "realistic, independent competitions", it often comes out as the best reusable software.

NP 完全問題の性質は、最大の関心事をスケールします。データセットが小さいときの結果の品質が、データセットが大きくなったときの結果の品質を保証するものではありません。スケーリング問題は、のちにハードウェアを購入しても軽減されるものではありません。本番サイズのデータセットをできるだけ早めにテストするようにしてください。品質は、データセットが小さい時に評価しないでください (本番でも同規模のデータセットを使用する場合は除きます)。代わりに、本番サイズのデータセットを解決し、アルゴリズムを変えて長時間実行したときの結果と比較します (可能な場合は手動での計画の結果も比較します)。

Planner は、最適化アルゴリズム (メタヒューリスティクなど​) と、ルールエンジン (Drools Expert など) によるスコア計算を比較する、初めてのフレームワークです。この組み合わせは、以下の理由により、非常に効率的です。

Planner は、最適化アルゴリズムの 3 つのファミリー (しらみつぶし探索、構築ヒューリスティック、およびメタヒューリスティク) に対応しています。選択肢としては、(構築ヒューリスティックと組み合わせて初期化する) メタヒューリスティックが推奨されます。

各ファミリーのアルゴリズムには、複数の最適化アルゴリズムがあります。

メタヒューリスティクの詳細は、無料の書籍『Essentials of Metaheuristics』または『Clever Algorithms』を参照してください。

ユースケースによって、一番適した 最適化アルゴリズム設定は異なります。ただし、以下の一般的な方法に比べると非常に優れており、おそらくこれまで使用していたものよりもはるかに優れています。

設定と最適化コードには全く、もしくはほとんど関与しない簡単な設定から始めます。

次に、計画エンティティの難易度の比較を実装し、以下のように変更します。

次に、レイトアクセプタンスを追加します。

ここまでは簡単です。これ以上時間をかけても、時間に対して得られる結果は少なくなります。また、この時点で得られた結果は、十分優れています。

ただし、かかった時間に対して得られるものは少なくなりますが、さらに優れた結果を得ることはできます。ベンチマーカー を使用して、異なる設定 (タブー探索、焼きなまし法、レイトアクセプタンス など) をいくつか試します。

ベンチマーカー を使用して、このサイズパラメーターの値を改善します。

時間をかける価値がある場合は、さらに検証を行います。複数のアルゴリズムを組み合わせてみてください。

多くの最適化アルゴリズムには、結果とスケーラビリティーに影響するパラメーターがあります。Planner は、例外による設定を提供するため、すべての最適化アルゴリズムにはデフォルトのパラメーター値があります。これは、JVM のガベージコレクションパラメーターに非常に良く似ているため、多くの場合はこれを調整する必要はありませんが、上級者は調整してください。

デフォルトのパラメーターは、多くの場合 (特にプロトタイプに対して) 十分優れていますが、開発時間に余裕がある場合は、さらに良い結果を得るために、ベンチマーカー を使用して調整する価値は十分あります。それぞれの最適化アルゴリズムに関するドキュメントでは、調整を行う高度な設定も示します。

Solver は、複数の最適化アルゴリズムを順番に使用できます。最適化アルゴリズムは、それぞれ Solver の フェーズ として示されます。複数の フェーズ のソリューションを同時に導出することはありません。

以下の設定では、3 つのフェーズが順番に実行します。

<solver>
  ...
  <constructionHeuristic>
    ... <!-- First phase: First Fit Decreasing -->
  </constructionHeuristic>
  <localSearch>
    ... <!-- Second phase: Late Acceptance -->
  </localSearch>
  <localSearch>
    ... <!-- Third phase: Tabu Search -->
  </localSearch>
</solver>

Solver のフェーズは、Solver の設定で指定した順番で実行します。最初の フェーズ が終了すると次の フェーズ が開始し、それが終了すると次が開始します。最後の フェーズ が終了すると、Solver が終了します。通常、Solver は最初に構築ヒューリスティックを実行してから、メタヒューリスティックスを 1 つまたは複数実行します。

フェーズが設定されていない場合、Planner は、デフォルトで、構築ヒューリスティックフェーズ、局所探索法フェーズの順に行います。

一部のフェーズ (特に構築ヒューリスティック) は自動的に終了します。自動的に終了しないフェーズ (特にメタヒューリスティック) は、フェーズが終了するように設定している場合に限り終了します。

<solver>
  ...
  <termination><!-- Solver termination -->
    <secondsSpentLimit>90</secondsSpentLimit>
  </termination>
  <localSearch>
    <termination><!-- Phase termination -->
      <secondsSpentLimit>60</secondsSpentLimit><!-- Give the next phase a chance to run too, before the Solver terminates -->
    </termination>
    ...
  </localSearch>
  <localSearch>
    ...
  </localSearch>
</solver>

(最後の フェーズ が完了する前に) Solver が終了すると、現在のフェーズが終了し、後続のフェーズは実行されません。

Solver は、フェーズを繰り返し実行します。各フェーズは、通常、Move を振り返し実行します。したがって、4 つのスコープ (Solver、フェーズ、ステップ、Move) がネスト状態となります。

ログを設定して、各スコープのログメッセージを表示します。

すべてのフェーズが自動的に終了するとは限らず、また終了するまで待たずに終わらせる場合もあります。Solver は、事前設定により同期的に、または別のスレッドから非同期に終了できます。

特にメタヒューリスティックフェーズでは、問題解決を終了するタイミングを設定する必要があります。たとえば、時間が終了した時、完全スコアに到達した時、もしくはそのソリューションが使用される直前などです。使用できない唯一の設定は、最適解を見つけることです (ただし、最適解が分かっている場合は可能です)。なぜなら、通常、メタヒューリスティックアルゴリズムが、いつ最適解を見つけるか分からないからです。現実世界では、これは大きな問題にはなりません。なぜなら、最適解を見つけるのに何年もかかることがあり、それよりも早く終了したくなるためです。これが問題となるのは、利用可能な期間に最適解を見つけられる場合です。

同期終了については、Solver または フェーズ の 終了 で、停止するタイミングを設定します。自分で作成した 終了 を実装することもできますが、組み込みの実装でも大概のニーズを満たします。すべての 終了 で、(一部の最適化アルゴリズムに必要な) 時間勾配 を計算できます。これは、Solver または フェーズ で問題解決にかかると見積もられている時間に対する、実際にこれまでかかった時間の割合です。

  <termination>
    <millisecondsSpentLimit>500</millisecondsSpentLimit>
  </termination>

  <termination>
    <secondsSpentLimit>10</secondsSpentLimit>
  </termination>

  <termination>
    <minutesSpentLimit>5</minutesSpentLimit>
  </termination>

  <termination>
    <hoursSpentLimit>1</hoursSpentLimit>
  </termination>

  <termination>
    <daysSpentLimit>2</daysSpentLimit>
  </termination>

  <termination>
    <minutesSpentLimit>150</minutesSpentLimit>
  </termination>

  <termination>
    <hoursSpentLimit>2</hoursSpentLimit>
    <minutesSpentLimit>30</minutesSpentLimit>
  </termination>

  <localSearch>
    <termination>
      <unimprovedMillisecondsSpentLimit>500</unimprovedMillisecondsSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedSecondsSpentLimit>10</unimprovedSecondsSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedMinutesSpentLimit>5</unimprovedMinutesSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedHoursSpentLimit>1</unimprovedHoursSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedDaysSpentLimit>1</unimprovedDaysSpentLimit>
    </termination>
  </localSearch>

  <termination>
    <bestScoreLimit>0</bestScoreLimit>
  </termination>

  <termination>
    <bestScoreLimit>0hard/-5000soft</bestScoreLimit>
  </termination>

  <termination>
    <bestScoreLimit>0/0/0/-5000</bestScoreLimit>
  </termination>

  <termination>
    <bestScoreFeasible>true</bestScoreFeasible>
  </termination>

  <localSearch>
    <termination>
      <stepCountLimit>100</stepCountLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedStepCountLimit>100</unimprovedStepCountLimit>
    </termination>
  </localSearch>

  <termination>
    <calculateCountLimit>100000</calculateCountLimit>
  </termination>

  <termination>
    <terminationCompositionStyle>OR</terminationCompositionStyle>
    <stepCountLimit>100</stepCountLimit>
    <bestScoreLimit>0</bestScoreLimit>
  </termination>

  <termination>
    <terminationCompositionStyle>AND</terminationCompositionStyle>
    <unimprovedStepCountLimit>5</unimprovedStepCountLimit>
    <bestScoreLimit>-100</bestScoreLimit>
  </termination>

public interface Solver<S extends Solution> {

    // ...

    boolean terminateEarly();
    boolean isTerminateEarly();

}

最適解が新たに見つかるたびに、Solver は 、Solver のスレッドで BestSolutionChangedEvent を発生させます。

このようなイベントをリッスンするには、SolverEventListener を Solver に追加します。

public interface Solver<S extends Solution> {

    // ...

    void addEventListener(SolverEventListener<S> eventListener);
    void removeEventListener(SolverEventListener<S> eventListener);

}

BestSolutionChangedEvent の newBestSolution は初期化されていないか実行可能ではない場合があります。このような状況を検出するには、BestSolutionChangedEvent でこのメソッドを使用します。

    solver.addEventListener(new SolverEventListener<CloudBalance>() {
        public void bestSolutionChanged(BestSolutionChangedEvent<CloudBalance> event) {
            // Ignore invalid solutions
            if (event.isNewBestSolutionInitialized()
                    && event.getNewBestSolution().getScore().isFeasible()) {
                ...
            }
        }
    });

フェーズ全体を実装せずにカスタムの構築ヒューリスティックを実装する場合など、フェーズ間、または最初のフェーズの前に、カスタムの最適化アルゴリズムを実行して、ソリューション を初期化したり、簡単に達成できる目標を定めてより良いスコアをすぐに得たりするだけでなく、スコア計算を再利用する場合があります。

CustomPhaseCommand インターフェースは以下のようになります。

public interface CustomPhaseCommand {

    void applyCustomProperties(Map<String, String> customPropertyMap);

    void changeWorkingSolution(ScoreDirector scoreDirector);

}

たとえば、AbstractCustomPhaseCommand を拡張し、changeWorkingSolution() メソッドを実装します。

public class ToOriginalMachineSolutionInitializer extends AbstractCustomPhaseCommand {

    public void changeWorkingSolution(ScoreDirector scoreDirector) {
        MachineReassignment machineReassignment = (MachineReassignment) scoreDirector.getWorkingSolution();
        for (MrProcessAssignment processAssignment : machineReassignment.getProcessAssignmentList()) {
            scoreDirector.beforeVariableChanged(processAssignment, "machine");
            processAssignment.setMachine(processAssignment.getOriginalMachine());
            scoreDirector.afterVariableChanged(processAssignment, "machine");
            scoreDirector.triggerVariableListeners();
        }
    }

}

CustomPhaseCommand を以下のように設定します。

<solver>
  ...
  <customPhase>
    <customPhaseCommandClass>org.optaplanner.examples.machinereassignment.solver.solution.initializer.ToOriginalMachineSolutionInitializer</customPhaseCommandClass>
  </customPhase>
  ... <!-- Other phases -->
</solver>

複数の customPhaseCommandClass インスタンスが順番に実行するように設定します。

  <customPhase>
    <customPhaseCommandClass>...MyUninitializer</customPhaseCommandClass>
    <forceUpdateBestSolution>true</forceUpdateBestSolution>
  </customPhase>

Solver 設定で CustomPhaseCommand の値を動的に設定するには (ベンチマーカー でこのパラメーターを調整可能)、customProperties 要素を使用します。

  <customPhase>
    <customProperties>
      <mySelectionSize>5</mySelectionSize>
    </customProperties>
  </customPhase>

次に、applyCustomProperties() メソッドを上書きして、Solver を構築する時に解析して適用します。

public class MySolutionInitializer extends AbstractCustomPhaseCommand {

    private int mySelectionSize;

    public void applyCustomProperties(Map<String, String> customPropertyMap) {
        String mySelectionSizeString = customPropertyMap.get("mySelectionSize");
        if (mySelectionSizeString == null) {
            throw new IllegalArgumentException("A customProperty (mySelectionSize) is missing from the solver configuration.");
        }
        solverFactory = SolverFactory.createFromXmlResource(partitionSolverConfigResource);
        if (customPropertyMap.size() != 1) {
            throw new IllegalArgumentException("The customPropertyMap's size (" + customPropertyMap.size() + ") is not 1.");
        }
        mySelectionSize = Integer.parseInt(mySelectionSizeString);
    }

    ...
}