第5章 スコア計算

5.1. スコアに関する用語

5.1.1. スコアについて

初期化された ソリューション には常にスコアがあります。スコアは、2 つのソリューションを客観的に比較する方法の 1 つです。スコアの高いソリューションのほうが優れています。Solver は、考えられるソリューションの中でスコア が一番高い ソリューション を見つけることを目的とします。最善解 は、問題解決時に Solver が特定した、スコア が一番高い ソリューション のことで、これが 最適解 となる場合もあります。

Planner は、どの ソリューション が特定のビジネスに適しているかを自動的に把握することはできないため、ビジネスのニーズに合わせて、特定の ソリューション のスコアを計算する方法を指定する必要があります。重要なビジネス制約を実装できない場合や、実装するのを忘れた場合、このソリューションはおそらく役に立ちません。

optimalWithIncompleteConstraints

以下のスコア手法を使用すると、Planner での制約を非常に柔軟に定義できます。

  • スコアの符号 (正または負): 制約型を最大化または最小化します。
  • スコアの重みづけ: 制約型にコスト/利益を追加します。
  • スコアレベル (ハード、ソフトなど): 制約型のグループに優先順位を付けます。
  • パレートスコアリング

5.1.2. スコア制約の符号 (正または負)

すべてのスコア手法は、制約をベースにしています。制約は (ソリューションの中でりんごの収穫を最大化するなど) 単純なパターンの場合も、より複雑なパターンの場合もあります。正の制約は、最大化させる制約のことで、負の制約は最小化させる制約を指します。

positiveAndNegativeConstraints

上の画像では、制約が正でも負でも、常にスコアが最高となる、最適解について例示しています。

計画問題の多くには、負の制約のみが含まれるので、スコアは負になります。このような場合には、完全スコアを 0 とし、違反した負の制約の重みを合計した値がスコアになります。たとえば、「4 個のクィーン」のソリューションも、相互に攻撃可能なクィーンペアの数を負にした値となります。

同じスコアレベルでも、負および正の制約を組み合わせることができます。

注記

ビジネスがすべてのスコア制約を事前に把握していると思い込まないでください。最初のリリース以降でも、スコア制約が追加、変更されることを想定してください。

特定のプランニングエンティティーセットで、(負制約の違反や、正制約の遵守により) 制約が有効になった場合のことを 制約の一致 と呼びます。

5.1.3. スコア制約の重みづけ

スコア制約の重要性は、すべて均等ではありません。ある制約 1 件に違反する場合と、別の制約を複数回違反する場合に、違反の程度が同じだとすれば、この 2 つの制約における重みは異なることになります (ただし、スコアレベルは同じです)。たとえば、配送経路問題では、「不満があるドライバー」制約の一致数 1 件と、「ガソリンタンクの使用量」制約の一致数 2 件の重みが同じになるように設定できます。

scoreWeighting

スコアの重みは、すべてに値段を付けられるユースケースで頻繁に使用されます。このような場合、正制約は収益を最大化し、負制約は経費を最小化するため、両方をあわせて利益を最大化します。スコアの重みづけは、社会的な 公平 を作り出す際にもよく使用されます。たとえば、「看護師」の例では、通常の日ではなく、大晦日に公休日を希望する場合、重みが大きくなります。

他の制約との関連を考慮して選択していくため、分析の面から考えると、制約に適切な重みを課すのは困難になる可能性があります。ただし、重みが正確ではないときの損害の大きさは、アルゴリズムが優れていないのに比べると少なくなります。

scoreTradeoffInPerspective

使用するプランニングエンティティーをベースに、制約一致の重みを動的に変更させることもできます。たとえば、「クラウドのバランス」の例でにおける、有効な コンピューター に対するソフト制約一致の重みは、その コンピューターコスト になります (コンピューターごとに異なります)。

注記

さらに、InstitutionParametrization クラスを使用した「試験の時間割」の例で示されているように、エンドユーザーがユーザーインターフェースで制約の重みを再調整できるようにすると便利になることが多いです。

5.1.4. スコア制約レベル (ハード、ソフトなど)

スコア制約を何回違反しても、そのスコア制約のスコアが他の制約よりも高くなる場合があります。このような場合には、スコア制約のレベルが異なります。たとえば、看護師は、(物理的に制約があり) 2 つのシフトを同時に勤務できないため、これはすべての満足度制約よりも勝ります。

多くのユースケースでは、ハードとソフトの 2 つのスコアレベルのみを使用します。2 つのスコアは、辞書式に比較されます。つまり、最初のスコアレベルが先に比較され、そのスコアレベルが異なると、他のスコアレベルは無視されます。たとえば、「ハード制約 0 件 + ソフト制約 100 万件」違反したスコアの方が、「ハード制約を 1 件 + ソフト制約を 0 件」違反したスコアよりも高くなります。

scoreLevels

「ハードレベルとソフトレベル」など、制約スコアレベルが 2 つ (以上) 存在する場合、そのスコアはハード制約に違反していないときにのみ評価されます。

注記

デフォルトでは、Planner は、常に全プランニング変数に計画値を割り当てます。実現可能解がないと、最善解には到達しません。代わりに、プランニングエンティティーの一部を割り当てないようにするには、過制約の計画 を適用します。

制約ごとに、スコアレベル、スコアの重み、スコア符号を選択する必要があります。たとえば、-1soft の場合、スコアレベルは soft、重みは 1、符号は負になります。実際のビジネスで別のスコアレベルを希望する場合は、制約の重みを大きくしないでください。score folding (スコアフォールディング) と呼ばれるハックに違反します。

scoreFoldingIsBroken
注記

