基于改进鱼群算法的园林路径设计优化方法研究
2020-12-28阙晨曦邓双兰思仁
阙晨曦 邓双 兰思仁
摘 要： 针对园林景观路径规划对于个性化服务与智能规划的需求，文中提出一种基于改进鱼群算法的园林景观路径设计优化方法。该算法通过构建二维导览模型来确定优化路径平滑度与总长度目标函数，实现无障碍路径规划。针对传统人工鱼群算法局部搜索能力较差、前期容易出现盲目搜索的问题，将和声搜索算法引入人工鱼群算法，对鱼群信息进行微调扰动从而得到更优的全局最优路径。仿真与实验测试结果表明，所提出的方法能够有效优化园林路径规划问题，进而得到更平滑、更合理的园林导览路径，且所提出的改进算法相对于传统算法具有更快的收敛速度。
关键词： 园林景观; 路径规划; 改进鱼群算法; 和声搜索; 最优路径; 仿真测试
中图分类号： TN915.02?34; TP391 文献标识码： A 文章编号： 1004?373X（2020）24?0113?04
Research on garden path design optimization method based on
improved fish swarm algorithm
QUE Chenxi1， DENG Shuang2， LAN Siren1
（1. Fujian agriculture and Forestry University， Fuzhou 350007， China;
2. Shanghai Tongji Urban Planning and Design Institute Co.， Ltd.， Shanghai 200092， China）
Abstract： In allusion to the demand for personalized services and intelligent planning for landscape path planning， a garden landscape path design optimization method based on improved fish school algorithm is proposed. The algorithm is used to build the two?dimensional guiding model to determine the objective functions of optimization path smoothness and total length， so as to achieve the barrier?free path planning. Aiming at the problem of poor local search ability and blind search in the early stage of traditional artificial fish swarm algorithm， the harmony search algorithm is introduced into the artificial fish swarm algorithm， and the fish swarm information is fine?tuned and disturbed to obtain a better global optimal path. The simulation and experimental testing results show that the proposed method can effectively optimize the garden path planning and obtain a smoother and more reasonable garden guiding path， and the proposed improved algorithm has faster convergence rate than that of the traditional algorithm.
Keywords： garden landscape; path planning; improved fish swarm algorithm; harmony search; optimal path; simulation testing
0 引 言
隨着物联网技术和高性能电子设备的迅速发展与推广，智慧安防、智慧医疗及智能交通等应用均采用了物联网的技术框架与思路为用户提供更加便捷化、人性化的服务[1]。同时为了加快旅游事业的发展，推进物联网技术在智慧园林中的应用，国内各大景区不断增加软件与硬件设施来构建园林智能导览系统[2?4]。该系统以APP的形式为旅客提供各类景点信息，实现用户与园林的智能交互[5?7]。其中，园林路径导览规划是智慧园林建设的重要一环，其通过引入智能路径规划应用为游客提供实时目的地图引导[8?10]。
目前，为了提升路径规划的运行速度与精确度，在各应用领域提出了多种智能优化和处理算法。文献[11]为了实现智能泊车入库，提出一种基于车辆运动模型的自动泊车路径跟踪算法。文献[12]提出使用遗传优化算法来提升工业机器人路径搜索的精度。文献[13]中，为了保证冷链物流运输的及时配送，通过分析车辆运行成本、货物变质成本和冷藏成本来构建车辆取货配送优化模型。文献[14]将低碳经济的思路引入冷链物流路径规划问题中，采用蚁群算法求解最优运输路径。
然而，目前针对园林导览路径规划的研究仍较少。为了提供个性化与智能化的路径规划流程，本文提出一种基于改进鱼群算法的园林路径规划算法。该算法通过构建园林导览二维模型来确定路径规划目标，并基于人工鱼群算法的迅速收敛与全局优化能力求解该多目标优化问题，实现了园林路径的快速规划。仿真与实验结果表明，所提出的方法能够有效解决园林路径规划问题，相对于传统算法具有更快的收敛速度。
1 园林路径规划模型
园林路径规划即根据用户的当前位置与目的位置，构建一条最优的游览路径。本文将该问题表示成在给定的直角坐标系xOy中，求解从起始点[S（xS，yS）]到目标点[T（xT，yT）]的最优路径问题。为了简化计算，本文将该直角坐标系进行仿射变换，将起始点到目标点间的路径表示为直线段ST，则xOy坐标系上的任意一点[P（X，Y）]可以表示为：
[xy=cos θ -sin θsin θ cos θ-1?XY-xSyS] （1）
[θ=arcsinyT-ySST] （2）
式中：[θ]为直线段ST与x轴间的距离;[（x，y）]为[P（X，Y）]映射后的坐标点。
由于在路径规划中存在各种障碍物，文中将其分为多边形障碍物与圆形障碍物。为了避免导览路径和障碍物发生碰撞，本文定义了以下防碰撞条件。
1） 防多边形碰撞。为了防止规划处的路径与多边形障碍物发生碰撞，本文设定的条件为：
[[（P1-Q1）（Q2-Q1）]?[（Q2-Q1）（P2-P1）]>0[（Q1-P1）（P2-P1）]?[（Q2-P1）（P2-P1）]>0] （3）
式中，两条线段的端点由[P2P1，Q2Q1]表示。
2） 防圆形碰撞。为了防止规划处的路径与圆形障碍物发生碰撞，本文设定的条件为：
[（y2-y1）x0-（x2-x1）y0+（y1x2-x1y2）（y2-y1）2+（x2-x1）2>R] （4）
式中：[x2x1，y2y1]为两条线段端点; [（x0，y0）]为圆形障碍物的圆心;R为半径。
2 基于改进人工鱼群算法的路径规划
为了获得距离更短、更平滑的目标线路，本文结合权重系数法来定义园林导览路径。该目标函数包括总长度[f1（P）]与平滑度[f2（P）]目标，具体表示如下：
[f（P）=w1f1（P）+w2f2（P）] （5）
式中，[w1，w2]为权重系数。
文中使用鱼群算法求解上述多目标优化问题，其是一种源于仿生学的智能优化算法。通过采用计算机程序来计算模拟鱼群的觅食、聚群、追尾及随机行为，从而求解目标函数并得到其最优解。然而，该算法在前期容易出现盲目搜索的问题。本文为了提升算法的全局搜索能力，将和声搜索算法引入其中。通过在迭代过程中产生大量的局部最优解，来提升鱼群随机行为的搜索效率。
文中假设搜索空间中存在N条人工鱼，并用[X=（x1，x2，…，xD）]表示人工鱼的状态信息，[f（x）]表示食物浓度，Y为式（5）所示的适应度函数值，[Xi-Xj]为人工鱼i与j间的距离。文中将和声搜索微调后的人工鱼状态赋值给人工鱼群，公式如下：
[X=（x1，x2，…，xD）=Xi=（xi1，xi2，…，xiD）] （6）
从人工鱼[Xi]的视野[Visual]内随机抽取一个状态[Xj]来更新[Xi]，公式如下：
[Xj=Xi+Visual·Rand（）] （7）
当更新后的状态[Xi]优于[Xj]时，则向状态[Xj]移动一定步长，公式如下：
[Xt+1i=Xti+Xi-XtiXi-Xti·step·Rand（）] （8）
当状态[Xi]不优于[Xj]时，继续更新[Xj]，直至达到最大觅食次数，公式如下：
[Xt+1i=xti+Visual·Rand（）] （9）
假设某人工鱼所处的状态为[Xi]，在其视野范围[dij
[Xt+1i=Xti+XC-XtiXC-Xti·step·Rand（）] （10）
对处于状态[Xi]的人工鱼，通過搜索其周围的同伴数量[nf]，计算[Xj]的最大适应度值[Yj]。当[Yjnf [Xt+1i=Xti+Xj-XtiXj-Xti·step·Rand（）] （11） 基于上述步骤与寻优操作，文中结合鱼群密度与追尾行为形成人工鱼库，并通过寻优操作生成新种群。然后使用和声搜索算法进行微调扰动，及时跳出局部最优解，从而得到全局最优解。其中，和声搜索的扰动因子为[δj（t）]，则人工鱼的状态演变公式为： [x′i（j）=xi（j）+δj（t）] （12） 本文提出的改进人工鱼群搜索算法的整体流程如图1所示。 1） 算法初始化。设置鱼群数量为N，每条鱼的视野为Visual，更新步长为Step。 2） 鱼群行为选择。根据每条鱼的追尾行为、觅食行为得到相应的[Xj]，并根据[Xnew=Xi+2·Visual]对[Xj]的每个分量进行混沌搜索。当状态[Xi]优于[Xj]时，使用式（8）更新[Xi];否则，使用式（9）更新[Xi]。
