スコアリングルールを書く

OptaPlanner

http://d.hatena.ne.jp/tokobayashi/20150312 で、Cheap time scheduling には DRL が無いと書きましたが、それを追加するための JIRA がオープンされています。

Add Drools score rules for example CheapTime Scheduling https://issues.jboss.org/browse/PLANNER-275

で、やってみました。これがなかなか大変でした！

準備

親切にも準備/手順を JIRA に書いてくれています。

手順

  • cheapTimeScoreRules.drl を作成します
  • cheapTimeSolverConfig.xml で、DRLを使うようにします
  • cheapTimeScoreRules.drl に制約を記述します
  • CheapTimeApp を実行します
  • cheapTimeSolverConfig.xml で assertionScoreDirectorFactory を有効にし(CheapTimeEasyScoreCalculator)、environmentMode で FAST_ASSERT 及び FULL_ASSERT を設定して CheapTimeApp を実行します。Exception が出たら直します
  • environmentMode 無しで CheapTimeApp を5分間走らせ、average calculate count per second (ACC) を確認します（ログの最後に出る）。

実際にやってみると｡｡｡

  • まず新規にクラスを作成せずに全ての制約を書けるかがんばってみる -> 無理！
  • ルールの効果を確認するために小さいデータセットを作る(sample01.xml を編集)。効果の確認のため、ちょいちょい変更したりする（特定期間の powerPriceMicros をガッと上げるとか）。
  • 簡単にテストできるよう CheapTimeHelloWorld 作る。でもGUIもすごく役に立つ！
  • 期間単位で評価する必要があるので MachinePeriodPart 導入
  • MachinePeriodPart の生成のために Period 導入
  • Idle vs Spin には2段階計算が必要 -> IdleCost 導入
  • ShadowVariable を使うにはドメインモデルに修正が入るので、今回はやめた。代わりに insertLogical を使う。
  • from collect / accumulate はかなり使う
  • できたっぽいよ！
  • FULL_ASSERT すると｡｡｡Exception でた。 score corruption だって
    • assertionScoreDirectorFactory マジ素晴らしい。正しい CheapTimeEasyScoreCalculator と比較して、スコアが違うと怒ってくれる
    • 今回は CheapTimeEasyScoreCalculator が既にあったので比較できたけど、新規プロジェクトでも、先に EasyJava の ScoreCalculator を作っておくと、DRL や IncrementalJava の実装が楽になる。２人で並行して作って、相互チェックなんてのもアリだろう
    • エラーメッセージで、easyScoreCalculator は constraintMatchEnabled = false なので、analysis が出ないって言われるけど、analysis はそれほど重要ではないと思われる。 assertionScoreDirectorFactory を incrementalScoreCalculatorClass に差し替えれば analysis が出るけど、同じ粒度、名前で制約を実装していないと、比較ができない
  • で、その score corruption だけど、scoreHolder.addHardConstraintMatch()をルールのRHS内で複数回呼んだせいで発生していた。
rule "resourceCapacity"
    when
        $machinePeriodPart : MachinePeriodPart()
    then
        for (int resourceAvailable : $machinePeriodPart.getResourceAvailableList()) {
            if (resourceAvailable < 0) {
                scoreHolder.addHardConstraintMatch(kcontext, resourceAvailable);
            }
        }
end

計算してから、一回だけ呼ぶようにすればいい

        long resourceAvailableTotal = 0;
        for (int resourceAvailable : $machinePeriodPart.getResourceAvailableList()) {
            if (resourceAvailable < 0) {
                resourceAvailableTotal += resourceAvailable;
            }
        }
        scoreHolder.addHardConstraintMatch(kcontext, resourceAvailableTotal);

RHSで複数回 addHardConstraintMatch を呼ぶと、LongConstraintUndoListener.undo() のせいでスコアがおかしくなる。フォーラムで確認して、仕様ならドキュメント化したほうがよさそう。 https://issues.jboss.org/browse/PLANNER-284 も関連してるかな。

    public void addHardConstraintMatch(RuleContext kcontext, final long weight) {
        hardScore += weight;
        registerLongConstraintMatch(kcontext, 0, weight, new LongConstraintUndoListener() {
            public void undo() {
                hardScore -= weight;
            }
        });
    }
  • ACC は｡｡｡ sample01.xml でテスト｡｡｡ ぐはあ、遅え！ ACC=376
    • ちなみに CheapTimeEasyScoreCalculator : ACC = 5867
    • CheapTimeIncrementalScoreCalculator : ACC = 177142 (Unbelievable!)
  • さあ、ここからチューニング
    • まずは stepCountLimit=10000 のベンチマーク cheapTimeStepLimitBenchmarkConfig.xml を作る
    • ルールを全部コメントアウト
    • 一個ずつ有効にしながら、ACC の変化を見る
      • period : 5521
      • machinePeriodPart : 1916
      • maximumCapacity : 1376
      • calculateIdleCost : 996
      • startTimeLimitsFrom/startTimeLimitsTo : 1012
      • machinePowerCostActive : 793
      • machinePowerCostOffToActive/machinePowerCostIdleToActive : 750
      • firstBoot : 686
      • taskPowerCost : 427
      • startEarly : 414
    • うーん、machinePeriodPart が大きなボトルネックだけどこれはどうしようもなさそう。ひとつずつ丁寧に見ていくか｡｡｡
      • enum だった STATUS を boolean に変更 : 426
      • LHS の順序を調整 : 442
      • memberOf やめて < > で比較 : 468
      • maximumCapacity に if 入れて不必要な addHard 止める : 462
      • MachinePeriodPart のフィールドから taskAssignmentList を削除 : 458
      • taskPowerCost の計算は MachinePeriodPart ではなく Period で : 600 （影響大！）
      • resourceInShortTotal を MachinePeriodPart 内で計算 : 620
      • CheapTimeApp で 5分計測 -> 670
  • よし、まあまあ改善したぞ
  • JIRA 上に Geoffrey からコメントが。「あんまりチューニングしなくてもいいよ。読み易さ重視で」「大きいデータなら EasyJava に勝てるはず」
    • instance05.xml でテストすると easy = 844, drl = 703 だった。これより大きいデータなら逆転するだろう