tokobayashiの日記 このページをアンテナに追加 RSSフィード

2014-10-27 OptaPlanner トレーニング

[OptaPlanner]OptaPlanner トレーニング  [OptaPlanner]OptaPlanner トレーニングを含むブックマーク

http://www.optaplanner.org/learn/training.html から optaplanner-training-6.2.0.CR1-training-2.zipダウンロードし、instructions/training.html を開いてみよう。まだ Lab 201 までしか作られていないが、手を動かすとっかかりにはとてもよさそう。

詳しく書こうと思ったけど、よくできてるので興趣を削がないよう、概要だけ書くことにします

Lab 101 : No more than 4 processes per computer

CloudBalancing により、プロセスコンピューターに配分していますお客様からもうひとつ要望がありました。「同じコンピューターに、あんまりたくさんプロセスをのっけないでください」

課題:よし、「4つより多くのプロセスを、1つのコンピューターに割当てない」というhard制約を追加しよう。

僕の場合: モロに score trap の pitfall にひっかかりました。フフフ。

Lab 102 : No process should hog half the CPU power

お客様要望ひとつプロセスCPUの半分より多くを食わないようにして(CPUが少ないコンピューター例外)」

課題

1. ひとつプロセスCPUの半分より多くを食うことを「Hog」と呼ぶ。(半分ちょうどはOK)

-> 6 CPU 以下のコンピュータ例外とする

2. 新規hard制約「プロセスによるコンピューターの Hog は許さない」

3. Hog についてのロジックJava実装すること

-> 制約自体はDRLに実装する

僕の場合: 解けたけど、evalでやったせいで、 score trap を回避できてませんでした。無念。

Lab 103 : Distribute network bandwidth fairly

お客様要望コンピューターはもう買っちゃったんで、あるやつ使ってね。なので値段は気にしなくていいよ」「コンピュータネットワーク帯域は全部同じ」「ネットワークは均等に使うようにしてね」

課題

1. hard制約「requiredNetworkBandwidthTotal」を削除

2. soft制約「computerCost」を削除

3. 新規soft制約「コンピューター毎のネットワーク帯域は可能な限り均等にする」

僕の場合: ドキュメントの「Fairness score constraints」を読んでも、単純にsoft制約の点数の足し算にすることになかなか気づけなかった。結構慣れが必要ですなあ。

Lab 201 : Tennis friends

7つのチームがテニスコート試合をします。18週あって、1週につき、4チームがコートを使います。各チームには「行けない日」があります。できるだけ均等にコートを使わせてあげたいです。チームの対戦相手も均等にあたるようにします。。。詳しくは原文で読んだ方がいいでしょう。

で、この問題モデル化します。とても重要トレーニングですね。絶対に Tennis example のドキュメントコードを見ないように!

初めてのひとにはメチャメチャ難しいかもしれません。でもできるだけ自分でよく考えて、自分なりの回答を書いた上で、正解を見て、「ああー」となりましょう。ああー

トラックバック - http://d.hatena.ne.jp/tokobayashi/20141027

2014-10-24 REHV備忘録 このエントリーを含むブックマーク

トラックバック - http://d.hatena.ne.jp/tokobayashi/20141024

2014-10-18 OptaPlanner N queens を考える その3

[OptaPlanner]OptaPlanner N queens を考える その3  [OptaPlanner]OptaPlanner N queens を考える その3を含むブックマーク

中身を覗いてみよう編だ。

まず logback.xmlクラス名を出しておこう。

<pattern>%d [%t] %-5p [%c] %m%n</pattern>

するとキーポイントになるクラスが出てくるかなー。

