前言：模擬退火（simulated annealing）技術，在每一步都以一定的概率接受比當前結果更差的結果，從而有助于“跳出”局部極小。在每次迭代過程中，接受“次優解”的概率要隨著時間的推移而逐漸降低，從而保證算法的穩定性。

嘻嘻嘻，推薦一篇好文章讓你快速學習模擬退火算法求解旅行商問題

作者用的是c++編寫的程序，而且作者在程序中設置的是每個城市的坐標，也就默認city a 到city b的距離和city b 到city a的距離一樣了，和老師題目要求的用非對稱矩陣來描述城市之間的距離是不一樣的。

下面我參考作者代碼，按老師的要求（A-B的距離不等于 B-A的距離）用 python 實現了TSP問題，其中參數也調了調。
不得不說，python真是個簡單便捷的語言呢！！！

''' 設有n個城市和距離矩陣D=[dij]， 其中dij表示城市i到城市j的距離，i，j=1，2 … n， 則問題是要找出遍訪每個城市恰好一次的一條回路并使其路徑長度為最短。 '''from time import time from copy import copy from numpy import exp import numpy as np import randomT0 = 10.0 # 初始溫度 T_end = 0.001 # 最低溫度 q = 0.98 # 退火系數 L = 10 # 每個溫度時的迭代此時，即鏈長 N = 5 # 城市數量 city_list = [i for i in range(N)] # 初始化一個解 city_dis = np.floor(10 * np.random.random((N, N)) + 1) # 城市之間的距離矩陣# 計算路徑長度 def path_len(path_list):path = 0for i in range(len(path_list) - 1):city1 = path_list[i]city2 = path_list[i + 1]dis = city_dis[city1][city2]path += dislast_city = path_list[-1]first_city = path_list[0]dis = city_dis[last_city][first_city]path += disreturn path# 采用隨機交換位置的方式產生新解 def create_new():pos1 = random.randint(0, N - 1) # randint閉區間pos2 = random.randint(0, N - 1)temp = city_list[pos1]city_list[pos1] = city_list[pos2]city_list[pos2] = tempif __name__ == '__main__':t1 = time()count = 0 # 記錄降溫次數T = T0city_list_copy = [] # 保存原始解while T > T_end: # 當溫度低于結束溫度時，退火結束for i in range(L):city_list_copy = copy(city_list) # 復制數組create_new() # 產生新解f1 = path_len(city_list_copy) # 初始解目標函數值f2 = path_len(city_list) # 新解目標函數值df = f2 - f1# Metropolis 準則if df >= 0:print("df:", df)print("exp:", exp(-df / T))if exp(-df / T) <= random.random(): # 保留原來解city_list = copy(city_list_copy)T *= q # 降溫count += 1t2 = time()print("城市之間的距離矩陣：\n", city_dis)print("模擬退火算法,初始溫度T0=%.2f,降溫系數q=%.2f,每個溫度迭代%d次,共降溫%d次\n" % (T0, q, L, count))print("TSP最優路徑為：", city_list)print("最優路勁長度為：%1f\n" % (path_len(city_list)))print("程序耗時：%1f秒\n" % (t2 - t1))

結果：

總結

以上是生活随笔為你收集整理的模拟退火算法求解TSP问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。