簡述

之前通過遺傳算法（Genetic Algorithm ）+C++實現解決TSP問題 寫了一些基本的原理。并且給出了C++版本代碼。

相比于近300行的C++程序，Python只用了160行就解決了 可以說是非常方便了~

基于之前的C++版本的Python版本代碼

import numpy as np import randomdef read_data(file='data.txt'):with open(file, 'r') as f:N = int(f.readline().replace('\n', ''))Mat = [0] * 10for i in range(N):Mat[i] = list(map(int, f.readline().replace('\n', '').split(' ')))return N, 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))pack = [0] * LENpackValue = [0] * LENfor i in range(LEN):random.shuffle(init)data = initpack[i] = data.copy()packValue[i] = calpathValue(pack[i])indexes = np.argsort(packValue)pack = np.array(pack)[indexes]packValue = np.sort(packValue)return packValue, pack# i: pack def preserve(i):global tempPack, tempPackValue, pack, packValue, tempIndextempPackValue[tempIndex] = packValue[i]tempPack[tempIndex] = pack[i].copy()tempIndex += 1def select():global N, pack, tempPack, tempPackValue, tempIndex, LEN, packValuetpk = tempPack[:tempIndex]tpkv = tempPackValue[:tempIndex]indexes = np.argsort(tpkv)tpk = np.array(tpk)[indexes]tpkv = np.sort(tpkv)pack = tpk[:LEN]packValue = tpkv[:LEN]def crossover(i, j):global N, pack, tempPack, tempPackValue, tempIndextimes = random.randint(1, N - 2)indexes = [0] * timesfor t in range(times):if t == 0:indexes[t] = random.randint(0, N - times - 1)else:indexes[t] = random.randint(indexes[t - 1] + 1, N - times + t - 1)tempPack[tempIndex] = pack[i].copy()pack_j_reindex = pack[j].copy()[indexes]count = 0for v in range(N - 1):if count >= times: breakif tempPack[tempIndex][v] in pack_j_reindex:tempPack[tempIndex][v] = pack_j_reindex[count]count += 1tempPackValue[tempIndex] = calpathValue(tempPack[tempIndex])tempIndex += 1tempPack[tempIndex] = pack[j].copy()pack_i_reindex = pack[i].copy()[indexes]count = 0for v in range(N - 1):if count >= times: breakif tempPack[tempIndex][v] in pack_i_reindex:tempPack[tempIndex][v] = pack_i_reindex[count]count += 1tempPackValue[tempIndex] = calpathValue(tempPack[tempIndex])tempIndex += 1def mutation(i):global N, pack, tempPack, tempPackValue, tempIndextimes = random.randint(1, N - 2)indexes = [0] * timesfor t in range(times):if t == 0:indexes[t] = random.randint(0, N - times - 1)else:indexes[t] = random.randint(indexes[t - 1] + 1, N - times + t - 1)origin_indexes = indexes.copy()random.shuffle(indexes)tempPack[tempIndex] = pack[i].copy()for t in range(times):tempPack[tempIndex][indexes[t]] = pack[i][origin_indexes[t]]tempPackValue[tempIndex] = calpathValue(tempPack[tempIndex])tempIndex += 1if __name__ == '__main__':N, Mat = read_data()LEN = 25pc, pm = 0.7, 0.97NOTMORETHANstayINGV = 10packValue, pack = initial()tempLEN = LEN * LENtempPack = [[0] * N] * tempLENtempPackValue = [0] * tempLENtempIndex = 0global_Value = packValue[0]stayinGV = 0while True:tempIndex = 0for i in range(LEN):preserve(i)if random.random() < pm:mutation(i)if i == LEN - 1: breakfor j in range(i + 1, LEN):if tempIndex >= tempLEN: breakif random.random() < pc:crossover(i, j)select()if packValue[0] < global_Value:global_Value = packValue[0]stayinGV = 0elif packValue[0] == global_Value:stayinGV += 1else:print("Something wrong")breakif stayinGV == NOTMORETHANstayINGV:breakprint(global_Value)print(0, end='-->')for i in pack[0]:print(i, end='-->')

• 所用的數據：
  • 表示是的10個點之間的距離矩陣

10 0 58 82 89 17 50 26 48 70 19 58 0 74 46 70 2 70 49 87 60 82 74 0 58 76 98 37 97 34 67 89 46 58 0 15 17 28 69 46 79 17 70 76 15 0 98 60 69 97 89 50 2 98 17 98 0 81 14 43 47 26 70 37 28 60 81 0 43 73 56 48 49 97 69 69 14 43 0 39 0 70 87 34 46 97 43 73 39 0 53 19 60 67 79 89 47 56 0 53 0

