OptaPlannerによる組み合わせ最適化

第3回：EclipseでOptaPlannerを動かしてみる

〜環境構築とサンプルの実行方法の解説〜

株式会社オージス総研データアナリシス部
西腋清行

2015年3月12日

連載第二回目では、実際にOptaPlannerのサンプルコードを追いながらシフトスケジュールにおけるクラス設計とDRL設計のポイントを解説しました。連載第三回目の本記事では、Eclipseを使ってOptaPlannerを実行・デバッグ・ベンチマークする手順を解説したいと思います。

1 環境構築

まずはEclipseとDRL用のRule Editorを用意します。

1.1 Eclipseの用意

本記事ではEclipseはVer 4.4.1(Luna SR1a)の「Eclipse IDE for Java EE Developers」を利用しています。

1.2 Drools and jBPM toolsの用意

DRL用のRule EditorはDrools and jBPM toolsの中に含まれているため、Droolsのダウンロードサイト(https://www.drools.org/download/download.html)より「droolsjbpm-tools-distribution-6.1.0.Final.zip」をダウンロードし、ZIPファイルを解凍しておきます。

次にEclipseにDrools and jBPM toolsをインストールするため、[Help]-[Install New Software]をクリックします。

ダウンロードしたdroolsjbpm-tools-distribution-6.1.0.Final.zipを解凍すると「org.drools.updatesite」フォルダがありますので、InstallダイアログのAddボタンをクリックしLocalボタンより「org.drools.updatesite」フォルダを選択します。

「org.drools.updatesite」フォルダを選択しOKボタンをクリックすると、以下のようにDrools and jBPM toolsの内容が表示されますので、全てにチェックを入れNextボタンをクリックします。

図 6　 Drools and jBPM toolsを認識させたInstall New Softwareダイアログ

インストール内容の一覧が表示されるのでNextボタンをクリックします。

Drools and jBPM toolsのライセンスが表示されるのでライセンス内容を確認してから「I accept the terms of license agreement」を選択しFinishボタンをクリックします。

インストールが開始されます。

インストール中に未サインの警告が表示されます。OKボタンでインストールを継続できます。

インストールが終了すると以下ダイアログが表示されます。YesボタンをクリックしEclipseを再起動します。

1.3 サンプルコードの用意

サンプルコードを連載二回目の「hiroba-optaplanner-shift-schedule.zip」よりダウンロードし、ZIPファイルを解凍しておきます。

解凍したサンプルコードをEclipseにインポートするため、[File]-[Import]をクリックします。

サンプルコードはMavenを利用していますので「Existing Maven Projects」を選択しNextボタンをクリックします。

「hiroba-optaplanner-shift-schedule.zip」を解凍すると作成される「hiroba-optaplanner-shift-schedule」フォルダを任意の場所に移動し、そのフォルダをRoot Directoryとして選択します。
Root Directoryを入力しEnterキーを押すとpom.xmlが表示されますので、Projectにチェックを入れFinishボタンをクリックします。

1.4 プロジェクトの調整

インポートしたサンプルコードは一部コンパイルエラーが出る状態ですので、必要に応じて以下の調整をしてください。

ZIP作成時にsrcフォルダ下のtestフォルダとjavaフォルダが消えてしまっているので追加します。

Java Build PathのJavaバージョンがずれることがあるので修正します。
プロジェクトを右クリックし[Properties]をクリックします。

[Java Build Path]を選択し[Libraries]の[JRE System Library]をダブルクリックします。

[JavaSE-1.7]を選択しFinishボタンをクリックします。

2 サンプルアプリケーションの実行

サンプルコードを実行するにはjp.co.ogis_ri.optaplanner.jobSolutionのApp.javaを右クリックし[Run As]-[Java Application]をクリックします。

アプリケーションが開始されるとConsoleにログが表示されます。以下のようなログが出力され続ければ動作環境の構築は成功です。

3 OptaPlannerを実行させるコードの解説

連載第二回目で解説したシフトスケジュールのプロジェクトを実行する方法を解説します。

アプリケーションを開始しているAppクラスでは、まず初めに設定ファイルを基にSolverクラスを生成します。

App.java 48行目

// Build the Solver
SolverFactory solverFactory =  SolverFactory
        .createFromXmlResource("jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerConfig.xml");
Solver solver = solverFactory.buildSolver();

次に、実際に解きたいシフトスケジュールを表したJobSolutionを作成します。サンプルではCSVファイルよりデータを読み取り仕事（Job）と人（People）を作成し、JobSolutionを構築しています。

App.java 53行目

JobSolution unsolvedJobSolution = new JobSolutionGenerator()
        .createJobSolution();

この際、連載第二回目でも解説したようにJobとPeopleの間にJobAssignmentを入れていますが、これから組合せを解いていくのでJobAssignmentのPeopleプロパティはnullのままにしています。（JobSolutionGenerator.java 114～130行目を参照）

これは、全く初期の状態から組合せを探索する際はどの仕事に誰を割当てるかは未定であるためです。もし既に仮決めの割当がある場合や前回の結果がある場合などは、その情報を元にPeopleプロパティに対象となる人を設定しても構いません。そのように明示した場合は、その組合せ状態からより良い組合せの探索が開始されます。

解きたいと思っているシフトスケジュールの問題を表すJobSolutionが作成できれば、実際にSolverに与えて組合せの探索を行います。Solverのsolveメソッドは同期呼び出しになっており、かつ探索は設定ファイルで指定した条件が満たされるまで探索が続けられるので、探索が終わるまではメソッド呼び出しの戻りはありません。
よってWebアプリやクライアントアプリに組み込む際はUIが固まりますので、非同期呼び出しの仕組みを追加してください。

App.java 62行目

solver.solve(unsolvedJobSolution);

このsolveメソッドが呼び出されると探索が開始され、ログが出力されます。
4行目から出力されている「CH」はConstruction Heuristicの略で初期状態の構築を行っています。設定ファイルのconstructionHeuristicタグで指定した方法に則り、仕事への人の割当の初期状態を決めています。

INFO  o.d.c.k.b.impl.KieRepositoryImpl - KieModule was added:MemoryKieModule[ ReleaseId=org.default:artifact:1.0.0-SNAPSHOT]
DEBUG o.drools.core.impl.KnowledgeBaseImpl - Starting Engine in PHREAK mode
INFO  o.o.core.impl.solver.DefaultSolver - Solving started: time spent (296), best score (0hard/-55000000soft), random (MERSENNE_TWISTER with seed 0).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (0), time spent (374), score (0hard/-54800000soft), selected move count (51), picked move (Job0499Assignment => People0000).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (1), time spent (406), score (0hard/-54600000soft), selected move count (51), picked move (Job0498Assignment => People0001).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (2), time spent (453), score (0hard/-54400000soft), selected move count (51), picked move (Job0497Assignment => People0003).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (3), time spent (469), score (0hard/-54200000soft), selected move count (51), picked move (Job0496Assignment => People0002).

Construction Heuristicではある明示的なルールによって初期の割当を作成しますので、まだより良い組合せの「探索」は行われていません。以下の3行目で「Construction Heuristic phase (0) ended」と出るとConstruction Heuristicの終了で、この後からメタヒューリスティックな解法の特徴でもある「探索」が行われLocal Searchを表す「LS」と出力されるようになります。

DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (498), time spent (3445), score (0hard/-20347soft), selected move count (51), picked move (Job0001Assignment => People0018).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (499), time spent (3462), score (0hard/-20347soft), selected move count (51), picked move (Job0000Assignment => People0000).
INFO  o.o.c.i.c.DefaultConstructionHeuristicPhase - Construction Heuristic phase (0) ended: step total (500), time spent (3462), best score (0hard/-20347soft).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (0), time spent (3883), score (0hard/-20323soft), new best score (0hard/-20323soft), accepted/selected move count (599/835), picked move (Job0019Assignment <=> Job0001Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (1), time spent (3961), score (0hard/-525soft), new best score (0hard/-525soft), accepted/selected move count (190/253), picked move (Job0295Assignment => People0049).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (2), time spent (4117), score (0hard/-523soft), new best score (0hard/-523soft), accepted/selected move count (388/533), picked move (Job0064Assignment <=> Job0068Assignment).

探索が行われている際により良い組合せが発見できた際には「new best score」と出力され、より良い組合せが発見できなかった場合はnewが無くなり「best score」だけの出力になります。探索が進んでいくと徐々により良い組合せを発見しにくくなるのもメタヒューリスティックな解法の特徴ですので、徐々に「new」が出力される頻度は減っていきます。

DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (3), time spent (4242), score (0hard/-515soft), new best score (0hard/-515soft), accepted/selected move count (285/383), picked move (Job0222Assignment <=> Job0233Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (4), time spent (4273), score (0hard/-495soft), new best score (0hard/-495soft), accepted/selected move count (88/122), picked move (Job0064Assignment <=> Job0051Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (5), time spent (4678), score (0hard/-495soft),     best score (0hard/-495soft), accepted/selected move count (1000/1380), picked move (Job0114Assignment <=> Job0110Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (6), time spent (5038), score (0hard/-495soft),     best score (0hard/-495soft), accepted/selected move count (1000/1415), picked move (Job0013Assignment <=> Job0007Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (7), time spent (5132), score (0hard/-491soft), new best score (0hard/-491soft), accepted/selected move count (238/333), picked move (Job0099Assignment <=> Job0109Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (8), time spent (5257), score (0hard/-487soft), new best score (0hard/-487soft), accepted/selected move count (302/433), picked move (Job0127Assignment <=> Job0139Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (9), time spent (5272), score (0hard/-485soft), new best score (0hard/-485soft), accepted/selected move count (71/108), picked move (Job0082Assignment <=> Job0078Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (10), time spent (5491), score (0hard/-484soft), new best score (0hard/-484soft), accepted/selected move count (991/1400), picked move (Job0496Assignment <=> Job0301Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (11), time spent (5647), score (0hard/-464soft), new best score (0hard/-464soft), accepted/selected move count (725/1055), picked move (Job0390Assignment <=> Job0384Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (12), time spent (5662), score (0hard/-460soft), new best score (0hard/-460soft), accepted/selected move count (77/116), picked move (Job0150Assignment <=> Job0163Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (13), time spent (5849), score (0hard/-258soft), new best score (0hard/-258soft), accepted/selected move count (756/1096), picked move (Job0301Assignment <=> Job0499Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (14), time spent (6123), score (0hard/-258soft),     best score (0hard/-258soft), accepted/selected move count (1000/1458), picked move (Job0379Assignment <=> Job0376Assignment).

設定ファイルで指定した条件にて探索が終了すると、以下の3・4行目のログが出力されsolveメソッドの呼び出しが終了します。

DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (269), time spent (59949), score (0hard/-149soft), new best score (0hard/-149soft), accepted/selected move count (362/1459), picked move (Job0082Assignment <=> Job0089Assignment).
DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (270), time spent (60012), score (0hard/-149soft),     best score (0hard/-149soft), accepted/selected move count (62/372), picked move (Job0116Assignment <=> Job0119Assignment).
INFO  o.o.c.i.l.DefaultLocalSearchPhase - Local Search phase (1) ended: step total (271), time spent (60012), best score (0hard/-149soft).
INFO  o.o.core.impl.solver.DefaultSolver - Solving ended: time spent (60012), best score (0hard/-149soft), average calculate count per second (7039).

solveメソッドの呼び出しが終了した後、実際に解かれたシフトスケジュールの人の割当状態を取得するために、getBestSolutionメソッドにてJobSolutionを取得します。

App.java 63行目

Solution solvedSolution = solver.getBestSolution();

取得したJobSolutionに含まれるJobAssignmentのPeopleプロパティにはPeopleインスタンスが設定されており、探索中に発見できた最も良いシフトスケジュールの割当を表しています。App.java 66～95行目では得られたシフトスケジュールの割当をデバッグ用に出力しています。

4 デバッグ

Appクラスやシフトスケジュールの問題を表現するために存在するJobAssignmentクラス・Peopleクラスなどは、通常のJavaコードなのでEclipseのデバッグ機能でステップ実行が可能です。しかし、DRL（サンプルコードではoptaplannerJobSolutionScoreRules.drl）は通常のデバッグができません。
そこで、環境構築の章でインストールしたDrools and jBPM toolsに含まれる「Rule Editor」を利用し、DRLをデバッグする方法を解説します。

4.1 DRLへのブレークポイントの設定

Drools and jBPM toolsをインストールしている場合、DRLファイルを開くとデフォルトで「Rule Editor」にて開かれるようになっています。Rule Editorで開かれているかはファイル名の前に表示されている特有のアイコンを確認するか、エディタ下部のタブ「Text Editor」「Rate Tree」が表示されているかで判別できるかと思います。

このRule Editorを利用するとthen句の中にブレークポイントを設定し、デバッグ中に一時停止させることが可能です。ブレークポイントの設定は行数番号の左側をダブルクリックまたは「Ctrl + Shift + B」ショートカットでも可能です。

4.2 DroolsApplicationのデバッグ実行

Rule Editorで設定したブレークポイントにて一時停止させるには「Debug As」-「Drools Application」からデバッグ実行を行います。（「Java Application」でデバッグ実行するとDRLでは一時停止しません）

デバッグを開始すると、ペナルティ値の計算をするためにDRLが利用されるとブレークポイントの場所で一時停止します。

Javaコードのブレークポイントで一時停止した場合は「Variables」タブで変数を参照することができますが、DRLのデバッグ時にも同様にDRLで定義している変数を参照することができます。
DRLのデバッグ時の「Variables」タブに表示される変数は、基本的にthen句の中で利用されているものだけになります。下記のようにwhen句の中だけで利用されている変数（たとえば$day）は、「Variables」タブに表示されません。しかし、デバッグ時に確認したい場合がありますので、そのような場合は以下のようにSystem.out.printlnメソッド等を利用し変数を何かしらの方法で利用することで「Variables」タブに表示させられます。

図 27　「Variables」タブに認識させるために、$job1変数を利用してみる

しかしDRLのデバッグ時に注意してほしい点として、メタヒューリスティックな解法の動作の特徴があります。以前にも解説したように「少しずつ組合せを変更しペナルティ値チェックを繰り返しながら組合せを改善していく」「組合せの変更はランダムである」と言う２点です。
１つ目の理由によりDRLのデバッグ時は何度もブレークポイントで一時停止しますし、２つ目の理由で結果が毎回異なる場合もあり得ます。さらに、System.out.printlnメソッドなどでログを出力した場合は出力されるログ量が非常に多く、判別がつかなくなることもあり得ます。
ですので、DRLのブレークポイント・ステップ実行・ログ出力は、あまり現実的なものでは無い場合も多いかと思います。しかし意図しない動き、例えば条件的にはペナルティ値が追加されないはずなのにペナルティ値が加算されている、と言った机上デバッグでも解決できない場合の非常手段としては有効に使えると思います。実際にサンプルコードを作成している際にもSystem.out.printlnメソッドによるログ出力や「Variables」タブでの変数の確認で問題を解決したことがありました。

5 ベンチマーク

連載第二回にも書いたようにOptaPlannerには複数のアルゴリズムが実装されており、実際に利用する際にはそれぞれパラメータを設定する必要があります。しかし、実際に解こうとする組合せ最適化問題ではどのアルゴリズムが適しており、かつパラメータはどれぐらいの値が良いのか見定めるのは簡単ではありません。
そこでOptaPlannerでは複数のアルゴリズム・パラメータにより組合せ最適化問題を試行し、結果をレポート出力する機能があります。ですので、実際に解こうとする組合せ最適化問題に適したアルゴリズム・パラメータを決めるヒントを得るためにもベンチマークを利用してみてください。

5.1 ベンチマークの起動方法

ベンチマークを起動するには、以下のロジックにてPlannerBenchmarkクラスのインスタンスを作成しベンチマーカーを起動します。createFromXmlResourceメソッドでしている設定ファイルはベンチマーク用の設定ファイルになるため、実際に問題を解く際に利用した設定ファイルとは異なるので注意してください。

BenchmarkApp.java　31行目

private void execute() {
  PlannerBenchmarkFactory plannerBenchmarkFactory = PlannerBenchmarkFactory
    .createFromXmlResource("jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerBenchmarkConfig.xml");
  PlannerBenchmark plannerBenchmark = plannerBenchmarkFactory
    .buildPlannerBenchmark();
  plannerBenchmark.benchmark();
}

5.2 ベンチマーク用のデータ読み込みクラス

ベンチマークを動かすには実際の組合せ最適化問題を表すインスタンスが必要となりますので、組み合わせ最適化問題を表すSolutionクラスを作成するデータ読み込みクラスを作成する必要がります。このクラスはorg.optaplanner.persistence.common.api.domain.solution.SolutionFileIOインタフェースを実装することで自作することも可能です。（OptaPlannerの公式サンプルでは、デフォルトのXStreamSolutionFileIOが利用されておりXMLシリアル化された情報からSolutionクラスを構築しています）

サンプルでは最低限の機能だけを実現するためreadメソッドを実装し、前述のApp.java 53行目でも利用したメソッドにてJobSolutionクラスのインスタンスを作成しています。

public class BenchmarkSolutionFileIO implements SolutionFileIO {

  protected final transient Logger logger = LoggerFactory.getLogger(this.getClass());

  @Override
  public String getInputFileExtension() {
    return null;
  }

  @Override
  public String getOutputFileExtension() {
    return null;
  }

  @Override
  public Solution read(final File inputSolutionFile) {

    this.logger.debug("read");

    return new JobSolutionGenerator().createJobSolution();
  }

  @Override
  public void write(final Solution solution, final File outputSolutionFile) {
  }

}

5.3 ベンチマーク用設定ファイル

表 1　ベンチマークの基本設定
タグ名	概要
benchmarkDirectory	ベンチマークの結果とレポートを出力するディレクトリを設定します
parallelBenchmarkCount	ベンチマーク機能では複数のアルゴリズム・パラメータ、又は複数の問題（シフトスケジュールの場合は仕事数が小さいものと大きいものを2パターン用意するなど）を解くため、マルチスレッドで同時に複数の評価を行うことができます。数値を入れることで同時に実行されるスレッド数を明示的に指定することができます。また「Auto」にすると、実行環境のコア数を基に自動的にスレッド数を調整します。配布しているサンプルでは「3」と指定してあります。 CPUのコア数が少ない場合は「Auto」に修正してください。
warmUpSecondsSpentLimit	実際のベンチマークを開始する前に一定時間仮のベンチマークを実行することでJavaの動作を安定させる必要がります。その仮のベンチマークの実行時間（秒）を指定します HotSpot JITコンパイラの場合1回目の評価はどうしても不利になりがちであるためです

5.4 inheritedSolverBenchmarkタグ

inheritedSolverBenchmarkタグの中にはベンチマークの基本設定を記述します。ベンチマークは複数のアルゴリズム・パラメータの設定で試行しますが解くべき問題やクラスの設定などは全て同じになるので、その同じ設定についてinheritedSolverBenchmarkタグ内に記述します。

表 2　 problemBenchmarksタグ内の設定
タグ名	概要
solutionFileIOClass	ベンチマーク用のデータ読み込みクラスを指定します。
inputSolutionFile	ベンチマーク用のデータ読み込みクラスのreadメソッドの引数となるファイルを指定します。このinputSolutionFileタグは複数記述することが可能です。複数記述した場合はそれぞれについてreadメソッドが呼び出され、複数のSolutionクラスが作成されます。よって、複数の組合せ最適化問題（シフトスケジュール作成の場合、仕事が少ない場合と多き場合など）についても同時に試行することも可能です。
problemStatisticType	ベンチマークを実行した際に取得する情報を指定します。複数記述することで同時に複数の情報を取得することも可能です。

表 3　 problemStatisticTypeタグの設定値
値	概要
BEST_SCORE	ペナルティ値（スコア値）の時間推移を集計します
STEP_SCORE	ステップごとの実際のペナルティ値（スコア値）の時間推移を集計しますアルゴリズムによってはペナルティ値を一時的に悪化させるように組合せを変更し、最適化問題の「局所解」から脱出しようとします。よって、探索中のペナルティ値は必ずしもBest Scoreと同一にはなりません
CALCULATE_COUNT_PER_SECOND	時間当たりのペナルティ値（スコア値）の計算回数を集計します
BEST_SOLUTION_MUTATION	ペナルティ値（スコア値）の時間当たりの変化量を集計します
MOVE_COUNT_PER_STEP	時間当たりの組合せの変化量を集計します
MEMORY_USE	メモリの使用量の時間推移を集計します

inheritedSolverBenchmarkタグのsolverタグには、連載第二回目にて解説した設定を記述します。ベンチマークを行う場合、クラスの指定やペナルティ値の計算方法、終了条件、初期状態を作成するConstruction Heuristicの設定は同じものを使いまわす場合が多いと思いますので、サンプルでもこれらの設定をinheritedSolverBenchmarkタグのsolverタグに記述しています。

5.5 solverBenchmarkタグ

ベンチマークでは複数のアルゴリズム・パラメータを試すので、主に組合せを探索するLocal Searchの方法を変えます。solverBenchmarkはそのベンチマークの試行毎に実際の行うアルゴリズム・パラメータを指定します。

表 4　 solverBenchmarkタグ内の設定
タグ名	概要
name	試行毎に判別するための名前を設定します
solver	連載第二回目の「メタヒューリスティックな解法の指定」で解説したアルゴリズム・パラメータを指定します

実際にベンチマークを実行する際は、inheritedSolverBenchmarkタグ内のsolverタグに設定された値と、solverBenchmarkタグ内のsolverタグに設定された値を合体さえたものがSolverに渡されます。
サンプルではinheritedSolverBenchmarkタグ内のsolverタグは以下のようになっています。

<inheritedSolverBenchmark>

  <solver>
    <randomSeed>0</randomSeed>
    <randomType>MERSENNE_TWISTER</randomType>

    <solutionClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobSolution</solutionClass>
    <entityClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobAssignment</entityClass>
	
    <!-- Score configuration -->
    <scoreDirectorFactory>
      <scoreDefinitionType>HARD_SOFT_BIG_DECIMAL</scoreDefinitionType>
      <scoreDrl>jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerJobSolutionScoreRules.drl</scoreDrl>
    </scoreDirectorFactory>

    <!-- Optimization algorithms configuration -->
    <termination>
      <minutesSpentLimit>1</minutesSpentLimit>
    </termination>

    <constructionHeuristic>
      <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    </constructionHeuristic>
  </solver>
</inheritedSolverBenchmark>

また、solverBenchmarkは以下のように3つ設定されています。

<solverBenchmark>
  <name>simulatedAnnealing0</name>
  <solver>   
    <localSearch>
      <acceptor>
        <simulatedAnnealingStartingTemperature>1hard/1000000soft</simulatedAnnealingStartingTemperature>
      </acceptor>
      <forager>
        <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>
  </solver>
</solverBenchmark>

<solverBenchmark>
  <name>lateAcceptance0</name>
  <solver>   
    <localSearch>
      <acceptor>
        <lateAcceptanceSize>1000</lateAcceptanceSize>
      </acceptor>
      <forager>
        <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>
  </solver>
</solverBenchmark>

<solverBenchmark>
  <name>entityTabuSize0</name>
  <solver>   
    <localSearch>
      <acceptor>
        <entityTabuSize>10</entityTabuSize>
      </acceptor>
      <forager>
        <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>
  </solver>
</solverBenchmark>

よって、ベンチマークは以下の3つを試行する事となります（inputSolutionFileが複数設定されている場合は、各問題に対しそれぞれのベンチマークを実行しますので、ベンチマーク数×問題数の試行が行われます）

ベンチマーク1個目：焼きなまし法（パラメータ：1hard/1000000soft）

<inheritedSolverBenchmark>

  <solver>
    <randomSeed>0</randomSeed>
    <randomType>MERSENNE_TWISTER</randomType>

    <solutionClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobSolution</solutionClass>
    <entityClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobAssignment</entityClass>

    <!-- Score configuration -->
    <scoreDirectorFactory>
      <scoreDefinitionType>HARD_SOFT_BIG_DECIMAL</scoreDefinitionType>
      <scoreDrl>jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerJobSolutionScoreRules.drl</scoreDrl>
    </scoreDirectorFactory>

    <!-- Optimization algorithms configuration -->
    <termination>
      <minutesSpentLimit>1</minutesSpentLimit>
     </termination>

    <constructionHeuristic>
      <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    </constructionHeuristic>

    <localSearch>
      <acceptor>
        <simulatedAnnealingStartingTemperature>1hard/1000000soft</simulatedAnnealingStartingTemperature>
      </acceptor>
      <forager>
        <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>

  </solver>
</inheritedSolverBenchmark>

ベンチマーク2個目：Late Acceptance（パラメータ：1000）

<inheritedSolverBenchmark>

  <solver>
     <randomSeed>0</randomSeed>
     <randomType>MERSENNE_TWISTER</randomType>

    <solutionClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobSolution</solutionClass>
    <entityClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobAssignment</entityClass>

    <!-- Score configuration -->
    <scoreDirectorFactory>
      <scoreDefinitionType>HARD_SOFT_BIG_DECIMAL</scoreDefinitionType>
      <scoreDrl>jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerJobSolutionScoreRules.drl</scoreDrl>
    </scoreDirectorFactory>

    <!-- Optimization algorithms configuration -->
    <termination>
      <minutesSpentLimit>1</minutesSpentLimit>
    </termination>
    
    <constructionHeuristic>
       <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    </constructionHeuristic>

    <localSearch>
      <acceptor>
        <lateAcceptanceSize>1000</lateAcceptanceSize>
      </acceptor>
      <forager>
        <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>

  </solver>
</inheritedSolverBenchmark>

ベンチマーク3個目：禁断探索法（パラメータ：10）

<inheritedSolverBenchmark>

  <solver>
    <randomSeed>0</randomSeed>
    <randomType>MERSENNE_TWISTER</randomType>

    <solutionClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobSolution</solutionClass>
    <entityClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobAssignment</entityClass>

    <!-- Score configuration -->
    <scoreDirectorFactory>
      <scoreDefinitionType>HARD_SOFT_BIG_DECIMAL</scoreDefinitionType>
      <scoreDrl>jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerJobSolutionScoreRules.drl</scoreDrl>
    </scoreDirectorFactory>

    <!-- Optimization algorithms configuration -->
    <termination>
      <minutesSpentLimit>1</minutesSpentLimit>
    </termination>

    <constructionHeuristic>
      <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    </constructionHeuristic>

    <localSearch>
      <acceptor>
        <entityTabuSize>10</entityTabuSize>
      </acceptor>
      <forager>
        <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>
  </solver>
</inheritedSolverBenchmark>

5.6 サンプルのベンチークの実行

サンプルのベンチマークを実行するにはjp.co.ogis_ri.optaplanner.jobSolutionのBenchmarkApp.javaを右クリックし[Run As]-[Java Application]をクリックします。

ベンチマークを開始すると動作を安定させるためにwarmUpSecondsSpentLimitタグで指定した秒数の間だけベンチマークが仮実行されます。以下の3行目に出力されている「Warm up started」がその目印になっています。
このウォームアップの際は、solverBenchmarkで指定したベンチマークのうち最初の設定が利用され1スレッドだけで実行されています。

INFO  o.o.b.impl.PlannerBenchmarkRunner - Benchmarking started: solverBenchmarkResultList size (3), parallelBenchmarkCount (3).
INFO  o.o.b.impl.PlannerBenchmarkRunner - ================================================================================
INFO  o.o.b.impl.PlannerBenchmarkRunner - Warm up started
INFO  o.o.b.impl.PlannerBenchmarkRunner - ================================================================================
INFO  o.d.c.k.b.impl.KieRepositoryImpl - KieModule was added:MemoryKieModule[ ReleaseId=org.default:artifact:1.0.0-SNAPSHOT]
DEBUG o.drools.core.impl.KnowledgeBaseImpl - Starting Engine in PHREAK mode
DEBUG j.c.o.o.j.BenchmarkSolutionFileIO - read
INFO  o.o.core.impl.solver.DefaultSolver - Solving started: time spent (608), best score (0hard/-55000000soft), random (MERSENNE_TWISTER with seed 0).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (0), time spent (733), score (0hard/-54800000soft), selected move count (51), picked move (Job0499Assignment => People0000).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (1), time spent (764), score (0hard/-54600000soft), selected move count (51), picked move (Job0498Assignment => People0001).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (2), time spent (811), score (0hard/-54400000soft), selected move count (51), picked move (Job0497Assignment => People0003).
DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (3), time spent (827), score (0hard/-54200000soft), selected move count (51), picked move (Job0496Assignment => People0002).

ウォームアップが終了する際には「Warm up ended」が出力され、その直後にparallelBenchmarkCountタグで指定した個数のベンチマーク用スレッドが起動されます。

サンプルでのログ出力の設定では、ログレベルの前にスレッド名が出力されているため複数スレッドで同時にベンチマークが施行されているのが分かると思います。

[main] DEBUG o.o.c.i.l.DefaultLocalSearchPhase -     LS step (136), time spent (30010), score (0hard/-259soft),     best score (0hard/-259soft), accepted/selected move count (294/1024), picked move (Job0290Assignment <=> Job0292Assignment).
[main] INFO  o.o.c.i.l.DefaultLocalSearchPhase - Local Search phase (1) ended: step total (137), time spent (30010), best score (0hard/-259soft).
[main] INFO  o.o.core.impl.solver.DefaultSolver - Solving ended: time spent (30010), best score (0hard/-259soft), average calculate count per second (6490).
[main] INFO  o.o.b.impl.PlannerBenchmarkRunner - ================================================================================
[main] INFO  o.o.b.impl.PlannerBenchmarkRunner - Warm up ended
[main] INFO  o.o.b.impl.PlannerBenchmarkRunner - ================================================================================
[pool-2-thread-2] DEBUG j.c.o.o.j.BenchmarkSolutionFileIO - read
[pool-2-thread-3] DEBUG j.c.o.o.j.BenchmarkSolutionFileIO - read
[pool-2-thread-1] DEBUG j.c.o.o.j.BenchmarkSolutionFileIO - read
[pool-2-thread-3] INFO  o.d.c.k.b.impl.KieRepositoryImpl - KieModule was added:MemoryKieModule[ ReleaseId=org.default:artifact:1.0.0-SNAPSHOT]
[pool-2-thread-3] DEBUG o.drools.core.impl.KnowledgeBaseImpl - Starting Engine in PHREAK mode
[pool-2-thread-1] INFO  o.d.c.k.b.impl.KieRepositoryImpl - KieModule was added:MemoryKieModule[ ReleaseId=org.default:artifact:1.0.0-SNAPSHOT]
[pool-2-thread-1] DEBUG o.drools.core.impl.KnowledgeBaseImpl - Starting Engine in PHREAK mode
[pool-2-thread-3] INFO  o.o.core.impl.solver.DefaultSolver - Solving started: time spent (94), best score (0hard/-55000000soft), random (MERSENNE_TWISTER with seed 0).
[pool-2-thread-1] INFO  o.o.core.impl.solver.DefaultSolver - Solving started: time spent (47), best score (0hard/-55000000soft), random (MERSENNE_TWISTER with seed 0).
[pool-2-thread-3] DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (0), time spent (141), score (0hard/-54800000soft), selected move count (51), picked move (Job0499Assignment => People0000).
[pool-2-thread-3] DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (1), time spent (156), score (0hard/-54600000soft), selected move count (51), picked move (Job0498Assignment => People0001).
[pool-2-thread-1] DEBUG o.o.c.i.c.DefaultConstructionHeuristicPhase -     CH step (0), time spent (94), score (0hard/-54800000soft), selected move count (51), picked move (Job0499Assignment => People0000).

各スレッドのベンチマークの試行はsolverタグに記述された終了条件を満たすまで実行されます。よって条件によっては各スレッドでのベンチマークの終了タイミングが異なります。

また、solverBenchmarkタグがスレッドの数よりも多い場合、いずれかのスレッドでのベンチマークの試行が終わり次第未実行のベンチマークを逐次開始していき、全てのベンチマークが終了した時点でレポートが出力されます。

5.7 ベンチマークのレポート

出力されるベンチマークのレポートはbenchmarkDirectoryタグで指定したディレクトリに作成されるフォルダ（フォルダ名：ベンチマーク開始時間）に出力され、index.htmlを開くことで参照することができます。

5.8 ベンチマークレポートのResult summary

主に各ベンチマークの最終的なペナルティ値（スコア値）を比較できます。

「Score level 0」は、Hardの制約が最終的にどれくらい残っているかを表したものとなります。サンプルのシフトスケジュールの問題の場合は、Hardの制約は全て解決しているため「0」になります。
「Score level 1」は、Softの制約が最終的にどれくらい残っているかを表したものとなります。サンプルのシフトスケジュールの問題の場合は、負荷平均化を行う為のペナルティ値が残っているためベンチマーク毎にどれくらい残っているかを表しています。

また以下では「lateAcceptance0」と名付けたアルゴリズム・パラメータの設定が最も良い答えを出したことが分かります。

5.9 ベンチマークレポートのPerformance summary

主に各ベンチマークの1秒当たりのペナルティ値（スコア値）の比較回数を比較できます。
例えば、シフトスケジュールで仕事量やメンバー数が異なる問題をベンチマークした際、仕事量・メンバー数が増えた際に爆発的に計算量が増えてしまい1秒当たりのペナルティ値の比較が極端に悪化する場合があります。これはDRLでの制約の書き方に不適切な部分があるためと思われますが、このような場合に実運用へ展開すると実用的な計算速度が出なくなる不具合が発生しかねません。
よって、実運用の前に問題の規模（シフトスケジュールでは仕事量やメンバー人数）によって極端に性能が悪化しないかも確認しておくと良いと思います。

グラフの横軸は問題規模となっています。サンプルでは一つの問題で複数のアルゴリズムを比較したベンチマークなので、横軸への広がりが無いものとなっています。

5.10 ベンチマークレポートのProblem benchmarks

problemStatisticTypeタグで指定した情報の時間推移のグラフを表示します。
BEST_SCOREとSTEP_SCOREについては「Score level 0」「Score level 1」が表示され、Hard制約とSoft制約のそれぞれでペナルティ値（スコア値）が経過時間と共にどのように減少したかを見ることができます。

ちなみにWindows環境にてサンプルのpom.xmlにて指定しているOptaPlanner 6.1.0を利用すると、Problem benchmarksのimgタグの指定に問題があるようで画像が表示されない不具合があります。適宜imgタグのsrc属性を修正してください。次バージョンで修正される予定になっています。

まとめ

連載三回にてメタヒューリスティックな解法とOptaPlannerでのシフトスケジューリング作成方法を解説しました。皆さんもシフトスケジューリング作成など組合せ最適化を解く場面で活用されてみてはいかがでしょうか。
また、OptaPlannerではシフトスケジューリング以外の組合せ最適化を解くこともできます。次回は、組合せ最適化の一つで順序の最適化を行う配送・集荷経路作成サンプルを紹介したいと思います。

『Opta Planner』は、Redhat JBoss BRMS『Business Resource Planner』のコミュニティ版です