改进遗传算法求解文化旅游线路规划问题

张瑞姣，陈崇成*，黄正睿，方 荟,2

(1.数字中国研究院(福建)福州大学空间数据挖掘与信息共享教育部重点实验室，福建 福州 350116；2.闽江学院福建省信息处理与智能控制重点实验室，福建 福州 350108)

“自由”旅行方式因其能快速推荐旅游行程，辅助游客决策而广受欢迎。旅游线路规划是旅游推荐领域研究的热点，而旅游线路规划问题(tourist trip design problem，TTDP)则是针对有兴趣访问多个兴趣点(point of interest，POI)的游客的旅行计划问题，需要顾及游客偏好，使其满意度最大化，其本质上是带利益的旅行商问题或者车辆路径问题[1]，即非确定性多项式难题(nondeterministic polynomially problem，NP)。定向运动问题(orienteering problem，OP)是TTDP的一个简化模型，是指在限定时间内访问具有相关利润的多个地点，且每个地点只能访问一次，使得推荐的旅行线路具有最大的总利润。针对OP的研究，根据不同的限制条件发展了多种变体，如考虑景点开放时间作为限制条件的带时间窗口的OP问题(OP with time windows，OPTW)[2]等，从而使规划的线路更加符合实际。现有的OP研究大多是面向热门旅游景点，且仅考虑POI的单个属性特征作为景点的利益(如评分最大、距离最小、花费最小等)来构建目标函数，但这并不适用于文化旅游领域。文化旅游中的POI具有许多重要特征(例如文化背景、历史相关性等)，这些重要特征是文化旅游的核心竞争力。因此，需要将每个特征的分数范围都与该POI相关联，利用OP建模，为每个POI建模多个分数[3]，从而综合衡量POI。

目前，TTDP的求解方法主要包括精确算法、启发式算法和智能化元启发式算法。其中，精确算法虽然能得到精确的解，但其搜索能力较差，只能适用于小规模的POI规划[4]。启发式算法能够在短时间内得到可行解，但解的质量并不高[5]。智能化元启发式算法成为解决该问题的主流算法。元启发式算法包括遗传算法[6]、粒子群算法[7]、蚁群算法[8]、模拟退火算法(simulated annealing algorithm，SAA)[9]等。SAA是一种源于固体退火原理的启发式优化算法，可以较大概率获得全局优化结果，广泛应用于优化问题、旅行商问题等。遗传算法(genetic algorithm，GA)源于达尔文提出的自然进化论的思想，遵循竞争的自然法则和优胜劣汰的生存法则[4]，因其搜索速度快、随机性强、过程简单、灵活性强的特点而广泛应用于各个领域，例如组合优化、生产调度等。但GA也存在固有的弊端，种群会在进化过程中因多样性的减少而造成过早收敛问题，也称局部最优问题[10]。因此，保证种群多样性以避免算法陷入局部最优。国内外学者对于上述GA问题的解决研究可大致分为两类：一是提高初始种群质量；二是保持进化中种群多样性等。LI等[11]提出了基于信息熵与博弈论的混合GA(hybrid genetic algorithm，HGA)，利用信息熵生成初始种群以提升其多样性，避免算法陷入局部最优解。谭文安等[12]利用混沌理论在GA初始种群获得更优秀的初始群体, 从而提高算法效率。SUN等[13]提出了利用余弦相似性理论对相邻种群间的多样性和相似性进行限定，通过对交叉和变异概率的自适应调整，保持进化过程中的种群多样性，提高算法的收敛和全局最优解。WANG等[14]提出了基于多子代的GA(multi-offspring genetic algorithm，MO-GA)，利用多个交叉算子产生多个子代种群以提高种群子代的多样性，解决旅行商问题，使得可行解更加接近最优解。王福林等[15]利用两点交叉算子产生多子代保持种群遗传进化中的生物多样性，提高遗传算法的收敛速度。XIN等[16]利用多子代战略，在传统遗传算法之后增加多域倒位遗传算子，解决旅行商问题，显著提高种群多样性，提升算法收敛和鲁棒性。

