Drools Planner でウィッシュリストから出産祝いを送る

注：このエントリは実際に行われた出産祝いとは何の関係もありません

Drools Planner は難しい問題を解いてくれるソフトウェアです。

• 1.1. What is Drools Planner?
  • http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html_single/index.html#d0e26

要はいくつかの制約条件を元に、最適解を導いてくれる、ということです。

examples を走らせればすぐに分かると思います。いろんなユースケースがありますね。

• 1.4. Download and run the examples
  • http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html_single/index.html#downloadAndRunTheExamples

次はやはり Quick start です。

• Chapter 2. Quick start
  • http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html_single/index.html#quickStart

ここでは examples のなかの、'Cloud Balance' が例になっています。クラウド上のコンピュータに対し、必要なプロセスをどのように割り当てると最も効率的か、というお題です。

• Hard制約 : プロセスが必要とするCPU/Memory/ネットワーク帯域の合計がコンピュータの上限を越えない
• Soft制約 : コンピュータのメンテナンス費を最小限にする

Planner がどのように使われるか、非常にわかりやすいユースケースですね。

examples はそれぞれ Swing と コマンドラインの Main クラスが用意されています。Eclipseで実行するには、以下の手順で。

• drools-planner-distribution-5.5.0.Final/examples/sources を Eclipse で import
• クラスパスに drools-planner-distribution-5.5.0.Final/binaries 以下のjarを通す
• CloudBalancingHelloWorld を実行。2分くらいかかる。
• 重要なファイルは
  • cloudBalancingSolverConfig.xml : Solver を生成する設定ファイル。アルゴリズムなど
  • CloudProcess.java : プランされる中心エンティティ
  • CloudComputer.java : こっちはあくまでCloudProcessの属性。プランの変数
  • CloudBalance.java : ソリューション。CloudProcessとCloudComputerの初期リソースを持ち、Solverに解決させる。解決後の BestSolution も表現できる
  • cloudBalancingScoreRules.drl : 制約条件及び、スコアリングの「ルール」
  • CloudBalancingHelloWorld.java : 上記を実行する Main クラス

さて、やっぱ自分で作らないとわかった気がしないですね。Cloud Balanceでも結構難しいので、もっと簡単なやつ。。。

• • • • • • • -

出産祝いを送るとき、Amazonのウィッシュリストを作ってもらってその中から選んだりするじゃないですか？でももはやそれらは本人が欲しいものなんだから、そこからさらにどれを送るか選別するって結構難しいですよね！そんで有志からきりのいい金額を集めておつりが出ないようにしたいですよね！

そんなあなたに Drools Planner。

• まずプランエンティティを定義
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/Item.java
    • @PlanningEntity をつける必要があります
• 次にプラン変数
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/Bucket.java
    • カートに入れるグループは cart = true で 入れないグループは cart = false。　このクラス無しにできないかなーって思ったけど、今のところ不明
• ソリューション
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/WishListSolution.java
    • だいたい CloudBalance のパクリです。シンプルな問題なので、SimpleScoreを使います
• difficultyComparatorClass
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/ItemDifficultyComparator.java
    • んー、アルゴリズムによってはいらないと思う。でかいものから隙間を埋めていく、っていう bin packing の考え方ですね。
• Mainクラス
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/WishListSolver.java
    • ウィッシュリストのアイテムをWishListSolutionにセットして、solve!
• Solverの設定ファイル
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/wishListSolverConfig.xml
    • 後半のアルゴリズムが肝なんだけどごめんなさい、全然分かっていません！今回は走らせるのがメインなので、アルゴリズムについてはまた後ほど。。。
• ルール
  • https://github.com/tkobayas/example-projects/blob/master/WishListSolver/src/org/example/wishListScoreRules.drl
    • 制約が無いのでスコアリングルールのみです。予算への乖離がすくなければスコアが上がります。予算(1000円×11人)がハードコードされているのはご愛嬌ということで。

Run! なんか必要以上に回っている気がするのは多分適切なアルゴリズム設定をしてないからです。ごめんなさい。ともあれ 5 で finish します。

さあでました。

============= Best Solution =============
おかゆこがま 200ml : price = 1015
ベビーソファ 専用腰ベルト入り : price = 3670
6重ガーゼケット トドラーケット : price = 6300
Total = 10985

これならおつりを配らなくてもいいですね。ありがとう Planner!

# Drools Planner の肝はアルゴリズム設定により効果的に（= 早さと精度のバランス）問題を解決できることにあります。この WishListSolver はそこらへん全く考慮してないので、本来の魅力の 10% も伝えてないと思います。後日に期待だ！