ビジネスの条件によりハード制約には違反できないため、すべての重みを同じにする (つまり、重みを重要視しない) 場合も注意は必要です。固有のデータセットに実行可能解が存在しなくても、少なくとも実現不可解を使用して、ビジネスに欠けているビジネスリソースがいくつあるかを推測することはできるため、重みがすべて同じというのは正しくありません。たとえば、「クラウドのバランス」サンプルにおける「新たに購入すべきコンピューターの数」などが例としてあげられます。

さらに、スコアトラップ が作成される可能性が高くなります。たとえば、「クラウドのバランス」において、コンピュータープロセス を処理する際、CPU が 7 基分少ない場合は、CPU が 1 基分のみ足りないときの 7 倍の重みを課す必要があります。

スコアレベルは、3 つ以上サポートされます。たとえば、ある企業が、収益は従業員の満足度より重要である (あるいはその反対) と決定しても、どちらも、物理的な実際の制約よりも優先されることはないようにします。

注記

(Planner は多くのスコアレベルを処理できますが) 公平さまたは負荷分散をモデル化するのに、スコアレベルを多数使用する必要はありません

5.1.5. パレートスコアリング (多目的最適化スコアリング)

(多目的最適化としても知られている) パレート最適化のユースケースは、他と比べてあまり一般的ではありません。パレートスコアリングでは、スコア制約のスコアレベルは同じですが、相互に重みが課されているわけではありません。2 つのスコアを比較する際に、各スコア制約が個別に比較され、最も優勢なスコア制約を持つスコアが勝ちます。パレートスコアリングは、スコアレベルやスコア制約の重みと組み合わせることができます。

正の制約を使用する例を見てみましょう。ここでは、りんごとオレンジを最も多く取得することを目的にします。りんごとオレンジは比較できないので、それぞれに重みを課します。ただし、比較はできなくても、りんご 2 個はりんご 1 個に勝っていることは記述できます。同様に、りんご 2 個とオレンジ 1 個は、オレンジ 1 個だけよりも勝っていることも記述できます。最終的に (スコアを同じに宣言する時点)で スコアを比較できなくても、最適なスコアセットを特定できます。このようなスコアを、パレート最適と呼びます。

paretoOptimizationScoring

スコアが同じと見なされることが非常に多くなり、Planner が探し出した複数の最善解 (同等のスコア) から手動で選択できるようになっています。上の例で、ユーザーはソリューション A (りんご 3 個とオレンジ 1 個) とソリューション B (りんご 1 個とオレンジ 6 個) の中から選択する必要があります。Planner が、りんごが多いソリューション、オレンジが多いソリューション、りんごとオレンジの組み合わせがより適切なソリューション (りんご 2 個とオレンジ 3 個など) など、他のソリューションを検出していないことは保証されます。

Planner にパレートスコアリングを実装するには、カスタムの ScoreDefinition およびスコアを実装 します (さらに、BestSolutionRecaller を置き換えます)。これは、今後のバージョンで、カスタマイズしなくても使用できるようになります。

注記

パレート スコアcompareTo メソッドは、パレートの比較を行うため、推移的ではありません。たとえば、りんご 2 個はりんご 1 個より優れていて、りんご 1 個とオレンジ 1 個は同じですが、りんご 2 個がオレンジ 1 個よりも優れているわけではありません (実際には同じ)。パレートの比較は、インターフェース java.lang.ComparablecompareTo メソッドのコントラクトに違反しますが、Planner のシステムは、本書でそのように記載がない限り、パレート比較でも安全に使用できます

5.1.6. スコア手法を組み合わせて使用

これまでに説明したスコア手法はすべて、シームレスに組み合わせることができます。

scoreComposition

5.1.7. スコアインターフェース

スコアは、Score インターフェースで表現され、Comparable を継承します。

public interface Score<...> extends Comparable<...> {
    ...
}

使用する Score 実装は、ユースケースにより異なります。スコアは、1 つの long 値に効率よく収まらない可能性があります。Planner には、組み込みの Score 実装が複数含まれていますが、カスタムの Score も実装できます。傾向としては、組み込みの HardSoftScore を使用するユースケースが多くなっています。

scoreClassDiagram

Score 実装 (HardSoftScore など) は、Solver のランタイム中は常に同じでなければなりません。Score 実装は、Solver の設定で ScoreDefinition として設定されます。

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

5.1.8. スコア計算で浮動小数点を使用しない

スコア計算に floatdouble を使用しないようにしてください。代わりにBigDecimal を使用してください。

浮動小数点 (float および double) では、小数点が正しく表現されません。たとえば、double0.05 を正しく保持できず、代わりに最近似値が保持されます。したがって、特に計画問題において、浮動小数点が含まれる (加算や減算などの) 演算があると、決定が間違ってしまう可能性があります。

scoreWeightType

さらに、浮動小数点数の加算は結合的ではありません。

System.out.println( ((0.01 + 0.02) + 0.03) == (0.01 + (0.02 + 0.03)) ); // returns false

これにより スコアが正しくなくなります

10 進数 (BigDecimal) ではこの問題は発生しません。

注記

BigDecimal の演算の処理は、intlong または double の演算に比べてはるかに遅くなります。新手法では、計算の平均数が 5 で除算されていました。

そのため、場合によっては、スコアの重みが int または long に収まるように、すべての 数に 10 の倍数 (1000 など) を掛けて使用するとよいでしょう。

5.2. スコア定義の選択

Score 実装には、ScoreDefinition 実装も含まれます。たとえば、SimpleScoreSimpleScoreDefinition により定義されます。

注記

データベース (JPA/Hibernate) または XML/JSON (XStream/JAXB) に スコア を適切に記述する方法は、「統合」の章を参照してください。

5.2.1. SimpleScore

SimpleScore には、-123 などの int の値が含まれ、SimpleScore のスコアレベルは 1 つとなっています。

  <scoreDirectorFactory>
    <scoreDefinitionType>SIMPLE</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

