10.2. 分数计算类型

计算解决方案分数的方法有几种:

  • 简单 Java 分数计算 :以 Java 或其他 JVM 语言通过单一方法实施所有限制。这个方法无法扩展。
  • 约束 流分数计算 :将每个约束实施为 Java 或其他 JVM 语言的独立约束流。这个方法快速且可扩展的。
  • 增量 Java 分数计算 (不推荐):使用 Java 或其他 JVM 语言实施多种低级别方法。这个方法快速、可扩展,但很难实施和维护。
  • Drools 分数计算(已弃用): 将每个约束作为 DRL 中的单独分数规则实施。这个方法可扩展。

每个分数计算类型都可以用于任何分数定义,如 HardSoftScoreHardMediumSoftScore。所有分数计算类型都面向对象,并可重复利用现有的 Java 代码。

重要

分数计算必须为只读。它不得以任何方式更改计划实体或问题事实。例如,分数计算不得对分数计算中的规划实体调用 setter 方法。

如果可以预测,在启用了 environmentMode 断言时,OptaPlanner 不会重新计算解决方案分数。例如,在完成获奖步骤后,无需计算分数,因为之前已完成并撤消。因此,无法保证在分数计算过程中应用的更改实际发生。

要在规划变量更改时更新计划实体,请使用 shadow 变量。

10.2.1. Implenting the 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. 在 solver 配置中配置 EasyScoreCalculator 类。以下示例演示了如何在 N Queens 问题中实施这个接口:

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
      </scoreDirectorFactory>
  3. 要在 solver 配置中动态配置 EasyScoreCalculator 方法的值,以便基准器可以调整这些参数,添加 easyScoreCalculatorCustomProperties 元素并使用自定义属性:

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

10.2.2. 实施增量 Java 分数计算类型

Incremental 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. 在 solver 配置中配置 incrementalScoreCalculatorClass 类。以下示例演示了如何在 N Queens 问题中实施这个接口:

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

    编写和审核增量分数计算器代码可能比较困难。通过使用 EasyScoreCalculator 来满足 environmentMode 触发的断言,以保证其正确性。

  3. 要在 solver 配置中动态配置 IncrementalScoreCalculator 的值,以便基准器可以调整这些参数,添加 incrementalScoreCalculProperties 元素并使用自定义属性:

      <scoreDirectorFactory>
        <incrementalScoreCalculatorClass>...MyIncrementalScoreCalculator</incrementalScoreCalculatorClass>
        <incrementalScoreCalculatorCustomProperties>
          <property name="myCacheSize" value="1000"/>
        </incrementalScoreCalculatorCustomProperties>
      </scoreDirectorFactory>
  4. 可选:实现 ConstraintMatchAwareIncrementalScoreCalculator 接口,以促进以下目标:

    • 使用 ScoreExplanation.getConstraintMatchTotalMap () 对每个分数约束进行分割,以说明分数。
    • 通过 ScoreExplanation.getIndictmentMap () 中断来视觉化或排序规划实体。
    • 如果在 FAST_ASSERTFULL_ASSERT environmentMode 中损坏 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 () 代码通常会复制 normal IncrementalScoreCalculator 方法的一些逻辑。约束流和 Drools Score Calculation 没有这种缺点,因为它们在不需要任何额外的域代码时会自动匹配。