难以与 Optaplanner 同时满足硬约束和中约束

Question

我使用 OptaPlanner 6.2 实现了一个传感器调度问题，该问题具有 1 个硬约束、1 个中等约束和 1 个软约束。我遇到的麻烦是，要么我可以在 30 秒左右后满足一些硬约束，然后求解器在满足这些约束的额外分钟终止时取得的进展很小。我不认为这个问题是过度限制的；我也不知道如何帮助本地搜索过程显着提高分数。

我的问题是一个调度问题，我预先计算传感器在求解之前可以观察物体的所有可能时间（间隔）。我将问题建模如下：

硬约束 - 区间不能重叠

 when
   $s1: A( interval!=null,$id: id, $doy : interval.doy, $interval: interval, $sensor: interval.getSensor())
  exists A( id > $id, interval!=null, $interval2: interval, $interval2.getSensor() == $sensor, $interval2.getDoy() == $doy, $interval.getStartSlot() <= $interval2.getEndSlot(), $interval.getEndSlot() >= $interval2.getStartSlot() )
 then
   scoreHolder.addHardConstraintMatch(kcontext,-10000);

中等约束 - 每个分配都应该有一个间隔

when
  A(interval==null)
then
  scoreHolder.addMediumConstraintMatch(kcontext,-100);

软约束-在区间class

中最大化一个property/value

when
  $s1: A( interval!=null)
then
  scoreHolder.addSoftConstraintMatch(kcontext,-1 * $s1.getInterval().getSomeProperty())

A：实体策划class；每个实例都是对特定对象的分配（即具有与间隔 class 中的一个对应的成员 objectid）

间隔：规划变量class，传感器和对象的所有可能间隔（开始时间、停止时间）

在 A 中，我将对 B 实例（间隔）的访问限制为仅与该分配关联的对象的访问。对于我的测试用例，有 40000 个左右的间隔，但每个对象只有几十个。 A 大约有 1100 个实例（因此每个实例有几十个可能的间隔）。

@PlanningVariable(valueRangeProviderRefs = {"intervalRange"},strengthComparatorClass = IntervalStrengthComparator.class, nullable=true)
public Interval getInterval() {
    return interval;
}

@ValueRangeProvider(id = "intervalRange")
public List<Interval> getPossibleIntervalList() {
    return task.getAvailableIntervals();
}

在我的解决方案中 class： //尝试将其注释掉，因为整体区间列表不适用于所有 A @ValueRangeProvider (id="intervalRangeAll") public 列表 getIntervalList() { return 间隔； }

@PlanningEntityCollectionProperty
public List<A> getAList() {
    return AList;
}

我查看了文档并尝试了很多东西。我的问题有点像我看过的护士名单和课程安排示例之间的交叉。我正在使用 FIRST_FIT_DECREASING 构造启发式。

我尝试过的：

在 A.getInterval()
晚接受，禁忌，两者。
基准测试。我没有发现任何问题和平均值
添加 IntervalChangeFactory 作为 moveListFactory。将自定义 ChangeMove 限制为是否可以接受间隔（即是否强制执行 IntervalChangeMove.isDoable 中的硬约束）。

这是一个例子，其中大多数硬约束都没有得到满足，但中等约束是：

[main] INFO org.optaplanner.core.impl.solver.DefaultSolver - Solving  started: time spent (202), best score (0hard/-112500medium/0soft), environment  mode (REPRODUCIBLE), random (WELL44497B with seed 987654321).
[main] INFO org.optaplanner.core.impl.constructionheuristic.DefaultConstructionHeuristicPhase - Construction Heuristic phase (0) ended: step total (1125), time spent (2296), best score (-9100000hard/0medium/-72608soft).
[main] INFO org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase - Local Search phase (1) ended: step total (92507), time spent (30000), best score (-8850000hard/0medium/-74721soft).
[main] INFO org.optaplanner.core.impl.solver.DefaultSolver - Solving ended: time spent (30000), best score (-8850000hard/0medium/-74721soft), average calculate count per second (5643), environment mode (REPRODUCIBLE).

所以我不明白为什么搜索过程无法处理硬约束。由于我所做的所有修补工作，我每秒的任何计算计数都已降至 10000 以下。

Answer 1

如果不是由于分数陷阱（请参阅文档，这是首先要解决的问题），可能是因为它陷入了局部最优并且没有从一个可行的解决方案到另一个可行的解决方案的移动，除了那些没有太大变化的解决方案。有几种方法可以解决这个问题：

添加粗粒度的移动（但仍保留细粒度的移动，例如 ChangeMove！）。您可以添加通用课程粒度移动（例如支柱移动）或添加自定义移动。不要开始做更聪明的 select 或尝试只 select 可行的动作，这是一个坏主意（因为它会杀死你的 ACC 或会限制你的搜索 space）。只需混合粗粒度的动作（=多样化）以补充细粒度的动作（=集约化）。
更好的领域模型 也可能有帮助。 Project Job Scheduling 和 Cheap Time scheduling 示例有一个领域模型，自然会导致更小的搜索 space，同时仍然允许所有可行的解决方案。
增加 Tabu 列表大小、LA 大小或在 SA 起始温度中使用硬约束。但我想你已经用基准测试器试过了。
打开 TRACE 日志记录以查看 optaplanner 的决策。只看达到局部最优后的部分
以后我还会添加Ruin&Recreate招式，这将比自定义招式或更好的领域模型代码少得多（但效率会更低）。

难以与 Optaplanner 同时满足硬约束和中约束

Difficulty satisfying hard and medium constraints simultaneously with Optaplanner

scheduling

constraints

optaplanner