基于改进遗传算法的研学旅行线路优化与实现※

樊 丹 史晋娜 许 霞

(四川旅游学院，四川 成都 610100)

2013年国家出台的《国民旅游休闲纲要(2013—2020年)》中提出“研学旅行”[1]一词以来，以“文化体验”与“教育”为侧重点的研学旅行逐渐成为学者研究的新热点，研学旅行正处于大有可为的发展机遇期。2016年教育部、国家发展改革委等15个部门印发的《关于推进中小学生研学旅行的意见》中强调，要以基地为重要依托，积极推动资源共享和区域合作，打造一批示范性研学旅行精品线路，逐步形成布局合理、互联互通的研学旅行网络[2]。合理的研学旅行线路是高效开展研学旅行活动的重要保障，因此打造研学旅行精品线路成为研学旅行组织者和旅游服务部门的迫切需求。

1 问题描述

目前，针对研学旅行线路的设计，研究者普遍从旅游资源开发、保护等角度对景点进行筛选和串联设计，较少涉及运用智能优化算法对研学旅行线路进行设计及优化，几乎没有将研学旅行线路进行实景虚拟旅游的创新应用。

设计最优研学旅行线路的问题，可简化为连接各旅游目的地的最短路径问题(TSP旅行商问题)。最短路径问题解决的是如何寻找到一条路径，遍历所有的节点，使路径总长度之和达到最小值。国内外的学者对最短路径问题进行了深入的研究，应用较为广泛的智能优化算法有:粒子群算法[3]、布谷鸟算法[4]、遗传算法[5]、蚂蚁算法[6]等。

由于遗传算法的择优机制是一种“软”政策，使它具有良好的通用性、并行性和稳健性，因此本文选择对遗传算法的择优机制进行改进，以此来提高算法的全局搜索能力。本文整体结构如下：建立时间可达性模型对研学旅行景点进行筛选；使用改进的遗传算法对筛选出的优质研学旅行景点进行串联和优化；重点将遗传算法应用到Android平台，设计实现一款智能手机端的研学旅行线路优化软件，供用户和线路设计者以借鉴与参考。

2 遗传算法设计

遗传算法(GA)起源于对生物系统所进行的计算机模拟研究，20世纪70年代初期由美国密歇根大学的Holland教授首先提出，在一系列研究工作的基础上，同世纪80年代由Goldberg进行归纳总结，最终形成了遗传算法的基本框架。遗传算法模拟的是生物界优胜劣汰进化过程，从一个种群开始，重复执行选择、交叉和变异等遗传算子对种群进行不断进化，最后得到全局最优解[7]。

2.1 染色体的编码与解码

本文采用路径表示的符号编码方法，即将景点编号编码为基因，以景点编号遍历的完整路径编码为染色体，这种编码的方式由路径染色体出发，便于通过快速解码的方式得到相应可行解。

2.2 适应度函数

本文将n个景点的最优旅行线路问题简化为对称型TSP问题，选用的适应度函数为：

(1)

式(1)中，D(i,j)表示第i个景点和第j个景点的实际距离。

2.3 选择算子

为了使群体中的优质个体得以保留，本文选用精英策略与轮盘赌组合选择算子。

2.3.1 采用精英策略来保留优质个体

在每一代的进化过程中，对相对适应度进行排序，以设置保护因子的方式，保留多个优质个体直接复制进入下一代，不参与交叉、变异等遗传运算。个体的相对适应度，计算式如下：

(2)

式(2)中，λ(xi)是第i个个体xi的相对适应度；F(xi)是个体xi自身的适应度。

2.3.2 按轮盘赌的方式对其余的个体进行累计概率选择，最终生成下一代的个体

选用精英策略与轮盘赌组合改进的选择算子，既可以保证优质个体被保留在下一代群体中，又可以避免某个局部优质个体不易被淘汰而快速扩散，提高了算法的全局搜索能力。

2.4 交叉和变异算子

由于普通交叉算子不适合解决TSP问题，本文采用二点交叉和逆转变异的算子来进行产生新子代的操作，在一定程度上使最优模式得以最大可能保留。

2.5 终止原则

对种群进行迭代，当达到最大迭代次数后，即可输出当代最优解和目标函数值，结束遗传算法。

3 遗传算法求解及结果

3.1 案例背景

本文以成都市为例。成都市作为首批国家历史文化名城，承载着四千余年的历史，独特的地理环境和悠久的历史文化造就了成都市丰富的旅游资源，文化旅游特别是研学旅行发展潜力巨大，现有人文景区景点172处[8]。

3.2 旅游景点筛选

本文使用定性和定量结合的方法来完成优质研学旅行景点的筛选与整理。

3.2.1 定性方法

针对研学旅行中旅行者对于出游需求、景点选择的明确程度各有差异的情况，本文选择的研学景点侧重于节省出游路途时间与文化遗传类景点。出于节省研学旅行时间的考虑，所选景点尽量避开交通拥堵的区域。研学旅行更多需要体现它的“教育”功能[9]，在旅行中感受文化的滋养与熏陶，而文化遗产类景点正好切合这一点。结合上述的两个条件，对成都市172个人文景点进行首次筛选和整理，定性地选出35个文化遗产类景点。

3.2.2 景点综合评价模型

运用景点综合评价模型[10]对旅游景点进行定量计算与评价。通过量化各影响因素的权重，求解出景点的综合评价值，客观反映景点的“性价比”，选择出优质研学景点。计算公式如下：

(3)