隨機生成數據并展示動圖

• 黑色的點是起點。
• 我在知乎上看到類似的圖，就試著改了下自己的代碼也實現了這個效果。生成gif是基于我之前寫的代碼

import numpy as np import random import matplotlib.pyplot as plt import os import shutil import imageiodef create_data(N, xu=10, yu=10, xd=-10, yd=-10):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))pack = [0] * LENpackValue = [0] * LENfor i in range(LEN):random.shuffle(init)data = initpack[i] = data.copy()packValue[i] = calpathValue(pack[i])indexes = np.argsort(packValue)pack = np.array(pack)[indexes]packValue = np.sort(packValue)return packValue, pack# i: pack def preserve(i):global tempPack, tempPackValue, pack, packValue, tempIndextempPackValue[tempIndex] = packValue[i]tempPack[tempIndex] = pack[i].copy()tempIndex += 1def select():global N, pack, tempPack, tempPackValue, tempIndex, LEN, packValuetpk = tempPack[:tempIndex]tpkv = tempPackValue[:tempIndex]indexes = np.argsort(tpkv)tpk = np.array(tpk)[indexes]tpkv = np.sort(tpkv)pack = tpk[:LEN]packValue = tpkv[:LEN]def crossover(i, j):global N, pack, tempPack, tempPackValue, tempIndextimes = random.randint(1, N - 2)indexes = [0] * timesfor t in range(times):if t == 0:indexes[t] = random.randint(0, N - times - 1)else:indexes[t] = random.randint(indexes[t - 1] + 1, N - times + t - 1)tempPack[tempIndex] = pack[i].copy()pack_j_reindex = pack[j].copy()[indexes]count = 0for v in range(N - 1):if count >= times: breakif tempPack[tempIndex][v] in pack_j_reindex:tempPack[tempIndex][v] = pack_j_reindex[count]count += 1tempPackValue[tempIndex] = calpathValue(tempPack[tempIndex])tempIndex += 1tempPack[tempIndex] = pack[j].copy()pack_i_reindex = pack[i].copy()[indexes]count = 0for v in range(N - 1):if count >= times: breakif tempPack[tempIndex][v] in pack_i_reindex:tempPack[tempIndex][v] = pack_i_reindex[count]count += 1tempPackValue[tempIndex] = calpathValue(tempPack[tempIndex])tempIndex += 1def mutation(i):global N, pack, tempPack, tempPackValue, tempIndextimes = random.randint(1, N - 2)indexes = [0] * timesfor t in range(times):if t == 0:indexes[t] = random.randint(0, N - times - 1)else:indexes[t] = random.randint(indexes[t - 1] + 1, N - times + t - 1)origin_indexes = indexes.copy()random.shuffle(indexes)tempPack[tempIndex] = pack[i].copy()for t in range(times):tempPack[tempIndex][indexes[t]] = pack[i][origin_indexes[t]]tempPackValue[tempIndex] = calpathValue(tempPack[tempIndex])tempIndex += 1def 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)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 = 20points, Mat = create_data(N)LEN = 40pc, pm = 0.7, 0.97NOTMORETHANstayINGV = 30packValue, pack = initial()tempLEN = LEN * LENtempPack = [[0] * N] * tempLENtempPackValue = [0] * tempLENtempIndex = 0global_Value = packValue[0]draw(pack[0], global_Value)stayinGV = 0while True:tempIndex = 0for i in range(LEN):preserve(i)if random.random() < pm:mutation(i)if i == LEN - 1: breakfor j in range(i + 1, LEN):if tempIndex >= tempLEN: breakif random.random() < pc:crossover(i, j)select()if packValue[0] < global_Value:global_Value = packValue[0]draw(pack[0], global_Value)stayinGV = 0elif packValue[0] == global_Value:stayinGV += 1else:print("Something wrong")breakif stayinGV == NOTMORETHANstayINGV:breakprint(global_Value)print(0, end='-->')for i in pack[0]: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-GA.gif', generated_images, 'GIF', duration=0.5)

總結

以上是生活随笔為你收集整理的遗传算法解决TSP问题 Python实现【160行以内代码】的全部內容，希望文章能夠幫你解決所遇到的問題。

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