難以滿足與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同時硬和中等約束條件

回答

相關問題