この scoreDefinitionType には以下が設定できます。

  • SIMPLE_LONG: int の値ではなく、long の値を含む SimpleLongScore を使用します。
  • SIMPLE_DOUBLE: int の値ではなく、double の値を含む SimpleDoubleScore を使用します。これを使用することは推奨されていません。
  • SIMPLE_BIG_DECIMAL: int 値ではなく、BigDecimal 値を含む SimpleBigDecimalScore を使用します。

5.2.2. HardSoftScore (推奨)

HardSoftScore には、-123hard/-456soft など、ハード int 値や ソフトint 値が含まれます。HardSoftScore のスコアレベルは 2 つ (ハードとソフト) です。

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

この scoreDefinitionType には以下が設定できます。

  • HARD_SOFT_LONG: int 値ではなく、long 値を含む HardSoftLongScore を使用します。
  • HARD_SOFT_DOUBLE: int 値ではなく、double 値を含む HardSoftDoubleScore を使用します。これを使用することは推奨されていません。
  • HARD_SOFT_BIG_DECIMAL: int 値ではなく、BigDecimal 値を含む HardSoftBigDecimalScore を使用します。

5.2.3. HardMediumSoftScore

-123hard/-456medium/-789soft など、ハード int 値、ミディアム int 値、ソフト int 値を含む HardMediumSoftScore。HardMediumSoftScore には、スコアレベルは 3 つ (ハード、ミディアム、ソフト) になります。

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_MEDIUM_SOFT</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

この scoreDefinitionType には以下が設定できます。

  • HARD_MEDIUM_SOFT_LONG: int 値ではなく、long の値を含む HardMediumSoftLongScore を使用します。

5.2.4. BendableScore

BendableScore では、スコアレベルの数を設定できます。ハードレベル 2 つ、ソフトレベル 3 つなど、ハード int 値の配列と、ソフト int 値の配列を含みます。スコアは、-123/-456/-789/-012/-345 などになります。

  <scoreDirectorFactory>
    <scoreDefinitionType>BENDABLE</scoreDefinitionType>
    <bendableHardLevelsSize>2</bendableHardLevelsSize>
    <bendableSoftLevelsSize>3</bendableSoftLevelsSize>
    ...
  </scoreDirectorFactory>

ハードおよびソフトのスコアレベルの数は、設定時に指定する必要があります。問題解決時に変更することはできません。

この scoreDefinitionType には以下が設定できます。

  • BENDABLE_LONG: int 値ではなく、long を含む BendableLongScore を使用します。
  • BENDABLE_BIG_DECIMAL: int 値ではなく、BigDecimal を含む BendableBigDecimalScore を使用します。

5.2.5. カスタムスコアの実装

ScoreDefinition インターフェースは、スコア表現を定義します。

カスタムの スコア を実装するために、カスタムの ScoreDefinitionを実装する必要があります。 AbstractScoreDefinition (できれば HardSoftScoreDefinition をコピーアンドペーストして) を継承します。

次に、SolverConfig.xml でカスタムの ScoreDefinition をフックします。

  <scoreDirectorFactory>
    <scoreDefinitionClass>...MyScoreDefinition</scoreDefinitionClass>
    ...
  </scoreDirectorFactory>

JPA/HibernateXStream などとシームレスに組み合わせるには、グルーコードを記述する必要があります。

5.3. スコア計算

5.3.1. スコア計算のタイプ

ソリューションスコア を計算する方法は複数あります。

  • Easy Java のスコア計算: Java メソッドを 1 つ実装します。
  • Java インクリメント演算子によるスコア計算: 複数の Java メソッドを実装します。
  • Drools スコア計算 (推奨): スコアルールを実装します。

スコア算出タイプはすべてのスコア定義を使用できます。たとえば、Easy Java スコア計算は HardSoftScore を出力します。

スコア計算のタイプはすべてオブジェクト指向型で、既存の Java コードを再利用することができます。

重要

スコア計算は読み取り専用にし、プランニングエンティティーまたは問題ファクトを変更しないようにしてください。Drools スコアルールの RHS 内において、プランニングエンティティーでセッターメソッドを呼び出さないようにしてください。これは、論理的に挿入された オブジェクトには適用されません。このオブジェクトは、論理的に挿入されているスコアルールにより変更できます。

(environmentMode アサーション が有効になっていない限り) Planner が ソリューション のスコアを推測できる場合には、ソリューションが再計算されません。たとえば、Move が勝利ステップの前に実行し元に戻ったため、勝利ステップの後にスコアを計算する必要はありません。そのため、スコア計算中に適用されたこのような変更が実際に行われる保証はありません。

5.3.2. Easy Java スコア計算

Java でスコア計算を簡単に実装する方法には、以下の特徴があります。

  • メリット:

    • Plain old Java (POJO): 学習曲線がない
    • 既存のコードベースやレガシーシステムにスコア計算を委譲する機会がある
  • デメリット:

EasyScoreCalculator インターフェースのメソッドを 1 つだけ実装します。

public interface EasyScoreCalculator<Sol extends Solution> {

    Score calculateScore(Sol solution);

}

たとえば、N クィーンの例では以下のようになります。

public class NQueensEasyScoreCalculator implements EasyScoreCalculator<NQueens> {

    public SimpleScore calculateScore(NQueens nQueens) {
        int n = nQueens.getN();
        List<Queen> queenList = nQueens.getQueenList();

        int score = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Queen leftQueen = queenList.get(i);
                Queen rightQueen = queenList.get(j);
                if (leftQueen.getRow() != null && rightQueen.getRow() != null) {
                    if (leftQueen.getRowIndex() == rightQueen.getRowIndex()) {
                        score--;
                    }
                    if (leftQueen.getAscendingDiagonalIndex() == rightQueen.getAscendingDiagonalIndex()) {
                        score--;
                    }
                    if (leftQueen.getDescendingDiagonalIndex() == rightQueen.getDescendingDiagonalIndex()) {
                        score--;
                    }
                }
            }
        }
        return SimpleScore.valueOf(score);
    }

}

