Geoffrey来日

OptaPlanner リード開発者の Geoffrey De Smet が来日して、色々話を聞けました。めっちゃいいひとです。

ドキュメント

バンバン改善してるから latest を見てね。 http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html

ドキュメント、スライドの絵はほとんど InkScape でSVG書いてるんだって。

サンプル

モデリングから細かいコーディングの説明まで、ほとんど optaplanner-examples のサンプルで説明してくれました。つまりそれだけ examples に良いネタが揃ってるってことです。私もブログの examples シリーズ引き続き頑張ります。

SwingのGUIだけど、ポチポチクリックしたら結構いじくれます。それで強制的に変なリソース割当をして、plannerがどうやって修正するかを見たりできます。

ビデオ

http://www.optaplanner.org/learn/video.html こちらもトピック毎にハンパなく取りそろえられています

アルゴリズム

Q「ベストなアルゴリズムを選ぶ方法は？」
A「ベンチマークを走らせるんだ」
そう、ベンチマーク走らせて比較すればよいので、あんまりアルゴリズムに悩む必要は無い感じ。むしろモデリングやスコアリングでパフォーマンス改善できるかどうかが肝のようだ。

設定

<environmentMode>FULL_ASSERT</environmentMode>

FULL_ASSERT モードでバリバリ設定ミスを検出できます。本番化（というか本格的なテスト）の前に FULL_ASSERT をやっておこう。

SolverConfig.xml はスキーマが無いが、要素/属性名が全て org.optaplanner.core.config 以下のパッケージ/クラスにマッピングされている（xstream使っている）。org.optaplanner.core.config をざっと読み込むと、書くのが楽になりそう。

OptaPlanner ソースの構成

これ見ればばっちり
http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#methodologyOverview

スコアリング

• Easy Java
  • 簡単、遅い
• Incremental Java
  • 難しい、速い
• Drools
  • やや簡単、速い

よって Drools がかなりおすすめ。

OptaPlannerは狂ったように fireAllRules() しまくるので、スコアリングルールの処理速度は重要。ログを活用してルールの実行速度を確認する。ルールが遅い時は、個別にルールのコメントアウトなどしてボトルネックを判別する。

モデリング

一番盛り上がったトピック。「こつ」があるよね？と、さんざん聞き倒した。

• まずモデルを正規化しよう
• 1-N のリレーションの N側が @PlanningEntity、1側が @PlanningVariable
• N-N の時は 1-N N-1 にする
• PlanningVariable が複数の時は「それは本当にPlanningVariableか(プランしたいのか)？単なるフィールドではないか？」を自問する
• 「何かに何かを割り当てる」とき、片方は PlanningVariable で、片方は固定値になるはず（Pigeon and Pigeon hole の問題だ、って言ってた）
• とはいえ、複数の PlanningVariable は可能。ただし search space を減らすためにも、PlanningVariable の削減は重要
  • 例えば N Queens では、Column は固定で Row だけが PlanningVariable だった。これはモデリング時に頭を働かせることで、問題を小さくできた、ということ
• 個人的には PlanningEntity は「何かと何かを結びつける Assignment」だ、という考え方で進めるとモデリングしやすいと思った。Cloud Balance の "Process" は Process と Computer を結びつける ProcessComputerAssignment だと考えていい。しかし、ここで ProcessComputerAssignment と Process は 1-1 の関係になるので、正規化すると同じクラスになっちゃった、ということ。
• 「PlanningEntity は List の PlanningVariable を持てるか？」って聞くと、「Valid なリクエストだ。ただし近い将来には予定されていない」だそうです。上記 1-N のモデリング定跡に真向から反するしね。
• Chained Variable
  • 巡回セールスマン問題(http://d.hatena.ne.jp/tokobayashi/20141227)で書いた、PlanningVariableGraphType.CHAINED のこと。とにかくここを読もう http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#chainedPlanningVariable
  • 「Routing系の問題って特殊だよね」って聞くと「そう。実装してないソフトウェアも多い。Routing系の問題を効率的にモデリングするためにChainedを導入した」とのこと。逆に言うと、Routing系の問題でなければ使わないと思う。
• Shadow Variable
  • http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#shadowVariable
  • こちらは Chained より、使用するケースが多そう。「他のVariableが変更された時に間接的に変化する値」にこのアノテーション（@InverseRelationShadowVariable or @CustomShadowVariable）をつける。これにより、「その値の計算速度が速くなる」＆「Droolsエンジンにこの値の変更を通知する」の2点が行われる。もうちょっと深く見ないと正確な説明ができないかな｡｡｡
• Overconstrained
  • @PlanningVariable(nullable = true) の場合を Overconstrained と呼ぶ。その PlanningVariable が null でもよい、solution として成立する、ということ。問題は OptaPlanner は null を 'uninitialized' の意味で使うので、nullable = true のケースでは、動的なプランニングの効率が悪くなる。逆に言うと、nullable = false のケースでは Construction Heuristic は、新規に追加された(nullの)Variable だけ評価する（これを Warm start と呼ぶ）。Chained では使えない。
  • ただ、Overconstrained という用語自体の意味は理解できてないっす http://en.wikipedia.org/wiki/Overconstrained_mechanism この wikipedia の Overconstrained_mechanism は関係ないな。制約問題における overconstrained は http://ktiml.mff.cuni.cz/~bartak/constraints/over_constr.html に書かれているように、単に「制約が厳しすぎて解が得られない」という理解でよさそう。なのでそのような問題の場合は null でもよいと。

Contribution

Contribution 大歓迎！ Pull Request 大歓迎！JIRA はこちら https://issues.jboss.org/browse/PLANNER/

僕のブログも載せてもらったよ http://www.optaplanner.org/learn/testimonialsAndCaseStudies.html