按規則分配資源 - 模擬退火是否合適？

Question

我想設計一個可以根據規則分配資源的應用程序。我相信模擬退火是可行的，但我不太熟悉，我想知道是否有可能適用的替代算法。例如，如果我有一個網格，並且我可以爲網格中的每個單元着色，我想設計一個算法，爲如下規則集找到最佳或接近最佳的解決方案：

• 1000×1000網格
• 必須將500個紅細胞，500個藍細胞，1000個綠色細胞
• 紅細胞必須接觸另一個紅細胞
• 一個藍色的電池不能接觸到另一個藍細胞
• 綠色小區可以僅沿邊緣
• 安排可以基於從上左上角

着色細胞的平均距離進行評分被放置會模擬退火適合這個問題？我需要一種可以快速可靠地計算解決方案的算法（從幾秒到幾分鐘）。

Answer 1

模擬退火將獲得接近最優解相當快的。但是，正確實施模擬退火（這不是太多的代碼）可能非常具有挑戰性。許多人（包括過去的我自己）都錯誤地實現了它，認爲他們做得正確，並且認爲算法不太好。

替代算法是禁忌搜索，遺傳算法，單純形，...

下面是你的約束會在Drools Planner喜歡（Java，開源，ASL）：

rule "A red cell must be touching another red cell" 
when 
    // There is a cell assignment of color red 
    $a1: CellAssignment(color = RED, $x1 : x, $y1 : y) 
    // There is no other red cell a neighbor of it 
    not CellAssignment(color = RED, eval(MyDistanceHelper.distance(x, y, $x1, $y1) == 1)) 
then 
    insertLogical(new IntConstraintOccurrence(
      "A red cell must be touching another red cell", 
      ConstraintType.NEGATIVE_HARD, 1, // weight 1 
      $a1)); 
end 

rule "A blue cell must not be touching another blue cell" 
when 
    // There is a cell assignment of color blue 
    $a1: CellAssignment(color = BLUE, $x1 : x, $y1 : y) 
    // There is another blue cell a neighbor of it 
    $a2: CellAssignment(color = BLUE, eval(MyDistanceHelper.distance(x, y, $x1, $y1) == 1)) 
then 
    insertLogical(new IntConstraintOccurrence(
      "A blue cell must not be touching another blue cell", 
      ConstraintType.NEGATIVE_HARD, 1, // weight 1 
      $a1, $a2)); 
end 

... 

現在最有趣的部分是：一旦你有你的分數的規則，你可以扔掉一些算法（禁忌搜索，模擬退火......）（見Benchmarker支持），並使用最好的生產。參考手冊中的更多信息。

Answer 2

這基本上是一個約束滿足問題，我不希望模擬退火在合理的時間內接近最優。但是，它可能會讓您很快就達不到最佳解決方案，因此無論何時您都可能會終止。這就是說，如果你想解決這個問題，到目前爲止最好的方法是使用某種CSP解算器。我使用IBM CPLEX OPL對其進行了編碼，將其編譯爲整數線性程序（ILP）並由CPLEX解算器解決。如果你在學術界，你可以免費獲得一份CPLEX，如果你不是，你可以在GLPK中做一個非常類似的事情。您也可以在一段固定的時間後終止許多ILP求解器，並獲得目前爲止的最佳解決方案。

此外，您可以爲此特定設置進行多項加速操作。首先，綠色節點可以從問題中消除，它們總是沿着頂部和左邊緣排列起來，如果與紅色/藍色相比，總是會有如此多的綠色，那麼放入藍色或紅色的邊緣。這些更改使得求解器（對於1000x1000網格）能夠在10秒內達到最佳值的7％，但在15分鐘後仍未找到實際的最佳分配。

如果您有興趣，下面是一個100x100網格的OPL代碼，包含100個綠色，50個紅色，50個藍色。

using CPLEX; 
dvar int grid[0..102][0..102][0..2] in 0..1; 
minimize (sum(i in 1..101, j in 1..101, k in 0..2) grid[i][j][k]*(i*i + j*j)); 

subject to { 

// edge conditions so I can always index i-1 and i+1 in all cases 
forall(i in 0..102) (sum(j in 0..2) (grid[i][0][j] + grid[i][102][j])) == 0; 
forall(i in 0..102) (sum(j in 0..2) (grid[0][i][j] + grid[102][i][j])) == 0; 

// only one color per cell 
forall(i in 1..101, j in 1..101) 
    (sum(k in 0..2) grid[i][j][k]) <= 1; 

// 50 red 
sum(i in 1..101, j in 1..101) grid[i][j][0] == 50; 

// 100 green 
sum(i in 1..101, j in 1..101) grid[i][j][1] == 100; 

// 50 blue 
sum(i in 1..101, j in 1..101) grid[i][j][2] == 50; 

// green must be on the edge (not on not-edge) 
forall(i in 2..100, j in 2..100) 
    grid[i][j][1] == 0; 

// red must be next to another red 
forall(i in 1..101, j in 1..101) 
    (1 - grid[i][j][0]) + grid[i+1][j][0] + grid[i-1][j][0] + grid[i][j+1][0] + grid[i][j-1][0] >= 1; 

// blue cannot be next to another blue 
forall(i in 1..101, j in 1..101) 
    (1-grid[i][j][2]) + (1-grid[i+1][j][2]) >= 1; 
forall(i in 1..101, j in 1..101) 
    (1-grid[i][j][2]) + (1-grid[i-1][j][2]) >= 1; 
forall(i in 1..101, j in 1..101) 
    (1-grid[i][j][2]) + (1-grid[i][j+1][2]) >= 1; 
forall(i in 1..101, j in 1..101) 
    (1-grid[i][j][2]) + (1-grid[i][j-1][2]) >= 1; 
} 

這裏是最佳位置是在大約10秒解決了3.05Ghz機

G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G 
G B R R R B R R R B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R B R B R B R R _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R R B R R R B R B R B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R B R B R R R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B R R R B R B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R B R R R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R R B R B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R R R B _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B R B R B _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R R R B _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _