一、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

运行结果示例，只截图了一半

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,长沙

如需更换城市找到相关城市的经纬度，修改此文件即可。