下载文档原格式
Value Engineering1介绍在20世纪90年代，意大利学者提出了一种新的启发式算法-蚂蚁群体算法（ACA ），该算法模拟了天然蚂蚁的路由行为，具有以下优点：①具有良好的鲁棒性，只要稍加修改，它就可以用来解决其他问题；②分布式计算，基于总体结构具有并行性；③很容易与其他方法相结合，ACA 可以与其他启发式算法相结合，很容易地改变其性能。
虽然该算法大约在10年前才被提出，但在各种应用中都已经具有了一定的竞争力，但我们还没有清楚地认识到它的本质，对收敛性的分析和对算子和参数的设计都是非常不成熟的[1-2]。
近年来，一些学者提出了一种新的算法———蚁群优化（ACO ），为蚁群算法系统提供了新的研究方向。
2蚁群优化算法通过房照大自然中蚂蚁寻找食物的行为，衍生出来了一种智能仿生算法，就是蚁群算法。
蚁群算法的两个重要步骤分别是计算状态转移概率，以及信息素更新[3]。
2.1状态转换概率在蚁群算法中，网格i 中的蚂蚁k根据信息素的浓度在t 时刻选择网格j 的概率路线：（1）其中πij 表示路径中的信息素浓度；ηij 表示启发式信息强度；α和β分别表示信息素浓度的启发式因子和启发式因子的期望值；J k 表示蚂蚁k 的当前备选路径的集合。
2.2信息素更新规则在迭代过程中，需要更新路径中的信息素浓度。
方程（1）显示信息素浓度T ij 和启发式信息ηij 在蚂蚁如何选择路径上起着决定性的作用[4-5]。
其中，ηij 不随时间改变，只与蚂蚁k 的位置有关。
信息素Tij 的更新规则如下：（2）（3）式中ρ∈（0，1）为信息素蒸发因子，表示信息素随时间衰减的速度；ΔT ij （t ）是新增加的信息素的浓度值。
根据方程（3），ΔT ij （t ）与信息素强度因子Q 和路径长度Lk 有关。
3改进蚁群算法研究根据许多研究，蚁群算法中的过渡规则是寻找最短路径的关键[6-8]。
在本文中，我们通过分配刺激概率来帮助蚂蚁选择面向目标的安全网格，并基于全局启发式信息使其适应大规模转换；并建立了改进的信息素更新规则和新的动态蒸发策略，以提高全局搜索能力，加速收敛。
多策略蚁群算法求解越野路径规划吴天羿;许继恒;刘建永;昝良【摘要】针对车辆的越野路径规划问题,设计了以最少行驶时间为目标的多策略蚁群算法.首先,分析了地形坡度和地表属性对于车辆路径规划的综合影响,通过叠加坡度与粗糙度约束建立了禁忌表;其次,一方面引入了自适应调整策略以提高路径搜索的有效性,另一方面设计了双向搜索策略以增加蚂蚁之间的协作能力和成功路径的搜索机率;另外,还提出了子路径多段交叉策略以提高算法的全局搜索能力和收敛速度,在详细叙述改进算法的步骤之后,优化了算法的部分参数取值;最后,就基本算法和改进算法的性能指标、收敛代数和仿真结果进行了比较与分析.实验结果表明,改进算法能够快速有效地实现越野路径规划,较之基本算法有一定的优越性.【期刊名称】《解放军理工大学学报（自然科学版）》【年(卷),期】2014(015)002【总页数】7页(P158-164)【关键词】多策略;蚁群;路径规划;双向搜索;子路径多段交叉【作者】吴天羿;许继恒;刘建永;昝良【作者单位】解放军理工大学野战工程学院,江苏南京210007;解放军理工大学野战工程学院,江苏南京210007;解放军理工大学野战工程学院,江苏南京210007;解放军理工大学野战工程学院,江苏南京210007【正文语种】中文【中图分类】TP31越野环境下，车辆的路径规划面临着很大的挑战，比如，地形坡度不定严重限制或影响了车辆的行进，地表属性复杂对车辆行进构成多种多样的延迟或阻碍。
因此，有必要研究一种符合实际地形环境的越野路径规划方法。
蚁群算法［1］由Dorigo M等人于1991年在法国巴黎召开的第一届欧洲人工生命会议（European conference on artificial life，ECAL）上提出，并最早成功应用于解决旅行商问题（travelling salesman problem，TSP），具有较强的鲁棒性和较强的全局搜索能力，已先后应用于车辆路径规划、机器人规划、航迹规划等问题。
一种基于改进蚁群算法的AGV 小车三维路径规划研究AGV 小车是一种能够自主移动、无需人工操控的智能运输设备，广泛应用于工业生产和物流领域中。
在实际应用中，AGV 小车的路径规划是非常重要的一环，而三维路径规划则更加具有挑战性。
因此，本文基于改进蚁群算法，探讨三维路径规划的研究现状和改进方向，并在此基础上提出了一种新的算法，以帮助AGV 小车实现更加高效和准确的路径规划。
一、研究现状在AGV 小车路径规划领域，变量路径规划方法被广泛应用。
传统的可变规划路径通常使用A*、Dijkstra 等算法，但这些算法应用于三维路径规划面临的挑战主要包括多个目标点、地形、环境和动态障碍物等问题，难以满足实际应用的要求。
近年来，蚁群算法被引入到AGV 小车路径规划中，并受到学术界和工业界的广泛关注。
蚁群算法是一种基于仿生学的优化算法，模拟了蚂蚁在物质流动和信息交互过程中的行为方式，通过大量的个体采用正反馈和信号传递的方式，实现了全局优化的目标。
二、改进方向尽管蚁群算法已被广泛应用于AGV 小车路径规划，但仍存在一些缺陷。
例如，蚂蚁搜索范围过大，从而导致收敛速度较慢，搜索质量较低，陷入局部最优解；蚂蚁行为策略过于简单，导致种群表现难以发挥出全局优化的效果。
因此，本文提出了以下的改进方向：1.改进蚁群算法的信息素更新策略。
传统的蚁群算法通过反馈信息素浓度，有助于蚂蚁发现优秀解和路径，但容易导致陷入局部最优解。
因此，可以引入防止过早收敛的策略，比如引入启发式信息素和启发式规划策略，以提高搜索质量。
2.改进蚁群算法的路线选择策略。
传统的蚁群算法仅通过正反馈的方式，对路线进行选择。
可以引入负反馈机制，使蚂蚁能够适应地形和环境的变化，实现全局搜索效果。
3.对蚂蚁行为进行调整。
蚂蚁行为策略过于简单，往往不能准确和灵活地适应不同的环境和场景。
应该加强对蚂蚁行为策略的分析，以发挥种群表现的最大优化效果。
三、改进算法的实现本文基于改进蚁群算法的思路，提出了一种新的三维路径规划算法。
基于改进蚁群优化算法的AUV三维路径规划
蒲兴成;冼文杰;聂壮
【期刊名称】《智能系统学报》
【年(卷),期】2024(19)3
【摘要】针对蚁群算法在三维路径规划时收敛速度慢且难以收敛至最优的缺点,提出一种新的改进蚁群算法,并将其应用于自主式水下机器人(autonomous underwater vehicle,AUV)三维路径规划。
与现有算法相比,改进算法优点主要体现在3个方面:首先,引进伪随机状态转移概率提升算法全局搜索能力;其次,将距离和轨迹限定因子引入启发式函数,距离因子保证搜索不断趋近目标点,在轨迹限定因子约束下,轨迹累计转角更小,以此提升收敛速度和精度;最后,通过扩大信息素增量差距并逐步提高信息素衰减系数,进一步提高路径规划效率。
实验结果表明,改进蚁群算法能够获得累计转角更小路径,且路径长度更小,收敛速度更快。
【总页数】8页(P627-634)
【作者】蒲兴成;冼文杰;聂壮
【作者单位】重庆邮电大学计算机科学与技术学院;铜陵学院数学与计算机学院【正文语种】中文
【中图分类】TP242
【相关文献】
1.基于改进型蚁群算法的AUV路径规划
2.改进蚁群算法在AUV三维路径规划中的研究
3.改进型蚁群算法的AUV三维路径规划
4.基于改进蚁群算法的AUV路径规划
5.基于改进鲸鱼优化算法的AUV三维路径规划
因版权原因，仅展示原文概要，查看原文内容请购买。
基于改进蚁群算法的工业机械臂避障路径规划基于改进蚁群算法的工业机械臂避障路径规划一、引言工业机械臂广泛用于生产线上的自动化操作，其在提高生产效率和减少劳动强度上发挥着重要作用。
然而，在繁忙的生产环境中，机械臂往往需要在有限的空间内进行运动，并避免与障碍物发生碰撞。
因此，如何规划一条安全有效的避障路径成为了工业机械臂设计中的一个关键问题。
二、蚁群算法蚁群算法是一种模拟蚂蚁群体行为的优化算法，具有分布式、自适应和并行计算的特点。
它通过模拟蚂蚁在寻找食物和寻找路径时的工作原理，将问题转化为寻找最优路径的问题。
蚁群算法由于其在优化问题上的较好性能而被广泛应用于路径规划中。
三、工业机械臂避障路径规划为了实现工业机械臂的自主避障，我们将改进蚁群算法应用于机械臂的路径规划。
具体步骤如下：1.地图建模：首先，我们需要对工作环境进行地图建模，将机械臂运动区域分割为离散的网格。
每个网格可以表示机械臂的一个运动状态，可以是机械臂关节的角度、位置或姿态等。
同时，将障碍物的位置也标记在地图上。
2.初始参数设置：为了进行算法迭代，我们需要设置蚂蚁的数量、遗忘因子、信息素释放量等初始参数。
这些参数的选择将直接影响算法的性能和收敛速度。
3.信息素更新：蚁群算法的核心是信息素的更新。
在路径规划中，信息素可以理解为蚂蚁在网格上留下的标记，用于指导其他蚂蚁的行动。
通过信息素的更新，可以实现路径的更新和优化。
4.路径选择：蚂蚁在选择下一个状态时，会根据当前状态的信息素浓度和启发因子进行选择。
在路径规划中，启发因子可以是距离、路径的连续性等。
蚂蚁通过遍历网格，并根据信息素浓度与启发因子进行路径选择，从而找到一条路径。
5.路径更新：当蚂蚁完成一次遍历后，需要对路径进行更新。
这里采用的方式是根据路径的长度和信息素浓度来更新网格的信息素。
路径越短，信息素增量越大，从而增加了路径的选择概率。
6.迭代优化：根据蚁群算法的特点，我们可以通过多轮迭代来优化路径选择。
基于改进蚁群算法的机器人路径规划DOI :10.19557/ki.1001-9944.2020.11.009李静,高俊钗(西安工业大学电子信息工程学院,西安710000)摘要:在机器人路径规划过程中,针对传统蚁群算法易陷入局部最优、搜索时间过长等问题,该文提出了一种改进的蚁群算法。
用栅格法建立环境模型,引入概率选择函数,降低死锁概率,增加路径平滑度;用Logistic 模型的混沌扰动改进信息素的更新方式,提高路径规划的全局搜索能力及收敛速度。
仿真结果表明,改进后的蚁群算法减少了路径长度,提高了全局搜索能力且减少了搜索时间。
关键词:路径规划;蚁群算法;Logistic 模型;ROS 中图分类号:TN91文献标志码:A文章编号:1001⁃9944(2020)11⁃0039⁃05Robot Path Planning Based on Improved Ant Colony AlgorithmLI Jing ,GAO Jun ⁃chai(College of Electronic and Information Engineering ,Xi ’an Technological University ,Xi ’an 710000,China )Abstract :In the process of robot path planning ,in view of the traditional ant colony algorithm is easy to fall into lo ⁃cal optimum ,the problem such as the search time is too long ,this paper proposes an improved ant colony algorithm.Environment model is established with grid method ,and the introduction of probability choice function ,reduce the probability of a deadlock ,increasing path smoothness ;Using the Logistic model of chaotic disturbance improvedpheromone update methods ,improve the global search ability and convergence speed of path planning.The simulation results show that the improved ant colony algorithm reduces the path length ,improves the global search ability and reduces the search time.Key words :path planning ;ant colony algorithm ;Logistic model ;ROS收稿日期:2020-08-05;修订日期:2020-10-10基金项目:陕西省重点研发计划项目(2018GY ⁃184)作者简介:李静(1995—),女,在读硕士研究生,研究方向为电子与通信工程;高俊钗(1971—),女,博士,副教授,研究方向为电子信息工程。
《装备制造技术》2018年第03期0引言近年来随着移动机器人技术的大量应用，作为其重要分支的路径规划技术也受到了学者的广泛关注。
所谓路径规划即是在充满障碍物的规划空间中找到一条从起点到终点的最优、最短路径，并且能够无碰撞地成功地绕开环境中所有的障碍物。
目前，在路径规划领域中应用的比较多的算法主要分为两类，一类是可视图法[1]、自由空间法[2]、拓扑图法等传统的求解方法；另一类则是采用遗传算法、蚁群算法、神经网络法等智能算法。
虽然上述的各种方法为路径规划问题提供了不同的解决方案，但是各种方法在执行上总是存在着不同的缺点与优点，并没有一种方法能够完全适应各种环境条件下的任何系统。
蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法，该算法具有较强的鲁棒性、优良的分布式计算机制、易于与其他算法相结合等优点[3]。
因此，自意大利的Dorigo[4]学者提出蚁群算法以来，如今已经在各行各业得到了广泛的应用。
但传统的蚁群算法由于其复杂性往往需要很长的搜索时间，而算法搜索初期的盲目性也容易造成算法收敛速度慢等缺点[5]。
针对上述缺点，许多学者也提出了相应的改进方法，如Stutzle[6]为了避免蚁群算法趋于停滞、陷于局部最优，对信息素的更新范围进行了限定，从而提出了搜索效果更好的最大最小蚂蚁系统（MMAS）。
黄震等[7-9]学者则是将蚁群算法与其他表现较好优化算法如遗传算法、A*算法等相结合，从而提出了收敛性较好的混合蚁群算法。
大量的文献[10]也表明，多数学者对蚁群算法的改进主要聚焦于信息素的更新方式以及怎样提高种群的多样性，很少有学者关注蚂蚁的搜索方向以及启发函数信息的更新。
因此，本文基于传统的蚁群算法加入了自适应调整启发函数，局部最优方向引导机制，并在此基础上提出了一种改进的蚁群路径规划算法，该算法具有较高的收敛速度。
1传统的蚁群路径规划算法虽然蚁群算法的提出是着眼于解决旅行商问题（TSP），但其基本思想却可以应用于许多其他问题的求解，路径规划问题便是其中之一。
Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ 计算机应用，２０１３，３３（４）：１１５７—１１６０ ＩＳＳＮ １００１—９０８１
Ｃ０ＤＥＮ ＪＹＩＩＤＵ ２０１３．．０４．．Ｏ１
ｈｔｔｐ：／／ｗｗｗ．ｊｏｃａ．ｃｎ
文章编号：１００１—９０８１（２０１３）０４—１１５７—０４ ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０８７．２０１３．０１１５７ 基于改进蚁群算法的越野路径规划
吴天羿。，许继恒，刘建永 （解放军理工大学野战工程学院，南京２１０００７） （｝通信作者电子邮箱２７４６２４６４２＠ｑｑ．ｃｏｒｎ）
摘要：针对车辆的越野路径规划问题，研究并分析了地形坡度和地表属性对于车辆路径规划的综合影响。引 入了“窗口移动法”对地形进行先期的坡度计算和通行性分析，就轮式车辆和履带式车辆分别建立了地表属性的粗糙 度评价指标，并采用“面积占优法”将地表属性栅格化。通过建立禁忌表，叠加了坡度与粗糙度的约束影响以减少搜 索范围，提高搜索效率。构造了改进蚁群算法的估价函数，并结合路径表设计了考虑坡度和粗糙度约束的路径优化 算法。仿真结果表明，该算法能够快速有效地实现符合真实地形环境的越野路径规划。 关键词：蚁群算法；越野路径规划；坡度；地表属性；粗糙度；信息素 中图分类号：ＴＰ３９１．９ 文献标志码：Ａ
Ｃｒｏｓｓ－ｃｏｕｎｔｒｙ ｐａｔｈ ｐｌａｎｎｉｎｇ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ＷＵ Ｔｉａｎｙｉ ，ＸＵ Ｊｉｈｅｎｇ，ＬＩＵ Ｊｉａｎｙｏｎｇ （Ｃｏｌｌｅｇｅ ｏｆＦｉｅｌｄ Ｅｎｇｉｎｅｅｒｉｎｇ，ＰＬＡ Ｕｎｉｖｅｎｉｔｙ ｏｆＳｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ Ｊｉａｎｇｓｕ ２１０００７，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｖｅｈｉｃｌｅ’Ｓ ｃｒｏｓｓ—ｃｏｕｎｔｒｙ ｐａｔｈ ｐｌａｎｎｉｎｇ ｐｒｏｂｌｅｍ，ｔｈｅ ｇｅｎｅｒａｌ ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｔｅｒｒａｉｎ ｓｌｏｐｅ ａｎｄ ａｔｔｒｉｂｕｔｅ ｏｆ ｔｈｅ ｅａｒｔｈ’Ｓ ｓｕｒｆａｃｅ ｏｎ ｐａｔｈ ｐｌａｎｎｉｎｇ ｗａｓ ｒｅｓｅａｒｃｈｅｄ ａｎｄ ａｎａｌｙｚｅｄ．Ｗｉｔｈ ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ”ｗｉｎｄｏｗ ｍｏｖｉｎｇ ｍｅｔｈｏｄ”ｔｏ ｂｅｆｏｒｅｈａｎｄ ｊｕｄｇｍｅｎｔ ａｎｄ ｔｒａｆｆｉｃ ｃａｂｉｌｉｔｙ ａｎａｌｙｓｉｓ ａｂｏｕｔ ｔｅｒｒａｉｎ ｓｌｏｐｅ，ｔｈｅ ｒａｔｉｎｇ ｉｎｄｅｘ ａｂｏｕｔ ｌａｎｄｆｏｒｍ ｒｏｕｇｈｎｅｓｓ ｏｆ ｗｈｅｅｌｅｄ ｖｅｈｉｃｌｅｓ ａｎｄ ｃｒａｗｌｅｒ ｖｅｈｉｃｌｅｓ ｗｅｒｅ ｅｓｔａｂｌｉｓｈｅｄ ａｎｄ ｔｅｒｒａｉｎ ｒｏｕｇｈｎｅｓｓ ｗａｓ ｒａｓｔｅｒｉｚｅｄ ｗｉｔｈ ｔｈｅ”ａｒｅａ ｄｏｍｉｎａｎｔ ｍｅｔｈｏｄ”． Ｃｏｎｓｔｒａｉｎｔ ｅｆｆｅｃｔ ｏｆ ｓｌｏｐｅ ａｎｄ ｒｏｕｇｈｎｅｓｓ ｏｆ ｗｅｒｅ ｓｔａｃｋｅｄ ｉｎ ｏｒｄｅｒ ｔｏ ｒｅｄｕｃｅ ｔｈｅ ｓｅａｒｃｈ ｓｃｏｐｅ ａｎｄ ｉｍｐｒｏｖｅ ｔｈｅ ｓｅａｒｃｈ ｅｆｆｉｃｉｅｎｃｙ ｔｈｒｏｕｇｈ ｅｓｔａｂｌｉｓｈｉｎｇ ｔａｂｏｏ ｌｉｓｔ．Ｔｈｅ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｗａｓ ｓｔｒｕｃｔｕｒｅｄ，ａｎｄ ｗｉｔｈ ｒｅｆｅｒｅｎｃｅ ｔｏ ｔｈｅ ｐａｔｔｉ ｔａｂｌｅ，ａ ｐａｔｈ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗａｓ ｄｅｓｉｇｎｅｄ ｗｉｔｈ ｔｈｅ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｏｆ ｓｌｏｐｅ ａｎｄ ｒｏｕｇｈｎｅｓｓ ｃｏｎｓｔｒａｉｎｔ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｒｅａｌｉｚｅ ｃｒｏｓｓ—ｃｏｕｎｔｒｙ ｐａｔｈ ｐｌａｎｎｉｎｇ ｉｎ ａｃｃｏｒｄａｎｃｅ ｗｉｔｈ ｒｅａｌ ｔｅｒｒａｉｎ ｅｎｖｉｒｏｎｍｅｎｔ． Ｋｅｙ ｗｏｒｄｓ：Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ（ＡＣＡ）；ｃｒｏｓｓ－ｃｏｕｎｔｒｙ ｐａｔｈ ｐｌａｎｎｉｎｇ；ｓｌｏｐｅ；ａｔｔｒｉｂｕｔｅ ｏｆ ｔｈｅ ｅａｒｔｈ’Ｓ ｓｕｒｆａｃｅ； ｒｏｕｇｈｎｅｓｓ；ｐｈｅｒｏｍｏｎｅ
０ 引言 越野环境下，车辆的路径规划面临着很大的挑战：１）地形坡 度不定，严重限制或影响了车辆的行进；２）地表屙陛复杂，对车辆 行进构成多种多样的延迟或阻碍；３）采用实车演练，不但人力物 力财力消耗大，而且人员和车辆的安全也难以保障。因此有必要 研究一种符合实际地形环境的越野路径规划方法。 现有的三维路径规划算法…包括Ａ 算法、遗传算法、粒 子群算法等。Ａ 算法 的计算量会随着维数的增加而急剧 增加，遗传算法和粒子群算法只是准三维规划算法，不能有效 地利用问题的启发信息，并且处理约束条件的能力较弱。蚁 群算法 ，作为一种正反馈的启发式搜索算法，具有收敛速 度快、分布计算且能全局搜索的优点。 刘利强等 设计了基于蚁群算法的三维路径规划算法， 保证了水下潜器的潜航深度稳定、快速巡航以及安全避障。 但该方法设置了固定的前进方向，且在规定的前进步长下，设 定了上浮下潜、左移右移的最大步长，因此搜索的范围受到了 较大的限制，且一旦遇到“死点”，不能进行迂回寻径。葛小 三等 将连续三维表面进行格网离散化，通过对信息素更新 进行加权修正、引入最优蚂蚁策略以及缩小最好和最差路径 上的信息量差异，提高了算法的有效性；但算法并未考虑地形 坡度以及地表属性对路径搜索的影响。 本文以越野环境下的车辆为研究对象，考虑地形坡度和 地表属性因素对于路径规划的影响，利用改进的蚁群算法研 究并分析了越野路径规划问题。实验结果证明，改进后的蚁 群算法具有较强的鲁棒性和较好的搜索能力。
ｌ数据预处理 由于格网模型 具有数据结构简单、规律性强、易于构 建高效的数据索引等特点，且与树结构具有天然的一致性，因 此采用规则正方形格网模型作为三维地形的构建基础。 １．１ Ｓｌｏｐｅ表的建立 － 地形的高程数据来源于５ ｍ×５ ｍ的栅格，并假定车辆的 投影面积恰为一个栅格单元。根据格网单元（ｉ， ）中的四个 顶点（对应高程为ｚ ，ｚ ｚ ，Ｚ ＋ ），求得格网中心 点Ｐ “的高程ｚ ｆ ｏ Ｚ ｆ，７＝（Ｚ ，ｆ＋ｚ ＋１，ｆ＋Ｚｆ＋１．，＋１＋Ｚ
，，＋１）／４ （１）
坡度（Ｓｌｏｐｅ）是表示地表面在该点倾斜程度的矢量，由坡 度大小和坡向两个因素组成。假设车辆适合通行的坡度大小 为０。～３０。，当车辆准备向下一个格网移动时，需要实时地计 算移动方向上的坡度大小，以判断两格网之间的通行性。 算法引入“窗口移动法” ，以格网的中心点坐标序列代
收稿日期：２０１２－１０—０９；修回日期：２０１２－１１．２７。 作者简介：吴天羿（１９８４一），男，江苏南通人，博士研究生，主要研究方向：指挥自动化、运筹分析；许继恒（１９７６一），男，陕西咸阳人，副教 授，博士，主要研究方向：数字化战场；刘建永（１９６１～），男，江苏泰州人，教授，博士生导师，主要研究方向：指挥自动化、运筹分析。 第４期 吴天羿等：基于改进蚁群算法的越野路径规划 ｌ１５９ 发函数Ｈ（ｉ ， ）来计算选择概率Ｐ（ｉ ， ），然后根据各格网 的选择概率采用轮盘赌的方式选择下一相邻格网。
ｆ ｌ－ｌ（ｉ ， 刘 Ｐ（ ， ）＝｛∑ （ ， ， ’一一 （２） 【０， 日（ ，，／）：０
。 』 ，Ｓｌｏｐｅ（ｔｌ（ｉ ｑ（ｉ ，， ｌ（， ）＝｛△Ｄ＋ ，／）’ ～一 ‘（３） ｔＯ， Ｓｌｏｐｅ（ｉ ，Ｊ ， ）＝０
其中：ｐｈ（ｉ ， ）表示当前格网（ｉ ， ）的信息素大小， 是信 息素相对重要性参数，口是启发信息相对重要性参数；Ｊ是系 数，△Ｄ是格网（ｉ， ）到（ｉ ， ）的实际距离；Ｑ（ｉ ， ）是（ｉ ， ）到终点（ｉ ，Ｊ ）的欧几里得距离。 ２．２．２信息素更新 蚁群算法使用信息素吸引蚂蚁搜索，信息素的更新包括 局部和全局更新两部分。 局部更新是指当蚂蚁经过该格网时，该格网的信息素就 减少，以增加蚂蚁搜索未经过格网的概率，达到全局搜索的目 的。其更新公式为： ｐｈ（ｉ， ）：（１一ｄｅｃｒ） ｐｈ（ｉ， ） （４） 其中ｄｅｃｒ为信息素的挥发系数。 全局更新是指当所有蚂蚁完成一次路径搜索时进行的信 息素更新，以避免搜索到的解空间过快收敛。本算法采用精 英蚂蚁 策略，以当前迭代中的最优路径进行信息素更新， 确保蚂蚁的搜索集中在最优解的附近。其更新公式为： ｐｈ（ｉ， ）＝（１一ｒｏｕ） ｐｈ（ｉ， ）＋ＦＯＵ Ａｐｈ（ｉ， ） （５） 卸ｈ（ｉ，Ｊ）＝Ｋ／ｒａｉｎ（１ｅｎｇｔｈ（ｍ，）） （６） 其中：ＦＯＵ代表信息素更新系数， 是系数，ｌｅｎｇｔｈ（ｍ ）代表 第ｍ 只蚂蚁经过的路径长度。 由于信息素挥发系数的存在，当问题规模较大时，易使那 些没有被搜索到的格网的信息素减少接近到０，导致过早收 敛于非全局最优解。同时，为了更完全地搜索解空间，有必要 限制信息素的最大值以适当增加随机选择的概率。采用最大 最小蚂蚁 思想，对格网的信息素作如下限制： ｐｈ（ｉ， ）：ｆｐｈｍａｘ，ｐｈ（ ， ）≥Ｐ ｍ“ （７） ｔｐｈ ｉ ，ｐｈ（ｉ， ）＜ｐｈ ２．２．３路径生成 建立Ｐａｔｈ表，以记录每只蚂蚁走过的路径。Ｐａｔｈ由一个 ｍ Ｘ ２ｎ的矩阵表示，记录了路径的 、ｙ轴坐标序号，且满足 『Ｐａｔｈ（ｍ ，１：２）＝［ｉ ， ］，ｍ ≤ｍ ，ｏ、 Ｌｌｅｎｇｔｈ（Ｐａｔｈ（ｍ ，：））＝２ ｎ 其中：ｍ是蚂蚁的规模，ｎ是搜索到的路径集中最多格网路径 的格网个数，ｌｅｎｇｔｈ（Ｐａｔｈ（ｍ ，：））是第ｍ 条路径的列数。 由于蚂蚁搜索采用的是随机型的轮盘赌方法，容易出现 搜索到“死点”而终止搜索的情况，所以不是每条 Ｐａｔｈ（ｍ ，：）都代表搜索到的可行解路径，也不是所有可行解 路径的有效格网（即非０值格网坐标序列）的个数都是２ 个。 倘若第ｍ 只蚂蚁在未搜索到第ｎ个格网时，就已完成初始点 到终点的路径搜索或者已经到达“死点”，则Ｐａｔｈ（ｍ ，：）中 剩下的元素以０补齐，因此只有满足式（９）的才可作为可行 解： ＝ｎ， （Ｐａｔｈ（ｍ ，：））；ｍ ≤ｍ ｛Ｐａｔｈ（ｍ ， 一１）＝ｉ ｄ （９） Ｐａｔｈ（ｍ ， ）＝ ｄ 其中：ｎ （Ｐａｔｈ（ｍ ，：））表示计算Ｐａｔｈ（ｍ ，：）中非０元素 的个数。当Ｐａｔｈ（ｍ ，：）确认为可行解后，则可计算本次路 径的距离Ｄｉｓｔ（ｍ ）。 ２．３算法步骤 算法的具体步骤如下 １）数据预处理。读取高程数据，根据式（１）得到格网中 心点的高程，并建立Ｓｌｏｐｅ表、Ｒｏｕｇｈｎｅｓｓ表和Ｔａｂｕ表。 ２）初始化 、Ｊ、ｄｅｃｒ、ＦＯＵ、Ｋ和ｍ等系数，并设置初始点 （ｉ ， ）、终点（ｉ。 ，Ｊｏ ）、初始ｐｈ（ｉ， ）以及最大循环次 数ＮＣ 。将全部蚂蚁置于初始点，令△ｐ＾（ｉ， ）＝０，ＮＣ＝１。 ３）开始第ＮＣ次循环，启动所有蚂蚁并恢复Ｔａｂｕ表为初 始状态，且令初始点的Ｔａｂｕ（ｉ， ）＝０。 ４）对每只蚂蚁ｍ ，先根据式（３）计算相邻格网的启发值 Ｈ（ｉ ，，），并代入式（４）求得选择概率Ｐ（ｉ ， ），再用轮盘赌 法选择下一格网。 ５）根据式（５）和式（８）进行信息素的局部更新，将相邻格 网加入到Ｐａｔｈ（ｍ ，：），且令该格网的Ｔａｂｕ（ｉ， ）＝０。 ６）判断第ＮＣ次循环是否结束，若否，返回到４）。 ７）根据式（１０）判断Ｐａｔｈ（ｍ ，：）是否是可行解。若是计 算该路径的距离Ｄｉｓｔ（ｍ ）。 ８）第ｍ 只蚂蚁搜索结束，ｍ ＝ｍ ＋１，判断ｍ ≤ｍ，若 是，返回到４）。 ９）找出第ＮＣ次循环中距离最短的规划路径 Ｂｅｓｔｐａｔｈ（ｍ ｍｉｎ，：）以及相应的路径距离Ｂｅｓｔｄｉｓｔ（ｍ ，：），根 据式（６）～（８）进行信息素的全局更新。 １Ｏ）第ＮＣ次循环结束，ＮＣ＝ＮＣ＋１，该次的 Ｂｅｓｔｐａｔｈ（ｍ ，：）与第ＮＣ一１次的相比较，取距离 Ｂｅｓｔｄｉｓｔ（ｍ ，：）较小的路径作为当前的最优路径。判断 ＮＣ≤Ⅳｃ ，若是，返回３）；否则，结束搜索并输出结果。
