10.2. 分数计算类型
计算解决方案分数的方法有几种:
- 简单 Java 分数计算 :以 Java 或其他 JVM 语言通过单一方法实施所有限制。这个方法无法扩展。
- 约束 流分数计算 :将每个约束实施为 Java 或其他 JVM 语言的独立约束流。这个方法快速且可扩展的。
- 增量 Java 分数计算 (不推荐):使用 Java 或其他 JVM 语言实施多种低级别方法。这个方法快速、可扩展,但很难实施和维护。
- Drools 分数计算(已弃用): 将每个约束作为 DRL 中的单独分数规则实施。这个方法可扩展。
每个分数计算类型都可以用于任何分数定义,如 HardSoftScore 或 HardMediumSoftScore。所有分数计算类型都面向对象,并可重复利用现有的 Java 代码。
分数计算必须为只读。它不得以任何方式更改计划实体或问题事实。例如,分数计算不得对分数计算中的规划实体调用 setter 方法。
如果可以预测,在启用了 environmentMode 断言时,OptaPlanner 不会重新计算解决方案分数。例如,在完成获奖步骤后,无需计算分数,因为之前已完成并撤消。因此,无法保证在分数计算过程中应用的更改实际发生。
要在规划变量更改时更新计划实体,请使用 shadow 变量。
10.2.1. Implenting the 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); } }在 solver 配置中配置
EasyScoreCalculator类。以下示例演示了如何在 N Queens 问题中实施这个接口:<scoreDirectorFactory> <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass> </scoreDirectorFactory>要在 solver 配置中动态配置
EasyScoreCalculator方法的值,以便基准器可以调整这些参数,添加easyScoreCalculatorCustomProperties元素并使用自定义属性:<scoreDirectorFactory> <easyScoreCalculatorClass>...MyEasyScoreCalculator</easyScoreCalculatorClass> <easyScoreCalculatorCustomProperties> <property name="myCacheSize" value="1000" /> </easyScoreCalculatorCustomProperties> </scoreDirectorFactory>
10.2.2. 实施增量 Java 分数计算类型
Incremental 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); } }在 solver 配置中配置
incrementalScoreCalculatorClass类。以下示例演示了如何在 N Queens 问题中实施这个接口:<scoreDirectorFactory> <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass> </scoreDirectorFactory>重要编写和审核增量分数计算器代码可能比较困难。通过使用
EasyScoreCalculator来满足environmentMode触发的断言,以保证其正确性。要在 solver 配置中动态配置
IncrementalScoreCalculator的值,以便基准器可以调整这些参数,添加incrementalScoreCalculProperties元素并使用自定义属性:<scoreDirectorFactory> <incrementalScoreCalculatorClass>...MyIncrementalScoreCalculator</incrementalScoreCalculatorClass> <incrementalScoreCalculatorCustomProperties> <property name="myCacheSize" value="1000"/> </incrementalScoreCalculatorCustomProperties> </scoreDirectorFactory>可选:实现
ConstraintMatchAwareIncrementalScoreCalculator接口,以促进以下目标:-
使用
ScoreExplanation.getConstraintMatchTotalMap ()对每个分数约束进行分割,以说明分数。 -
通过
ScoreExplanation.getIndictmentMap ()中断来视觉化或排序规划实体。 如果在
FAST_ASSERT或FULL_ASSERTenvironmentMode中损坏IncrementalScoreCalculator,您会收到详细的分析。public interface ConstraintMatchAwareIncrementalScoreCalculator<Solution_, Score_ extends Score<Score_>> { void resetWorkingSolution(Solution_ workingSolution, boolean constraintMatchEnabled); Collection<ConstraintMatchTotal<Score_>> getConstraintMatchTotals(); Map<Object, Indictment<Score_>> getIndictmentMap(); }例如,在机器重新分配中,为每个约束类型创建一个
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 ()代码通常会复制 normalIncrementalScoreCalculator方法的一些逻辑。约束流和 Drools Score Calculation 没有这种缺点,因为它们在不需要任何额外的域代码时会自动匹配。
-
使用