基于海洋捕食者算法的乡村旅游路径规划研究

姚静娟

(阜阳职业技术学院,安徽 阜阳 236000)

0 引言

随着国民经济的快速发展,国民的生活水平得到了很大程度的提升,越来越多的国民选择外出旅游,这在很大程度上促进了旅游业的快速发展。旅游产业的发展既可以使得不同地区之间的资金流转速度加快,同时也有效带动了周边地区经济的快速发展。乡村旅游在乡村振兴战略实施过程中发挥着至关重要的作用,通过大力发展乡村旅游产业,可以更好地促进农村经济的快速发展,持续增加农民收入。乡村旅游路径规划直接影响到乡村旅游的发展,科学化的路径规划策略促进乡村旅游快速发展,实现乡村经济振兴。李磊等针对传统乡村旅游路径规划算法效率低的问题提出了基于蚁群算法的乡村旅游线路规划算法,同时和模拟退火算法、基本蚁群算法进行对比,验证了所提出的蚁群优化算法具有路径搜索速度快、缓解景点拥堵等优点[1]。储玖琳等对旅游景区游客拥堵疏散路径规划问题进行研究,提出了游客疏散路径规划的数学模型,该数学模型充分地考虑了最短客流疏散时间,将疏散节点与疏散路径上的需求整合到最优疏散路径的选取中,仿真结果表明所提出的数学模型有效减少了旅游景区游客疏散的时间和滞留的人数[2]。孙薇等以西安市为例,采用分步优化、聚类分析、蚁群算法、0-1规划、层次分析等数学方法构建了旅游路线规划数学模型,有效确保了游客游览全国201个5A级旅游景点的时间最短、费用最低[3]。随着乡村旅游的快速发展,乡村旅游路径规划对进一步促进乡村旅游的发展具有至关重要的作用。海洋捕食者算法(Marine Predators Algorithm,MPA)是一种新型元启发式优化算法,具有更强的寻优能力[4]。基于此,提出一种基于海洋捕食者算法的乡村旅游路径规划模型,并通过对比试验说明所提出的乡村旅游路径规划算法在旅游路径规划上的效率更高。

1 乡村旅游路径规划模型及求解

1.1 乡村旅游路径规划模型

乡村旅游路径规划模型是典型的旅行商问题(Traveling Salesman Problem,TSP),即一个人要去若干个景点,其从一个景点出发,在经过所有的旅游景点之后回到出发点,如何选择旅游的路线,确保总的路径最短[5]。从图论的角度来讲,TSP的本质是在带权完全无向图中寻找权值最小的哈密顿回路。TSP问题的可行解为所有景点的全排列,这使得伴随着旅游景点数量的增加将产生组合爆炸,属于NP完全问题。对该问题的精准求解方法有线性规划法、动态规划法等,但是随着旅游景点数量的增多,精准求解方法就变得理论可行实践不可行。对NP完全问题的求解目前常用的算法有遗传算法、蚁群算法、贪婪算法等[6]。

1.2 乡村旅游路径规划模型求解

MPA是由Afshin Faramarzi等人在2020年提出的,该算法对海洋中适者生存的规则进行了模拟。采用MPA对所构建的乡村旅游路径规划问题进行求解,从而获得最短的旅游路线。MPA算法中,猎物与捕食者身份是相互变化的,同时算法特有的海洋记忆存储和海洋漩涡使得算法在优化问题求解中具有更为明显的优势。MPA求解过程如下[7]:

1)初始化。设Xmin和Xmax分别为猎物搜索边界的下限与上限,同时在猎物搜索边界内对初始猎物位置X0初始化,即

X0=Xmin+rand·(Xmax-Xmin)

(1)

式中:rand为闭区间[0,1]上的随机数。

达尔文进化论是物种起源于生物发展的一般规律理论,按照适者生存理论,那么海洋中处于顶级的捕食者相对于其他级别的捕食者在觅食方面具有更为突出的优势,因此可以将顶级的捕食者作为最优解,从而构建精英矩阵,即

(2)

式中:XI为顶级捕食者向量;n为搜索代理的数量;d为维数。

海洋世界属于自然界的重要组成部分,因此捕食者与猎物之间同样也构成生物链,即捕食者寻找猎物,猎物寻找自身的食物,食物继续寻找下一级的食物。因此,不论是捕食者还是猎物,其都可以被定义为搜索代理。MPA迭代的过程中就是顶级捕食者被更加优秀的捕食者替换的过程,即对精英矩阵Elite进行更新,将更新后的顶级捕食者作为此时算法所求得的问题的最优解。与精英矩阵相对应的矩阵为猎物矩阵Prey,海洋中的捕食者通过猎物矩阵Prey来更新自身的位置,猎物矩阵Prey为

(3)

2)优化方案。MPA包含三个阶段:第一阶段为迭代初期,当前的迭代次数小于最大迭代次数的1/3,此时进行全部搜索,通过布朗随机游走来更新猎物矩阵Prey;第二阶段为迭代中期,当前的迭代次数小于最大迭代次数的2/3,此时海洋中的种群分为猎物和捕食者两个部分,其中猎物做Levy运动,负责在搜索空间内开发,捕食者做布朗运动,负责在搜索空间内探索;第三阶段为迭代后期,当前的迭代次数大于最大迭代次数的

2/3,能够有效提升算法的局部开发能力,捕食者策略为Levy运动。MPA三个阶段示意图如图1所示。

