Optaplanner：隨機很低「平均每次calcultate數第二」並聯

解決我使用Optaplanner解決一個比較小的優化問題時。對於我的用例，需要進行許多這樣的優化，但這就是爲什麼我開始並行運行它們的原因。並行性基於Java 8'parallel stream。它不允許控制要使用的實際線程數，但我相信它是基於可用的CPU數量。Optaplanner：隨機很低「平均每次calcultate數第二」並聯

對於大多數求解器的運行，這似乎很好地工作，但我注意到，我有時得到了只有當這個問題被單獨運行，這是不可重複的單次運行無效的解決方案。

檢查日誌後，我注意到，「平均每秒計算次數」非常低無效的解決方案，同時罰款等運行。事實上，無效溶液竟是（天真地構建的）初始溶液：

[rkJoinPool.commonPool-worker-6] (DefaultSolver.java:203)  Solving started: time spent (0), best score (-5hard/-2medium/168soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). 
[rkJoinPool.commonPool-worker-6] (DefaultConstructionHeuristicPhase.java:158) Construction Heuristic phase (0) ended: step total (0), time spent (1), best score (-5hard/-2medium/233soft). 
[rkJoinPool.commonPool-worker-4] (DefaultSolver.java:203)  Solving started: time spent (1), best score (-5hard/-1medium/579soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). 
[rkJoinPool.commonPool-worker-4] (DefaultConstructionHeuristicPhase.java:158) Construction Heuristic phase (0) ended: step total (0), time spent (1), best score (-5hard/-1medium/617soft). 
[rkJoinPool.commonPool-worker-5] (DefaultSolver.java:203)  Solving started: time spent (1), best score (-6hard/-3medium/137soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). 
[rkJoinPool.commonPool-worker-7] (DefaultLocalSearchPhase.java:152) Local Search phase (1) ended: step total (42), time spent (704), best score (0hard/0medium/808soft). 
[rkJoinPool.commonPool-worker-4] (DefaultLocalSearchPhase.java:152) Local Search phase (1) ended: step total (22), time spent (218), best score (0hard/0medium/1033soft). 
[rkJoinPool.commonPool-worker-5] (DefaultSolver.java:238)  Solving ended: time spent (210), best score (-6hard/-3medium/137soft), average calculate count per second (4), environment mode (REPRODUCIBLE). 
[rkJoinPool.commonPool-worker-7] (DefaultSolver.java:238)  Solving ended: time spent (746), best score (0hard/0medium/808soft), average calculate count per second (25256), environment mode (REPRODUCIBLE). 
[rkJoinPool.commonPool-worker-4] (DefaultSolver.java:238)  Solving ended: time spent (219), best score (0hard/0medium/1033soft), average calculate count per second (30461), environment mode (REPRODUCIBLE).

通知線程4和7如何產生良好的結果與25-30k ACCS，而螺紋5產生的無效結果，只用來4個ACCS （考慮到200ms終止超時，我假設實際上只採取了一個步驟）。

以下配置使用了哪個使用benchmarker確定（儘管在單個線程設置）：

<termination> 
    <millisecondsSpentLimit>2000</millisecondsSpentLimit> 
    <unimprovedMillisecondsSpentLimit>200</unimprovedMillisecondsSpentLimit> 
</termination> 
<constructionHeuristic> 
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType> 
</constructionHeuristic> 
<localSearch> 
    <localSearchType>HILL_CLIMBING</localSearchType> 
</localSearch>

我假定這個問題有與幾個解算器並行運行的事實做同時使用基於時間的終止標準。終止時間是基於「掛鐘時間」還是實際CPU時間？並行運行時

是使用基於時間的終止條件不是個好主意？這似乎是使用所有可用計算能力的最佳方式。單個解算器看起來隨機會出現什麼問題只能執行這麼幾個步驟？

來源

2017-08-16 geld0r

你想做什麼？多賭注解決？爬坡通常不如Tabu Search，Late Acceptance等。 –

我正在嘗試從可用團隊中構建一個足球隊名單。這是一個模擬的一部分，其中這是反覆進行各種團隊和比賽。我將不得不再次考慮所提到的meta啓發式 - 我認爲它們在基準測試中完全不起作用。 – geld0r

TS和LA做。 SA不需要額外的配置。 –

millisecondsSpentLimit和unimprovedMillisecondsSpentLimit基於掛鐘時間，而不是實際的CPU時間。由於這些作業可能會在IO下阻塞（調用Solver.solve()時不是這種情況），因此並行流不會將線程數限制爲CPU的數量。我更喜歡使用線程池大小爲Math.max(1, Runtime.getRuntime().availableProcessors() - 2)的ExecutorService。

來源

2017-08-17 13:39:03

我會試試這個。說實話，我只使用基於流的並行性，因爲它是最容易實現的。作爲替代方案，使用基於步驟的終止標準可以更好地工作，如此處所述？ https://docs.optaplanner.org/7.1.0.Final/optaplanner-docs/html_single/index.html#stepCountTermination – geld0r

肯定會。雖然scoreCalucationLimit在TS和LA之間可能更公平（因爲TS慢速步進，LA快速步進）。 –

我重新（並擴展了）我的基準測試，尤其是專注於爲每個元啓發式找到一個好的配置。事實證明，禁忌搜索爲我的問題提供了更可靠的結果（儘管爬山和其他人並沒有太多糟糕）。我最終沒有選擇scoreCalculationLimit，而只是500ms的unimprovedMillisecondsLimit。有了這種配置，我再也沒有看到這個問題。關於流和線程數量的話題，我遵循這裏的建議：https://stackoverflow.com/a/22269778/2574340 – geld0r

Optaplanner：隨機很低「平均每次calcultate數第二」並聯

回答

相關問題