OptaPlanner REPRODUCIBLE模式下Tabu搜索步得分持续下降

问题表现 #

基于约束流实现过约束排班问题的增量计分计算时，出现环境模式相关的异常表现：

• 环境模式设为REPRODUCIBLE时，局部搜索性能极差
• 环境模式设为FAST_ASSERT时，程序运行正常

基准测试使用如下配置：

<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark"
                  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                  xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">

    <benchmarkDirectory>/Users/martijn/Downloads/benchmark</benchmarkDirectory>
    <inheritedSolverBenchmark>
        <solver>
            <solutionClass>nl.pompkracht.rosteringengine.optaplanner.adapter.Roster</solutionClass>
            <entityClass>nl.pompkracht.rosteringengine.optaplanner.adapter.ShiftAssignment</entityClass>
            <domainAccessType>GIZMO</domainAccessType>
            <scoreDirectorFactory>
                <constraintProviderClass>nl.pompkracht.rosteringengine.optaplanner.adapter.RosterConstraintProvider
                </constraintProviderClass>
            </scoreDirectorFactory>
            <termination>
                <minutesSpentLimit>1</minutesSpentLimit>
            </termination>
            <constructionHeuristic>
                <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
            </constructionHeuristic>
        </solver>
    </inheritedSolverBenchmark>

    <solverBenchmark>
        <name>Fast assert</name>
        <solver>
            <environmentMode>FAST_ASSERT</environmentMode>
            <localSearch>
                <localSearchType>TABU_SEARCH</localSearchType>
            </localSearch>
        </solver>
    </solverBenchmark>
    <solverBenchmark>
        <name>Reproducible</name>
        <solver>
            <environmentMode>REPRODUCIBLE</environmentMode>
            <localSearch>
                <localSearchType>TABU_SEARCH</localSearchType>
            </localSearch>
        </solver>
    </solverBenchmark>

</plannerBenchmark>

实际运行观测到：FAST_ASSERT模式下medium得分随运行时间逐步提升，REPRODUCIBLE模式无该现象。

开启debug日志后可观测到：REPRODUCIBLE模式下步得分持续下降，始终无法找到新的最优得分：

2022-07-07 19:32:09.125  INFO 32658 --- [nchmarkThread-1] .c.i.c.DefaultConstructionHeuristicPhase : Construction Heuristic phase (0) ended: time spent (648), best score (0hard/-47medium/-281887soft), score calculation speed (9232/sec), step total (288).
2022-07-07 19:32:09.444 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (0), time spent (967), score (-1hard/-47medium/-279647soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1000), picked move ...
2022-07-07 19:32:09.574 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (1), time spent (1097), score (-14hard/-46medium/-281215soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1007), picked move ...
2022-07-07 19:32:09.701 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (2), time spent (1224), score (-29hard/-47medium/-279567soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1016), picked move ...
2022-07-07 19:32:09.818 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (3), time spent (1341), score (-36hard/-47medium/-279567soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1018), picked move ...
2022-07-07 19:32:09.952 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (4), time spent (1475), score (-45hard/-47medium/-279567soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1027), picked move ...
2022-07-07 19:32:10.084 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (5), time spent (1607), score (-53hard/-47medium/-279567soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1038), picked move ...
2022-07-07 19:32:10.226 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (6), time spent (1749), score (-69hard/-47medium/-279439soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1051), picked move ...
2022-07-07 19:32:10.370 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (7), time spent (1893), score (-74hard/-48medium/-276959soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1064), picked move ...
2022-07-07 19:32:10.511 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (8), time spent (2034), score (-91hard/-48medium/-274943soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1061), picked move ...
2022-07-07 19:32:10.647 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (9), time spent (2170), score (-96hard/-48medium/-275199soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1069), picked move ...
2022-07-07 19:32:10.781 DEBUG 32658 --- [nchmarkThread-1] o.o.c.i.l.DefaultLocalSearchPhase        :     LS step (10), time spent (2304), score (-106hard/-47medium/-277375soft),     best score (0hard/-47medium/-281887soft), accepted/selected move count (1000/1086), picked move ...

最初疑问：该异常是否由得分约束编写问题导致？

定位过程 #

经逐步排查，异常行为可锁定到如下单条约束实现：

fun simultaneousAssigmentConflict(constraintFactory: ConstraintFactory): Constraint =
    constraintFactory.forEach(ShiftConflict::class.java).join(
        ShiftAssignment::class.java, Joiners.equal({ it -> it.shiftOne }, { it.shift.shiftId })
    ).ifExists(ShiftAssignment::class.java,
        Joiners.equal({ conflict, _ -> conflict.shiftTwo }, { it.shift.shiftId }),
        Joiners.filtering { _, assignmentOne, assignmentTwo ->
            assignmentOne.worker?.workerId?.let { it == assignmentTwo.worker?.workerId } ?: false
        }).penalize("Assignment of other shift during this shift or during resting period", ONE_HARD)   

验证两种调整方式均可让REPRODUCIBLE模式下局部搜索恢复正常：

• 将constraintFactory.forEach替换为已废弃的constraintFactory.from方法
• 将ifExists过滤器替换为join操作，调整后代码如下：

fun simultaneousAssigmentConflict(constraintFactory: ConstraintFactory): Constraint =
    constraintFactory.forEach(ShiftConflict::class.java)
        .join(ShiftAssignment::class.java, Joiners.equal({ it -> it.shiftOne }, { it.shift.shiftId })).join(
            ShiftAssignment::class.java,
            Joiners.equal({ conflict, _ -> conflict.shiftTwo }, { it.shift.shiftId }),
            Joiners.filtering { _, assignmentOne, assignmentTwo ->
                assignmentOne.worker?.workerId?.let { it == assignmentTwo.worker?.workerId } ?: false
            }).penalize("Assignment of other shift during this shift or during resting period", ONE_HARD)

根本原因 #

经OptaPlanner核心开发人员溯源确认：

这是Drools的上游缺陷，相关修复已在上游提交，预计合入OptaPlanner 8.25.0.Final版本。

内容的提问来源于stack exchange，提问作者Martijn van der Woud