TRACE [org.optaplanner.core.impl.domain.solution.descriptor.SolutionDescriptor]     Model annotations parsed for Solution NQueens:
TRACE [org.optaplanner.core.impl.domain.solution.descriptor.SolutionDescriptor]         Entity Queen:
TRACE [org.optaplanner.core.impl.domain.solution.descriptor.SolutionDescriptor]             Variable row (genuine)
INFO  [org.optaplanner.examples.nqueens.persistence.NQueensGenerator] NQueens 4 has 4 queens with a search space of 256.
INFO  [org.optaplanner.core.impl.solver.DefaultSolver] Solving started: time spent (55), best score (uninitialized/0), random (JDK with seed 0).
TRACE [org.optaplanner.core.impl.heuristic.selector.entity.decorator.SortingEntitySelector]     Created cachedEntityList with size (4) in entitySelector(Sorting(FromSolutionEntitySelector(Queen))).
TRACE [org.optaplanner.core.impl.heuristic.selector.entity.decorator.SortingEntitySelector]     Sorted cachedEntityList with size (4) in entitySelector(Sorting(FromSolutionEntitySelector(Queen))).
TRACE [org.optaplanner.core.impl.constructionheuristic.decider.ConstructionHeuristicDecider]         Move index (0), score (0), move (col2@null => row0).
DEBUG [org.optaplanner.core.impl.constructionheuristic.DefaultConstructionHeuristicPhase]     CH step (0), time spent (82), score (0), selected move count (1), picked move (col2@null => row0).
...
INFO  [org.optaplanner.core.impl.constructionheuristic.DefaultConstructionHeuristicPhase] Construction Heuristic phase (0) ended: step total (4), time spent (111), best score (-1).
TRACE [org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider]         Move index (0), score (-2), accepted (true), move (col0@row1 => row0).
TRACE [org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider]         Move index (1) not doable, ignoring move (col0@row1 => row1).
TRACE [org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider]         Move index (2), score (-2), accepted (true), move (col0@row1 => row2).
TRACE [org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider]         Move index (3), score (-2), accepted (true), move (col0@row1 => row3).
TRACE [org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider]         Move index (4), score (-2), accepted (true), move (col1@row2 => row0).
...
DEBUG [org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase]     LS step (0), time spent (128), score (-1),     best score (-1), accepted/selected move count (12/12), picked move (col1@row2 => row3).
...
INFO  [org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase] Local Search phase (1) ended: step total (2), time spent (138), best score (0).
INFO  [org.optaplanner.core.impl.solver.DefaultSolver] Solving ended: time spent (140), best score (0), average calculate count per second (278).

で、ログを出力しているところらへんにブレークポイントを張って、デバッガでうろうろする。

DefaultSolver

nqueensSolverConfig.xml を元に SolverFactory からボコっと作られるのが DefaultSolver。これが phaseList を保持し、各 Phase を実行する。

DefaultConstructionHeuristicPhase

ConstructionHeuristicPhase を管理する。solveメソッド内で、Step のループを行う。ループは entityPlacer から受け取る Placement 毎に 1 Step となる。

ConstructionHeuristicDecider

各 Step 内で、placement から供給される Move の中からつの Move を決定する。ConstructionHeuristicMoveScope が Moveラッパーとして役立っているようだ。

DefaultLocalSearchPhase

LocalSearchPhase を管理する。solveメソッド内で、Step のループを行う。ループは Phase が terminate されるまで続ける。

LocalSearchDecider

moveSelector, acceptor, forager を従えた重要プレイヤーだ。各 Step 内で、moveSelector から供給される Move の中からつの Move を決定する。processMoveメソッドで、acceptor がその Moveaccept するか判定する。LocalSearchMoveScope が Moveラッパーとして役立っているようだ。

PhaseLifecycleListener

多くのクラスが PhaseLifecycleListener を implements しており、phaseStarted/phaseEnded, stepStarted/stepEnded のライフサイクルに応じて、整然と処理を実行している。

DroolsScoreDirector

ConstructionHeuristicDecider.processMove() / LocalSearchDecider.processMove() -> DefaultSolverScope.calculateScore() -> DroolsScoreDirector.calculateScore() の流れで呼ばれ、DRL を元にスコア計算する。これは Drools じゃなくてもよい。例えば EasyScoreCalculator を implements し、スコア計算方法Java実装することもできる。N Queen には NQueensEasyScoreCalculator が既にあるので、nqueensSolverConfig.xml指定すれば使える。

トラックバック - http://d.hatena.ne.jp/tokobayashi/20141018

2014-10-07 OptaPlanner N queens を考える その2

[OptaPlanner]OptaPlanner N queens を考える その2  [OptaPlanner]OptaPlanner N queens を考える その2を含むブックマーク

アルゴリズム編だ!

その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>

http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#firstFitDecreasing

難しそうなところからセットしていく。だから真ん中の列のクイーンから置いていたんだね(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

です。

<changeMoveSelector> は普通に1個動かすだけ。N queens はこれでいいのかな。

http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#changeMoveSelector

<selectionOrder>ORIGINAL</selectionOrder> は、Move の順番はそのままでいじりません、と。

http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#selectionOrder

<entityTabuSize>5</entityTabuSize> は Tabu Search をやる、ということですね。(tabu は taboo の意のようです)

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)を防ぎます。

<forager> はデフォルトで、最もスコアの良いものを選びます。処理時間を短縮するため <acceptedCountLimit> を設定するケースが多いようです。

さて、やはり基本の 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 はスコアが悪くなる Moveaccept しないのです。(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." って書いてあるんで、使うべきではないのでしょう。

トラックバック - http://d.hatena.ne.jp/tokobayashi/20141007

2014-10-04 OptaPlanner N queens を考える その1

[OptaPlanner]OptaPlanner N queens を考える その1  [OptaPlanner]OptaPlanner N queens を考える その1を含むブックマーク

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

実行

ログ

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

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 を実行しま

さて、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 の総当たりで、よりよいものがあれば選ぶ。ベタだって?いやいや、これが速いんですよ!

トラックバック - http://d.hatena.ne.jp/tokobayashi/20141004