式(3)中，EV代表该景点的综合评价值，其值越大表明该景点的“性价比”越高，wi代表第i个影响因素ci的权重，vi代表第i个影响因素ci的评价值。

假设研学旅行是以旅行大巴或私家车为交通工具，路况通畅，天气等一切突发情况不纳入考虑范围。运用ArcGIS10.0软件，对景点间的线路进行数字化处理，计算出各景点间的运行时间，得到各景点之间的最短通行时间矩阵。对各景点间的最短通行时间矩阵采用加权平均通行时间的计算，计算公式如下：

(4)

式(4)中，Tij为区域中景点i到景点j的最短通行时间，n为区域中参与分析景点的个数，Mij为景点i到景点j的权重系数，Ai为旅游景点i的时间可达性系数。

3.2.3 景点筛选结果

通过计算可得35个景点的时间可达性系数，综合考虑景点等级、门票费用、时间限制等影响因素，最终选择综合评价值排名前8的景点，景点综合评价值见表1。

表1 景点综合评价指标

3.3 遗传算法的仿真实验结果

3.3.1 遗传算法参数选取

遗传算法参数的选取会影响到最终输出结果的优劣，考虑仿真结果的客观性，程序中初步选取的遗传算法参数如表2所示。

表2 遗传算法参数表

3.3.2 实验结果

通过对优选的8个研学景点进行时间、经纬度等数据的采集，使用MATLAB R2017a对数据进行编码、初始化以及遗传等操作，得出优化前后的研学旅行路径图如1、图2所示。

图1 遗传算法优化前路径图

图2 遗传算法优化后路径图

本文因使用路径染色体编码的优势，可直接在可行解中得到从不同景点出发的最优路线，如表3所示。

表3 最优研学旅行线路

3.3.3 实验结果分析

随着进化代数的增加，最短路径长度逐步下降，在进化至120代之后趋于稳定，如图3所示。

图3 遗传进化路线

由图1、图2、图3的分析可以看出，本文中改进的遗传算法可以有效解决研学旅行线路优化问题，由此验证了经过改进的遗传操作策略是可行与有效的。

4 Android终端程序设计与实现

为了使研学旅行者能更好地获取旅游景点，更快捷地获得最优旅行线路等相关信息，达到集体和自主旅行的多重目标。本小节将改进的遗传算法应用到Android平台上，设计开发了一款智能手机端的研学旅行软件，从遗传算法的角度合理地减少旅行者在时间和经济等方面一些不必要的开支。

4.1 开发环境搭建

本文中选用Android Studio 2.3.3进行Android项目的开发，软件配置环境如表4所示。

表4 配置环境

4.2 界面设计实施

4.2.1 系统功能设计

研学旅行APP主要以成都市周边研学旅行线路优化为例，其主要服务对象是研学旅行者，主要功能是为研学旅行者提供最优旅行线路规划、定位及景点查询服务。系统功能设计如图4所示。

图4 研学旅行系统功能结构图

研学景点模块是整个系统功能的核心模块，包括研学景点概览、智能规划两个子页面。研学景点概览页面采用列表的形式展示各个研学景点介绍及图片信息的选择按钮。智能规划页面通过研学线路智能规划的选择按钮，主要展示利用改进的遗传算法对研学景点的数据信息进行整合与计算，推送给用户最优的研学旅行行程总览，实现实景虚拟旅游的创新运用。

4.2.2 用户界面的设计实现

4.2.2.1 研学景点功能设计实现

研学景点模块是系统的核心功能模块。界面的编程在SpinnerActivity类中实现，在SpinnerActivity类中，分别对各个图标按钮的点击事件setOnItemClickListener()进行监听，并重写onItemClick()方法。当用户进行选择操作时，控制当前Activity跳转到具体的功能界面。该界面的运行效果截图如图5所示。

4.2.2.2 搜索景点与定位功能设计实现

搜索景点、定位模块其主要作用是为用户提供其他辅助功能，通过对百度地图的二次开发实现该模块的功能,可搜索成都及其他城市旅游景点信息及定位。界面的编程分别在Main3Activity及locationActivity类中实现，运行效果截图如图6所示。

图6 其他功能界面运行

4.3 系统测试与测试结果分析

4.3.1 系统测试

对客户端的测试主要分为功能测试、开发平台测试两个方面。在整个系统的开发阶段，测试设备的类型包括Android虚拟机和Redmi Note3，测试平台为:蒲公英内测平台。

4.3.2 测试结果分析

从测试结果来看，系统的界面功能模块实现正常、运行稳定，各项的测试结果均达到预期效果。特别是研学景点这一核心功能模块，将本文所改进的遗传算法应用到系统中进行研学旅行线路优化，及时推送给用户有效地优化旅游线路，输出的详细规划结果更具智能化和人性化。

4.3.3 用户使用

用户只需通过扫描二维码的形式免费下载使用，二维码如图7所示。

5 结论与展望

面对研学旅行组织者在线路规划方面所遇到的困难与旅行者的个性化旅游需求现状，本文利用改进的遗传算法求解成都周边研学旅行线路优化问题，设计并实现了遗传算法科学应用到Android开发平台的研学旅行APP。经过严格的算法实验与系统测试后，结果表明遗传操作是有效的，研学旅行系统的功能模块实现正确、运行稳定。改进的遗传算法对研学旅行线路优化及研学旅行APP的设计与实现，使研学旅行线路规划更加智能和实用，为研学旅行线路的设计优化提供有力的支撑，具有较好的借鉴、参考意义。