Распределение ресурсов в соответствии с правилами - подходит ли имитационный отжиг?

Question

Я хотел бы разработать приложение, которое может распределять ресурсы в соответствии с правилами.Я полагаю, что имитированный отжиг подойдет, но я не слишком знаком с ним, и мне было интересно, есть ли альтернативные алгоритмы, которые могли бы подойти.

Например, если бы у меня была сетка, и я мог бы покрасить каждую ячейку вЯ хотел бы разработать алгоритм, который нашел бы оптимальное или близкое к оптимальному решение для набора правил, например:

• 1000x1000 сетка
• Должен разместить 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, получить в пределах 7% от оптимального менее чем за 10 секунд, но все еще не нашел фактического оптимального назначения через 15 минут.

Вот код OPL длясетка 100x100 с 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,05 ГГц

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