Solver の設定では以下のように設定します。

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
  </scoreDirectorFactory>

または、ランタイム時に EasyScoreCalculator インスタンスを構築して、Programmatic API で設定します。

    solverFactory.getSolverConfig().getScoreDirectorFactoryConfig.setEasyScoreCalculator(easyScoreCalculator);

5.3.3. Java インクリメント演算子によるスコア計算

Java で​インクリメンタルにスコア計算を実装する方法には、以下の特徴があります。

  • メリット:

    • 非常に速く、スケーラビリティーが高い

      • 正しく実装されている場合には、最速である
  • デメリット:

    • 記述が難しい

      • スケーラブルな実装はマッピング、インデックスなどを多用する (Drools ルールエンジンで対応できる内容)。
      • これらのパフォーマンス最適化をすべて、学習、設計、記述、改善する必要がある
    • 読み込みが困難である

      • スコア制約を定期的に変更すると、メンテナンスコストがかさむ可能性がある

インターフェース IncrementalScoreCalculator の全メソッドを実装して、AbstractIncrementalScoreCalculator クラスを継承します。

public interface IncrementalScoreCalculator<Sol extends Solution> {

    void resetWorkingSolution(Sol workingSolution);

    void beforeEntityAdded(Object entity);

    void afterEntityAdded(Object entity);

    void beforeVariableChanged(Object entity, String variableName);

    void afterVariableChanged(Object entity, String variableName);

    void beforeEntityRemoved(Object entity);

    void afterEntityRemoved(Object entity);

    Score calculateScore();

}
incrementalScoreCalculatorSequenceDiagram

たとえば、N クィーンの例では以下のようになります。

public class NQueensAdvancedIncrementalScoreCalculator extends AbstractIncrementalScoreCalculator<NQueens> {

    private Map<Integer, List<Queen>> rowIndexMap;
    private Map<Integer, List<Queen>> ascendingDiagonalIndexMap;
    private Map<Integer, List<Queen>> descendingDiagonalIndexMap;

    private int score;

    public void resetWorkingSolution(NQueens nQueens) {
        int n = nQueens.getN();
        rowIndexMap = new HashMap<Integer, List<Queen>>(n);
        ascendingDiagonalIndexMap = new HashMap<Integer, List<Queen>>(n * 2);
        descendingDiagonalIndexMap = new HashMap<Integer, List<Queen>>(n * 2);
        for (int i = 0; i < n; i++) {
            rowIndexMap.put(i, new ArrayList<Queen>(n));
            ascendingDiagonalIndexMap.put(i, new ArrayList<Queen>(n));
            descendingDiagonalIndexMap.put(i, new ArrayList<Queen>(n));
            if (i != 0) {
                ascendingDiagonalIndexMap.put(n - 1 + i, new ArrayList<Queen>(n));
                descendingDiagonalIndexMap.put((-i), new ArrayList<Queen>(n));
            }
        }
        score = 0;
        for (Queen queen : nQueens.getQueenList()) {
            insert(queen);
        }
    }

    public void beforeEntityAdded(Object entity) {
        // Do nothing
    }

    public void afterEntityAdded(Object entity) {
        insert((Queen) entity);
    }

    public void beforeVariableChanged(Object entity, String variableName) {
        retract((Queen) entity);
    }

    public void afterVariableChanged(Object entity, String variableName) {
        insert((Queen) entity);
    }

    public void beforeEntityRemoved(Object entity) {
        retract((Queen) entity);
    }

    public void afterEntityRemoved(Object entity) {
        // Do nothing
    }

    private void insert(Queen queen) {
        Row row = queen.getRow();
        if (row != null) {
            int rowIndex = queen.getRowIndex();
            List<Queen> rowIndexList = rowIndexMap.get(rowIndex);
            score -= rowIndexList.size();
            rowIndexList.add(queen);
            List<Queen> ascendingDiagonalIndexList = ascendingDiagonalIndexMap.get(queen.getAscendingDiagonalIndex());
            score -= ascendingDiagonalIndexList.size();
            ascendingDiagonalIndexList.add(queen);
            List<Queen> descendingDiagonalIndexList = descendingDiagonalIndexMap.get(queen.getDescendingDiagonalIndex());
            score -= descendingDiagonalIndexList.size();
            descendingDiagonalIndexList.add(queen);
        }
    }

    private void retract(Queen queen) {
        Row row = queen.getRow();
        if (row != null) {
            List<Queen> rowIndexList = rowIndexMap.get(queen.getRowIndex());
            rowIndexList.remove(queen);
            score += rowIndexList.size();
            List<Queen> ascendingDiagonalIndexList = ascendingDiagonalIndexMap.get(queen.getAscendingDiagonalIndex());
            ascendingDiagonalIndexList.remove(queen);
            score += ascendingDiagonalIndexList.size();
            List<Queen> descendingDiagonalIndexList = descendingDiagonalIndexMap.get(queen.getDescendingDiagonalIndex());
            descendingDiagonalIndexList.remove(queen);
            score += descendingDiagonalIndexList.size();
        }
    }

    public SimpleScore calculateScore() {
        return SimpleScore.valueOf(score);
    }

}

Solver の設定では以下のように設定します。

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass>
  </scoreDirectorFactory>

