- 👤author: @Zerui Wang、@Yunqi Sun
- 🗞️version2.0
- 📅2021年12月13日
本文档主要讲解在optaplanner代码中进行算法替换的流程和方法。
| 序号 | 名称 | 含义 |
|---|---|---|
| 1 | solution | 问题的解决方案，一个规划问题有很多解决方案，算法的目的就是得到一个最优或次优的解决方案 |
| 2 | constraints | 问题约束，表示对问题约束条件，同时也是计算solution的score的规则。数学上一般是很多不等式 |
| 3 | workingSolution | 工作解决方案（当前），问题搜索最佳解决方案过程中经过的solution |
| 4 | bestSolution | 最佳解决方案（当前），问题求解过程中对当前得分最高的solution的称呼 |
| 5 | solver | 问题求解器，可以通过配置文件进行配置，配置内容包括算法配置和顺序、终止条件、随机数设置等 |
| 6 | phase | 问题“求解阶段”，一般一个问题的求解会有多个阶段，每个阶段使用一种算法 |
| 7 | score | 一个solution的得分，分数计算规则的在contraints中定义 |
| 8 | bestScore | bestSolution的得分（score） |
| 9 | domain model | 领域模型，对规划问题的定义，包含若干特定属性——问题事实（problem fact），计划实体、计划变量等 |
| 10 | move | 从一个solution到另一个solution的改变 |
| 11 | 邻域 | 一个solution经过一个move所能到达的所有solution的集合 |
optaplanner代码中多用工厂设计模式，template method等。
- 这一小节主要帮助理解后面的算法替换
- 实际的算法替换过程不一定用得上其中的某些类，因为optaplanner会对他们进行操作，不用算法进行操作
包括如下类
- 计划实体（planning entity），问题求解过程中可以改变的类
- 计划变量（panning variable），规划实体类的属性(或属性) ，在解决过程中发生变化。在此示例中，它是类 Process 上的属性计算机。
- 影子变量（shadow variable），如果存在多个关系和字段是计划变量，那么可能存在影子变量，它的值基于一个或多个计划变量计算得来
- 问题事实（problem fact），optaplanner无法改变的输入数据，一般是规划实体的数量等
- 问题（planning solution），解决方案类
问题求解器配置，有两种创建方式
-
直接在代码中嵌入
SolverFactory<CloudBalance> solverFactory = SolverFactory.create(new SolverConfig() .withSolutionClass(CloudBalance.class) .withEntityClasses(CloudProcess.class) .withConstraintProviderClass(CloudBalancingConstraintProvider.class) .withTerminationSpentLimit(Duration.ofMinutes(2)));
-
基于xml配置文件定义
<solver> <randomSeed>0</randomSeed> <solutionClass>org.optaplanner.examples.nqueens.domain.NQueens</solutionClass> <entityClass>org.optaplanner.examples.nqueens.domain.Queen</entityClass> <scoreDirectorFactory> <constraintProviderClass>org.optaplanner.examples.nqueens.score.NQueensConstraintProvider</constraintProviderClass> <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend> </scoreDirectorFactory> <constructionHeuristic> ... </constructionHeuristic> <localSearch> ... </localSearch> </solver>
solverCofig中主要包含如下定义
-
Score configuration：分数配置，包括硬约束和软约束。optaplanner支持多种实现方式（java se，ConstraintStreams，drools引擎）
-
Domain model configuration，领域模型配置（What optaplanner can change）
<solutionClass>org.optaplanner.examples.cloudbalancing.domain.CloudBalance</solutionClass> <entityClass>org.optaplanner.examples.cloudbalancing.domain.CloudProcess</entityClass>
-
Optimization algorithms configuration，算法配置。包含求解使用算法类型和算法属性和参数配置。我们的替换算法的配置方式后面会讲解
<!-- 局部搜索算法的配置 --> <localSearch> <!-- 终止条件配置 --> <termination> <bestScoreLimit>0</bestScoreLimit> </termination> <!-- moveSelector配置 --> <unionMoveSelector> <changeMoveSelector/> <swapMoveSelector/> <pillarChangeMoveSelector/> <pillarSwapMoveSelector/> </unionMoveSelector> <!-- 禁忌搜索配置 --> <acceptor> <entityTabuSize>7</entityTabuSize> </acceptor> </localSearch> <!-- 自定义算法配置 --> <customPhase>--> <customPhaseCommandClass> org.optaplanner.core.impl.phase.custom.NoChangeCustomPhaseCommand </customPhaseCommandClass> </customPhase>
move是从$solution_A$到$solution_B$的变化。例如，下面的移动将皇后c从第0行改到第2行
move
这里仅介绍基本定义，optaplanner还定义了更多的move种类，比如swapmove
MoveSelector 的主要功能是在需要的时候创建 Iterator<move> 。即邻域中的move，优化算法将循环遍历这些move所到达的solutions。
这个不是算法的必要部分，但是是一个重要且好用的轮子，可配置性强，optaplanner自带算法大部分都用到该轮子。
文档详细介绍了move和moveSelector的配置方法，这里没必要过于详细描述。第三部分的示例中会使用
问题求解阶段类，其抽象类定义多个生命周期接口。
solve：算法主要逻辑calculateWorkingStepScore计算进行一次move得到的workingSolution的得分solvingStarted：生命周期方法，solver求解开始之前调用solvingEnded：生命周期方法，solver求解结束phaseStarted：生命周期方法，- 一个算法求解开始时调用
- 其中对一些类的实例进行初始化
phaseEnded：算法结束时调用- 其他
solver类中包含一个phaseList，solver.solve()中会逐个调用phase.solve().
solverScopephaseScopestepScopemoveScope
- solver会迭代运行多个phase（算法）
- 一个phase会进行多个step
- 进行一次step需要尝试多个move
这些形成了如下的嵌套关系，每个scope类中保留了每个步骤的信息，比如
- moveScope中保存所进行的move实例
- stepScope中会保存遍历邻域之后选择的move
⚠️ 我们替换算法不会用到这些类的全部功能，只会用到一部分，其中大部分是规定动作
算法替换主要流程
替换算法主要逻辑（phase.solve()）编写流程
optaplanner-examples/src/main/resources/org/optaplanner/examples/
各个示例的算法配置文件都在这个目录下，第一部分讲解solverConfig时说过，求解器（solver）可以由xml文件构建。我们以nqueen问题的optaplanner-examples/src/main/resources/org/optaplanner/examples/nqueens/nqueensSolverConfig.xml为例
在代码倒数第二行加入，如下代码
<customPhase>
<customPhaseCommandClass>
org.optaplanner.core.impl.phase.custom.NoChangeCustomPhaseCommand
</customPhaseCommandClass>
</customPhase>这是optaplanner给开发者预留的自定义算法接口
我们也可以像其他算法一样进行一定的参数配置，
<customPhase>
<customPhaseCommandClass>...MyCustomPhase</customPhaseCommandClass>
<customProperties>
<property name="mySelectionSize" value="5"/>
</customProperties>
</customPhase>这些参数可以在工厂类optaplanner-core/src/main/java/org/optaplanner/core/impl/phase/custom/DefaultCustomPhaseFactory.java里使用
phaseConfig.getCustomProperties()获取供算法求解或配置算法使用
optaplanner给开发者预留了自定义算法接口，但是与我们的需求有一定差距。所以替换算法不能直接在原仓库进行代码增添，请克隆我们提供的仓库
git clone https://github.com/xinwuyun/optaplanner-alter.gitoptaplanner-core/src/main/java/org/optaplanner/core/impl/phase/custom
算法替换在此处进行，文件夹下包含
我们主要的工作可以只在这个文件夹下进行
如果完全按照opta的设计模式，则也需要在
/optaplanner-core/src/main/java/org/optaplanner/core/config文件夹下进行相应编写，这样完全可以，但认为过于繁琐。
算法主要逻辑放在DefaultCustomPhase.java的solve方法中即可，修改好配置文件后，optaplanner会自动调用
工厂类即该目录下的DefaultCustomPhase.java，工厂类创建中的各个组件（属性）将他们组装成DefaultCustomPhase。
当我们想要在DefaultCustomPhase中添加某个组件（属性）时，按照如下步骤进行
- 首先肯定定义该类（及其工厂类），如果这个类是已有的轮子则不用定义
- 在
DefaultCustomPhase中引入并在类中添加该属性及其getter、setter方法 - 在
DefaultCustomPhaseFactory中的buildPhase方法中创建这个类的实例，调用setter方法。
整体的求解器的输入是问题定义，optaplanner会将问题定义转换为算法的输入。
算法主要逻辑在phase.solve()，传入的参数是solverScope。
solverScope中包含算法求解必须的所有资料。opta提供了诸多接口供算法使用。所以从更抽象的角度来理解输入如下：
- 当前solution，即当前解决方案，算法会对这个solution进行优化
- scoreDirector：用于计算分数
这里不理解请继续看下面两个小节
算法输出是优化后的bestSolution和bestScore
算法实际上不会返回某个值，但是会在算法进行过程中对solverScope中的bestScore和bestSolution直接进行修改（前提是算法发现了更优解）
对于启发式算法，算法的主要求解流程
- 对邻域（当前solution下所有move）进行遍历
- 依据各个move得到的新的solution的得分（score）和算法规则，挑选出合适的move
- 对当前bestSolution进行该move得到新的bestSolution
- 不断执行该步骤直到满足算法的终止条件（比如达到局部最优解、10步之内没有得到更优解、得到了分数大于0的solution、求解时长超过2分钟等）
对于其中的每一步，opta都提供了相应的接口来实现
使用moveSelector，在第三部分中有应用的示例。
for(Move<Solution_> move : moveSelector){
}得分使用scoreDirector获取，scoreDirector通过下面的代码调用
InnerScoreDirector<Solution_, ?> scoreDirector = solverScope.getScoreDirector();调用move.doMove(scoreDirector);可以在workingSolution上进行改变，并返回一个move的反动作，再调用scoreDirector.calculateScore()可以得到分数。
最后，调用undoMove.doMove(scoreDirector)可以将workingSolution退回到初始的状态。
注意，这里所谓的workingSolution在scoreDirector实例中维护，开发者不必关心
Move<Solution_> undoMove = move.doMove(scoreDirector);
Score score = scoreDirector.calculateScore();
undoMove.doMove(scoreDirector);遍历过邻域后，算法能够得到一个move作为nextStep，同时获得它的分数。
进行如下调用，更新bestSolution和相关属性。
stepScope.setScore(maxScore);
doStep(stepScope, nextStep);
stepEnded(stepScope);
phaseScope.setLastCompletedStepScope(stepScope);doStep的内容如下
protected void doStep(CustomStepScope<Solution_> stepScope, Move<Solution_> step) {
Move<Solution_> undoStep = step.doMove(stepScope.getScoreDirector());
predictWorkingStepScore(stepScope, step);
solver.getBestSolutionRecaller().processWorkingSolutionDuringStep(stepScope);
}算法的终止将在下一小节讲解，接口如下。
while(!phaseTermination.isPhaseTerminated(phaseScope))
也就是说本文档会对启发式算法的替换用处更大，如果是实现其他算法，比如粒子群算法，本小节算法的进行可能会有一定的变化
上面说了算法会不断进行直到*当前状态（运行时间、bestScore等）*满足算法的终止条件，optaplanner提供了相应接口，我们可以在配置文件中对termination条件进行配置，在算法代码中只需要调用如下代码即可得知算法是否达到终止条件
phaseTermination.isPhaseTerminated(phaseScope)
- 达到一定时间时停止
- 一定时间内没有最优解更新
- 达到需要的分数
- 走过的step数超过一定值
- 走过的step数表示2.5中步骤2、3的重复次数
- 一定step数内没有最优解更新
- 注意和一定时间内区分
- 其他（不常用）
在配置文件中有两种添加方式
-
全局termination
-
-
写在相应算法中，
-
注意，必须作为算法的第一个子标签
-
配置规则书写见官方文档，链接和目录如下
https://docs.optaplanner.org/8.11.1.Final/optaplanner-docs/html_single/index.html#termination
MoveSelector前面已经讲解过，MoveSelector 的主要功能是在需要的时候创建 Iterator<move> 。优化算法将循环遍历这些步骤的子集。
moveSelector是一个在optaplanner提供的其他算法中经常用的工具
在第三部分的实例中，我们会实践在算法中使用他，这里不细说。
- 该仓库基于仓库进行了一定修改
- 主分支是等待进行算法替换的分支
finish分支是完成本文算法替换的分支
git clone https://github.com/xinwuyun/optaplanner-alter.git接下来的文档基于主分支(main)进行，也可以使用如下命令切换到finish分支直接查看完成后的代码
git checkout finish运行任一示例，以nqueen为例，在IDE中做好运行配置
如果是idea，设置workingDirectory为
/Users/xinwuyun/Documents/code/optaplanner/optaplanner/optaplanner-examples
运行optaplanner-examples/src/main/java/org/optaplanner/examples/nqueens/app/NQueensHelloWorld.java，看一下输出
最后能看到如下结果
结尾展示了棋盘的排布，算法先后使用了构造启发式算法和禁忌搜索
作为示例，这里实现最简单的贪心算法
- 探索初始状态的邻域K
- 在K中选择得分最高的状态；
- 若此状态得分大于当前，则选择此状态为下一个状态；否则算法停止；
- 重复2，3直至最优或算法停止
solver的配置保存在一个xml文件中。nqueen的solver配置保存在org/optaplanner/examples/nqueens/nqueensSolverConfig.xml中。
这个路径在
helloWorld.java指定
xml文件内容如下：
通过配置该文件，可以定义运行示例时使用什么算法和算法次序。这里先后定义了两个算法：1. 构造启发式；2. 局部搜索算法。
两个算法的代码分别在
示例运行过程中，optaplanner对于每个算法会首先构建对应的Factory类，再build每一个算法的实例。使用算法时，调用***Phase.solve。
开始替换算法
在nqueensSolverConfig.xml中的倒数第二行下方添加如下标签，注释掉LocalSeach算法配置
<customPhase>
<customPhaseCommandClass>
org.optaplanner.core.impl.phase.custom.NoChangeCustomPhaseCommand
</customPhaseCommandClass>
</customPhase>接下来的工作主要围绕这里进行optaplanner-core/src/main/java/org/optaplanner/core/impl/phase/custom。
这里有最基础的代码。我们需要在上面增加我们需要的部分
- 在
DefaultCustomPhase.java中定义一个moveSelector
在类中添加如下代码
import org.optaplanner.core.impl.heuristic.selector.move.MoveSelector;
protected MoveSelector<Solution_> moveSelector;
public MoveSelector<Solution_> getMoveSelector() {
return moveSelector;
}
public void setMoveSelector(MoveSelector<Solution_> moveSelector){
this.moveSelector = moveSelector;
}- 在
DefaultCustomPhaseFactory.java创建moveSelector
添加如下方法
import org.optaplanner.core.config.heuristic.selector.common.SelectionCacheType;
import org.optaplanner.core.config.heuristic.selector.common.SelectionOrder;
import org.optaplanner.core.config.heuristic.selector.move.generic.ChangeMoveSelectorConfig;
import org.optaplanner.core.impl.heuristic.selector.move.MoveSelector;
import org.optaplanner.core.impl.heuristic.selector.move.generic.ChangeMoveSelectorFactory;
protected MoveSelector<Solution_> buildMoveSelector(HeuristicConfigPolicy<Solution_> configPolicy) {
// 定义move的缓存类型 https://docs.optaplanner.org/8.9.1.Final/optaplanner-docs/html_single/index.html#generalSelectorFeatures
// JUST_IN_TIME表示不使用缓存
SelectionCacheType defaultCacheType = SelectionCacheType.JUST_IN_TIME;
// 定义实体和变量的选择次序
// https://docs.optaplanner.org/8.9.1.Final/optaplanner-docs/html_single/index.html#selectionOrder
// 按照默认次序（类似顺序）
SelectionOrder defaultSelectionOrder = SelectionOrder.ORIGINAL;
ChangeMoveSelectorConfig changeMoveSelectorConfig = new ChangeMoveSelectorConfig();
MoveSelector<Solution_> moveSelector = new ChangeMoveSelectorFactory<Solution_>(changeMoveSelectorConfig)
.buildMoveSelector(configPolicy, defaultCacheType, defaultSelectionOrder);
return moveSelector;
}
}在buildPhase方法中调用buildMoveSelctor得到moveSelector示例，将其交给phase
phase.setMoveSelector(buildMoveSelector(phaseConfigPolicy));在DefaultCustomPhase.java中的phaseStarted和phaseEnded中分别添加
moveSelector.phaseStarted(phaseScope);和
moveSelector.phaseEnded(phaseScope);- 在
solve中编写算法逻辑
我们在中间注释处编写算法逻辑
上面我们说过使用下面这段代码进行判断
while(!phaseTermination.isPhaseTerminated(phaseScope))本算法要求：如果在邻域中没有发现更优解，则算法停止，转换为配置文件中的语言为
<termination>
<bestScoreLimit>0</bestScoreLimit>
<unimprovedStepCountLimit>1</unimprovedStepCountLimit>
</termination>上面的配置表示，当bestScore$\ge$0时算法停止;当有1个step内没有发现更优解时算法停止(即邻域内没有发现更优解）
// 括号中的内容即可检查上图中的Termination是否成立
while(!phaseTermination.isPhaseTerminated(phaseScope)){
// **********************************
// 遍历邻域，从中挑选一个move作为nextstep
// **********************************
}先import
import org.optaplanner.core.api.score.Score;
import org.optaplanner.core.impl.heuristic.move.Move;
import org.optaplanner.core.impl.heuristic.selector.move.MoveSelector;
import java.util.ArrayList;
import java.util.Collections;将下面代码添加到solve方法中间的注释处
// scoreDirector用于计算得分
InnerScoreDirector<Solution_, ?> scoreDirector = solverScope.getScoreDirector();
while(!phaseTermination.isPhaseTerminated(phaseScope)){
//******
// 固定操作
//******
CustomStepScope<Solution_> stepScope = new CustomStepScope<>(phaseScope);
// 用数组保存领域中和相应得分
List<Move<Solution_>> moves = new ArrayList<>();
List<Score> scores = new ArrayList<>();
// 固定
stepStarted(stepScope);
// 遍历邻域
for(Move<Solution_> move : moveSelector){
// 进行move，会对当前solution进行修改
// 返回一个move的反动作，方便回滚
Move<Solution_> undoMove = move.doMove(scoreDirector);
// 计算改变的solution得分
Score score = scoreDirector.calculateScore();
// 保存得分和move
moves.add(move);
scores.add(score);
// 回滚
undoMove.doMove(scoreDirector);
}
// 选择最高得分的move
Score maxScore = Collections.max(scores);
int i = scores.indexOf(maxScore);
Move<Solution_> nextStep = moves.get(i);
// 将最高分存放到stepScope中
stepScope.setScore(maxScore);
//******
// 固定操作
//******
doStep(stepScope, nextStep);
stepEnded(stepScope);
phaseScope.setLastCompletedStepScope(stepScope);
}doStep应在选定nextStep，并且nextStep可以接受之后调用
protected void doStep(CustomStepScope<Solution_> stepScope, Move<Solution_> step) {
Move<Solution_> undoStep = step.doMove(stepScope.getScoreDirector());
predictWorkingStepScore(stepScope, step);
solver.getBestSolutionRecaller().processWorkingSolutionDuringStep(stepScope);
}运行org.optaplanner.examples.nqueens.app.NQueensHelloWorld#main
注意此时nqueenSolverConfig.xml，注释掉<LocalSearch>
输出如下
根据输出可以看到，替换算法进行了两步后到达局部最优，算法停止。
这些是构造器启发式算法的输出。由于前面我们配置文件中的
localSearch算法，所以示例没有调用localSearch
比如如果我们要实现禁忌搜索，以避免陷入局部最优解。则可以在算法进行过程中维护一个step数组储存最近的若干nextStep，遍历邻域过程中增加一个isAccepted(move/stepScope)，筛选掉禁忌move。
禁忌搜索
optaplanner已经实现了，代码可供参考
封装
上面的描述比较面向过程，较好的方式是定义决定器(Decider)，捕捉器Forager，接受器Acceptor。对于不同算法或者同一算法的不同变体，这些xx器有不同的配置和实现。
比如，我们希望在我们替换的贪婪算法基础上实现禁忌搜索，则可以实现一个Acceptor，其中维护一个step队列，保存最近几个step，实现一个isAccepted方法。
在customPhase中创建一个acceptor实例，遍历邻域时，对每个move调用accoptor.isAccepted(move)
while(!phaseTermination.isPhaseTerminated(phaseScope)){
...
for(move : moveSelector){
if(!accoptor.isAccepted(move)){
continue;
}
...
}
...
}最佳实践参考optapanner实现的LocalSearch算法（及其变体）的实现.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent