一、TSP问题
TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。简单示例如下图所示：
二、求解算法
下面使用遗传算法对此TSP问题求近似解，不了解此算法的同学请先移步此知乎链接：
如何通俗易懂地解释遗传算法？有什么例子？
最终效果如下图
主要运行代码如下：
# coding:utf:8
import numpy as np
import random
import matplotlib.pyplot as plt
from matplotlib.ticker import FormatStrFormatter
import operator
import time
import pandas as pd
from tsp1.mutations import select_best_mutaion
def main():
global p_mutation, max_generation
generation = 1
population_cur = init_population()
fitness = get_fitness(population_cur)
time_start = time.time()
# 终止条件
while generation < max_generation:
# 父代最好的留1/4活下来
population_next = select_sorted_population(fitness, population_cur, population_size // 4)
# 杂交
for i in range(population_size):
p1, p2 = selection(fitness, 2)
child1, child2 = crossover(population_cur[p1], population_cur[p2])
# 变异
if random.random() < p_mutation:
child1 = select_best_mutaion(child1, distmat)
if random.random() < p_mutation:
child2 = select_best_mutaion(child2, distmat)
population_next.append(child1)
population_next.append(child2)
# 选出下一代的种群
population_next = select_sorted_population(get_fitness(population_next), population_next, population_size)
# 找出精英记录下来
pre_max_fitness, pre_max_individual = get_elite(fitness, population_cur)
record(pre_max_fitness)
# 换代
population_cur = population_next
generation += 1
# 更新fitness
fitness = get_fitness(population_cur)
# 记录并画图
final_fitness, final_individual = get_elite(fitness, population_cur)
record(final_fitness)
time_end = time.time()
print('进化花费时间：', time_end - time_start)
print('最后的路径距离（km）：', get_distance(final_individual) * 111)
plot(final_individual)
return
# 排序，并且返回length长的population
def select_sorted_population(fitness, population, length):
global population_size
sort_dict = {
}
for i in range(len(population)):
sort_dict[(fitness[i], 1 / fitness[i])] = i
sorted_key = sorted(sort_dict.keys(), key=operator.itemgetter(0), reverse=True)
sorted_index = [sort_dict[i] for i in sorted_key]
sorted_population = [population[i] for i in sorted_index]
return sorted_population[:length]
# 画图
def plot(sequence):
global record_distance, coordinates
plt.figure(figsize=(15, 6))
plt.subplot(121)
plt.plot(record_distance)
plt.ylabel('distance')
plt.xlabel('iteration ')
plt.subplot(122)
x_list = []
y_list = []
for i in range(len(sequence)):
lat = coordinates[sequence[i]][0]
lon = coordinates[sequence[i]][1]
x_list.append(lat)
y_list.append(lon)
for one in name.itertuples(index=False):
lat1 = one[0]
if lat1 == lat:
lon1 = one[1]
if lon1 == lon:
# 显示城市名
city = one[2]
plt.text(lat, lon, city)
print(city)
print(' |')
break
lat = coordinates[sequence[0]][0]
lon = coordinates[sequence[0]][1]
x_list.append(lat)
y_list.append(lon)
for one in name.itertuples(index=False):
lat1 = one[0]
if lat1 == lat:
lon1 = one[1]
if lon1 == lon:
# 显示城市名
city = one[2]
print(city)
break
plt.plot(x_list, y_list, 'c-', label='Route')
plt.plot(x_list, y_list, 'ro', label='Location')
# 防止科学计数法
ax = plt.gca()
ax.xaxis.set_major_formatter(FormatStrFormatter('%.2f'))
ax.yaxis.set_major_formatter(FormatStrFormatter('%.2f'))
plt.xlabel("Longitude")
plt.ylabel("Latitude")
plt.title("Tsp Route")
plt.rcParams['font.sans-serif'] = ['SimHei'] # 显示中文标签
plt.rcParams['axes.unicode_minus'] = False # 这两行需要手动设置
plt.grid(True)
plt.legend()
plt.show()
# 获取最好的数据
def get_elite(fitness, population):
max_index = fitness.index(max(fitness))
max_fitness = fitness[max_index]
max_individual = population[max_index]
return max_fitness, max_individual
def record(f):
global record_distance
# 经纬度转千米的单位要乘以111
record_distance.append(1 / f * 111)
# 轮赌盘选择算子
def selection(fitness, num):
def select_one(fitness, fitness_sum):
size = len(fitness)
i = random.randint(0, size - 1)
while True:
if random.random() < fitness[i] / fitness_sum:
return i
else:
i = (i + 1) % size
res = set()
fitness_sum = sum(fitness)
while len(res) < num:
t = select_one(fitness, fitness_sum)
res.add(t)
return res
# 获得一个旅行路径的距离
def get_distance(sequence):
global distmat
cost = 0
for i in range(len(sequence)):
cost += distmat[sequence[i - 1]][sequence[i]]
return cost
# 计算适应值
def get_fitness(population):
fitness = []
for i in range(len(population)):
fitness.append(1 / get_distance(population[i]))
return fitness
# 杂交算子
def crossover(parent1, parent2):
global individual_size
a = random.randint(1, individual_size - 1)
child1, child2 = parent1[:a], parent2[:a]
for i in range(individual_size):
if parent2[i] not in child1:
child1.append(parent2[i])
if parent1[i] not in child2:
child2.append(parent1[i])
return child1, child2
# 初始化种群
def init_population():
global individual_size, population_size
population_init = []
for i in range(population_size):
l = list(range(individual_size))
population_init.append(random.sample(l, individual_size))
return population_init
# 获得城市之间的距离矩阵
def get_distmat(M):
length = M.shape[0]
distmat = np.zeros((length, length))
for i in range(length):
for j in range(i + 1, length):
distmat[i][j] = distmat[j][i] = np.linalg.norm(M[i] - M[j])
return distmat
if __name__ == "__main__":
# 准备数据
file = 'data1.csv'
demo = 'demo.csv'
coordinates = pd.read_csv(file, usecols=[1, 2], header=None).values
name = pd.read_csv(demo, usecols=[0, 1, 2], encoding='gbk', header=None)
distmat = get_distmat(coordinates)
# 参数初始化
individual_size = coordinates.shape[0]
max_generation = 3500
population_size = 10
p_mutation = 0.2
record_distance = []
# 运行
main()
mutations.py
# coding:utf:8
import random
# SMB
def select_best_mutaion(s, distmat):
s_res = [slide_mutation(s[:]), inversion_mutation(s[:]), irgibnnm_mutation(s[:], distmat)]
res = [get_distance(s_res[0], distmat), get_distance(s_res[1], distmat), get_distance(s_res[2], distmat)]
min_index = res.index(min(res))
return s_res[min_index]
# 滑动变异
def slide_mutation(s):
a, b = get_two_randint(len(s))
t = s[a]
for i in range(a + 1, b + 1):
s[i - 1] = s[i]
s[b] = t
return s
# 获得一个旅行路径的距离
def get_distance(sequence, distmat):
cost = 0
for i in range(len(sequence)):
cost += distmat[sequence[i - 1]][sequence[i]]
return cost
# 倒置变异
def inversion_mutation(s):
# 自己手写的2变换
a, b = get_two_randint(len(s))
for i in range(a, (a + b) // 2 + 1):
s[i], s[b + a - i] = s[b + a - i], s[i]
return s
# 返回（小，大）两个随机数
def get_two_randint(size):
b = a = random.randint(0, size - 1)
while a == b:
b = random.randint(0, size - 1)
if a > b:
return b, a
return a, b
# irgibnnm
def irgibnnm_mutation(s, distmat):
a, b = get_two_randint(len(s))
# 先inversion
for i in range(a, (a + b) // 2 + 1):
s[i], s[b + a - i] = s[b + a - i], s[i]
# 再RGIBNNM
b = (b + 1) % len(s)
min = b - 1
for i in range(len(s)):
if i == b:
continue
if distmat[b][min] > distmat[b][i]:
min = i
s[b], s[min - 4] = s[min - 4], s[b]
return s
运行结果示例，只截图了一半
迭代次数与距离的关系
data1.csv
Beijing,116.41667,39.91667
shanghai,121.43333,34.5
tianjin,117.2,39.13333
guangzhou,113.23333,23.16667
zhuhai,113.51667,22.3
hangzhou,120.2,30.26667
chongqing,106.45,29.5667
qingdao,120.33333,36.03333
fuzhou,119.3,26.08333
lanzhou,103.73333,36.03333
nanchang,115.9,28.68333
nanjing,118.78333,32.05
shenyang,123.38333,41.8
zhengzhou,113.65,34.76667
wuhan,114.31667,30.51667
xian,108.95,34.26667
changchun,125.35,43.8833
haikou,110.35,20.01667
guiyang,106.71667,26.56667
changsha,113,28.2
demo.csv
116.41667,39.91667,北京
121.43333,34.5,上海
117.2,39.13333,天津
113.23333,23.16667,广州
113.51667,22.3,珠海
120.2,30.26667,杭州
106.45,29.5667,重庆
120.33333,36.03333,青岛
119.3,26.08333,福州
103.73333,36.03333,兰州
115.9,28.68333,南昌
118.78333,32.05,南京
123.38333,41.8,沈阳
113.65,34.76667,郑州
114.31667,30.51667,武汉
108.95,34.26667,西安
125.35,43.8833,长春
110.35,20.01667,海口
106.71667,26.56667,贵阳
113,28.2,长沙
如需更换城市找到相关城市的经纬度，修改此文件即可。
转载：https://blog.csdn.net/qq_30803353/article/details/112198630
查看评论