本文在上述研究的基础上，提出了改进的GA以求解文化旅游线路规划问题。首先，根据景点的文化属性构建旅游线路规划模型；其次，利用Jaccard系数和多变异算子提升GA的初始种群和进化中种群的多样性，避免算法的早收敛问题；再次，以长征景点中遵义会议为例，对比提出算法与GA求解模型，证明了所提算法的优越性。

1 文化旅游线路规划模型

本文借鉴OPTW，即在OP的基础上考虑POI的到达时间要在景点的时间窗之内，公式如下：

Topentime≤Tarrivetime≤Tclosetime

(1)

若Tarrivetime=Tclosetime，则游客不能充分游览景点造成旅游体验差。因此，本文将到达时间与游览时间相加得到游览完景点的时间点，使其不得超过景点关闭时间，并以最大化综合线路评分为目标函数。

1.1 问题描述

由于景点文本中干扰信息多，涉及文化信息的较少，常用的文本挖掘方法会造成挖掘结果精度不准的问题。为此，本文采用正则表达式来精确表征一组字符串[17]，并以具有重要意义的长征文化为例，通过红色旅游构成要素[18]及长征文化特点，确定待挖掘景点的文化特征，包括人物、事件和类型(如红军亭、红军桥等)。利用HanLP工具对文本进行分词，然后预定义文化特征，利用正则表达式将景点与特征精确匹配。

模型顾及多种限制因素，包括游客需求和景点属性，其中，游客需求包括游客偏好、起始位置、旅行天数；后者则包括景点的经纬度、文化特征、开放时间、评分、游览时间。为了便于数学模型构建，对模型涉及的问题进行描述，模型涉及到的符号及其含义见表1。

表1 符号及含义

定义1景点信息。对于每一个景点Si⊂S，Si={tt,l,to,tc,w,r} ，其中r为景点标签集合，r={rp,re,rl}，便于游客选择感兴趣文化主题或景点文化类型。

定义2POI集合s。s是指游客选择了感兴趣的r后产生的POI集合，s={s1,s2,…,sn}，其中n表示集合中POI的数量。

定义3交通时间ttr。ttr为两部分，分别是ttru和ttrs。对于线路c={s1,s2,…,sk}，k=1,2,…,n，k≤n，则

(2)

(3)

(4)

定义4景点到达时间ta。ta对于不同时段的景点有不同的数学表达式。对于多日旅程，旅行第一天选定的第一景点的到达时间如式(5)所示，其余旅行新一天中第一个景点的到达时间如式(6)所示，其余ta则参照式(7)。

ta(si)=ts+ttru(ps,si)

(5)

ta(si)=ts+ttrs(si,sj)

(6)

ta(sj)=ta(si)+ttrs(si,sj)+tt(si)

(7)

定义5游客总旅行时间T。T由游客的交通时间和景点游览时间组成，对于线路c={s1,s2,…,sk}，k=1,2,…,n，k≤n，则

(8)

定义6景点综合评分sw。sw由两部分组成，即景点评分和景点文化特征，分别对两者进行归一化处理即可得到景点综合评分，其中景点文化特征需要每个特征按归一化过程处理。

(9)

式中：wmin、rpmin、remin、rlmin分别表示Si中评分、人物、事件和文化类型的最小值；wmax、rpmax、remax、rlmax分别对应上述最大值。

定义7线路综合评分Z。Z即线路包含的景点的综合评分之和。若对于c={s1,s2,…,sk}，k=1,2,…,n，k≤n，则c的线路综合评分为

(10)

1.2 OPTW模型

OPTW模型以综合线路评分为目标，充分考虑游客偏好、旅游时间等因素，从而求解更为合理的旅游线路。OPTW数学模型可以表示为

(11)

s.t.T

(12)

(13)

(14)

ttru(ps,si)

(15)

(16)

其中：式(11)表示模型的目标函数；式(12)表示T要满足游客的旅行总时间要求；式(13)表示对景点是否游览标注；式(14)表示更为严格的时间窗控制；式(15)表示游客从起始位置到首个景点的交通时间应在某个时间段；式(16)表示一个假设条件，即景点间的往返距离一致。

