0

我决定学习模拟退火作为解决这个问题的新方法。它本质上询问如何用 -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))
4

2 回答 2

1

首先要做一些事情，这可能会很快引导您找到一个可行的解决方案，而无需做任何其他事情（例如，交换启发式）：

  • 在主迭代循环的顶部附近添加一条线，以 计算 t0 状态的成本（即，您的起始配置）；

  • 在主循环中，在计算当前迭代成本的行之后插入一个打印语句——写入文件，该迭代的成本函数返回的值；在其下方添加一行，每 20 次迭代或类似的东西打印一次该值（例如，大约每秒一次，大约是我们能够理解滚动数据的最快速度）

    如果 n % 10 == 0：打印（what_cost_fn_returned_this_iteration）

  • 不要打电话给acceptance_probability；组合优化问题没有自然收敛准则；通常的做法是在发生以下任何一种情况时跳出主循环：

    已达到最大迭代次数

    过去 __ 次迭代中成本函数的当前最小值变化小于 __%；例如，如果在过去 100 次迭代中，成本（通过使用移动窗口比较最小值和最大值）变化小于 1%

    在迭代过程中达到最小值后，成本现在随着迭代次数不断增加

其他一些观察：

  • 有了正确的诊断（见上文），您将能够确定：（i）从一些初始成本，我的求解器在做什么？即，它是否正朝着越来越低的价值或多或少的直接路径移动？是不是在震荡？是在增加吗？（如果是后者，解决方法通常是你有一个向后的标志）

  • 一个 6 x 6 的矩阵非常小——这并没有给
    成本函数留下太多的空间

  • 重新编写您的成本函数，以便“完美”解决方案返回
    零成本，而所有其他解决方案都具有更高的价值

  • 1000 次迭代并不多；尝试将其增加到 50,000

于 2016-01-07T08:37:46.213 回答
0

new_grid = grid[:]做一个浅拷贝。深层复制或修改网格并恢复为原始网格可以解决问题。

于 2016-01-08T04:26:08.280 回答