10.2. スコア計算の種類

ソリューションのスコアを計算するには、いくつかの種類の方法があります。

  • Easy Java のスコア計算: Java または別の JVM 言語の単一メソッドですべての制約をまとめて実装します。この方法は拡張性がありません。
  • 制約ストリームのスコア計算: 各制約を Java または別の JVM 言語で個別の制約ストリームとして実装します。この方法は高速で拡張可能です。
  • Java インクリメント演算子によるスコア計算 (非推奨): Java または別の JVM 言語で複数の低レベルメソッドを実装します。この方法は高速で拡張可能ですが、実装と保守が非常に困難です。
  • Drools スコア計算 (非推奨): 各制約を DRL の個別のスコアルールとして実装します。この方法は拡張可能です。

各スコア計算タイプは、HardSoftScoreHardMediumSoftScore など の任意のスコア定義で機能します。すべてのスコア計算タイプはオブジェクト指向であり、既存の Java コードを再利用できます。

重要

スコア計算は読み取り専用である必要があります。計画主体や問題の事実をいかなる形でも変更してはなりません。たとえば、スコア計算では、プランニングエンティティーのセッターメソッドを呼び出してはなりません。

OptaPlanner は、environmentMode アサーションが有効でない限り、ソリューションを予測できる場合には、ソリューションのスコアを再計算しません。たとえば、勝利ステップが完了した後、その動きは以前に実行され取り消されているため、スコアを計算する必要はありません。そのため、スコア計算中に適用された変更が実際に行われるという保証はありません。

計画変数が変更されたときに計画エンティティーを更新するには、代わりにシャドウ変数を使用します。

10.2.1. Easy Java のスコア計算タイプの実装

Easy Java のスコア計算タイプは、Java でスコア計算を実装する簡単な方法を提供します。Java または別の JVM 言語の単一メソッドですべての制約をまとめて実装できます。

  • 利点:

    • プレーンな古い Java を使用するため、学習曲線が不要です
    • スコア計算を既存のコードベースまたはレガシーシステムに委譲する機会を提供します
  • デメリット:

    • 最も遅い計算タイプ
    • インクリメント演算子によるスコア計算がないため拡張できません

手順

  1. EasyScoreCalculator インターフェイスを実装します。

    public interface EasyScoreCalculator<Solution_, Score_ extends Score<Score_>> {
    
        Score_ calculateScore(Solution_ solution);
    
    }

    次の例では、N Queens 問題でこのインターフェイスを実装しています。

    public class NQueensEasyScoreCalculator
        implements EasyScoreCalculator<NQueens, SimpleScore> {
    
        @Override
        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);
        }
    
    }
  2. ソルバー設定で EasyScoreCalculator クラスを設定します。次の例は、N クイーン問題でこのインターフェイスを実装する方法を示しています。

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
      </scoreDirectorFactory>
  3. EasyScoreCalculator メソッドの値をソルバー設定で動的に設定し、ベンチマーカーがこれらのパラメーターを調整できるようにするには、easyScoreCalculatorCustomProperties 要素を追加し、カスタムプロパティーを使用します。

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>...MyEasyScoreCalculator</easyScoreCalculatorClass>
        <easyScoreCalculatorCustomProperties>
          <property name="myCacheSize" value="1000" />
        </easyScoreCalculatorCustomProperties>
      </scoreDirectorFactory>

10.2.2. Java インクリメント演算子によるスコア計算によるスコア計算タイプの実装

Java インクリメント演算子によるスコア計算タイプは、Java でスコア計算を増分的に実装する方法を提供します。

注記

このタイプは推奨されません。

  • 利点:

    • 非常に高速で拡張可能です。正しく実装されていれば、これが現時点で最も高速なタイプです。
  • デメリット:

    • 記述しにくいです。

      • マップやインデックスなどを多用するスケーラブルな実装です。
      • これらのパフォーマンスの最適化をすべて自分で学習、設計、作成、改善する必要があります。
    • 読みにくいです。スコア制約を定期的に変更すると、メンテナンスコストが高くなる可能性があります。