图1 MPA迭代三个阶段示意图

第一阶段:在迭代初期阶段,捕食者速度大于猎物速度,优化策略为勘探策略,其数学表达式为

{Si=SB⊗(Elitei-RB⊗Preyi)

Preyi=Preyi+P·R⊗Si

(4)

式中:Si为移动步长,RB为正态分布的布朗运动随机向量,⊗为逐项乘法运算,P=0.5是一个常数,R为区间[0,1]上均匀随机向量。

第二阶段:在迭代中期阶段,捕食者速度与猎物速度同步,优化策略为捕食者基于布朗运动策略负责勘探,猎物基于Levy运动策略负责开发,其数学表达式为

{Si=RL⊗(Elitei-RL⊗Preyi)

Preyi=Preyi+P·R⊗Si

(5)

{Si=RB⊗(RB⊗Elitei-Preyi)

Preyi=Elitei+P·CF⊗Si

(6)

式中:RL为Levy分布的随机向量,CF为控制移动步长的自适应参数,其数学表达式为

(7)

式中:Iter为当前迭代次数,Itermax为最大迭代次数。

第三阶段:在迭代后期阶段,捕食者速度小于猎物速度,优化策略为基于Levy运动的开发策略,其数学表达式为

{Si=RL⊗(RL⊗Elitei-Preyi)

Preyi=Elitei+P·CF⊗Si

(8)

3)涡流和FADs效应。考虑到涡流和鱼类聚集装置(fish aggregating devices,FADs)效应会使得海洋捕食者的觅食行为发生改变,即避免MPA在寻找最优解的过程中出现过早收敛、陷入局部极值的问题,数学模型为

(9)

式中:U为二进制向量,r为区间[0,1]上的随机数,FADs为影响概率,r1和r2为猎物矩阵索引。

2 仿真试验

假定某乡村旅游景区共有10个旅游景点,为验证算法的有效性,10个旅游景点的分布尽量分散,具体如图2所示。

图2 乡村旅游景点分布图

分别采用MPA、GA[8]、PSO[9]求解旅游线路规划问题,各优化算法参数设置如表1所示。

表1 各优化算法参数设置

为对比3种优化算法规划乡村旅游路径的性能,将乡村旅游景区各景点的拥堵情况作为评价指标,对所设置的10个旅游景点开展旅游路径规划,获得乡村旅游景区在10:00～12:00的拥堵情况,结果如图3所示。

由图3可知,采用PSO算法所规划的路径相对于GA算法所规划的路径,景点的拥堵情况得到了一定程度的缓解,特别是景点5的拥堵缓解最为明显。采用MPA算法所规划的路径相对于PSO算法,各景点的游客负载更为均衡,即MPA算法所规划旅游路径更为合理。

为了对比GA、PSO、MPA在迭代寻找最优路径上的效率,设计试验对比3种算法在迭代过程中的进化速度,结果如图4所示。

由图4可知,GA算法在迭代190次以后开始收敛,获得规划最短路径。PSO算法在迭代170次以后开始收敛,获得规划最短路径。MPA算法在迭代100次以后开始收敛,获得规划最短路径。不论是GA算法、PSO算法,还是MPA算法,其均可以通过迭代获得旅游规划最短路径,但是MPA算法获得旅游规划最短路径的效率比较高,优于GA、PSO。

a) GA算法 b) PSO算法 c) MPA算法图3 景区各景点拥堵情况结果

a) GA算法 b) PSO算法 c) MPA算法图4 迭代寻优对比

3 案例分析

乡村旅游作为以旅游度假为宗旨,以村庄野外为空间,对生态环境无破坏的村野旅游形式,备受越来越多市民的喜爱。乡村旅游的快速发展能够有效带动乡村经济的快速发展,为乡村提供更多的就业岗位。乡村旅游路径规划直接影响游客对乡村旅游的满意度,通过科学化的路径规划策略,使得游客能够游览所有的景点,提升乡村旅游的竞争力[10]。选择湖北省十堰市柳陂镇乡村旅游作为研究对象,其包含15个乡村旅游景点,具体如图5所示。

图5 柳陂镇乡村旅游景点

由于所在地是山区,这使得规划最短的旅游路径变得至关重要。采用MPA算法对乡村旅游路径进行规划,迭代次数与最优路径长度关系如图6所示。

图6 迭代寻优过程

由图6可知,采用MPA规划乡村旅游路径,在迭代150次以后开始收敛,获得最短路径长度为17.2 km。柳陂镇15个乡村旅游景点分布和拥堵情况如图7所示。

图7 景点分布及拥堵情况

由图7可知,采用MPA所规划的乡村旅游路径,各景点的游客负载相对比较均衡,其中景点10和景点13相对比较拥堵。

4 结论

乡村旅游是旅游业的重要组成部分,旅游路径规划直接影响到乡村旅游的市场竞争力。乡村旅游路径规划是典型的旅行商问题,采用MPA求解旅行商问题,获得规划的乡村旅游路径。将MPA和GA、PSO对比,通过仿真试验验证了MPA所规划的路径各景点游客负载更均衡,且算法的迭代寻优效率更高。将MPA应用于湖北省十堰市柳陂镇乡村旅游15个旅游景点的路径规划中,结果表明所有景点的游客负载相对比较均衡,最短路径长度为17.2 km,该路径规划对更好地促进乡村旅游的发展具有一定的参考价值。