2 遗传算法改进

2.1 进化策略

2.1.1初始化种群产生方式的改进

Jaccard相似系数可用于比较有限样本集之间的相似性和差异[19]。本文引入Jaccard相似系数产生初始种群，利用Jaccard相似度得到个体间的相似性，然后通过Jaccard距离计算个体间的差异。Jaccard相似系数为

(17)

Jaccard距离为

D(pi,pi+1)=1-J(pi,pi+1)

(18)

式中：pi、pi+1分别为初始种群中的个体；M为种群规模。个体间的Jaccard距离与Jaccard相似度相反：J(pi，pi+1)越大表明个体间基因的重叠率越高，个体越相似，反之则差异越大；而D(pi，pi+1)越大，表明个体间差异越大。

2.1.2多子代策略

根据WANG等[14]提出的多子代策略，在交叉算子后增加多个变异算子产生多个子代个体，从父代与子代个体中选择适应度最好的个体组成新种群。突变算子是一种维持从一个种群到下一个种群的遗传多样性的操作[20]，则多个突变算子可以增加种群多样性。本文选择常用的3种变异算子：倒位变异、多次交换变异和插入变异。其中，倒位变异是指两变异位置之间的基因倒序排列得到子代的过程；多次交换变异就是多次进行交换变异操作，以p1=[1,2,3,4,5,6]两次交换变异为例，第一次交换2、4，则得到p2=[1,4,3,2,5,6]，第二次交换1、6，则得到最终变异p3=[6,4,3,2,5,1]；插入变异是将第2个变异位置的基因插入第1个变异位置基因之后。

2.2 算法流程

综上所述，本文提出了多变异算子的遗传算法(Multi-Mution GA，MMGA)，算法的流程图如下：

图1 MMGA流程图

MMGA的具体步骤如下：

步骤1初始化种群生成。利用Jaccard产生初始种群，产生过程如下：

1)设定临界距离H0。

2)使用随机方法产生第1个个体。

3)用同样的方法生成之后的个体，同时计算新产生的染色体与种群已有个体的Jaccard 距离H。如果满足H>H0，则该个体添加到新种群；否则，重新生成新的个体，直至满足H>H0。

4)重复步骤3，达到设定的种群规模M即可得到初始种群。

步骤2适应度评价。适应度评价是根据目标函数式(11)和各种限制条件，计算个体中满足约束条件的POI，求解适应度。

步骤3采用赌盘选择法选取M(种群规模)个个体组成种群进行之后的交叉操作。

步骤4采用类似于顺序交叉的方式，随机产生2个交叉点，将一个体基因的第3部分作为开始，将另一个体去除重复的基因依次插入之后产生一个子代个体，同样的方式产生另一子代个体。

步骤5采用倒位变异、多次交换变异和插入变异对父代个体进行变异操作，产生3个子代个体。

步骤6计算步骤5产生的子代个体和父代个体的适应度，并选择其中适应度最大的个体组成新的种群。

步骤7判断是否满足遗传进化终止条件。本文将最大进化代数设为终止条件，若进化代数小于进化代数最大值，则返回步骤2继续执行；否则，算法结束，输出适应度最好的个体(即可行解)。

3 实验设计与结果分析

3.1 数据介绍与案例说明

3.1.1数据介绍

长征是1934—1936年中国共产党领导的中国工农红军第一、二、四方面军和红二十五军分别从各根据地向陕甘地区进行的战略大转移，其铸就的长征精神和文化是我国优秀文化和爱国精神的重要组成部分。长征跨越地域范围广，沿途旅游资源较为分散。

长征旅游景点数据以田竞等[21-25]的《重走长征路》系列图书为数据源收集景点数据，辅以望路者旅游网站、百度百科、文献等的景点文化信息，共得到376个景点数据。对长征旅游景点等级状况进行统计，其中，国家4A级和5A级景点的数量分别为26个和4个，国家级文物保护单位70个。长征景点简介信息是由景点的位置、基本情况及涉及的长征人物、时间等组成的文化文本，以福缘桥景点为例，如图2所示。线路规划时需要考虑景点的相关属性信息，则景点所含信息见表2。

