
傲天居士
2022/04/06阅读:87主题:默认主题
震惊!某高校学生竟用Python求解最优旅游路线!
1. 问题引入
假期到了,王傲天同学想把全国各地城市旅游一遍。众所周知,王傲天同学非常懒,就连旅游也要规划最短路径。那么如何找寻最短旅游线路呢?这就是著名的旅行商问题(Travelling Salesman Problem, TSP)。
旅行商问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。TSP是组合优化中的一个NP困难问题,因此没有解析解,但我们可以使用启发式算法找到最优解或准最优解。
启发式算法有很多:基于材料统计力学的模拟退火算法(Simulated Annealing, SA),基于自然选择原理和自然遗传机制的遗传算法(Genetic Algorithms, GA),以及粒子群优化算法等(Particle Swarm Optimization, PSO)。王傲天同学这次采用遗传算法寻找最优路径。
遗传算法以自然选择原理为基础,模拟自然界生物进化机制,通过群体搜索技术,最终得到最优解或准最优解。为减少陷入局部最优解的概率,遗传算法必须进行变异和交叉操作。遗传算法需设置参数,包括种群大小 ,最大迭代次数 ,交叉率 、变异率 等等。遗传算法的简易流程如下:
-
设置编码策略。可采用二进制编码、格雷码、符号编码、排列编码等。TSP问题常用排列编码 -
初始化种群。可采用改良圈算法得到初始化种群。 -
设置目标函数。TSP中目标函数为路径长度。 -
交叉操作。以单点交叉为例,对于2个父代个体,随机选取一个交叉点对染色体片段进行交叉互换操作。 -
变异操作。将个体染色体中某些基因进行变动。 -
选择。在父代种群和子代种群中选择使得目标函数值最小的 个个体作为新一代种群。对新一代种群继续进行交叉、变异、选择。直到满足精度要求或达到最大迭代次数。
2. 实战操作
2.1 获取数据
旅游当然要首先确定目标城市。王傲天同学的目标城市清单包括北京、上海、广州、武汉、沈阳、昆明、喀什、西安、洛阳等。获取目标城市的经纬度坐标信息。这里推荐一个网址:https://maplocation.sjfkai.com/。
现在有了目标城市的经纬度坐标,接下来就是用遗传算法求解最优路径。首先要明白由经纬度坐标求两城市间球面距离的方法。
2.2 已知经纬度求球面距离
不妨把地球当成理想球体,且半径为 。球面上有 两点,经纬度坐标分别为 ,其中 与 分别表示经度和纬度。在空间直角坐标系中, 两点坐标分别为:
则由向量的知识可以得出:
化简得到:
因此 两点的球面距离为 . 注意这里的角是弧度制。
2.3 计算距离矩阵
首先导入需要的模块并读取数据文件。
import numpy as np
import matplotlib.pyplot as plt
import os
import pandas as pd
import math
# 路径自行设置
mypath=r"..."
data=pd.read_excel(os.path.join(mypath+"\\"+"location.xlsx"))
然后获取经纬度信息(Python的math模块的三角函数的输入值默认是弧度制,因此事先将经纬度坐标转化为弧度制)
points = np.array(data[['经度','纬度']])*math.pi/180
由于王傲天同学从深圳出发并回到深圳,因此指定起点与终点:
start_point=end_point=[points[-1]]
中间点:
pass_points=points[0:-1,]
计算距离矩阵:
points_coordinate=np.concatenate([pass_points,start_point,end_point])
num_points=pass_points.shape[0]
dist_matrix=np.zeros((num_points+2,num_points+2))
for i in range(num_points+2):
for j in range(i,num_points+2):
dist_matrix[i,j]=6370*math.acos((math.cos(points_coordinate[i,0]-points_coordinate[j,0])
*math.cos(points_coordinate[i,1])*math.cos(points_coordinate[j,1])
+math.sin(points_coordinate[i,1])*math.sin(points_coordinate[j,1])))
distance_matrix=dist_matrix+np.transpose(dist_matrix)
2.4 遗传算法
首先定义目标函数:
def cal_total_distance(routine):
num_points, = routine.shape
routine=np.concatenate([[num_points],routine,[num_points+1]])
return sum([distance_matrix[routine[i], routine[i+1]] for i in range(num_points+2-1)])
接下来傲天同学直接调用Python库scikit-opt,省去了自行编写代码的麻烦(真是把懒发挥到了极致)。首先安装库pip install scikit-opt
,而后调用:
from sko.GA import GA_TSP
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=0.1)
best_points, best_distance = ga_tsp.run()
可以看出设置种群大小为50,最大迭代次数为500,变异率为0.1。 获取最优路径(注意加上起点和终点)并画图:
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([[num_points],best_points,[num_points+1]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()
得到路径图及迭代精度收敛图:
其中左边子图表示路径图,右边子图表示迭代精度收敛图。可以看出迭代超过400次后精度几乎不再下降。同时也给出了最优路径的总长度为19228.8km.
3. 地图可视化
傲天同学已经由遗传算法得出最优路径,可他还是不满意。有没有一种方法能将最优路径表现在地图上呢?经查找资料,傲天同学发现Python库folium可以实现。于是首先安装库pip install folium
.
首先计算中心区域。傲天同学将data数据中的经纬度平均值作为中心点。注意到folium要求纬度在前,经度在后,这与我们的数据恰好相反。因此:
from folium import plugins
import folium
# 取经纬度平均值为中心点(注意)folium包要求坐标形式以纬度在前,经度在后
m = folium.Map([np.mean(data['纬度']),np.mean(data['经度'])], zoom_start=10) #中心区域的确定
由遗传算法得出的最优路径映射到经纬度坐标:
data0=[data.iloc[-1,:]]
data1=np.concatenate([data,data0])
location=np.zeros((num_points+2,2))
#输入坐标点(注意)folium包要求坐标形式以纬度在前,经度在后
for k in range(num_points+2):
location[k,0]=data1[best_points_[k],-1]
location[k,1]=data1[best_points_[k],1]
将坐标用线段连接:
route = folium.PolyLine( #polyline方法为将坐标用线段形式连接起来
location, #将坐标点连接起来
weight=3, #线的大小为3
color='orange', #线的颜色为橙色
opacity=0.8 #线的透明度
).add_to(m) #将这条线添加到刚才的区域m内
m.save(os.path.join(mypath+'\\'+'Heatmap1.html')) #将结果以HTML形式保存
得到路线的热力图如:
作者介绍

傲天居士
微信公众号:进击的王傲天