アルゴリズム編だ！
その1でやったように、optaplanner-examples の NQueensHelloWorld で実験します。
src/main/resources/org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml が設定の肝です。
Construction Heuristic
まずは初期状態を決めるための Construction Heuristic。FIRST_FIT_DECREASING が設定されています。
<constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
難しそうなところからセットしていく。だから真ん中の列のクイーンから置いていたんだね(DEBUGログを思い出そう)。「難しそう」をどう判断するのかは QueenDifficultyWeightFactory に実装している。
private static int calculateDistanceFromMiddle(int n, int columnIndex) {
int middle = n / 2;
int distanceFromMiddle = Math.abs(columnIndex - middle);
if ((n % 2 == 0) && (columnIndex < middle)) {
distanceFromMiddle--;
}
return distanceFromMiddle;
}で、@PlanningEntityである Queen が参照する。
@PlanningEntity(difficultyWeightFactoryClass = QueenDifficultyWeightFactory.class)
では FIRST_FIT に変えてみよう。
<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
こっちはDifficultyを考慮しないので
2014-10-07 22:24:14,330 [main] DEBUG CH step (0), time spent (82), score (0), selected move count (1), picked move (col0@null => row0). 2014-10-07 22:24:14,344 [main] DEBUG CH step (1), time spent (96), score (0), selected move count (3), picked move (col1@null => row2). 2014-10-07 22:24:14,352 [main] DEBUG CH step (2), time spent (104), score (0), selected move count (5), picked move (col2@null => row4). 2014-10-07 22:24:14,354 [main] DEBUG CH step (3), time spent (106), score (0), selected move count (2), picked move (col3@null => row1). 2014-10-07 22:24:14,357 [main] DEBUG CH step (4), time spent (109), score (0), selected move count (4), picked move (col4@null => row3). 2014-10-07 22:24:14,363 [main] DEBUG CH step (5), time spent (115), score (-1), selected move count (8), picked move (col5@null => row0). 2014-10-07 22:24:14,368 [main] DEBUG CH step (6), time spent (120), score (-2), selected move count (8), picked move (col6@null => row2). 2014-10-07 22:24:14,374 [main] DEBUG CH step (7), time spent (125), score (-3), selected move count (8), picked move (col7@null => row4).
col0から順番に入れていきますね。最終スコアは -3 なので結果は変わらなかった。でも、これを 128 queens でテストすると
FIRST_FIT -> score (-31)
FIRST_FIT_DECREASING -> score (-17)
でした。やっぱり FIRST_FIT_DECREASING は効果アリですね！
Local Search
次は初期状態から改善するための Local Search。こんな設定がされています。
<localSearch>
<changeMoveSelector>
<selectionOrder>ORIGINAL</selectionOrder>
</changeMoveSelector>
<acceptor>
<entityTabuSize>5</entityTabuSize>
</acceptor>
<forager>
</forager>
</localSearch>この設定の意味合いはこちら
http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#d0e9093
- MoveSelector で可能な Move をリストアップ
- acceptor で不要な Move を排除
- forager で最終的なひとつの Move を決定
です。
http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#changeMoveSelector
http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#selectionOrder
http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#tabuSearch
Tabu Search は Hill Climbing をベースにしながら、直近の操作（この場合 entity=Queen）を tabu list に入れ、一定期間（= TabuSize）それを使わないというアルゴリズムです。これにより、Hill Climbing でありがちな局所停滞（= local optima）を防ぎます。
さて、やはり基本の Hill Climbing に変えてみましょうか。
<acceptor>
<acceptorType>HILL_CLIMBING</acceptorType>
</acceptor>実行
2014-10-07 23:19:43,181 [main] DEBUG LS step (0), time spent (158), score (-2), new best score (-2), accepted/selected move count (18/56), picked move (col6@row1 => row7). 2014-10-07 23:19:43,206 [main] DEBUG LS step (1), time spent (183), score (-2), best score (-2), accepted/selected move count (11/56), picked move (col2@row4 => row7). 2014-10-07 23:19:43,233 [main] DEBUG LS step (2), time spent (209), score (-1), new best score (-1), accepted/selected move count (10/56), picked move (col0@row3 => row6). 2014-10-07 23:19:43,259 [main] DEBUG LS step (3), time spent (236), score (0), new best score (0), accepted/selected move count (2/56), picked move (col2@row7 => row5). 2014-10-07 23:19:43,259 [main] INFO Local Search phase (1) ended: step total (4), time spent (236), best score (0).
ふむ、問題なくクリアしましたね。ポイントはログの "accepted/selected move count (2/56)" で accepted が極端に少ないこと（= 2）。HILL_CLIMBING はスコアが悪くなる Move はaccept しないのです。（Tabu Search は許容する）
何回か N を変えて試したのですが、local optima （＝ スコアが一定で停滞する）を起こすことはできませんでした。まあ、" it's recommend to never use Hill Climbing, unless you're absolutely sure there are no local optima in your planning problem." って書いてあるんで、使うべきではないのでしょう。
