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

2015-01-17 OptaPlanner examples その5

[]OptaPlanner examples その5 OptaPlanner examples その5を含むブックマーク

Tennis club scheduling

OptaPlanner training (http://d.hatena.ne.jp/tokobayashi/20141027) をやってないひとはここを読む前に、先に training をやりましょう!

f:id:tokobayashi:20141229233114p:image

ここまでが「Basic examples」です。今回は日時、人、リソースを要素としたプランニングの基礎パターンと言えそうです。

各チームに公平にテニスコートを使ってもらい、またできるだけ対戦相手が偏らないようにする、という制約です。「公平さ」をどうルール表現するかの例題でもあります。

  • TennisSolution : @PlanningSolution
    • List<Team> getTeamList() : @ValueRangeProvider(id = "teamRange")
    • List<TeamAssignment> getTeamAssignmentList() : @PlanningEntityCollectionProperty
  • TeamAssignment : @PlanningEntity
    • Team getTeam() : @PlanningVariable(valueRangeProviderRefs = {"teamRange"})
    • Day day
    • int indexInDay

Team と Day が N-N の関係になるので、間に TeamAssignment を用意して @PlanningEntity にする、という基本パターン。一日に何チームがコートを使えるか、というのは indexInDay で表現している。複雑なケースだとここもクラス化されるはず。

「各チームが公平にテニスコートを使う」は「対戦相手が偏らないようにする」より重要な制約なので、ここでは HardMediumSoftScore という制約3段構えが来ました。Hard は絶対破ってはダメMedium は破ってもいいけど、Medium の点数は Soft の点数より絶対的に重視される。つまりいくら Soft が良くても、Medium の点数が下がれば採用されない。

「公平さ」を表現する「Fairness score」はここを読もう。 http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#fairnessScoreConstraints

まあ簡単に言えば、「自乗してマイナス」。

rule "fairAssignmentCountPerTeam"
    when
        $t : Team()
        $total : Number() from accumulate(
            $a : TeamAssignment(team == $t),
            count($a)
        )
    then
        scoreHolder.addMediumConstraintMatch(kcontext, - ($total.intValue() * $total.intValue()));
end
トラックバック - http://d.hatena.ne.jp/tokobayashi/20150117

2015-01-13 Geoffrey来日

[]Geoffrey来日 Geoffrey来日を含むブックマーク

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

ドキュメント

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

ドキュメントスライドの絵はほとんど InkScapeSVG書いてるんだって

サンプル

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

SwingGUIだけど、ポチポチクリックしたら結構いじくれます。それで強制的に変なリソース割当をして、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() しまくるので、スコアリングルールの処理速度は重要ログ活用してルールの実行速度を確認する。ルールが遅い時は、個別ルールコメントアウトなどしてボトルネック判別する。

モデリング

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

Contribution

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

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

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

2015-01-10 bash備忘録 このエントリーを含むブックマーク

CLASSPATH=
for name in `ls lib/*.jar`; do
  CLASSPATH="${CLASSPATH}:$name"
done

echo ${CLASSPATH}
トラックバック - http://d.hatena.ne.jp/tokobayashi/20150110

2015-01-07 発音 このエントリーを含むブックマーク

  • Jiri イジー
  • Jirka イルカ
  • Maciej マチェイ
トラックバック - http://d.hatena.ne.jp/tokobayashi/20150107

2014-12-29 OptaPlanner examples その4

[]OptaPlanner examples その4 OptaPlanner examples その4を含むブックマーク

Dinner party

f:id:tokobayashi:20141229233115p:image

パーティの席決めです。様々な条件を考慮して各テーブルに参加者を最適な組み合わせで配置する。。。そう、結婚式で一度だけ経験しましたよ。

このサンプルでは、男女が交互に並ぶ、隣同士が共通の趣味を持つ、1テーブルに職業を適正なバランスで配置する、という制約が与えられています。

  • DinnerParty : @PlanningSolution
    • List<Seat> getSeatList() : @ValueRangeProvider(id = "seatRange")
    • List<SeatDesignation> getSeatDesignationList() : @PlanningEntityCollectionProperty
  • SeatDesignation : @PlanningEntity
    • Seat getSeat() : @PlanningVariable(valueRangeProviderRefs = {"seatRange"})
    • Guest guest

SeatDesignation は Guest と Seat の組み合わせを保持し、「誰がどの席に座るか」を示すエンティティ比較的単純ですね。SeatDesignation は 1-1 で固定の Guest を保持する(variable ではない)ため、Guest を PlanningEntity にするようなモデリングもアリなはず。Gender、Job、JobType、Hobby、HobbyPractician は、Guest に関連するクラスモデリングの際に、比較的細かい粒度クラス化されている印象。おそらくクラスにした方がルールが書きやすいからだろう。

ルールの1例。

rule "twoSameJobTypePerTable"
    when
        $jobType : JobType()
        $table : Table()
        not (
            SeatDesignation(guestJobType == $jobType, seatTable == $table, $leftId : id, $firstJob : guestJob)
            and SeatDesignation(guestJobType == $jobType, seatTable == $table, id > $leftId,
                    differentKindIfNeeded($firstJob))
        )
    then
        scoreHolder.addConstraintMatch(kcontext, -100);
end

あれ?そういえばなんで JobType みたいなファクトが insert されるのだろう。どれがルールで使用するファクトだって明示してたっけ?

http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#planningProblemAndPlanningSolution

getProblemFacts() でした。ルール以外のスコアリング方法の時は必要無いそうです。

この example は DRL だけじゃなく、XSL(dinnerPartyExtraScoreRules.xls)にも追加の細かい席決めルール記述されています。「DemocratとRepublicanは隣にしてはダメ」とか。dinnerPartyExtraScoreRules.xls の読み込み指定は dinnerPartySolverConfig.xml に一行追加するだけ。

  <scoreDirectorFactory>
    <scoreDefinitionType>SIMPLE</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/dinnerparty/solver/dinnerPartyScoreRules.drl</scoreDrl>
    <scoreDrl>org/optaplanner/examples/dinnerparty/solver/dinnerPartyExtraScoreRules.xls</scoreDrl>
  </scoreDirectorFactory>
トラックバック - http://d.hatena.ne.jp/tokobayashi/20141229