如何打破OptaPlanner中重复违反教师冲突硬约束的局部最优？

一、教师冲突约束是否属于Score Trap？ #

官方示例的这个约束逻辑本身没问题，但要先确认两个关键点：

• 数据可行性：检查是否存在某个教师的课时量超出了可用时段的承载上限（比如教师一天最多能排8节课，但给他安排了9节）。如果数据本身无解，再怎么调算法也达不到0hard。
• 约束计数是否重复：forEachUniquePair默认是无序配对，不会重复计数(A,B)和(B,A)，但可以手动加Joiners.lessThan(Lesson::getId)来强制只统计一次，避免因计数重复导致分数显示异常（比如实际4次冲突却显示-8hard）。建议查看基准测试的约束匹配详情，确认是8个独立冲突还是重复计数。

如果数据可行、计数也没问题，那这个约束本身不是Score Trap，问题出在搜索算法陷入了局部最优。

二、Mimic Selection 和 Nearby Selection 对当前场景有用吗？ #

• Mimic Selection：主要用于联动调整相关实体（比如调整某课时时段时，同步调整同教师的其他课时），单独用它对解决当前的教师冲突帮助有限，配合其他移动选择器可能有辅助作用，但不是破局的核心手段。
• Nearby Selection：作用是缩小搜索范围，聚焦在相邻时段/教室的移动，适合大规模排课问题。如果你的问题规模不大（课时数不多），它的效果不明显；如果规模较大，能提升搜索效率，但对突破当前的局部最优帮助不大。

三、迭代局部搜索（ILS）实现指南 #

OptaPlanner 8.x支持通过配置文件或Java API实现ILS，核心思路是破坏现有解中存在冲突的部分，再用构造启发式重建，具体步骤如下：

1. 配置文件方式（推荐） #

在solverConfig.xml中添加ILS阶段：

<solver>
  <!-- 先跑构造启发式得到初始解 -->
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
  <!-- 迭代局部搜索阶段 -->
  <localSearch>
    <localSearchType>ITERATIVE_LOCAL_SEARCH</localSearchType>
    <!-- 只选择存在教师冲突的课时进行破坏 -->
    <changeMoveSelector>
      <entitySelector>
        <filterClass>com.yourpackage.ConflictTeacherLessonFilter</filterClass>
      </entitySelector>
    </changeMoveSelector>
    <!-- 只接受更优或同等分数的解，避免退化 -->
    <acceptor>
      <acceptorType>HILL_CLIMBING</acceptorType>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
    </forager>
    <!-- 每次破坏8个课时（对应当前的8次冲突），用构造启发式重建 -->
    <phaseCustomProperties>
      <property name="destroySize" value="8"/>
      <property name="recreateType" value="CONSTRUCTION_HEURISTIC"/>
    </phaseCustomProperties>
  </localSearch>
</solver>

需要实现ConflictTeacherLessonFilter来筛选出冲突的课时：

public class ConflictTeacherLessonFilter implements SelectionFilter<Lesson> {
    @Override
    public boolean accept(ScoreDirector<TimeTable> scoreDirector, Lesson lesson) {
        // 检查该课时所属教师是否存在冲突
        return scoreDirector.getConstraintMatchTotalMap().values().stream()
                .filter(total -> "Teacher conflict".equals(total.getConstraintName()))
                .flatMap(total -> total.getConstraintMatchSet().stream())
                .anyMatch(match -> match.getJustificationList().contains(lesson));
    }
}

2. Java API方式 #

如果用代码配置Solver：

SolverFactory<TimeTable> solverFactory = SolverFactory.create(new SolverConfig()
        .withSolutionClass(TimeTable.class)
        .withEntityClasses(Lesson.class)
        .withPhases(
                // 构造启发式阶段
                new ConstructionHeuristicPhaseConfig()
                        .withConstructionHeuristicType(ConstructionHeuristicType.FIRST_FIT_DECREASING),
                // 迭代局部搜索阶段
                new LocalSearchPhaseConfig()
                        .withLocalSearchType(LocalSearchType.ITERATIVE_LOCAL_SEARCH)
                        .withMoveSelectorConfig(new ChangeMoveSelectorConfig()
                                .withEntitySelectorConfig(new EntitySelectorConfig()
                                        .withFilterClass(ConflictTeacherLessonFilter.class)))
                        .withAcceptorConfig(new AcceptorConfig()
                                .withAcceptorType(AcceptorType.HILL_CLIMBING))
                        .withForagerConfig(new ForagerConfig()
                                .withAcceptedCountLimit(1000))
                        .addPhaseCustomProperty("destroySize", 8)
                        .addPhaseCustomProperty("recreateType", "CONSTRUCTION_HEURISTIC")
        ));

关键注意事项 #

• 破坏规模：设置为当前冲突的课时数量（8），精准破坏问题部分，避免过度破坏降低搜索效率。
• 重建策略：用构造启发式重建比随机重建效率更高，能保证重建后的解基础质量。
• 接受策略：HILL_CLIMBING确保只保留更优解，防止解退化。

额外排查建议 #

1. 验证数据可行性：手动尝试给那8个冲突的课时重新分配时段，看是否能找到无冲突的方案。如果手动都做不到，说明数据本身不可行，需要调整课时分配或增加教师/时段资源。
2. 排查其他硬约束：临时禁用其他5个硬约束，看是否能得到0hard解。如果可以，说明其他约束间接导致了教师冲突无法解决，需要逐个排查约束间的矛盾。

内容的提问来源于stack exchange，提问作者bdearg