模拟退火无法返回最优解

我决定学习模拟退火作为一种新的攻击方法 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))