10.2. スコア計算の種類
ソリューションのスコアを計算するには、いくつかの種類の方法があります。
- Easy Java のスコア計算: Java または別の JVM 言語の単一メソッドですべての制約をまとめて実装します。この方法は拡張性がありません。
- 制約ストリームのスコア計算: 各制約を Java または別の JVM 言語で個別の制約ストリームとして実装します。この方法は高速で拡張可能です。
- Java インクリメント演算子によるスコア計算 (非推奨): Java または別の JVM 言語で複数の低レベルメソッドを実装します。この方法は高速で拡張可能ですが、実装と保守が非常に困難です。
- Drools スコア計算 (非推奨): 各制約を DRL の個別のスコアルールとして実装します。この方法は拡張可能です。
各スコア計算タイプは、HardSoftScore や HardMediumSoftScore など の任意のスコア定義で機能します。すべてのスコア計算タイプはオブジェクト指向であり、既存の Java コードを再利用できます。
スコア計算は読み取り専用である必要があります。計画主体や問題の事実をいかなる形でも変更してはなりません。たとえば、スコア計算では、プランニングエンティティーのセッターメソッドを呼び出してはなりません。
OptaPlanner は、environmentMode アサーションが有効でない限り、ソリューションを予測できる場合には、ソリューションのスコアを再計算しません。たとえば、勝利ステップが完了した後、その動きは以前に実行され取り消されているため、スコアを計算する必要はありません。そのため、スコア計算中に適用された変更が実際に行われるという保証はありません。
計画変数が変更されたときに計画エンティティーを更新するには、代わりにシャドウ変数を使用します。
10.2.1. Easy Java のスコア計算タイプの実装
Easy Java のスコア計算タイプは、Java でスコア計算を実装する簡単な方法を提供します。Java または別の JVM 言語の単一メソッドですべての制約をまとめて実装できます。
利点:
- プレーンな古い Java を使用するため、学習曲線が不要です
- スコア計算を既存のコードベースまたはレガシーシステムに委譲する機会を提供します
デメリット:
- 最も遅い計算タイプ
- インクリメント演算子によるスコア計算がないため拡張できません
手順
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); } }ソルバー設定で
EasyScoreCalculatorクラスを設定します。次の例は、N クイーン問題でこのインターフェイスを実装する方法を示しています。<scoreDirectorFactory> <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass> </scoreDirectorFactory>EasyScoreCalculatorメソッドの値をソルバー設定で動的に設定し、ベンチマーカーがこれらのパラメーターを調整できるようにするには、easyScoreCalculatorCustomProperties要素を追加し、カスタムプロパティーを使用します。<scoreDirectorFactory> <easyScoreCalculatorClass>...MyEasyScoreCalculator</easyScoreCalculatorClass> <easyScoreCalculatorCustomProperties> <property name="myCacheSize" value="1000" /> </easyScoreCalculatorCustomProperties> </scoreDirectorFactory>
10.2.2. Java インクリメント演算子によるスコア計算によるスコア計算タイプの実装
Java インクリメント演算子によるスコア計算タイプは、Java でスコア計算を増分的に実装する方法を提供します。
このタイプは推奨されません。
利点:
- 非常に高速で拡張可能です。正しく実装されていれば、これが現時点で最も高速なタイプです。
デメリット:
記述しにくいです。
- マップやインデックスなどを多用するスケーラブルな実装です。
- これらのパフォーマンスの最適化をすべて自分で学習、設計、作成、改善する必要があります。
- 読みにくいです。スコア制約を定期的に変更すると、メンテナンスコストが高くなる可能性があります。
手順
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(); }
次の例では、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); } }ソルバー設定で、
incrementalScoreCalculatorClassクラスを設定します。次の例は、N クイーン問題でこのインターフェイスを実装する方法を示しています。<scoreDirectorFactory> <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass> </scoreDirectorFactory>重要インクリメント演算子によるスコア計算コードの一部を作成したりレビューしたりするのは難しい場合があります。
EasyScoreCalculatorを使用して、environmentModeによってトリガーされたアサーションを実行することによって、その正確性をアサートします。ソルバー設定で
IncrementalScoreCalculatorの値を動的に設定し、ベンチマーカーがそれらのパラメーターを調整できるようにするには、incrementalScoreCalculatorCustomProperties要素を追加し、カスタムプロパティーを使用します。<scoreDirectorFactory> <incrementalScoreCalculatorClass>...MyIncrementalScoreCalculator</incrementalScoreCalculatorClass> <incrementalScoreCalculatorCustomProperties> <property name="myCacheSize" value="1000"/> </incrementalScoreCalculatorCustomProperties> </scoreDirectorFactory>オプション:
ConstraintMatchAwareIncrementalScoreCalculatorインターフェイスを実装して、次の目標を達成します。-
ScoreExplanation.getConstraintMatchTotalMap()を使用して、スコア制約ごとにスコアを分割してスコアを説明します。 -
ScoreExplanation.getIndictmentMap()を使用して、それぞれが破る制約の数によって計画エンティティーを視覚化または並べ替えます。 IncrementalScoreCalculatorがFAST_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 スコア計算には、追加のドメイン固有のコードを必要とせずに、必要に応じて制約一致が自動的に認識されるため、この欠点はありません。
-