オプションで、IncrementalScoreCalculatorFAST_ASSERT または FULL_ASSERT environmentMode に折り畳まれている場合に、ScoreDirector.getConstraintMatchTotals() でスコアを説明するか、より良い出力を取得するには、ConstraintMatchAwareIncrementalScoreCalculator インターフェースも実装します。

public interface ConstraintMatchAwareIncrementalScoreCalculator<Sol extends Solution> {

    void resetWorkingSolution(Sol workingSolution, boolean constraintMatchEnabled);

    Collection<ConstraintMatchTotal> getConstraintMatchTotals();

}

5.3.4. Drools スコア計算

5.3.4.1. 概要

Drools ルールエンジンを使用してスコア計算を実装します。すべてのスコア制約を、1 つまたは複数のスコアルールとして記述します。

  • メリット:

    • 追加設定せずにスコアのインクリメンタル計算ができる

      • 多くの DRL 構文は前向き連鎖を使用するので、追加のコードなしでインクリメントの計算が可能である。
    • スコア制約が別のルールに分かれている

      • 既存のスコアルールを簡単に追加または編集できる
    • スコア制約を柔軟に増やすことができる

      • 方法: ディションテーブルで以下を定義する

        • Excel (XLS) スプレッドシート
        • KIE Workbench WebUI
      • DSL で自然言語に変換できる
      • KIE Workbench リポジトリーで格納し、リリースできる
    • 今後のバージョンでも、追加設定せずにパフォーマンスの最適化ができる

      • どのリリースでも、Drools ルールエンジンの速度が向上する傾向にある
  • デメリット:

    • DRL の学習曲線
    • DRL の使用

      • 多言語の使用が懸念されるため、組織によっては DRL などの新しい言語の使用が禁止される場合があります。

5.3.4.2. Drools スコアルールの設定

スコアルールの配置場所を定義する方法は複数存在します。

5.3.4.2.1. クラスパスの scoreDrl リソース

これは、単純な方法です。スコアルールを、クラスパスリソースとして提供される DRL ファイルに配置します。Solver の設定の <scoreDrl> 要素に、スコアルールの DRL ファイルを追加します。

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
  </scoreDirectorFactory>

通常のプロジェクト (Maven ディレクトリー構造に準拠) では、DRL ファイルは $PROJECT_DIR/src/main/resources/org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl (WAR プロジェクトの場合も同様) に配置されます。

注記

<scoreDrl> 要素には、ClassLoader.getResource(String) で定義されたクラスパスリソースが必要です。ファイル、URL、Webapp リソースは受け入れられません。以下を参照して、ファイル を使用してください。

スコアルールが複数の DRL ファイルに分かれている場合は、<scoreDrl> 要素を複数追加します。

オプションで、Drools 設定プロパティーも設定できます (ただし、後方互換性の問題に注意してください)。

  <scoreDirectorFactory>
    ...
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
    <kieBaseConfigurationProperties>
      <drools.equalityBehavior>...</drools.equalityBehavior>
    </kieBaseConfigurationProperties>
  </scoreDirectorFactory>
5.3.4.2.2. scoreDrlFile

ローカルのファイルシステムで ファイル を使用するには、クラスパスリソースの代わりに、Solver 設定の <scoreDrlFile> 要素に、スコアルールの DRL ファイルを追加します。

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrlFile>/home/ge0ffrey/tmp/nQueensScoreRules.drl</scoreDrlFile>
  </scoreDirectorFactory>
警告

移植性の理由から、ファイルよりもクラスパスリソースが推奨されます。あるコンピューターに構築されているアプリケーションを別のコンピューターで使用する場合に、ファイルの場所が異なる可能性があります。さらに、オペレーティングシステムが異なる場合に、移植可能なファイルパスを選択するのは困難です。

スコアルールが複数の DRL ファイルに分かれている場合は、<scoreDrlFile> 要素を複数追加します。

5.3.4.2.3. Maven リポジトリーからの KJAR の ksessionName

これを使用することで、Workbench で定義されたスコアルールを使用するか、KJAR を構築して実行サーバーにデプロイすることができます。スコアルールも Solver 設定も KJAR のリソースです。クライアントは、ローカルクラスパス、ローカルの Maven リポジトリー、またはリモートの Maven リポジトリーから KJAR を取得できます。

スコアルールは DRL ファイルに配置されていますが、KieContainerMETA-INF/kmodule.xml ファイル経由でこのファイルを検索します。

<kmodule xmlns="http://www.drools.org/xsd/kmodule">
  <kbase name="nQueensKbase" packages="org.optaplanner.examples.nqueens.solver">
    <ksession name="nQueensKsession"/>
  </kbase>
</kmodule>

上記の kmodule で、org.optaplanner.examples.nqueens.solver パッケージの DRL ファイルをすべて取得します。また、kbase は別の kbase を継承することも可能です。

Solver の設定の <ksessionName> 要素に ksession 名を追加します。

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <ksessionName>nQueensKsession</ksessionName>
  </scoreDirectorFactory>

このアプローチを使用する場合には、SolverFactory.createFromKieContainerXmlResource(…​) メソッドを使用して SolverFactory を構築する必要があります。

5.3.4.3. スコアルールの実装

以下に、DRL ファイルにスコアルールとして実装されたスコア制約の例を紹介します。

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

このスコアルールは、rowIndex が同じクィーン 2 つごとに 1 回、トリガーされます。クィーンが A と B の 2 つある場合に、(A, B) にだけトリガーし、(B, A)、(A, A) または (B, B) にはトリガーされないようにするには、(id > $id) の条件が必要です。「4 個のクィーン」の以下のソリューションを使用して、スコアルールについて詳しく見ていきましょう。

unsolvedNQueens04

