傲天居士

V1

2022/04/06阅读:87主题:默认主题

震惊!某高校学生竟用Python求解最优旅游路线!

1. 问题引入

假期到了,王傲天同学想把全国各地城市旅游一遍。众所周知,王傲天同学非常懒,就连旅游也要规划最短路径。那么如何找寻最短旅游线路呢?这就是著名的旅行商问题(Travelling Salesman Problem, TSP)。

旅行商问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。TSP是组合优化中的一个NP困难问题,因此没有解析解,但我们可以使用启发式算法找到最优解或准最优解。

启发式算法有很多:基于材料统计力学的模拟退火算法(Simulated Annealing, SA),基于自然选择原理和自然遗传机制的遗传算法(Genetic Algorithms, GA),以及粒子群优化算法等(Particle Swarm Optimization, PSO)。王傲天同学这次采用遗传算法寻找最优路径。

遗传算法以自然选择原理为基础,模拟自然界生物进化机制,通过群体搜索技术,最终得到最优解或准最优解。为减少陷入局部最优解的概率,遗传算法必须进行变异和交叉操作。遗传算法需设置参数,包括种群大小 ,最大迭代次数 ,交叉率 、变异率 等等。遗传算法的简易流程如下:

  1. 设置编码策略。可采用二进制编码、格雷码、符号编码、排列编码等。TSP问题常用排列编码
  2. 初始化种群。可采用改良圈算法得到初始化种群。
  3. 设置目标函数。TSP中目标函数为路径长度。
  4. 交叉操作。以单点交叉为例,对于2个父代个体,随机选取一个交叉点对染色体片段进行交叉互换操作。
  5. 变异操作。将个体染色体中某些基因进行变动。
  6. 选择。在父代种群和子代种群中选择使得目标函数值最小的 个个体作为新一代种群。对新一代种群继续进行交叉、变异、选择。直到满足精度要求或达到最大迭代次数。

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形式保存

得到路线的热力图如:

分类:

数学

标签:

Python

作者介绍

傲天居士
V1

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