目前可以公开的一些情报
什么是运筹排班算法?
假设一个工厂场景，该工厂下有100个工人需要排班，全排列会有100！约等于 (10^{158})种结果，此类问题也属于NP问题；粗略计算一个地球年不到(10^8)秒，假设每秒可以运算(10^{10})种情况，也需要(10^{140})个地球年来跑完全部的结果集，进而得到全局最优解。
除此之外，考虑三班倒，有五条生产线，另外需要考虑约束：连上限制、休息限制、工种限制、生产计划限制、熟练度限制、请假换班、加班、公平性考虑等约束考虑；假设为每个个体受限于10种约束，100个人，会有1000个约束考虑，这时，再来人工来手动排班难度极大。
运筹学是一门通过数学统筹方法来尝试解决此类NP问题的学科，可以通过一些数学手段来缩减求解问题的规模，减少搜索范围；其主要分支有：线性规划、非线性规划、整数规划、几何规划、大型规划、动态规划、图论、网络理论、博弈论、决策论、排队论、存贮论、搜索论等。。
OptaPlanner的初步作用?
通过启发式算法，诸如暴力搜索、元启发式算法、进化算法、蚁群算法、粒子群算法、分支界定算法等搜索算法来找到一个局部近似解；使用惩罚项来构建约束，在规定的可以接受的时间范围，通过尽量降低惩罚分数，来得到一个较为最优的解。
原文地址
https://docs.optaplanner.org/7.45.0.Final/optaplanner-docs/html_single/index.html#nQueens
01. N皇后问题是啥？
约束项：
- 给出一个N * N的棋盘，问最多可以摆放几个国际象棋中的皇后，他们互不攻击。
- Queue可以攻击任意横向、纵向、两个对角线方向上的棋子。
开始照着葫芦画瓢~
葫芦见上期文章
02.初始化子状态类、输入输出域的类、约束打分规则类、测试类
构建最小的子状态类 Queen
@Data
@PlanningEntity
@NoArgsConstructor
public class Queen {
/**
* 固定字段
*/
private Long id;
/**
* 列坐标
*/
@PlanningVariable(valueRangeProviderRefs = "colIdxRange")
private Integer colIdx;
/**
* 行坐标
*/
@PlanningVariable(valueRangeProviderRefs = "rowIdxRange")
private Integer rowIdx;
public Queen(int i) {
id = (long) i;
}
@Override
public String toString() {
return String.format("Queen[id=%d: %d,%d]", id, colIdx, rowIdx);
}
public Integer getLeftDiagonalConflictCheck() {
return colIdx + rowIdx;
}
public Integer getRightDiagonalConflictCheck() {
return colIdx - rowIdx;
}
}
构建输入输出域
@Data
@NoArgsConstructor
@AllArgsConstructor
@PlanningSolution
public class ChessBoard {
@ValueRangeProvider(id = "colIdxRange") // 对应 @PlanningVariable下的id
@ProblemFactCollectionProperty // 输入 不变
private List<Integer> colIdxInitList;
@ValueRangeProvider(id = "rowIdxRange") // 对应 @PlanningVariable下的id
@ProblemFactCollectionProperty // 输入 不变
private List<Integer> rowIdxInitList;
/**
* 输入时: 无
* <p>
* 输出时:
* 输出结果存储在在 col/row idx
*/
@PlanningEntityCollectionProperty // 输出 结果域 (在计算过程中会一直进行尝试,直到尝试到最优解)
private List<Queen> queenList;
@PlanningScore
private HardSoftScore score;
@Override
public String toString() {
return "ChessBoard{" +
",
colIdxInitList=" + colIdxInitList +
",
rowIdxInitList=" + rowIdxInitList +
",
queenList=" + queenList +
",
score=" + score +
'}';
}
/**
* 绘制棋盘
*/
public void paintChessBoard(int n) {
System.out.println("打印棋盘,最后一行第1个点为(0,0),12点方向为x轴正轴方向
");
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
boolean flag = false;
for (Queen queen : queenList) {
if (queen.getRowIdx() == i && queen.getColIdx() == j) {
System.out.print(" * ");
flag = true;
}
}
if (!flag) {
System.out.print(" - ");
}
}
System.out.print("
");
}
}
}
约束（惩罚项）类 : 四种不合法的类型
public class QueueConstraintProvider implements ConstraintProvider {
@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
return new Constraint[]{
// Only hard Constraint
rowConflictCheck(constraintFactory),
colConflictCheck(constraintFactory),
// 加上左右对角线
leftDiagonalConflictCheck(constraintFactory),
rightDiagonalConflictCheck(constraintFactory),
};
}
private Constraint rowConflictCheck(ConstraintFactory constraintFactory) {
return constraintFactory.from(Queen.class)
.join(Queen.class,
Joiners.equal(Queen::getRowIdx),
Joiners.lessThan(Queen::getId)
)
.penalize("行约束", HardSoftScore.ONE_HARD);
}
private Constraint colConflictCheck(ConstraintFactory constraintFactory) {
return constraintFactory.from(Queen.class)
.join(Queen.class,
Joiners.lessThan(Queen::getId),
Joiners.equal(Queen::getColIdx)
)
.penalize("列约束", HardSoftScore.ONE_HARD);
}
private Constraint leftDiagonalConflictCheck(ConstraintFactory constraintFactory) {
return constraintFactory.from(Queen.class)
.join(Queen.class,
Joiners.lessThan(Queen::getId),
Joiners.equal(Queen::getLeftDiagonalConflictCheck)
)
.penalize("右对角线 约束", HardSoftScore.ONE_HARD);
}
private Constraint rightDiagonalConflictCheck(ConstraintFactory constraintFactory) {
return constraintFactory.from(Queen.class)
.join(Queen.class,
Joiners.lessThan(Queen::getId),
Joiners.equal(Queen::getRightDiagonalConflictCheck)
)
.penalize("左对角线 约束", HardSoftScore.ONE_HARD);
}
}
测试类
/**
* 记得保持在同一启动类的目录下
*/
@SpringBootTest
class NQueenOptaplannerApplicationTests {
@Resource
private SolverManager<ChessBoard, UUID> nQueensPuzzleSolverManager;
/**
* 01 N皇后测试
*/
@Test
void testNQueensPuzzle() {
int n = 5;
int queenNum = 4;
/////////////////////////////////////////////////////////////////////
List<Integer> colIdxInitList = new ArrayList<>();
List<Integer> rowIdxInitList = new ArrayList<>();
List<Queen> queenList = new ArrayList<>();
for (int i = 0; i < n; i++) {
colIdxInitList.add(i);
rowIdxInitList.add(i);
}
for (int i = 0; i < queenNum; i++) {
queenList.add(new Queen(i));
}
ChessBoard problem = new ChessBoard(colIdxInitList, rowIdxInitList, queenList, null);
UUID problemId = UUID.randomUUID();
// Submit the problem to start solving
SolverJob<ChessBoard, UUID> solverJob = nQueensPuzzleSolverManager.solve(problemId, problem);
ChessBoard solution;
try {
// Wait until the solving ends
solution = solverJob.getFinalBestSolution();
} catch (InterruptedException | ExecutionException e) {
throw new IllegalStateException(">>>>>Solving failed.", e);
}
System.out.println(solution);
System.out.println("
");
solution.paintChessBoard(n);
}
}
03. 测试
测试N=5，Queen=4时,是否存在对应的合法局面
默认使用的LocalSearch算法，跑了35917轮, 找到一个合理解, 返回; 打印如下
打印棋盘,最后一行第1个点为(0,0),12点方向为x轴正轴方向
- - * - -
- - - - -
- * - - -
- - - * -
* - - - -
测试N=5，QueenNum=5时,是否存在对应的合法局面
默认使用的LocalSearch算法，跑了36689轮, 找到一个合理解, 返回; 打印如下
( Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (14519/sec), phase total (2), environment mode (REPRODUCIBLE).)
打印棋盘,最后一行第1个点为(0,0),12点方向为x轴正轴方向
- - * - -
- - - - *
- * - - -
- - - * -
* - - - -
测试N=10，QueenNum=10时,是否存在对应的合法局面
Local Search phase (1) ended: time spent (5000ms), best score (-1hard/0soft), score calculation speed (12470/sec), step total (32526).
这时不存在对应的合法局面, 找到的局部最优解为-1hard/0soft，意思是违反了一个硬约束，打印局部最优解如下：
打印棋盘,最后一行第1个点为(0,0),12点方向为x轴正轴方向
- - - - - - - - - *
- - * - - - - - - -
- - - - - - * - - -
- - - * - - - - - -
- - - - - - - * - -
- - - - - - - * - -
- - - - * - - - - -
* - - - - - - - - -
- - - - - * - - - -
- - - - - - - - * -
测试N=10，QueenNum=10时,加大搜索时间到30s,再次尝试:
更改application.properties即可:
# The solver runs only for 5 seconds to avoid a HTTP timeout in this simple implementation.
# It's recommended to run for at least 5 minutes ("5m") otherwise.
optaplanner.solver.termination.spent-limit=30s
logging.level.org.optaplanner=debug
再次尝试，找到一个最优解 (0hard/0soft)，没有违反任何约束
DefaultLocalSearchPhase : Local Search phase (1) ended: time spent (30000), best score (0hard/0soft), score calculation speed (14415/sec), step total (236831).
打印棋盘,最后一行第1个点为(0,0),该点的12点方向为x轴正轴方向————
* - - - - - - - - -
- - - - - - - - - *
- - - - - - * - - -
- - - - * - - - - -
- - - - - - - * - -
- * - - - - - - - -
- - - - - - - - * -
- - * - - - - - - -
- - - - - * - - - -
- - - * - - - - - -
04. 最后
- N皇后的问题随着棋盘规则的增加，搜索难度也会大幅提升（NP问题），目前除了量子计算外，解决NP问题的一个手段就是数学武器。
- 局部搜索（Local Search）是解决最优化问题的一种启发式算法。因为对于很多复杂的问题，求解最优解的时间可能是极其长的。因此诞生了各种启发式算法来退而求其次寻找次优解，局部搜索就是其中一种。它是一种近似算法（Approximate algorithms）。
局部搜索算法是从爬山法改进而来的。简单来说，局部搜索算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。
引用链接: https://www.cnblogs.com/dengfaheng/p/9245559.html - 后续要加快速度，英文文档看着还是比较费劲的（单词都认识、句子可以读通顺，但理解起来就比较困难了），没多时间了，下周就要开始投入生产了；领导说，这个新项目的难点不是缺人力或者缺时间，而是是否存在有效解的问题，如何快速判断我们的算法是否值得继续优化等问题。
- 下一步：
- OPTA怎么选择其他的算法，目前使用的只有LS
- 怎么快速判断是否存在解（解空间）
- 怎么优化
- Boot的多线程计算
- 是否可以借助GPU加速