图2 福缘桥景点简介

表2 景点信息

3.1.2案例说明

以游客偏好为遵义会议的事件文化特征为例，与之相关的景点不只是遵义会址、红军总政治部。遵义会议是个历史过程，其前后会议如通道会议、黎平会议、会理会议等可看作遵义会议的系列会议[26]，因此，这些会议也是遵义会议事件标签的组成部分。此标签集中分布在云贵川的交界区域，地理跨度较小，共包含17个景点，景点名称及对应评分、人物、事件、类型见表3。

表3 遵义会议景点名称及评分、文化特征

3.2 实验与结果分析

3.2.1实验环境与参数

实验是在CPU为Intel(R)Core(TM) i7-4700 3.40 GHz、内存为32 GB、操作系统为 Windows 7旗舰版的 PC 机上进行。算法基于Eclipse软件平台，Java的版本为1.7的环境实现，使用到的工具包包括HanLP等。实验参数见表4。

表4 实验参数

3.2.2实验结果与分析

为了验证MMGA的优越性，将MMGA与传统GA以及SAA进行比较，以线路的综合评分为评价指标。实验分为两部分：一是相同旅行天数不同时间约束对比，二是相同时间约束不同旅行天数对比。每次算法得到的线路综合评分略有不同，因此每组实验运行100次，取平均值得到每组线路的综合评分。其中，游客的起始位置设为遵义会议火车站。

1)相同旅行天数不同时间约束对比

以旅行天数为2天为例，每天的旅行时间约束分别为6、7、8、9、10、11、12 h，得到不同时间约束下算法的对比，如图3所示。由图3可知，时间约束为9 h之前，3种算法的线路综合评分随着每天旅行时间的增加逐渐增加；时间约束为9 h之后，MMGA线路综合评分趋于平稳，SAA先增后降，GA则略有增长；与GA、SAA相比，MMGA线路综合评分最高，可以获取更高综合评分的线路。

图3 不同时间约束线路综合评分对比

2)相同时间约束不同旅行天数对比

通常每天的旅行时间ts为8 h，依据景点的关闭时间，将每天的时间约束设置为10 h。以天数分别为1、2、3、4、5、6 d的旅游天数为例，进行6组实验，生成遵义会议的一日至六日游的旅游路线，如图4所示。由图4可知，不同旅行天数限制下线路综合评分的对比，MMGA可以获得更高的线路综合评分。

图4 不同旅行天数线路综合评分对比

由于MMGA初始化种群产生方式的改进和多子代策略，算法中种群个体更为多样，后续参与遗传进化的种群个体有更高的适应度，使得算法可以快速获取优质可行解，有效避免了GA早收敛导致的局部最优问题，提升了算法的全局寻优能力。因此，MMGA在线路规划方面的结果要优于传统GA和SAA，能够推荐综合评分更高的线路，在满足景点热度的同时满足游客的文化需求，让游客可以充分游览景点，获得更好的旅游体验。但是，由于景点间的评分及文化特征差异较小(表2)，导致不同算法推荐线路的综合评分差异不显著。

4 结论与展望

本文基于OPTW构建文化旅行线路规划模型，该模型综合考虑了游客的起始位置、文化偏好、旅行天数、景点开放时间等多种约束因素，并根据景点的文化特征综合评价景点，设置线路利益目标函数。为了有效求解上述模型，提出了MMGA，利用Jaccard提高初始种群质量，通过多变异算子保持算法进化过程种群多样性，提升了算法全局寻优能力。实验结果表明，MMGA相较于传统GA和SAA能够规划出更为合理的旅游线路。但改进的算法相较于原算法更为复杂，算法运行时间会增加，此外，线路规划没有考虑环境因素，例如游览当天的天气状况、交通状况等；因此，今后工作中可以考虑算法运行时间的优化及多种现实条件下的线路规划，使路线能更贴近实际。