OptaPlanner examples その1

OptaPlanner

さて、OptaPlanner トレーニング（http://d.hatena.ne.jp/tokobayashi/20141027）をやったことで、自分のモデリング能力の無さを痛感しました。これを克服するにはまず既存のサンプルのモデルをよく読むところから始めねばならない。

N Queens


これはもうやった（http://d.hatena.ne.jp/tokobayashi/20141004）｡｡｡と思った？モデリングはちゃんと見てなかったー！というわけでここから始めます。

  • NQueens : @PlanningSolution
    • List getRowList() : @ValueRangeProvider(id = "rowRange")
    • List getQueenList() : @PlanningEntityCollectionProperty
  • Queen : @PlanningEntity
    • Row getRow() : @PlanningVariable(valueRangeProviderRefs = {"rowRange"}, strengthWeightFactoryClass = RowStrengthWeightFactory.class)
    • Column はただのフィールド

単純な値でも、クラスにした方が便利なのだろうか。

クイーンがエンティティで、行が変数。

NQueensGenerator.createNQueens() で初期 NQueens が作成される。RowとColumnもN個ずつインスタンス化する。ちょっと気持ち悪い。初期 Queen は Column だけ持っていて固定し、Row は最初 null。@ValueRangeProvider が選択可能な値を提供する。つまり、ConstructionHeuristic/LocalSearchのとき、NQueens.getRowList() の範囲から選んで、Queen.row にセットしていく。N Queens は ROW を変えるだけなので単純だ。といっても問題を与えられてすぐこのようにモデリングできるか？修行が必要です。

余談

TRACE [org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider]         Move index (0), score (-2), accepted (true), move (col0@row1 => row0).

のようにきれいなログが出るので、カスタムのMoveクラスを使っているのかな？と思ったけど、org.optaplanner.examples.nqueens.solver.move.RowChangeMove は使われていなかった。デフォルトで使う org.optaplanner.core.impl.heuristic.selector.move.generic.ChangeMove は

    public String toString() {
        return entity + " => " + toPlanningValue;
    }

なので、@PlanningEntity と @PlanningVariable の toString() を分かりやすくしておけばいい。

スコアリングルールは nQueensScoreRules.drl です。ルールをひとつ取り上げてみると、

rule "multipleQueensAscendingDiagonal"
    when
        Queen($id : id, row != null, $i : ascendingDiagonalIndex)
        Queen(id > $id, ascendingDiagonalIndex == $i)
    then
        scoreHolder.addConstraintMatch(kcontext, -1);
end

ascendingDiagonalIndex は column + row 、例えば Queen が 「3の4」にいれば、3+4=7 です。。。つまり、「2の5」や「6の1」でも同じになる｡｡｡そう、右上がりの斜めラインです。頭いいですね！ 

        public int getAscendingDiagonalIndex() {
            return (getColumnIndex() + getRowIndex());
        }

あと、「Queen(id > $id」のところもひと工夫で、重複評価を避けてパフォーマンスを上げています。

Cloud Balancing


Cloud Balancing のモデリングはここを見るべきですね。 http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/index.html#d0e653

  • CloudBalance : @PlanningSolution
    • List getComputerList() : @ValueRangeProvider(id = "computerRange")
    • List getProcessList() : @PlanningEntityCollectionProperty
  • CloudProcess : @PlanningEntity
    • CloudComputer getComputer() : @PlanningVariable(valueRangeProviderRefs = {"computerRange"}, strengthComparatorClass = CloudComputerStrengthComparator.class)

プロセスがエンティティで、コンピュータが変数。

やっぱどっちをエンティティにしてどっちを変数にするか、っていうのが最初の関門か。これは逆にしても出来るんじゃないか？やってみた｡｡｡

うはあ、@PlanningVariable が List になるときのやり方がわからねえ。後のサンプルに出て来てやり方を学べるはず。ここはスルーだ！

現時点の知識：1-N の関係の時は N側をエンティティにすると、@PlanningVariableを単一の変数にできるので簡単ってことかなあ

ルールをひとつ取り上げてみると

rule "requiredCpuPowerTotal"
    when
        $computer : CloudComputer($cpuPower : cpuPower)
        $requiredCpuPowerTotal : Number(intValue > $cpuPower) from accumulate(
            CloudProcess(
                computer == $computer,
                $requiredCpuPower : requiredCpuPower),
            sum($requiredCpuPower)
        )
    then
        scoreHolder.addHardConstraintMatch(kcontext, $cpuPower - $requiredCpuPowerTotal.intValue());
end

結構 from accumulate を使う感じです。慣れないと難しそうだけど、「合計チェック」系のルールの基本パターンだと思えばいいかな。