Имитированный отжиг не возвращает оптимального решения

Question

Я решил изучить смоделированный отжиг как новый метод для атаки this problem. Он по существу спрашивает, как заполнить сетку -1, 0 или 1, чтобы каждая сумма строк и столбцов была уникальной. В качестве тестового примера я использовал 6x6 сетку, для которых, безусловно, является оптимальным решение дается Neil:

1 1 1 1 1 1 6 
1 1 1 1 1 -1 4 
1 1 1 1 -1 -1 2 
1 1 0 -1 -1 -1 -1 
1 0 -1 -1 -1 -1 -3 
0 -1 -1 -1 -1 -1 -5 
5 3 1 0 -2 -4 

Моего код обычно не доходит до оптимального случая большинства трасс и даже возвращает неправильную сетку стоимость (old_cost должна соответствовать count_conflict(grid)). Неправильно ли установлены мои параметры, неправильно ли я реализован или, возможно, имитирован отжиг, а не жизнеспособный метод?

import random 
from math import exp 

G_SIZE = 6 
grid = [[1]*G_SIZE for i in range(G_SIZE)] 

def count_conflict(grid): 
    cnt = [0]*(2*G_SIZE+1) 
    conflicts = 0 
    for row in grid: 
     cnt[sum(row)] += 1 
    for col in zip(*grid): 
     cnt[sum(col)] += 1 

    #print(cnt) 
    for c in cnt: 
     if c == 0: conflicts += 1 
     if c > 1: conflicts += c-1 
    return conflicts 

def neighbor(grid): 
    new_grid = grid[:] 

    i = random.choice(range(G_SIZE)) 
    j = random.choice(range(G_SIZE)) 
    new_cells = [-1, 0, 1] 
    new_cells.remove(new_grid[i][j]) 
    new_grid[i][j] = random.choice(new_cells) 

    return new_grid 

def acceptance_probability(old_cost, new_cost, T): 
    if new_cost < old_cost: return 1.0 
    return exp(-(new_cost - old_cost)/T) 


# Initial guess 
for i in range(1, G_SIZE): 
    for j in range(0, i): 
     grid[i][j] = -1 

#print(grid) 

old_cost = count_conflict(grid) 
T = 10.0 
T_min = 0.1 
alpha = 0.99 
while T > T_min: 
    for i in range(1000): 
     new_sol = neighbor(grid) 
     new_cost = count_conflict(new_sol) 
     ap = acceptance_probability(old_cost, new_cost, T) 
     print(old_cost, new_cost, ap, T) 
     if ap > random.random(): 
      grid = new_sol 
      old_cost = new_cost 

    T *= alpha 

for row in grid: 
    print(row) 

print(count_conflict(grid)) 

Answer 1

new_grid = grid[:] делает мелкую копию. Глубокая копия или изменение сетки на месте и возврат к оригиналу решает проблему.

Answer 2

несколько вещей, чтобы сделать первый, и который может быстро привести вас к рабочему раствору, без необходимости делать что-нибудь еще (например, поменять эвристические):

• добавить линию вблизи сверху за пределами вашей основной итеративной петли, до рассчитать стоимость вашего состояния t0 (т.е. ваша стартовая конфигурация );

• внутри основного контура, вставьте один оператор печати только после линии, которая вычисляет стоимость для текущей итерации - который записывает в файл, значение, возвращаемое функцией затрат для этого итерации; чуть ниже, что добавить строку, которая выводит это значение каждые 20 итераций или что-то подобное (например, примерно один раз в секунду является примерно так же быстро, как мы можем понять, прокруткой данные)

  если п% 10 == 0: печать (what_cost_fn_returned_this_iteration)

• не называть accept_probability; нет естественной конвергенции критерий в задачах комбинаторной оптимизации; обычная практика является вырваться из основного цикла, когда любые из них происходит:

  максимального количества итераций было достигнуто

  текущего минимального значения функции затрат по прошлому __ Итерации изменилась меньше чем __%; например , если за последние 100 итераций, стоимость (путем сравнения мин и макс с помощью скользящего окна) изменяется менее чем на 1%

  после достижения минимума во время итерации, стоимость теперь последовательно увеличивается с итерацией подсчитывать

---

несколько других наблюдений:

• с диагностикой на месте (см. Выше) вы сможете: определить: (i) от начальной стоимости, что делает мой решатель? т.е. , он перемещается по более или менее прямому пути к нижнему и нижнему значениям? Он колеблется? Увеличивается ли она?(Если последнее, то исправление обычно, что у вас есть знак назад)

• матрица 6 х 6 является очень и очень мало - что не оставляет много для функции
  затрат на работу с

• повторно написать функцию стоимости, так что «идеальное» решение возвращает
  нулевой стоимости, а все остальные имеют более высокую стоимость

• 1000 итераций не много; попробуйте увеличить это до 50 000