基于自适应遗传算法的张掖市自驾旅游时间优化

文/孟小丁 许向阳 张文高

1 引言

随着人们生活水平的提高，利用节假日出行旅游已成为常态，如何为旅行者提供省时省力的出行选择，最大化体验旅行带来的收获，已经成为旅游企业关注的焦点和相关学科的研究热点。

冯爱芬[1]以洛阳市为例，从旅游者和组团考察两个角度，建立了洛阳市最佳旅游路线的图论模型和数学规划模型，运用Lingo软件进行求解。Hasuike T[2]提出了一种个性化旅游的框架，将问题归纳为非线性离散优化问题，用基于动态规划的贪心算法求解得到最优旅游路线。陆国锋[3]研究了多属性的景点评分机制和多约束多目标的旅游路线推荐方法，设计了k-Greedy算法求解，实现了向用户推荐多条旅行路线。侯乐[4]针对带时间窗的定向问题和带时间窗的TSP问题，提出了一种迭代局部搜索结合布谷鸟搜索的优化算法。宋晓宇[5]提出一种新的短时间体验式路线搜索，目的在于找到一条非重复多类别且收益最大化的最优景点访问路线，并设计SUB和MUB两种优化搜索算法。Gavalas T等人[6]考虑了用户的偏好，每天的旅行时间，景点的开放时间等信息，提出启发式的求解方法。Long Liu[7]针对自驾游和散客群体，提出了满足用户喜好并节省总时间的实时旅游路线推荐系统。王楠[8]重点考虑了兴趣点的动态属性，并提出了基于用户需求的景点路线利益规划算法。张燕君[9]考虑游客需求，交通时间，景点时间的不确定性，构建多目标的团队个性化旅游线路模型，提出了改进多态自适应的蚁群算法。吴清霞[10]提出了基于兴趣点和用户兴趣偏好的个性化旅游路线推荐算法。

综上所述，文献主要对旅游线路的模型，算法求解两个方面做了较为细致的研究。但实验仿真中并没有对河西走廊地段的景点做具体的研究。本文以张掖市为例，采集数据，利用简单遗传算法（Simple Genetic Algorithm，SGA）和自适应遗传算法（Adaptive Genetic Algorithm，AGA）分别求解最佳驾车旅行时间。自适应遗传算法能够使得交叉概率和变异概率保持动态变化，改进了收敛性能，进而显著提高了搜索效率。

2 问题分析

选取张掖市14个旅游景点，以其中一个景点为出发点，通过自驾游的形式游览各个景点，规定每个景点只能访问1次，最后需返回出发点，如何安排散客选择对这些景点的访问次序，使得总驾驶时间最短。这类问题可归纳为TSP问题的一种应用，是一种组合优化问题。

图1：交叉操作

图2：变异操作

其中，目标函数式（1）表示驾车行驶时间最小，约束条件式（2）和式（3）保证了仅有一条入边和一条出边，式（4）表示保证没有任何子回路解的产生，式（5）表示对景点是否访问。

3 简单遗传算法求解

针对上述的问题，遗传算法求解的主要步骤可以描述为：

第1步：编码操作。对于14个景点的访问，给每个景点编号（1～14），则（14—8—13—9—6—2—4—7—12—5—11—10—3—1）是一条合法的染色体。

图3：SGA和AGA运行结果比较

表1：张掖市14个景点的经纬度信息

表2：张掖市各景点之间的驾车时间 （单位：min）

表3：求解参数及运行结果

第2步：初始化种群。设初始化种群的数目为100，产生100×14的随机初始种群作为起始解；

第3步：适应度函数设计。记ti，i+1相邻景点i和i+1之间的驾车行驶时间，考虑起点终点相同的情况下，个体的适应度函数为：

优化的目标为选择驾车行驶时间的倒数，即驾车行驶时间越短，f取值越大，适应值最大的染色体越优。

第4步：遗传算子的设计

（1）选择操作。去除旧群体中适应值低的个体，将适应度值大的个体加入到下一代种群中。

（2）交叉操作。首先产生[1，14]区间内的两个随机数r1和r2，确定交配区域，对r1和r2两位置中间的数据进行交叉。若交叉后有重复的景点编号，采用部分映射的方法消除冲突。如图1所示。

（3）变异操作。变异策略采用对换变异方法，即产生两个[1，14]区间内随机整数，确定两个位置，互换其值。如图2所示。

4 自适应遗传算法求解

在上述SGA的描述中，算法作如下改动：

第1步：编码操作同上；

第2步：产生初始化种群同上。

第3步：定义适应度函数同上，计算各个个体的适应度值。

第5步：交叉操作。对种群中随机搭配成对的每一对个体，按照文献[11]的公式计算自适应交叉概率Pc。以Pc为交叉概率进行交叉操作。

第6步：变异操作。对种群中的所有个体，按照文献[11]的公式计算自适应交叉概率Pm。以Pm为变异概率进行变异操作。

在式子（7）和（8）中，一般取Pcl=0.9；Pc2=0.6；Pml=0.1；Pm2=0.001。

第7步：计算新个体的适应度，产生新种群；

第8步：判断是否达到给定的迭代次数，若达到，则结束；否则转到第4步。

5 实例验证

通过GPSspg查询网得到百度地图显示的张掖市14个景点的经纬度信息，如表1所示。编写matlab程序计算得到各景点之间的驾车行驶时间，如表2所示。

结合上述数据，各自重复实验11次，利用SGA计算得到平均最小驾车行驶时15.0099h，利用AGA计算得到平均最小驾车行驶时间为14.6485h，算法的控制参数及运行结果见表3所示。进化过程如图3所示。

6 总结

本文分别探讨了简单遗传算法和自适应遗传算法，应用于求解张掖市14个景点之间旅游路线的最短驾车行驶时间。结果表明，自适应遗传算法在改进了交叉算子和变异算子之后，程序的运行效果更佳，提高了遗传算法的寻优能力。