OptaPlanner如何移动无约束冲突实体以获取更优解？

问题描述 #

构造启发式阶段，规划器为首个MeetingAssignment实体找到无硬/中/软约束冲突的最优分配，但其余实体存在各类约束冲突。进入局部搜索阶段后，该首个实体被固定不再移动，而调整它的时隙反而能减少整体约束冲突数，得到更优解。尝试更换构造启发式算法（如first_fit_decrease）但因所有实体等价，无法定义难度比较器；查阅自定义移动文档，但不知如何实现“仅在有硬约束冲突时触发、仅针对无冲突的固定实体”的移动逻辑。

解决方案 #

1. 更换构造启发式为first_fit（无需难度比较器） #

既然所有实体等价，直接使用first_fit构造启发式即可。该算法按实体顺序依次分配首个可行的时隙，不会为首个实体刻意寻找“完美无冲突”的解，后续局部搜索阶段所有实体都处于可调整状态，自然能通过常规移动优化整体解。

配置示例：

<constructionHeuristic>
  <firstFit />
</constructionHeuristic>

2. 自定义过滤式移动选择器，精准控制可移动实体 #

如果必须保留原构造启发式的分配逻辑，可通过FilteredMoveSelector实现需求：

• 过滤条件1：仅允许无硬/中/软约束冲突的实体（即那个首个MeetingAssignment）生成移动
• 过滤条件2：仅当当前解存在硬约束冲突时，启用该移动选择器

实现步骤：

1. 编写移动过滤器类，实现MoveFilter接口：

public class TargetedEntityMoveFilter implements MoveFilter<MeetingSchedule> {
    @Override
    public boolean accept(ScoreDirector<MeetingSchedule> scoreDirector, Move<MeetingSchedule> move) {
        // 检查当前解是否存在硬约束冲突
        Score score = scoreDirector.getScore();
        if (score.getHardScore() == 0) {
            return false; // 无硬冲突时不触发
        }
        // 检查移动涉及的实体是否为无任何约束冲突的实体
        for (Object entity : move.getPlanningEntities()) {
            MeetingAssignment assignment = (MeetingAssignment) entity;
            // 通过ScoreDirector计算单个实体的约束冲突
            Score entityScore = scoreDirector.calculateScoreFromScratch(Collections.singletonList(assignment));
            if (entityScore.getHardScore() == 0 && entityScore.getMediumScore() == 0 && entityScore.getSoftScore() == 0) {
                return true;
            }
        }
        return false;
    }
}

2. 在局部搜索配置中添加该移动选择器，与常规移动选择器组合使用：

<localSearch>
  <unionMoveSelector>
    <!-- 常规移动选择器，处理有冲突的实体 -->
    <changeMoveSelector>
      <filterClass>com.yourpackage.ConflictedEntityFilter</filterClass>
    </changeMoveSelector>
    <!-- 自定义移动选择器，处理无冲突的目标实体 -->
    <changeMoveSelector>
      <filterClass>com.yourpackage.TargetedEntityMoveFilter</filterClass>
    </changeMoveSelector>
  </unionMoveSelector>
</localSearch>

3. 检查是否误设置了不可移动实体选择器 #

确认局部搜索配置中没有设置immovableEntitySelector将首个实体标记为不可移动。若存在相关配置，移除即可让所有实体参与局部搜索的移动调整。

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