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

我已经使用OptaPlanner 6.2实现了一个传感器调度问题，它有1个硬约束，1个中等约束和1个软约束。我遇到的麻烦是要么在30秒左右之后能够满足一些困难的约束，然后求解器在满足约束的情况下几乎没有进展，并需要额外的几分钟终止。我认为这个问题没有过度束缚，我也不知道如何帮助本地搜索过程显着提高分数。难以满足与Optaplanner同时硬和中等约束条件

我的问题是一个调度问题，其中我预先计算了传感器在解决问题之前可以观察对象的所有可能时间（间隔）。无间隔可以重叠

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);

软约束

硬约束：我如下建模的问题 - 最大化Interval类别中的特性/值
A：实体规划类;

答：实体规划类;每个实例都是对特定对象的赋值（即具有与Interval类中的对象相对应的成员objectid）

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

在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(); 
}

在我的解决方案类： //已经尝试评论了这一点，因为整个间隔列表并不适用于所有的A @ValueRangeProvider（ID = “intervalRangeAll”）公开名单getIntervalList（）{ 回报间隔; }

@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以下。

来源

2015-10-20 Tony B.

请参阅文档中的“分数陷阱”：硬约束可能应该惩罚重叠时间，而不是固定的权重（无论它们是重叠还是重叠）。 –

我将硬约束惩罚更改为-10，这没有什么区别。也许我误解了你的意思，“惩罚重叠的时间，而不是固定的权重”。在文档中描述的3种方式中，我已经在做第一种。我尝试了第二种方法，将重叠惩罚约束规则用作媒介，然后使用软约束（同时保持难度），这没有什么不同。第三种方式更多参与，但除非您有其他建议，否则我会看一看。 –

将其更改为-10仍然使其成为固定重量，无论重叠多少时间。不知道我如何改进文档。 IIRC的一个培训邮编实验室处理这个问题，请参阅optaplanner.org - >学习 - >培训。 –

如果不是由于分数陷阱（见文档，这是修复的第一件事），这可能是因为它被卡在局部最优，也没有移动，从1个可行的方案去到另一个除非那些变化不大的可行解决方案。有几种方法来处理是：

添加粗粒度移动（但仍留下了细粒度的动作，如在ChangeMove！）。您可以添加通用球场粒度移动（如柱子移动）或添加定制移动。不要开始制作更聪明的选择器，只尝试选择可行的动作，这是一个坏主意（因为它会杀死你的ACC或将限制你的搜索空间）。只要混合粒度运动（=多样化）来补充细粒度运动（=强化）。
A 更好的域名模式也可能有帮助。项目工作调度和廉价时间调度的例子有一个领域模型，这自然会导致更小的搜索空间，同时仍然允许所有可行的解决方案。
增加禁忌列表大小，LA大小或在SA起始温度中使用硬约束。但我认为你已经与基准测试者一起尝试过了。
打开TRACE登录查看optaplanner的决策。只有在达到局部最佳状态后才能看到该部分。在未来，我还会添加破坏&重新创建移动，这将比定制移动或更好的域模型少得多（但效率会更低）。

来源

2015-10-21 12:16:58

这是一个有用的名单，将有长期的好处。我曾尝试过一些大小的实验 - 你的子弹＃3。我只是简单地采取了一种简单的方法，其中只包括重叠间隔的严格限制。然后我意识到测试数据严重过度约束，并且解算器不能指望好。 –

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

回答

相关问题