模擬退火不返回（一）最優解

我決定學習模擬退火與攻擊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))

來源

2016-01-07 qwr

不知何故，我認爲基礎問題應該在數學問題板上發佈，因爲它似乎可以將這個問題轉化爲一組具有多個變量的鏈接方程，這些變量轉換爲矩陣計算。 – DainDwarf

我很確定SA不提供任何保證找到全局最小值。擲骰子的次數越多，在某些情況下（可能）你更有可能找到它。玩你的冷靜配置文件。至少在一開始，這是你必須進行半手動操作的事情。你能比較你的例程與已知的東西 - 爲什麼不與'scipy.optimize.anneal'並行運行並比較行爲。 – uhoh

@uhoh我已經擺弄了一些參數，但程序通常停止了短短的預期目標。由於模擬退火與N皇后問題一起工作，我希望它能在這裏工作。 – qwr

new_grid = grid[:]使一個淺拷貝。深層複製或修改網格並恢復到原始網格可解決問題。

來源

2016-01-08 04:26:08 qwr

一些事情要先做，哪些可能會很快導致你到一個有效的解決方案，而無需做任何事情（例如，交換啓發式）：

加線附近您的主迭代循環的頂部以外，以 計算（即，您的起動配置）的T0狀態的成本;
主循環內，插入一個print語句只是線，計算當前迭代成本後 - 寫入到一個文件中，由成本函數，該函數迭代返回的值;剛好低於添加用於打印每20次迭代或類似的東西（例如，約每一次第二是一樣快，我們可以理解滾動數據）

如果n％該值的線10 == 0：打印（what_cost_fn_returned_this_iteration）
請勿調用acceptance_probability;在組合優化問題中沒有自然收斂的標準;通常的做法是打出來的主循環當任何這些發生：

最大迭代次數已經達到

在過去的成本函數的最小電流值__迭代發生了變化少比__％;例如如果在過去的100次迭代，成本（通過比較分鐘，並使用最大移動窗）迭代期間達到最小後的變化小於1％

，成本現在與迭代持續增加算上

其他一些意見：

與地方（見上文），你將能夠診斷，以確定：（i）從一些初始費用，什麼是我的求解器幹什麼？即它是在一個或多或少的直接路徑中移動到更低和更低的值？它在搖擺嗎？它在增加嗎？（如果是後者，修復是通常你有倒退的跡象）
一個6×6矩陣是非常非常小 - 不留下很多的
代價函數
工作
重新寫你的成本函數，這樣一個「完美」的解決方案返回
零成本，以及所有其他有更高的價值
1000次迭代是不是很多;嘗試增加到50,000

來源

2016-01-07 08:37:46 doug

是不是用'old_cost = count_conflict（grid）'完成的第一個要點？ – qwr

如果沒有'acceptance_probability'，甚至會使用溫度？ – qwr

模擬退火不返回（一）最優解

回答

相關問題