网站首页  词典首页

请输入您要查询的论文：

　

标题 基于改进蚁群算法快速求解迷宫路径问题研究
范文 杨乐 向凤红 毛剑琳

摘要：针对传统蚁群算法收敛速度慢、搜索时间长、易陷入局部最优等缺点，在其基础上重新定义信息素更新方式。在搜索路径上进行选择优化处理，对搜索出的最短路径做平滑优化处理，使其能快速有效地搜索出最优路径。在解决迷宫路径问题上对传统蚁群算法进行了改进。仿真实验对比表明，改进后的蚁群算法在求解时间和距离上都远优于传统蚁群算法，能快速有效地求得问题的最优解，使解决二维路径问题得到进一步优化。
关键词：蚁群算法；迷宫；路径优化
DOI：10.11907/rjdk.173093
中图分类号：TP312
文献标识码：A文章编号：1672-7800（2018）007-0108-03
Abstract：Inthispapertosolvethemazeroutingproblemofthetraditionalantcolonyalgorithmisimproved，thetraditionalantcolonyalgorithmslowconvergencerateandlongsearchtime，easytofallintolocaloptima，onthebasisofredefiningthepheromoneupdatemethods，theselectionandoptimizationofprocessinginthesearchpath，smoothingoptimizationoftheshortestpathsearch，whichcanquicklyandeffectivelysearchtheoptimalpath.Throughsimulationexperiments，theimprovedantcolonyalgorithmisfarbetterthanthetraditionalantcolonyalgorithminsolvingtheoptimaltimeanddistance，theimprovedantcolonyalgorithmcanobtainmorefastandefficientsolution，afurtheroptimizationinsolvingtheproblemoftwo-dimensionalpath.Toovercomethetraditionalantcolonyalgorithm′sdefaultsofslowconvergencerate，longresearchtimeandgreattendencytolimmittolocaloptimalsolution，weredifinethepheromoneupdatemethod.Thesearchpathisselectivelyoptimizedandtheshortestpathissmoothedtosearchtheoptimalpathquicklyandefficiently.Thetraditionalantcolonyalgorithmonsolvingmazepathisimproved.Thesimulationexperimentsshowthattheimprovedalgorithmcanobtainfasterandmoreeffiecientsolutionsothatthesolutionfortwo-dimensionalpathisoptimized.
KeyWords：antcolonyalgorithm；maze；pathoptimization
0引言
迷宮问题是数据图形领域的经典问题[1]。迷宫指道路环境复杂，从入口进入之后很难找到出口的建筑物[2-3]。迷宫最优路径指从入口到出口距离最短的一条路径[4]。传统的蚁群算法搜索迷宫最优路径时，需要很长的搜索时间用来生成和更新信息素，辅助蚂蚁快速找到终点位置，然而求解速度和所需要的算法空间会随着迷宫环境复杂度的增大而不断增加[5-6]。文献[7]对二维空间进行环境建模，采用蚁群算法对机器人进行全局二位路径搜索；文献[8]引入一种变异算子，在搜索设计和信息素更新方式上进行改变，引入逆转变异和插入变异算子，对传统蚁群算法进行了局部优化改良；文献[9]引入精英策略，加入遗传算法中的排序概念，重新定义一种信息素更新方式，有效改善了蚁群算法求解速度慢的问题，增加了蚁群算法的求解速度和精确度；文献[10]加入遗传算法思想，在求解路径问题上设计编码、适应值函数、遗传操作，优化演化过程中的基因，提高搜索速度，快速解决了二维路径问题；文献[11]在蚁群算法中加入了平滑因子，平滑蚁群算法能避开障碍物，有效降低路径长度，增大了转折角度，路经规划结果优于传统蚁群算法。
本文借鉴已有文献算法，针对提高路径搜索时间与减少路径距离进行了研究。对传统蚁群算法进行了改进，在时间复杂度以及路径距离上进行了改进，在解决迷宫路径问题上取得了很好的结果。
1蚁群算法及改进思想
蚁群算法（AntColonyAlgorithm，ACA）是由意大利学者M.Dorigo等[12]于20世纪90年代提出的一种新的模拟算法，真实模拟了自然界蚂蚁群体的觅食行为，应用于交通、通信、化工、电力等领域，成功解决了许多组合优化问题[13]。
传统求解迷宫路径问题算法一般采用广度优先搜索或深度优先搜索，对求得的全部路径进行比较从而得到最优路径，该算法缺点是搜索效率低。随着人工智能算法研究的不断深入，涌现出仿生智能算法如遗传算法、蚁群算法等，相对于传统算法，在搜索效率上有了很大提高，但结果往往近似于最优解而非最优解。
本文对蚁群算法作了改进，在蚂蚁路径搜索过程做了几点调整：
（1）本文基于栅格环境求解最优路径。当蚂蚁所在位置有多条路径可搜索时，设蚂蚁当前位置为普通节点。当只有一条路径可以搜索时，就当前蚂蚁位置进行颜色标记。当蚂蚁所在位置搜索到的路径是封闭的、只能原路返回时，设置当前蚂蚁释放的信息激素为零并反馈所处节点信息素为零，直到返回到的节点为普通节点后再进行下一节点搜索。这样蚂蚁在下一轮搜索中就不会选择这条信息素几乎为零的道路，大大缩短了蚂蚁搜索的时间，提高了算法运行效率。
（2）在信息素更新方式上采取局部更新和全局动态更新相结合。当搜索出一条没有比其更短的路径时，蚂蚁会不断增强该路径信息素，从而忽视没有涉及到的节点。随着时间的积累，很容易导致搜索出的路径不是最优解。本文在信息素更新基础上，改变了原有的更新原则：当蚂蚁经过该路径时适当降低该路径信息素浓度，增加选择其它更优路径的概率，从而进行比对，有利于搜索出最优路径。
（3）对得到的最优路径进行优化处理。搜索结束得到一条完整的路径后，在迷宫中一定会有很多转折次数，并且转折角度有大有小，对路径有很大影响。对这些转角作平滑处理，增大转角度数降低转角次数以有效降低路径长度，从而使路径尽可能显得平滑，达到缩短起点到终点距离的目的。
2迷宫建模
主要利用栅格环境求解最优路径，根据实际需要构造不同复杂程度的二维地形图。如图1所示，用MATLAB构造一个四进四出的二维迷宫地形图，起点终点可以设置，其中黑色栅格相当于障碍物，迷宫中的围墙表示不可以通过，白色栅格相当于道路表示可行走通过。要求在移动时只能向周围白色栅格移动一步，在此基础上求解出最优路径。
3算法设计及流程
基于改进蚁群搜索算法流程如下：①初始化参数，根据迷宫规模大小、复杂程度进行抽象环境建模，确定入口起点、出口终点位置，将所有的蚂蚁置于起点；②计算各可行节点的启发函数，启发函数值是下一节点到终点距离的倒数，采用轮盘赌法选择下一可行节点；③当蚂蚁k移动到下一节点时，根据公式对当前节点进行局部信息素更新；④当判断蚂蚁进入死胡同需要原路返回时，设置当前节点信息素为零，并设置返回节点中的信息素也为零，直至返回到普通节点；⑤判断是否所有蚂蚁均到达终点，若是则进行全局信息素更新，若否则返回步骤②继续寻优；⑥判断是否达到最大迭代次数，若否则转向步骤②继续寻优，如是则输出当前群体中最短路径，即求解的最优路径；⑦对搜索求解出来的路径进行最后的优化处理。
3.1信息素更新
信息素更新是整个蚁群算法中最重要的一环，关系到能否成功求得最优路径。蚂蚁是依靠信息素浓度大小选择下一节点的，所以信息素初始化及更新方法在蚁群算法中有着非常重要的意义，改进信息素的更新方式也是改进蚁群算法的最佳方式。对迷宫的环境进行栅格建模，将整个搜索空间离散为二维空间上的点，这些点就是蚁群搜索路径中需要搜索的节点。因此，每个点都会对应一个信息素值，用来吸引蚂蚁。信息素浓度越高，经过该点的可能性越大，每个点在蚂蚁经过之后信息素的值都会实时更新。
信息素更新采用局部更新和全局更新相结合，局部更新信息素添加衰减系数，该点的信息素大小会随着蚂蚁的经过而减小，局部更新的目的是通过减小已经过点的信息素值增加蚂蚁未经过点的搜索概率，从而达到全局搜索目的。信息素更新公式为：
全局更新指所有蚂蚁完成从起点到终点的路径搜索时，以每只蚂蚁搜索路径的长度作为评价值进行比对，选出最短路径。路径越短，该路径上点的信息素值增加越大。信息素更新公式如下：
3.2群搜索策略
蚂蚁在当前点选择下一个点步骤如下：
（1）根据该点周围环境确定下一节点的可行点集合。
（2）根据启发函数公式依次计算该点到下一节点内可行点集合的启发函数值H（t），启发函数值大小表示下一节点到达终点距离的远近，有助于快速寻找到最优点。
（3）计算在可行节点内任一点的选择概率P：
（4）根据各点的选择概率采用轮盘赌法选择下一节点。
4实验仿真
分别采用传统蚁群算法和改进蚁群算法在跨度为17×17的正方形迷宫中搜索出一条从入口到出口的最佳路径。路径规划起点坐标为（0.5，17），终点坐标为（17，0.5），同时也可以任意设置其它入口与出口坐标，如圖2所示。
4.1仿真结果
分别采用传统蚁群算法和改进后的蚁群算法进行迷宫从入口到出口的路径搜索，得出的路径规划结果和最优个体适应度变化如图3、图4、图5、图6所示。
4.2数据结果对比
实验结果对比见表1。
5结语
本文改进蚁群算法能够快速搜索出一条从起点到终点的最优路径，与传统蚁群算法相比，在运行时间、最短距离、迭代次数、转折角度及平滑度上都有很大改进。实验仿真结果证明，改进后的蚁群算法能快速解决二维路径问题，优于传统的蚁群算法，能快速搜索出最优路径。
参考文献：
[1]徐守江.迷宫问题的路径优化[J].电脑知识与技术，2009，5（32）：9045-9046.
[2]燕忠.基于蚁群优化算法的若干问题的研究[D].南京：东南大学，2005.
[3]胡小兵，黄席樾.蚁群算法在迷宫最优路径问题中的应用[J].计算机仿真，2009，22（4）：115-116.
[4]齐勇，魏志强，殷波.增强蚁群算法的机器人路径规划[J].计算机工程与应用，2008，44（1）：54-56.
[5]侯文静，马永杰.求解TSP的改进蚁群算法[J].计算机应用研究，2010（6）：2087-2089.
[6]孙东秋.基于八方向跟踪算法的迷宫问题新解[J].计算机应用与研究，2015，22（4-2）：267-269.
[7]WENZQ，CAIZX.Globalpathplanningapproachbasedonantcolonyoptimizationalgorithm[EB/OL].http：//www.docin.com/p-1358599085.html.
[8]李向军，霍艳丽，曾勍炜，等.基于机器人路径规划的一种变异算子蚁群算法[J].计算机仿真，2015，32（2）：364-369.
[9]张家善，王志宏，陈应显.一种基于精英策略的改进蚁群算法及应用[J].计算机系统应用，2012，21（10）：105-108.
[10]石铁峰.改进遗传算法在移动机器人路径规划中的应用[J].计算机仿真，2011，2（28）：193-196.
[11]王红军，徐军，赵辉，等.基于平滑蚁群算法的机器人路径规划[J].燕山大学学报，2017，41（3）：278-282.
[12]丁建立，陈增强.基于混合蚂蚁算法的网络资源均衡与优化[J].仪器仪表学报，2013，2（32）：592-594.
[13]柴寅.融合栅格法与改进蚁群算法的机器人路径规划[D].武汉：武汉科技大学，2016.
[14]LIUJP，XUSH，ZHANGFH，etal.Ahybridgenetic-antcolonyoptimizationalgorithmfortheoptimalpathselection[C].beijing：ResearchcenterofGovermentGIS，2016.
[15]张贤.基于超声波测距的多机器人室内定位导航研究[D].哈尔滨：哈尔滨工业大学，2015.
（责任编辑：杜能钢）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2024/12/22 23:11:45