このソリューションでは、6 つ (A, B)、(A, C)、(A, D)、(B, C)、(B, D) および (C, D) に対して multipleQueensHorizontal のスコアルールが発生します。クィーンは同じ垂直線上または対角線上にないので、このソリューションのスコアは -6 になります。なお、「4 個のクィーン」の最適解スコアは 0 です。

注記

全スコアルールは、 (論理的に挿入されたファクトを直接的または間接的に使用して) 少なくとも 1 つのプランニングエンティティークラスに関連付けます。

これは、通常の例です。考えられるソリューションが何であっても計画中に結果は変わらないため、問題ファクトにだけ関連するスコアルールを記述しても効果はありません。

注記

kcontext 変数は、Drools Expert のマジック変数です。scoreHolder のメソッドは、この変数を使用しインクリメンタルスコアの計算を正しく行い、ConstraintMatch インスタンスを作成します。

5.3.4.4. スコアルールの重みづけ

ScoreHolder インスタンスは、scoreHolder のグローバルとして KieSession にアサートし、スコアルールで (直接的または間接的に) 更新する必要があります。

global SimpleScoreHolder scoreHolder;

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

// multipleQueensVertical is obsolete because it is always 0

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

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

Drools ルール言語 (DRL) の詳細は、Drools ドキュメント を参照してください。

ユースケースの多くは、制約の各一致に対する重みを使用することで、制約タイプや、一致そのものに課す重みを変えます。たとえば、コースの時間割 では、授業 を、座席が 2 つ足りない 講義室 に割り当てるのは、カリキュラム に、孤立した 授業 1 つを割り当てる時と同じだけマイナスと評価するように、重みを課しています。

global HardSoftScoreHolder scoreHolder;

// RoomCapacity: For each lecture, the number of students that attend the course must be less or equal
// than the number of seats of all the rooms that host its lectures.
rule "roomCapacity"
    when
        $room : Room($capacity : capacity)
        $lecture : Lecture(room == $room, studentSize > $capacity, $studentSize : studentSize)
    then
        // Each student above the capacity counts as 1 point of penalty.
        scoreHolder.addSoftConstraintMatch(kcontext, ($capacity - $studentSize));
end

// CurriculumCompactness: Lectures belonging to a curriculum should be adjacent
// to each other (i.e., in consecutive periods).
// For a given curriculum we account for a violation every time there is one lecture not adjacent
// to any other lecture within the same day.
rule "curriculumCompactness"
    when
        ...
    then
        // Each isolated lecture in a curriculum counts as 2 points of penalty.
        scoreHolder.addSoftConstraintMatch(kcontext, -2);
end

5.3.5. InitializingScoreTrend

InitializingScoreTrend は、変数が初期化されるにつれ、(すでに初期化済みの変数は変化しませんが) スコアがどのように変化するかを指定します。このような情報があれば、最適化アルゴリズム (このような構造ヒューリスティックやしらみつぶし探索) の実行速度は速くなります。

スコア (または個別の スコアレベル ) では、トレンドを指定します。

  • ANY (デフォルト): 追加の変数を初期化すると、スコアが正または負に変化する可能性があります。パフォーマンスが向上することはありません。
  • ONLY_UP (あまり使用されない): 追加の変数を初期化すると、スコアを正にだけ変更します。つまり、以下を意味します。

    • 正の制約しかない
    • 次の変数を初期化しても、前の初期化変数と一致した正の制約が一致しなくなるように、元に戻すことはできない
  • ONLY_DOWN: 追加の変数を初期化すると、スコアを負にだけ変更します。つまり、以下を意味します。

    • 負の制約しかない
    • 次の変数を初期化しても、前の初期化変数と一致した負の制約の一致が一致しなくなるように、元に戻すことはできない

負の制約しかないユースケースが多く、中でも、スコアが下がるだけの InitializingScoreTrend を使用するユースケースが多くなっています。

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>.../cloudBalancingScoreRules.drl</scoreDrl>
    <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
  </scoreDirectorFactory>

または、各スコアレベルのトレンドを個別に指定することもできます。

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>.../cloudBalancingScoreRules.drl</scoreDrl>
    <initializingScoreTrend>ONLY_DOWN/ONLY_DOWN</initializingScoreTrend>
  </scoreDirectorFactory>

5.3.6. 無効なスコアの検出

FULL_ASSERT (または FAST_ASSERT) に environmentMode を配置して、インクリメンタルスコアの計算 の破損を検出します。詳しい情報は、environmentModeに関するセクションを参照してください。ただし、スコア計算プログラムでは、実際にビジネスが希望する内容に、スコア制約が実装されているかどうかの確認はできません。

インクリメンタルスコア計算プログラムのコードには、記述やレビューが困難な箇所があります。異なる実装 (例: EasyScoreCalculator) を使用して精度をアサートし、environmentMode でトリガーされるアサーションを実行します。異なる実装を、assertionScoreDirectorFactory として設定します。

  <environmentMode>FAST_ASSERT</environmentMode>
  ...
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
    <assertionScoreDirectorFactory>
      <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
    </assertionScoreDirectorFactory>
  </scoreDirectorFactory>

このように設定すると、scoreDrlEasyScoreCalculator で検証されます。

5.4. スコア計算のパフォーマンスのヒント

5.4.1. 概要

Solver は、通常、その実行時間のほとんどをスコア計算に費やします (最も深いループで呼び出されます)。スコア計算が速いと、同じアルゴリズムを使用した場合に、同じ解 (ソリューション) をより短い時間で返します。一般的には、最善解が同じ時間内に返されます。

5.4.2. 秒あたりの平均計算数

問題の解決後、Solver秒あたりの平均計算数 をログに記録します。これは、スコア計算以外の実行時間も含まれていますが、問題データセットの問題スケールにより異なるため、スコア計算のパフォーマンスを測定するのに適しています。一般的に、スケールの高い問題の場合でも、EasyScoreCalculator の使用時以外は、1000 よりも高くなります。

