根据规则分配资源＆mdash;模拟退火适当吗？

我想设计一个可以根据规则分配资源的应用程序。我相信模拟退火会起作用，但我不太熟悉它，我想知道是否有其他算法可能适合。例如，如果我有一个网格，并且我可以为网格中的每个单元格着色，我想设计一种算法，该算法可以为以下规则集找到最佳或接近最佳的解决方案： 1000x1000网格必须放置500个红色细胞，500个蓝色细胞和1000个绿色细胞红细胞必须接触另一个红细胞蓝色细胞不得接触另一个蓝色细胞绿色单元格只能沿边缘放置可以基于来自左上角的有色细胞的平均距离对安排进行评分模拟退火是否适合这个问题？我需要一种可以快速可靠地计算解决方案的算法（几秒到几分钟）。

已邀请:

2 个回复

岭取

模拟退火将非常快速地接近最佳解决方案。然而，正确实现模拟退火（这不是那么多代码）可能非常具有挑战性。许多人（包括我自己过去）都错误地实现了它，认为他们做得对，并假设算法不是那么好。替代算法是禁忌搜索，遗传算法，单纯形，... 以下是您在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支持）并使用生产中最好的算法。参考手册中的更多信息。

死搭胯

这基本上是一个约束满足问题，我不希望模拟退火在合理的时间内达到接近最优的程度。但是，它可能会让您很快找到一个次优的解决方案，因此您可能会在您没有时间时终止。也就是说，如果你想以最佳的方式解决这个问题，目前最好的方法就是使用某种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;
}

这是在3.05Ghz机器上大约10秒内解决的最佳位置

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 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

要回复问题请先登录或注册

根据规则分配资源＆mdash;模拟退火适当吗？

2 个回复

发起人

simulated_annealing

问题状态

根据规则分配资源＆mdash;模拟退火适当吗？

与内容相关的链接

2 个回复

发起人

simulated_annealing

问题状态