OptaPlanner N queens を考える その1

OptaPlanner

OptaPlanner がどのように動いているか、サンプル「N queens」を題材に考えます。チェスのクイーンをN個、お互いがぶつからないように配置する問題です。

実行

  • http://www.optaplanner.org/ から OptaPlanner 6.1.0.Final をダウンロード
  • unzip
  • examples/runExamples.sh で実行
  • "N queens" をクリック
  • 左の '8queens.xml' をクリック（8x8の盤上に8個のクイーンを置く）
  • 右上の 'Solve' をクリック
    • 解けた！

ログ

さて、標準出力のほうにはこんなログが出ています。

2014-10-04 21:16:26,849 [SwingWorker-pool-3-thread-6] INFO  Solving started: time spent (1), best score (uninitialized/0), random (JDK with seed 0).
2014-10-04 21:16:26,850 [SwingWorker-pool-3-thread-6] DEBUG     CH step (0), time spent (2), score (0), selected move count (1), picked move (col4@null => row0).
2014-10-04 21:16:26,850 [SwingWorker-pool-3-thread-6] DEBUG     CH step (1), time spent (2), score (0), selected move count (3), picked move (col3@null => row2).
2014-10-04 21:16:26,851 [SwingWorker-pool-3-thread-6] DEBUG     CH step (2), time spent (3), score (0), selected move count (4), picked move (col5@null => row3).
2014-10-04 21:16:26,851 [SwingWorker-pool-3-thread-6] DEBUG     CH step (3), time spent (3), score (0), selected move count (5), picked move (col2@null => row4).
2014-10-04 21:16:26,851 [SwingWorker-pool-3-thread-6] DEBUG     CH step (4), time spent (3), score (0), selected move count (2), picked move (col6@null => row1).
2014-10-04 21:16:26,851 [SwingWorker-pool-3-thread-6] DEBUG     CH step (5), time spent (3), score (-1), selected move count (8), picked move (col1@null => row1).
2014-10-04 21:16:26,852 [SwingWorker-pool-3-thread-6] DEBUG     CH step (6), time spent (4), score (-2), selected move count (8), picked move (col7@null => row4).
2014-10-04 21:16:26,852 [SwingWorker-pool-3-thread-6] DEBUG     CH step (7), time spent (4), score (-3), selected move count (8), picked move (col0@null => row3).
2014-10-04 21:16:26,852 [SwingWorker-pool-3-thread-6] INFO  Construction Heuristic phase (0) ended: step total (8), time spent (4), best score (-3).
2014-10-04 21:16:26,855 [SwingWorker-pool-3-thread-6] DEBUG     LS step (0), time spent (7), score (-2), new best score (-2), accepted/selected move count (56/56), picked move (col6@row1 => row7).
2014-10-04 21:16:26,857 [SwingWorker-pool-3-thread-6] DEBUG     LS step (1), time spent (9), score (-2),     best score (-2), accepted/selected move count (49/56), picked move (col2@row4 => row7).
2014-10-04 21:16:26,859 [SwingWorker-pool-3-thread-6] DEBUG     LS step (2), time spent (11), score (-1), new best score (-1), accepted/selected move count (42/56), picked move (col0@row3 => row6).
2014-10-04 21:16:26,860 [SwingWorker-pool-3-thread-6] DEBUG     LS step (3), time spent (12), score (0), new best score (0), accepted/selected move count (36/56), picked move (col2@row7 => row5).
2014-10-04 21:16:26,860 [SwingWorker-pool-3-thread-6] INFO  Local Search phase (1) ended: step total (4), time spent (12), best score (0).
2014-10-04 21:16:26,862 [SwingWorker-pool-3-thread-6] INFO  Solving ended: time spent (14), best score (0), average calculate count per second (19000).

INFOレベルは Solver 自体の情報と、Phase を表示
DEBUGレベルは Step を表示
TRACEレベルは Move を表示

http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/#logging
http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/#scopeOverview

これらのログで、どのように最適化のアルゴリズムを実行しているかが追えます。

  • まず Construction Heuristic Phase。とりあえずクイーンを8つ置いて初期状態とします。
    • CH step の1回が、クイーンを1つ置くことを表します。「picked move (col4@null => row0)」 というのは col4 のクイーン（配置未定）をrow0に置いた、ということですね
    • 8個置いた時点で 「best score (-3)」でした。3ヶ所、クイーンがぶつかっている状態です。
  • 次にこの状態を改善するために Local Search Phase を実行します
    • LS step の1回が、クイーンを1つ動かすことを表します。「picked move (col6@row1 => row7)」のように動かすことで、「new best score (-2)」とスコアが改善しました。
    • LS step (3) で最終的にスコア0になりました。解決です。

さて、TRACEログも出してみよう。

examples/binaries/optaplanner-examples-6.1.0.Final.jar の中身を編集してもいいけど、今後は Eclipse から直接実行します。

  • [Import] -> [Existing Maven Project] で examples/sources をインポート
  • org.optaplanner.examples.nqueens.app.NQueensHelloWorld を実行

これはCUIなので軽くテストできます。続いて src/main/resources/logback.xml を編集

<logger name="org.optaplanner" level="trace"/>

これで再度NQueensHelloWorldを実行すると。各 Step において検討された Move が表示されます。Construction Heuristic では｡｡｡

2014-10-04 22:01:53,623 [main] TRACE         Move index (0), score (-1), move (col3@null => row0).
2014-10-04 22:01:53,627 [main] TRACE         Move index (1), score (-1), move (col3@null => row1).
2014-10-04 22:01:53,628 [main] TRACE         Move index (2), score (0), move (col3@null => row2).
2014-10-04 22:01:53,628 [main] DEBUG     CH step (1), time spent (100), score (0), selected move count (3), picked move (col3@null => row2).

row0 から総当たりして、現状維持の配置が見つかれば中断して採用、そうでなければ最善のものを採用。結構ベタですね。

Local Search では｡｡｡

...
2014-10-04 22:43:13,717 [main] TRACE         Move index (58), score (-4), accepted (true), move (col7@row4 => row2).
2014-10-04 22:43:13,718 [main] TRACE         Move index (59), score (-5), accepted (true), move (col7@row4 => row3).
2014-10-04 22:43:13,718 [main] TRACE         Move index (60) not doable, ignoring move (col7@row4 => row4).
2014-10-04 22:43:13,718 [main] TRACE         Move index (61), score (-3), accepted (true), move (col7@row4 => row5).
2014-10-04 22:43:13,719 [main] TRACE         Move index (62), score (-3), accepted (true), move (col7@row4 => row6).
2014-10-04 22:43:13,719 [main] TRACE         Move index (63), score (-3), accepted (true), move (col7@row4 => row7).
2014-10-04 22:43:13,720 [main] DEBUG     LS step (0), time spent (176), score (-2), new best score (-2), accepted/selected move count (56/56), picked move (col6@row1 => row7).

各 Step につき、 8x8=64 の総当たりで、よりよいものがあれば選ぶ。ベタだって？いやいや、これが速いんですよ！