重要

スコア計算を改善するには、最高スコアを上げるのではなく、秒あたりの平均計算数を上げることに焦点を当てます。スコア計算が大幅に改善しても、アルゴリズムがローカルまたはグローバルの最適条件に固定され、最高スコアが全く、またはほぼ改善されない場合もあります。計算数を監視している場合、スコア計算の改善は非常に簡単に確認できます。

さらに、計算数を監視すると、スコア制約を追加/削除できるだけでなく、元の計算数と比較することも可能です。最高スコアと元のスコアの比較は、りんごとオレンジを比較しているようなものなので、正しくありません。

5.4.3. インクリメンタルスコア計算 (差分)

ソリューション が変化したときのインクリメンタルスコアの計算 (差分ベースのスコア計算) は、すべてのソリューションを評価する全スコアを再計算するのではなく、以前の状態の差分を計算して新しい スコア を検出します。

たとえば、クィーン A を行 1 から 2 に移動したときは、クィーン B と C はどちらも変化しないため、B と C が相互に攻撃できるかどうかはチェックしません。

図5.1 クィーン 4 個のパズルにおけるインクリメンタルスコアの計算

incrementalScoreCalculationNQueens04

これは、パフォーマンスやスケーラビリティーが大幅に改善されます。Drools スコア計算では、複雑なインクリメンタルスコアの計算アルゴリズムを記述する必要はなく、スケーラビリティーが大幅に増えます。Drools ルールエンジンに困難な作業を任せるだけです。

時間の短縮は計画問題のサイズ (n) と相対的で、インクリメンタルスコアの計算のスケーラビリティーをさらに高めることができる点に注意してください。

5.4.4. スコア計算時のリモートサービスを呼び出さない

スコア計算でリモートサービスを呼び出さないようにしてください (EasyScoreCalculator とレガシーシステムをブリッジングしている場合を除きます)。ネットワークにレイテンシーがあると、スコア計算のパフォーマンスを低下させます。可能な場合は、これらのリモートサービスの結果をキャッシュします。

Solver の起動時に制約の一部が計算され、解決中に変化しない場合には、キャッシュされた問題ファクト に変換します。

5.4.5. 無意味な制約

特定の制約に決して違反しない (または常に違反する) ことが分かっている場合には、それをスコア制約に記述する必要はありません。たとえば、N クィーンの例では、スコア計算で、複数のクィーンが同じ列を占有するかどうかは確認しません。これは、クィーン は絶対に変化せず、ソリューション は、必ず別の にある各 クィーン で開始するためです。

注記

これは使用しすぎないようにしてください。特定の制約をデータセットが使用し、別のデータセットでは使用されていない場合には、できるだけ速く、その制約から結果を返すようにします。データセットをベースに、スコア計算を動的に変更する必要はありません。

5.4.6. 組み込みのハード制約

ハード制約を実装する代わりに、埋め込むこともできます。たとえば、授業 A は 講義室 X に割り当てるべきではありませんが、ソリューションで ValueRangeProvider を使用するため、Solver講義室 X にも割り当てようとします (ただし、割り当ててもハード制約に違反するだけです)。プランニングエンティティー上の ValueRangeProvider または フィルターセクション を使用して、授業 A が X 以外の 講義室 にのみ割り当てられるようにします。

これにより、実行できないソリューションを多くの最適化アルゴリズムが評価する時間が短縮されるため、スコア計算が速くなるだけでなく、ユースケースによってはパフォーマンスが向上する場合があります。ただし、一般的には、短期的には利点があっても長期的には悪影響となるため、これは優れたアイデアではありません。

  • 多くの最適化アルゴリズムは、プランニングエンティティーを変更する時にハード制約に自由に違反できるため、局所最適条件を回避することができます。
  • どちらの実装アプローチも、各ドキュメントで説明されているように制約 (機能の互換性、自動パフォーマンス最適化の無効化) があります。

5.4.7. スコア計算のパフォーマンスに関する他のヒント

  • スコア計算が正しい Number 型で行われることを確認します。int 値を合計する場合には、Drools で double を使用して合計すると所要時間が長くなるため、double を使用しないようにしてください。
  • パフォーマンスが最適になるように、サーバーモード (java -server) を常に使用するようにしてください。サーバーモードをオンにすることで、パフォーマンスの改善が 50% 見られました。
  • また、最新の Java バージョンを使用してください。Java 1.5 から 1.6 に切り替えることで、パフォーマンスの改善が 30% 見られました。
  • 成熟していない最適化は問題の原因になる可能性があることを忘れないようにしてください。設定ベースの調節ができるように、設計が柔軟に保たれていることを確認してください。

5.4.8. スコアトラップ

スコア制約がスコアトラップの原因になっていないことを確認してください。スコア制約がトラップされている場合には、重みを変えるほうが簡単であっても、異なる制約一致に同じ重みを使用しています。制約一致を効率的にまとめて、対象の制約に、上下変動のないスコア関数を作成します。これにより、Move を複数実行して解決するか、1 つの制約の重みを下げる必要があるソリューションが発生する可能性があります。スコープトラップの例は以下のとおりです。

  • テーブルごとに医師が 2 名必要ですが、一度に移動できるのは医師 1 名だけです。そのため、Solver が、医師のいないテーブルに医師を 1 名移動することは誘因にはなりません。このスコア関数では、スコア制約内で、医師が 1 名しかいないテーブルよりも、医師のいないテーブルにペナルティーを課します。
  • 2 つの試験を同時に実施する必要がありますが、一度に移動できるのは 1 つの試験だけです。そのため、Solver が、いずれかの試験を別の時間枠に移動し、同じ Move でもう 1 つの試験を移動しないようにする必要があります。同時に両試験を移動する、粒度の粗い Move を追加します。