手順

  1. IncrementalScoreCalculator インターフェイスのすべてのメソッドを実装します。

    public interface IncrementalScoreCalculator<Solution_, Score_ extends Score<Score_>> {
    
        void resetWorkingSolution(Solution_ 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();
    
    }
    IncrementalScoreCalculator のシーケンス図

    次の例では、N Queens 問題でこのインターフェイスを実装しています。

    public class NQueensAdvancedIncrementalScoreCalculator
        implements IncrementalScoreCalculator<NQueens, SimpleScore> {
    
        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);
        }
    
    }
  2. ソルバー設定で、incrementalScoreCalculatorClass クラスを設定します。次の例は、N クイーン問題でこのインターフェイスを実装する方法を示しています。

      <scoreDirectorFactory>
        <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass>
      </scoreDirectorFactory>
    重要

    インクリメント演算子によるスコア計算コードの一部を作成したりレビューしたりするのは難しい場合があります。EasyScoreCalculator を使用して、environmentMode によってトリガーされたアサーションを実行することによって、その正確性をアサートします。

  3. ソルバー設定で IncrementalScoreCalculator の値を動的に設定し、ベンチマーカーがそれらのパラメーターを調整できるようにするには、incrementalScoreCalculatorCustomProperties 要素を追加し、カスタムプロパティーを使用します。

      <scoreDirectorFactory>
        <incrementalScoreCalculatorClass>...MyIncrementalScoreCalculator</incrementalScoreCalculatorClass>
        <incrementalScoreCalculatorCustomProperties>
          <property name="myCacheSize" value="1000"/>
        </incrementalScoreCalculatorCustomProperties>
      </scoreDirectorFactory>
  4. オプション: ConstraintMatchAwareIncrementalScoreCalculator インターフェイスを実装して、次の目標を達成します。

    • ScoreExplanation.getConstraintMatchTotalMap() を使用して、スコア制約ごとにスコアを分割してスコアを説明します。
    • ScoreExplanation.getIndictmentMap() を使用して、それぞれが破る制約の数によって計画エンティティーを視覚化または並べ替えます。
    • IncrementalScoreCalculatorFAST_ASSERT または FULL_ASSERT環境モード で破損している場合は、詳細な分析を受け取ります。

      public interface ConstraintMatchAwareIncrementalScoreCalculator<Solution_, Score_ extends Score<Score_>> {
      
          void resetWorkingSolution(Solution_ workingSolution, boolean constraintMatchEnabled);
      
          Collection<ConstraintMatchTotal<Score_>> getConstraintMatchTotals();
      
          Map<Object, Indictment<Score_>> getIndictmentMap();
      }

      たとえば、マシンの再割り当てでは、制約タイプごとに 1 つの ConstraintMatchTotal を作成し、制約一致ごとに addConstraintMatch() を呼び出します。

      public class MachineReassignmentIncrementalScoreCalculator
              implements ConstraintMatchAwareIncrementalScoreCalculator<MachineReassignment, HardSoftLongScore> {
          ...
      
          @Override
          public void resetWorkingSolution(MachineReassignment workingSolution, boolean constraintMatchEnabled) {
              resetWorkingSolution(workingSolution);
              // ignore constraintMatchEnabled, it is always presumed enabled
          }
      
          @Override
          public Collection<ConstraintMatchTotal<HardSoftLongScore>> getConstraintMatchTotals() {
              ConstraintMatchTotal<HardSoftLongScore> maximumCapacityMatchTotal = new DefaultConstraintMatchTotal<>(CONSTRAINT_PACKAGE,
                  "maximumCapacity", HardSoftLongScore.ZERO);
              ...
              for (MrMachineScorePart machineScorePart : machineScorePartMap.values()) {
                  for (MrMachineCapacityScorePart machineCapacityScorePart : machineScorePart.machineCapacityScorePartList) {
                      if (machineCapacityScorePart.maximumAvailable < 0L) {
                          maximumCapacityMatchTotal.addConstraintMatch(
                                  Arrays.asList(machineCapacityScorePart.machineCapacity),
                                  HardSoftLongScore.valueOf(machineCapacityScorePart.maximumAvailable, 0));
                      }
                  }
              }
              ...
              List<ConstraintMatchTotal<HardSoftLongScore>> constraintMatchTotalList = new ArrayList<>(4);
              constraintMatchTotalList.add(maximumCapacityMatchTotal);
              ...
              return constraintMatchTotalList;
          }
      
          @Override
          public Map<Object, Indictment<HardSoftLongScore>> getIndictmentMap() {
              return null; // Calculate it non-incrementally from getConstraintMatchTotals()
          }
      }

      getConstraintMatchTotals() コードは、多くの場合、通常の IncrementalScoreCalculator メソッドのロジックの一部を複製します。制約ストリームと Drools スコア計算には、追加のドメイン固有のコードを必要とせずに、必要に応じて制約一致が自動的に認識されるため、この欠点はありません。