簡述

代碼我是基于我之前寫的兩篇，一篇是遺傳算法TSP的Python實現，一篇是模擬退火算法的解決TSP的C++實現。

• 模擬退火算法理論+Python解決函數極值+C++實現解決TSP問題
• 遺傳算法解決TSP問題 Python實現【160行以內代碼】

效果演示

對比

相比于遺傳算法來說沒有保持歷史中的較優數據，但是通過退火的算法思維，很鄰近點搜索的想法，任然能保持較為正確的收斂結果

代碼

import numpy as np import random import matplotlib.pyplot as plt import os import shutil import imageiodef create_data(N, xu=25, yu=25, xd=-25, yd=-25):fx = lambda: random.random() * (xu - xd) + xdfy = lambda: random.random() * (yu - yd) + ydcalDistance = lambda x, y: np.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)points = [(0, 0)] * Nfor i in range(N):points[i] = (fx(), fy())Mat = np.zeros((N, N))for i in range(N):for j in range(i + 1, N):dv = calDistance(points[i], points[j])Mat[i][j], Mat[j][i] = dv, dvreturn points, Matdef calpathValue(path):global Mattemp = Mat[0][path[0]]for i in range(len(path) - 1):temp += Mat[path[i]][path[i + 1]]temp += Mat[path[-1]][0]return tempdef initial():global Ninit = list(range(1, N, 1))random.shuffle(init)packValue = calpathValue(init)return init, packValuedef draw(path, pv):global points, N, TIMESIT, PNGFILE, PNGLISTplt.cla()plt.title('cross=%.4f' % pv)xs = [p[0] for p in points]ys = [p[1] for p in points]plt.scatter(xs, ys, color='b')xs = np.array(xs)ys = np.array(ys)plt.plot(xs[[0, path[0]]], ys[[0, path[0]]], color='r')for i in range(N - 2):plt.plot(xs[[path[i], path[i + 1]]], ys[[path[i], path[i + 1]]], color='r')plt.plot(xs[[path[N - 2], 0]], ys[[path[N - 2], 0]], color='r')plt.scatter(xs[0], ys[0], color='k', linewidth=10)for i, p in enumerate(points):plt.text(*p, '%d' % i)plt.savefig('%s/%d.png' % (PNGFILE, TIMESIT))PNGLIST.append('%s/%d.png' % (PNGFILE, TIMESIT))TIMESIT += 1if __name__ == '__main__':# N, Mat = read_data()TIMESIT = 0PNGFILE = './png/'PNGLIST = []if not os.path.exists(PNGFILE):os.mkdir(PNGFILE)else:shutil.rmtree(PNGFILE)os.mkdir(PNGFILE)N = 30points, Mat = create_data(N)T = 1000 # 起始溫度alpha = 0.995 # T_{k+1} = alpha * T_k方式更新溫度limitedT = 1. # 最小值的TiterTime = 1000 # 每個溫度下迭代的次數K = 0.8 # 系數Kp = 0path, value = initial()tempPath, tempValue = [], 0global_Best = value # 畫圖while T > limitedT:print(T)for i in range(iterTime):tempPath = path.copy()tx = random.randint(0, N - 2)ty = random.randint(0, N - 2)if tx != ty:tempPath[tx], tempPath[ty] = tempPath[ty], tempPath[tx]tempValue = calpathValue(tempPath)if tempValue <= value:path = tempPath.copy()value = tempValue.copy()else:p = np.exp((value - tempValue) / (K * T))if random.random() < p:path = tempPath.copy()value = tempValue.copy()if value < global_Best:global_Best = valuedraw(path, value)T *= alphaprint(value)print(0, end='-->')for i in path:print(i, end='-->')generated_images = []for png_path in PNGLIST:generated_images.append(imageio.imread(png_path))shutil.rmtree(PNGFILE) # 可刪掉generated_images = generated_images + [generated_images[-1]] * 5imageio.mimsave('TSP-SAA.gif', generated_images, 'GIF', duration=0.5)

總結

以上是生活随笔為你收集整理的模拟退火算法解决TSP（python实现 110+行代码）【gif生成】的全部內容，希望文章能夠幫你解決所遇到的問題。

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