たとえば、以下のようなスコアトラップを考えてみてください。負荷の高いコンピューターから空のコンピューターに青いアイテムを移動すると、ハードスコアが上がるはずです。以下のように、トラップされたスコア実装により、移動に失敗してしまいます。

scoreTrap

Solver は、最終的にこのトラップから外れますが、多くの労力を要します (特に、負荷の多いコンピューターのプロセスが多い場合など)。ペナルティーがないため、トラップから外すために、実際には負荷が多いコンピューターにプロセスを移動する可能性があります。

注記

スコアトラップを回避しても、スコア関数が局所最適条件を回避するほどスマートになるわけではありません。最適化アルゴリズムに、局所最適条件を処理させるようにしてください。

スコアトラップを回避すると、スコア制約ごとに、上下に変動しないスコア関数を回避することになります。

重要

実行不可能の程度を常に指定するようにしてください。ビジネスでは頻繁に、「ソリューションが実行できないものであれば、実行不可能なレベルは関係ない」と考えます。これは、ビジネスにとっては真実であってもスコア計算では異なるため、実行不可能なレベルを知ることで利点があります。実際には、ソフト制約では自然に実行されるので、ハード制約でも取り入れるだけなのです。

スコアトラップの使用方法は、複数存在します。

  • スコア制約を改善して、スコアの重みを区別します。たとえば、CPU が足りない場合に -1hard のペナルティーを課すのではなく、足りていない CPU の数ごとに -1hard のペナルティーを課します。
  • ビジネスの観点から、スコア制約を変更できない場合に、区別ができるスコア制約を使用して、レベルが低いスコアレベルを追加します。たとえば、CPU が足りない場合に -1hard を課し、さらに、足りない CPU の数だけ -1subsoft を課します。ビジネスでは、サブソフトスコアレベルが無視されます。
  • 粒度の粗い Move を追加して、既存の粒度の細かい Move をまとめて選択します。粒度の粗い Move が、複数の Move を効率よく実行して、1 つの Move でスコアトラップから抜け出します。たとえば、同じコンテナーから別のコンテナーに複数アイテムを移動する場合などです。

5.4.9. stepLimit ベンチマーク

すべての制約に、同じパフォーマンスコストがかかるわけではありません。1 つのスコア制約により、スコア計算のパフォーマンス全体が落ちてしまう可能性があります。ベンチマーカー を使用して 1 分間実行し、スコア制約を 1 つだけ残してすべてコメントアウトした場合に、秒単位の平均計算数がどうなるかを確認します。

5.4.10. 公平なスコア制約

ユースケースによっては、ビジネス要件に公平なスケジュール (通常はソフトスコア制約として) が含まれる場合があります。以下に例を示します。

  • 不満がでないように、従業員全体でワークロードを公平に分散します。
  • アセット全体でワークロードを均等に分散して、信頼性を上げます。

(特に公平性を正式化する方法は複数あるため) このような制約を実装するのは困難なように見えますが、通常、ワークロードを 2 乗した 実装が最も理想的に動作します。従業員/アセットごとに、ワークロード w をカウントし、スコアから w2 を除算します。

fairnessScoreConstraint

上記のように、ワークロードを 2 乗した 実装では、特定のソリューションから従業員 2 名を選択し、その 2 名の間で公平にワークロードを分散すると、新たなソリューションの全体スコアが改善されます。平均ワークロードからの差異だけを使用しないようにしてください。以下のように、不公平な結果になってしまう可能性があります。

fairnessScoreConstraintPitfall
注記

ワークロードを 2 乗 する代わりに、分散 (平均からの差異を 2 乗) または 標準偏差 (分散からの平方根) を使用することもできます。平均は計画時に変更しないため、これはスコア比較には影響しません。実装作業が増え (平均値が必要)、明らかに処理が遅くなります (計算にかかる時間が増えます)。

ワークロードが均等に分散されている場合には、上の図のように紛らわしいスコア (-34soft (ほぼ均等に分散された最終解)) よりも、0 スコアが好まれる場合が多くなります。これを null 化するには、スコアに、エンティティーの数を乗算した平均を追加するか、UI で分散または標準偏差を表示します。

5.5. スコアの説明: Solver 外でのスコア計算の使用

Web UI など、アプリケーションの他の部分で、スコアの計算が必要になる場合があります。これには、SolverScoreDirectorFactory を再利用して、その Web UI の別の ScoreDirector を構築します。

ScoreDirectorFactory scoreDirectorFactory = solver.getScoreDirectorFactory();
ScoreDirector guiScoreDirector = scoreDirectorFactory.buildScoreDirector();

次に、ソリューションスコア を計算する必要がある場合に使用します。

guiScoreDirector.setWorkingSolution(solution);
Score score = guiScoreDirector.calculateScore();

どのエンティティーが スコア のどの部分に影響を与えているのかを GUI で説明するには、ScoreDirector から ConstraintMatch オブジェクトを取得します。

for (ConstraintMatchTotal constraintMatchTotal : guiScoreDirector.getConstraintMatchTotals()) {
    String constraintName = constraintMatchTotal.getConstraintName();
    Number weightTotal = constraintMatchTotal.getWeightTotalAsNumber();
    for (ConstraintMatch constraintMatch : constraintMatchTotal.getConstraintMatchSet()) {
        List<Object> justificationList = constraintMatch.getJustificationList();
        Number weight = constraintMatch.getWeightAsNumber();
        ...
    }
}
注記

Drools スコア計算 は、自動的に制約の一致をサポートしますが、Java インクリメント演算子によるスコア計算 には、追加のインターフェース (対象のセクションを参照) が必要になります。