目前可以公开的一些情报
什么是运筹排班算法?
假设一个工厂场景，该工厂下有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
01. N皇后问题是啥？
约束项：
给出一个N * N的棋盘，问最多可以摆放几个国际象棋中的皇后，他们互不攻击。
Queue可以攻击任意横向、纵向、两个对角线方向上的棋子。
开始照着葫芦画瓢~
葫芦见上期文章
02.初始化子状态类、输入输出域的类、约束打分规则类、测试类
构建最小的子状态类 Queen
@Data
@PlanningEntity
@NoArgsConstructor
public class Queen {
/**
* 固定字段
*/
private Long id;
/**
* 列坐标
*/
@PlanningVariablevalueRangeProviderRefs = "colIdxRange")
private Integer colIdx;
/**
* 行坐标
*/
@PlanningVariablevalueRangeProviderRefs = "rowIdxRange")
private Integer rowIdx;
public Queenint 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 {
@ValueRangeProviderid = "colIdxRange") // 对应 @PlanningVariable下的id
@ProblemFactCollectionProperty // 输入 不变
private List<Integer> colIdxInitList;
@ValueRangeProviderid = "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 paintChessBoardint 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[] defineConstraintsConstraintFactory constraintFactory) {
return new Constraint[]{
// Only hard Constraint
rowConflictCheckconstraintFactory),
colConflictCheckconstraintFactory),
// 加上左右对角线
leftDiagonalConflictCheckconstraintFactory),
rightDiagonalConflictCheckconstraintFactory),
};
}
private Constraint rowConflictCheckConstraintFactory constraintFactory) {
return constraintFactory.fromQueen.class)
.joinQueen.class,
Joiners.equalQueen::getRowIdx),
Joiners.lessThanQueen::getId)
)
.penalize"行约束", HardSoftScore.ONE_HARD);
}
private Constraint colConflictCheckConstraintFactory constraintFactory) {
return constraintFactory.fromQueen.class)
.joinQueen.class,
Joiners.lessThanQueen::getId),
Joiners.equalQueen::getColIdx)
)
.penalize"列约束", HardSoftScore.ONE_HARD);
}
private Constraint leftDiagonalConflictCheckConstraintFactory constraintFactory) {
return constraintFactory.fromQueen.class)
.joinQueen.class,
Joiners.lessThanQueen::getId),
Joiners.equalQueen::getLeftDiagonalConflictCheck)
)
.penalize"右对角线 约束", HardSoftScore.ONE_HARD);
}
private Constraint rightDiagonalConflictCheckConstraintFactory constraintFactory) {
return constraintFactory.fromQueen.class)
.joinQueen.class,
Joiners.lessThanQueen::getId),
Joiners.equalQueen::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.addi);
rowIdxInitList.addi);
}
for int i = 0; i < queenNum; i++) {
queenList.addnew Queeni));
}
ChessBoard problem = new ChessBoardcolIdxInitList, rowIdxInitList, queenList, null);
UUID problemId = UUID.randomUUID);
// Submit the problem to start solving
SolverJob<ChessBoard, UUID> solverJob = nQueensPuzzleSolverManager.solveproblemId, problem);
ChessBoard solution;
try {
// Wait until the solving ends
solution = solverJob.getFinalBestSolution);
} catch InterruptedException | ExecutionException e) {
throw new IllegalStateException">>>>>Solving failed.", e);
}
System.out.printlnsolution);
System.out.println"
");
solution.paintChessBoardn);
}
}
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加速