基于遗传算法解决旅行商问题(Python代码)

大家好！本文为大家提供了遗传算法解决TSP问题的一种python实现。有兴趣的同学可以通过“蚁群算法解决TSP问题”，看看蚁群算法与遗传算法的不同之处。

import math
import numpy as np
import matplotlib.pyplot as plt
# 随机生成城市信息
nCity = 10
City = np.random.uniform(-10, 10, [nCity, 2])
Dis = { }
for i in range(nCity):
for j in range(nCity):
if i > j:
dis = ((City[i][0] - City[j][0]) ** 2 + (City[i][1] - City[j][1]) ** 2) ** 0.5
Dis[(i, j)] = dis
Dis[(j, i)] = dis
Data_BestFit =[]   #用于保存每一代蚂蚁的最优适应度
#适应度计算函数 适应值 = 1 / 路径距离
def Cal_Fit(X):
total_dis = Dis[(X[-1],X[0])]
for i in range(nCity-1):
total_dis += Dis[(X[i],X[i+1])]
return 1 / total_dis
def GA_TSP():
# 定义基本参数
nPop = 100  # 种群大小
Maxit = 100 # 最大迭代次数
Pm = 0.15   # 变异概率
Pc = 0.7    # 交叉概率
#种群初始化
X = [list(np.random.permutation(nCity)) for i in range(nPop)]
Fit = np.zeros([nPop])
Best_X = None
Best_Fit = -math.inf
for i in range(nPop):
Fit[i] = Cal_Fit(X[i])
if Fit[i] > Best_Fit:
Best_Fit = Fit[i]
Best_X = X[i].copy()
#迭代求解
for j in range(Maxit):
# 变异-在一个解中随机选取两座不同的城市交换遍历顺序
for k in range(nPop):
if np.random.random() < Pm:
point1 = int(np.random.random() * nCity)
point2 = int(np.random.random() * nCity)
while point1 == point2:
point1 = int(np.random.random() * nCity)
point2 = int(np.random.random() * nCity)
X[k][point1],X[k][point2] = X[k][point2],X[k][point1]
#交叉-交换解的部分序列
k = 0
while k < nPop:
if np.random.random() < Pc:
point = int(np.random.random() * nCity)
x1 = X[k][0:point+1]
x2 = X[k][point+1:nCity]
x2.extend(x1)
X[k] = x2
k += 1
#选择 以适应度占比为概率选取下一代个体(有的个体会被重复选取)
for i in range(nPop):
Fit[i] = Cal_Fit(X[i])
if Fit[i] > Best_Fit:
Best_Fit = Fit[i]
Best_X = X[i].copy()
fit = Fit.copy()
P = fit / sum(fit)
swarm = np.random.choice(range(nPop),size = nPop,replace=True,p = P)
x = X.copy()
for k in range(nPop):
X[k] = x[swarm[k]]
Data_BestFit.append(Best_Fit)
return Best_X ,Best_Fit
# 绘制路径与迭代曲线
def Draw_City(City, X ,Best_Fit):
X = list(X)
X.append(X[0])
coor_x = []
coor_y = []
for i in X:
i = int(i)
coor_x.append(City[i][0])
coor_y.append(City[i][1])
plt.plot(coor_x, coor_y, 'r-o')
plt.title('TSP with Genetic Algorithm\n'+'total_dis = '+str(round(Best_Fit,3)))
plt.show()
plt.plot(range(len(Data_BestFit)), Data_BestFit)
plt.title('Iteration_BestFit')
plt.xlabel('iteration')
plt.ylabel('fitness')
plt.show()
if __name__ == '__main__':
Best_X, Best_Fit = GA_TSP()
Draw_City(City ,Best_X ,(Best_Fit)**-1)

本文地址：https://blog.csdn.net/qq_44936034/article/details/112686431