本文最后更新于：2020年10月19日 下午
1.问题描述：
编写一个程序，使用遗传算法求解旅行商问题：
旅行商问题(Travelling Salesman Problem, 简记TSP，亦称货郎担问题):设有n个城市和距离矩阵D=[dij]，其中dij表示 城市i到城市j的距离，i，j=1，2 … n，问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。
2.问题定义：
- 定义个体、种群：每一条可能的路径为一个个体、所有个体构成种群。
- 定义适应度：计算每个个体的路径长度，以路径长度的倒数作为适应度。（即路径越长，适应度越差）
- 定义杂交方法：若产生的随机数大于交叉概率，则直接将父本保留，否则进行交叉。随机选择父本2的一个片段，遍历父本1：若该城市号码不在父本2中，则将其插入到交叉结果，若到达交叉点1则将父本2的片段插入交叉结果。
- 定义选择方法：每次选择适应度最低的个体，将其杀死。
- 定义突变方法：若产生的随机数大于突变概率，则不进行突变。否则采用倒置变异法，随机选择该基因的某一片段进行逆序。
3.算法流程：
- 确定种群规模N、杂交概率Pc、变异概率Pm、适应度函数F、终止条件。
- 产生初始种群，计算种群中每个个体的适应度。
- 开始进行进化操作：
- 使用选择方法杀死种群中适应度较低的若干个体。（物竞天择，适者生存）
- 开始繁殖：选择适应度最高的个体作为父本1，随机选择一个个体作为父本2。使其进行杂交，产生新个体。直到当前个体数量恢复到原始种群数量。
- 使新产生的种群按突变概率进行突变。
- 重复执行进化操作，直到达到迭代次数时，输出最优个体。
4.源代码：
import math
import random
import matplotlib.pyplot as plt
import sys
import copy
from PIL import Image
import numpy as np
class GA(object):
# 定义类属性
# 输入全国34个省、市、自治区直辖市的省会城市坐标
city_x = [86.61, 89.13, 127.34, 126.32, 123.42, 112.17, 116.40, 106.27, 111.98, 115.21, 117.04, 97.07, 103.82,
118.01, 108.94, 113.46, 117.28, 120.26, 121.46, 103.36, 112.29, 120.15, 107.51, 112.08, 115.89, 106.91,
120.31, 101.71, 123.01, 108.67, 113.98, 110.03, 113.54, 114.17]
city_y = [45.79, 30.66, 48.05, 44.38, 42.29, 42.81, 40.40, 36.76, 37.65, 38.44, 39.52, 35.62, 36.05, 36.37,
34.46, 34.25, 31.86, 32.54, 31.28, 30.65, 30.98, 29.28, 29.63, 27.79, 27.97, 26.67, 26.07, 24.84, 23.54,
22.68, 22.82, 19.33, 22.19, 22.32]
city = ['乌鲁木齐', '拉萨', '哈尔滨', '长春', '沈阳', '呼和浩特', '北京', '银川', '太原', '石家庄', '天津', '西宁',
'兰州', '济南', '西安', '郑州', '合肥', '南京', '上海', '成都', '武汉', '杭州', '重庆', '长沙', '南昌',
'贵阳', '福州', '昆明', '台北', '南宁', '广州', '海口', '澳门', '香港']
city_num = 34 # 城市数量
max_population_size = 100
population_size = max_population_size # 种群大小
killnum = 40 # 每次迭代杀死多少个个体
crossover_rate = 0.8 # 交叉概率
mutation_rate = 0.05 # 突变概率
iter = 500 # 迭代次数
best_dist = 0 # 最优距离
best_route = [] # 最优路线
def __init__(self):
# 定义实例属性：
self.population = np.array([]) # 种群数组
self.fitness = np.array([]) # 适应度数组
self.population = self.createpop(self.population_size) # 创建初始种群
self.fitness = self.get_fitness(self.population) # 计算初始化种群的适应度
def createpop(self, size): # 创建种群
pop = []
for i in range(size):
route = random.sample(range(0, self.city_num), self.city_num) #从0-n截取n个数据（得到初始随机路径）
pop.append(route)
return np.array(pop)
def get_fitness(self, pop):
fitness = np.array([])
for i in range(self.population.shape[0]):
d = self.get_distance(pop[i]) # 取一个个体，计算该个体的距离
fitness = np.append(fitness, 1/d) # np.array追加元素 以距离的倒数为适应度
return fitness
def get_distance(self, route): # 计算当前路径的长度
d = 0.0
for i in range(-1, self.city_num-1):
x = (self.city_x[route[i]]-self.city_x[route[i+1]])**2
y = (self.city_y[route[i]]-self.city_y[route[i+1]])**2
d += np.sqrt(x+y)
return d
def kill2(self):
worst_f_index = np.argmin(self.fitness) # 当前最差适应值的位置
self.population = np.delete(self.population, worst_f_index, axis=0) # 杀死若干个体
self.population_size = self.population.shape[0]
self.fitness = self.get_fitness(self.population) # 更新适应度
def breed(self):
while self.population_size < self.max_population_size: # 当前个体数小于种群数量时,进行繁衍
best_f_index = np.argmax(self.fitness) # 当前最好适应值的位置
p1 = self.population[best_f_index] # 选适应值最高的作为父本1
p2 = self.population[np.random.randint(0, self.population.shape[0]-1)] # 随机选父本2
c = self.cross(p1, p2)
c = c[np.newaxis, :] # 将（34， 转换为（1,34）
# print('交叉成功：',c)
# print('shape',self.population.shape,c.shape)
self.population = np.append(self.population, c, axis=0) # 进行交叉，追加到种群
self.fitness = self.get_fitness(self.population) # 更新适应度
self.population_size = self.population.shape[0] # 更新种群大小
# print(self.fitness.shape)
# print(self.fitness)
def cross(self, parent1, parent2): # 交叉p1和p2的片段
if np.random.rand() > self.crossover_rate: # 大于交叉概率0.7直接替换
return parent1
else:
index1 = np.random.randint(0, self.city_num-1) #随机产生位置1 注意：randint可以取到第二个参数的位置
index2 = np.random.randint(index1, self.city_num-1) # 随机产生位置1之后的位置2
tempGene = parent2[index1:index2] # 选取交叉的基因片段
newGene = []
p1len = 0
for g in parent1:
if p1len == index1: # 如果当前位置到达交叉点1
newGene.extend(tempGene) # 插入基因片段（将p2随机选取的一段作为新基因的开头）
if g not in tempGene:
newGene.append(g) # 若g没有在随机选的基因段里，则插入g
p1len += 1
newGene = np.array(newGene)
if newGene.shape[0] != self.city_num:
print('交叉错误')
return self.createpop(1)
# return parent1
return newGene
def mutate(self, gene): # 突变
if np.random.rand() > self.mutation_rate: # 大于突变概率0.005（大部分）
return gene
else:
index1 = np.random.randint(0, self.city_num-1)
index2 = np.random.randint(index1, self.city_num-1)
newgene = self.reverse(gene, index1, index2) # 倒置变异法
if newgene.shape[0] != self.city_num:
print("突变错误！")
return self.createpop(1)
return newgene
def reverse(self, gene, i, j): # 翻转i-j之间的片段
if i > j or j > self.city_num-1:
print("error")
return gene
else:
gg = np.copy(gene)
temp = gg[i:j] # 截取基因片段
new = []
n = 0
for g in gg:
if n == i: # 到达第i个位置
new.extend(temp[::-1]) # 插入逆序基因片段
if g not in temp: # 跳过已存在的基因片段（发生在插入基因片段之后的位置）
new.append(g)
n += 1
return np.array(new)
def evolution(self): # 进化
for i in range(self.iter): # 迭代次数
for k in range(self.killnum): # 杀死后20个个体
self.kill2() # 物竞天择，适者生存，杀死一些较差的个体
# print("杀死完个体数", self.population_size)
self.breed() # 开始繁殖 繁殖到达种群数量即停止
# print("繁殖完个体数", self.population_size)
for j in range(self.population_size):
self.population[j] = self.mutate(self.population[j]) # 突变
best_f_index = np.argmax(self.fitness) # 当前最好适应值的位置
self.best_route = self.population[best_f_index]
self.best_dist = self.get_distance(self.best_route)
print('迭代次数：%d,最优距离：%s' % (i, self.best_dist))
self.draw(self.best_route)
print("最佳路线：", [self.city[i] for i in self.best_route])
def draw(self, best): # 绘图方法
result_x = [0 for col in range(self.city_num + 1)]
result_y = [0 for col in range(self.city_num + 1)]
for i in range(self.city_num):
result_x[i] = self.city_x[best[i]] * 8 - 575
result_y[i] = (376 - self.city_y[best[i]] * 8 + 65) * 1.2
result_x[self.city_num] = result_x[0]
result_y[self.city_num] = result_y[0]
# print(result_x)
# print(result_y)
img = Image.open("./map.jpg")
plt.figure("map")
plt.imshow(img)
plt.plot(result_x, result_y, marker='o', mec='r', mfc='w', label=u'Route')
plt.legend() # 让图例生效
plt.margins(0)
plt.subplots_adjust(bottom=0.15)
plt.xlabel(u"x") # X轴标签
plt.ylabel(u"y") # Y轴标签
plt.title("TSP best:%05.3f iter:%d pop:%d kill:%d p:%d%%" % (self.best_dist, self.iter, self.max_population_size, self.killnum, self.crossover_rate*100)) # 标题
plt.show()
plt.close(0)
if __name__ == "__main__":
np.set_printoptions(threshold=1e6) # 设置打印数量的阈值
tsp = GA()
tsp.evolution()
#print(tsp.fitness)5.实验验证：
实验选取全国34个省、市、自治区的省会城市作为样本，根据地图描绘出其大概坐标位置。使用遗传算法求取最短路径，并将其绘制在地图上。实验中动态调整交叉概率、种群大小、每次迭代杀死个体的数目。
| 实验编号 | 交叉概率 | 种群大小 | 杀死数目 | 迭代次数 | 最优解 |
|---|---|---|---|---|---|
| 1 | 0.85 | 50 | 10 | 200 | 238 |
| 2 | 0.7 | 50 | 20 | 200 | 217 |
| 3 | 0.9 | 50 | 20 | 300 | 201 |
| 4 | 0.8 | 100 | 40 | 500 | 176 |
实验1：
实验2：
实验3：
实验4：
最短距离：176.056 [‘天津’, ‘石家庄’, ‘呼和浩特’, ‘太原’, ‘西安’, ‘银川’, ‘兰州’, ‘西宁’, ‘乌鲁木齐’, ‘拉萨’, ‘成都’, ‘重庆’, ‘贵阳’, ‘昆明’, ‘南宁’, ‘海口’, ‘澳门’, ‘广州’, ‘香港’, ‘台北’, ‘福州’, ‘杭州’, ‘上海’, ‘南京’, ‘合肥’, ‘南昌’, ‘长沙’, ‘武汉’, ‘郑州’, ‘济南’, ‘沈阳’, ‘长春’, ‘哈尔滨’, ‘北京’]
参考文献：
https://blog.csdn.net/jiang425776024/article/details/84532018
https://blog.csdn.net/u010451580/article/details/51178225
https://blog.csdn.net/woaixuexihhh/article/details/83826256
https://blog.csdn.net/sinat_31184961/article/details/85218294
https://www.cnblogs.com/pengsixiong/p/4823473.html