路径规划毕业设计

1引言1.1课题研究背景及意义1.2主要研究内容及关键问题2路径规划概述路径规划是智能交通系统研究的重要内容，同时也是车辆怎位与导航系统的重要组成部分，智能交通系统是包含若干子系统的复杂系统，其每个子系统都具有不同的功能，车辆龙位与导航系统是智能交通系统的一个主要的应用子系统而路径规划是车辆立位与导航系统的重要组成部分。所以可以用下图来描述三者之间的关系。2.1路径规划的概念路径规划是车辆定位系统与导航系统的重要组成部分，是它必不可少的核心功能之一。车辆定位与导航系统中的路径规划是在车辆行驶前或行驶过程中为司机提供从起始点到目标点的一条或若干条路线，来对司机的行车进行导航。路径规划可分为单车辆路径规划和多车辆路径规划，单车辆路径规划是在一个特左的道路网上根据一个车辆的当前位卷和目标给出单个路径规划，属于用户优化问题：多车辆路径规划是在一个特定的道路网上为所有的车辆规划各自的目标路径，属于系统优化问题。在计算机科学中，通常把求解两点之间一条路径的问题和多源最短路径问题，这些算法可视为单车辆路径规划的问题，多车辆路径规划比单车辆路径规划更复杂，单用于解决单车辆路径规划问题的背景知识将有利于研究多车辆路径规划的情形。2.2路径规划问题的效率针对一个特立的应用，在进行路径规划是可以采用多种标准来优化路线，这取决于系统的设计和用户的意愿。一条路径的好坏取决于许多因素，有些司机可能选择行驶距离最短的路径，而有些司机宁愿行驶距离长些但必须行车条件好一些。这些路径选择标准可由设讣决泄，也可由司机通过一个用户界而来选定。在选择最好路径时，必须具备一个数字地图，来挑选使属性值如时间和距离最小的路径。计算机中存储的具有拓补结构的车市路网由石点、边及相应的拓补关系构成。英中节点是道路的交叉点、端点，边是两右点间的一段道路，用于表示分段道路，边的权值可以上义为道路的距离或距离与英它信息的综合信息，此时可以将数字道路地图转化为带权有向图，因此无论采用何种标准，求解路网中两点之间的路径问题就可以归结为带权有向图的路径问题。在图论中有许多比较成熟的最短路径算法可供采用，但在车辆左位与导航系统中，这些算法通常不能直接使用，原因有两个：一、对于实时车辆导航系统，路径规划必须在一泄的时间内完成，这就要求路径规划算法具有较高的运算效率；二、对于车辆导航系统，负责路径规划的导航讣算机系统受车载环境和成本制约，处理能力和存储资粮十分有限，而在实际应用中的数字道路数据库往往规模庞大。因此在车辆左位与导航系统中路径规划的研究目的和任务是改进图论中的算法或者构造新的算法，实现在尽可能短的时间内找到一条理想的路径。只考虑了路径规划的时效性，可能导致规划后的路径不是最优路径，但却是比较理想的次优路径，能够被人们所接受，此时达到了时效性和最优性的平衡。这也是车辆泄位与导航系统所要求的。2.3路径规划的研究现状目前，国内外对路径规划方法的研究主要有两大类，传统方法与智能方法。传统方法主要包括：梯度法、栅格法、枚举法、可视图法、人工势场法、自由空间法、算法、随机搜索法等。英中人工势场法、梯度法易陷入局部最小点，枚举法、可视图法不易用于高维的优化问题。用于机器人路径规划的智能方法主要有：模糊逻辑、神经网络、遗传算法、蚁群算法、粒子群算法等。3.蚁群算法概述3.1蚁群算法原理在昆虫世界中，蚂蚁是一类群居昆虫。它们具有高度组织的社会性，不仅可以借助触觉和视觉的联系彼此沟通，而且可以借助于信息素进行大规模的协调行动。另外，蚂蚁还能够较快地适应环境的变化，比如：蚂蚁在搬运食物的过程中，路上突然碰到障碍物时，蚂蚁仍能够很快重新找到到达蚁穴的最短路径。蚂蚁究竟是如何完成这些复杂的任务呢?经大量研究发现，蚂蚁在发现食物后，如果食物较小则独自搬运，食物比较大时则会请求“外援”，同时，一路上会留下信息素，食物越大信息素的浓度越大，其它蚂蚁逐渐向信息素浓的方向靠近，以至足够多的蚂蚁最终找到食物并将食物搬回蚁穴。如果采用算法实现完成整个任务的过程，则遵循如下原则：活动范用：蚂蚁观察到的范用为一个方格形状，蚂蚁有一个速度半径的参数(如果是n).那么它能观察到的范围就是nxn个方格世界，并且移动的距离也在此范围内。周围环境：蚂蚁所处环境是虚拟的，包含有障碍物、其它蚂蚁以及信息素，信息素又有两种，找到食物的蚂蚁留下的食物信息素和找到蚁穴的蚂蚁留下的蚁穴的信息素。每只蚂蚁仅能感知英范围内的环境信息，同时信息素以一泄速率在环境中挥发。觅食规则：蚂蚁在可感知的范囤内寻找食物，如果有则直接过去。否则看是否有信息素，并朝信息素浓的方向前进，且每只蚂蚁大多会以小概率犯错误，不一立往信息素最多的位程移动。蚂蚁寻蚁穴的规则和此类似，只是它对蚁穴信息素有反应，对食物信息素无反应。移动规则：每只蚂蚁都朝信息素最浓的方向移动，当周囤设有信息素诱导时，蚂蚁按照自己原先运动方向前进，并在运动的方向会有一个随机的小的扰动。尽量避开刚走过的点以防止蚂蚁原地转圈。避障规则：当蚂蚁在移动的方向被障碍物挡住，它会随机的选择另一个方向，如果有信息素指引，它将遵循觅食的规则行走。撒播信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，随所走距离增加，撒播的信息素减少。依照以上规则，尽管蚂蚁之间没有直接关联，但是通过信息素这个纽带，可以把各只蚂蚁协调起来。由此产生的成功觅食或找到蚁穴的算法则正是最小化搜索食物的时间或找到蚁穴的最优路径。3.2蚁群算法的基本思想一群算法在解决一些组合优化问题中取得了较好的效果，因此该算法逐渐引起了许多研究者的注意，并将蚁群算法应用到实际问题中。在蚁群算法中，研究者们提出了人工群蚁的概念。人工蚁群与真实蚁群有很多相同之处，也有一些人工蚁群特有的本领。一方而，人工蚁群是真实蚁群行为特征的一种抽象，将其•实蚁群觅食行为中核心的部分抽象给人工蚁群。另一方面，由于人工蚁群是需要解决问题中的复杂优化问题，因此为了能够使蚁群算法更加有效，人工蚁群还具备了一些真实蚁群所不具备的特有本领。321真实蚁群与人工蚁群的共同点人工蚁群大部分的行为特征都是来源于真实蚁群，他们具有的共同特征主要表现如下：人工蚁群与真实蚁群一样，是一群相互合作的群体。蚁群中的每只蚂蚁都能建立一个解，蚂蚁个体通过相互的协作在全局范围内找出问题较优的解。人工蚁群和真实蚁群共同的任务是寻找起点(蚁穴)和终点(实物源)的最短路径(最优目标)。

（3） 人工蚁群与真实蚁群通过信息素进行间接通讯。在人工蚁群算法中信息素轨迹是通过状态变量来表示的。状态变量是一个二维信息素矩阵T来表示。矩阵中的元素Tij表示在节点i选择巧点j为移动方向的期望值。初始状态矩阵中的各元素设置初值，随着蚂蚁在所经过路径上释放信息素的增多，矩阵中的相应项的值也随之改变。人工蚁群算法就是通过修改矩阵中元素的值，来模拟真是蚁群中信息素更新的过程。（4） 人工蚁群还应用了真实蚁群觅食过程中的正反馈机制，似的使得问题的解向着全局最优的方向不断进化，最终能够有效的获得相对较优的解。（5） 人工蚁群与真实蚁群都存在着一种信息素挥发机制。这种机制可以使蚂蚁忘记过去，不会受过去的经验的过分束缚，这有利于指引蚂蚁向着新的方向进行搜索，避免过早收敛。（6） 人工蚁群与真实蚁群都是基于概率转移的局部搜索策略。蚂蚁在移动时，所应用的策略在是时间上和空间上都是完全局部的。3.2.2人工蚁群的特有功能从真实蚁群的行为中获得的启发来设计人工蚁群的更能还具备了真实蚁群不具有的一些特性：（1） 人工蚁群算法存在于一个离散的空间中，它们的移动是一个状态到另一个状态的转换。（2） 人工蚁群算法具有一个记忆它本身过去行为的内在状态。（3） 人工蚁群释放的信息素的虽，是由蚁群所建立的问题解决方案优劣程度函数决左的。（4） 蚁群算法更新信息量的时机是随不同问题而变化不反应真实蚁群的行为。如：有的问题中蚁群算法在产生一个解后改变信息量，有的问题中则做出一步选择就更改信息量，但无论哪一种办法，信息量的更新并不是随时可以进行的。（5） 为了改变系统的性能，蚁群算法中可以增加一些性能，如：前瞻性、局部优化、原路返回等。在很多应用中蚁群算法可以再局部优化过程总交换信息。3.3基本蚊群算法的框架 基本蚁群算法的结构流程初始化迭代次数NC=NC+1K>蚂蚊初始化迭代次数NC=NC+1f信息素更新r蚂蚁K=l按照状态转秒概率公式选择卜一个元素< 」输出程序结果按照状态转秒概率公式选择卜一个元素< 」输出程序结果3.4蚁群算法的数学模型将m只蚂蚁随机放到n个连通的城市上，并使各路径上信息素的浓度相等。(时刻位于城市i的蚂蚁K倾向于选择那些长度较短并且信息素浓度较高的路径，并在某一时间更新路径上的信息素浓度，当所有蚂蚁都遍历完n个城市以后，计算出此次遍历的最短路径。此后算法迭代至满足终止条件后结束，找到遍历整个城市的最短路径。蚂蚁K转移原则：访问未访问过的城市。选择城市j为目标城市的概率⑴：［叼⑴f［旬(/)】〃工［引⑴口•［加⑴l”‘ifjuallowedk彳夸(f)二 unallowed,0,otherwise当所有蚂蚁完成一次遍历后，更新路径上的信息素浓度丫:功(/4-/?)=Zir/y(r)+Ar/y，其中：为=工玄ijk=\时3=\Lk0,otherwise3.5采用蚁群算法求解最优路径蚁群算法实质上是采用信息正反馈机制，一旦具有正确的初始信息素的引导，蚁群就能够快速地收敛于最优解。具体表示如下：351信息素的表示“信息素”分布在每两个相邻栅格中心的连线上，通往障碍栅格的连线的信息素为0。蚂蚁从起始栅格开始搜索，蚂蚁的每一步搜索范弗1是与其当前所在栅格相邻的上、下、左、右4个栅格上。t时刻每一自由栅格中心i到其相邻自由栅格中心的信息素的值为⑴。3.5.2路径点的选择t时刻蚂蚁k择下一个城市的转移概率由下式确定［叼⑴严•［劝⑴I”畤⑴二口珈⑴F-［伽(屏，ueallowedAifjEallowedkO.othenvise3.5.3“信息素”更新机制随着时间的推移，以前留下的信息素逐渐消逝，用参数1一p表示信息素消逝程度，经过n个时刻，蚂蚁完成一次循环，信息素浓度根据式叼a+n)=C叼(/)+△「“调整Ar..表示本次循环中路径vi,j＞上的信息素的增量。△r彳=其中，Q是常数，表示第k只蚂蚁在本次循环中所走过的路0,otherwise径长度。3.6蚁群算法的简单应用一TSP问题求解用蚁群优化算法来解决旅行商问题的过程如下：首先，蚁群从同一地点或不同地点同时

出发，按照按照下而的概率公式逐次访问各个城市节点出发，按照按照下而的概率公式逐次访问各个城市节点［叼⑴严•［砌⑴许(g工［Till⑴F•［加⑴］0,ifjwallowedkueallowed,0.otherwise(g英中禁忌列表Tabu是保存了每只蚂蚁k已经访问过的城市的集合Jk=(N-Tabu},«、B是系统参数，分别表示信息素、距离对蚂蚁选择路径的影响程度；Zj表示由城市i到城市j的期望程度，可根拯某种启发算法具体确泄，一般为1/d月：t为边L()上的信息素强度。当蚁群完成了所有的巧点的访问后，在原路返回的过程中，根据所得的解的好坏去修改路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停I匕的条件(停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等)，如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。3.6.1模型中蚁群算法指标参数模型中有四个重要的参数：信息启发式因子：反映了蚂蚁在运动过程中所累积的信虽在指导蚂蚁群搜索中的相对重要程度。期望启发式因子：反映了期望启发式信息在指导蚁群在搜索过程中的相对重要程度。在蚁群算法模型中用参数P：表示信息素挥发因子，则1一P就是信息素残留因子。信息素强度Q：为蚂蚁循环一周时释放在所经路径上的信息素总3.6.2环境建模TSP(TravelingSalesmanProblem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。3.6.3算法的描述建立的模型从功能上来说，主要包括以下几点：①地图上节点、路径的显示功能，②可以随意添加或删除节点，③选左的巧点可以设置需求量约束，④可以手工调整相关参数，⑤能够演示路径变化将计算结果清晰表示出来。3.6.4算法的步骤3.3算法步骤考虑机器人路径规划问题，机器人处于节点f时，苴下一步选择的盯点必然是苴周囤相邻的8个节点中的非障碍节点。算法总体描述如下：(1)初始化，将m只蚂蚁放置在出发点gzgin,相应地，设置m个禁忌表，记为tabu(K=l,2....,m),以记忆蚂蚁所走过的肖点。设置迭代计数器n=0,最大代数为MAXoriy(0)=r0。设定蚂蚁的初始感觉刺激阈值AST=0,高强度信息素阈值为rm技高强度信息素肖点行走

步数P=0oJ2,g$加5⑵找出可行域，对于处于节点i的蚂蚁k,按式⑻找出可行域：alowcdJ2,g$加5件｝(8)⑶节点选择，分为两种情况：①若存在可行域，用式(9)找出蚂蚁k在节点i处可行域内能被感觉的肖点集合feeled={g|geallowedt・rl}>AST}⑼/fleetedA//fleetedA/7-(2)=0按式(10)进行节点选择y=<a式⑶随机选择,qv%贪心选择，其他|如外0,按式⑴)进行节点选择(4)式中，以区间(0,1)的随机数：q(>、q为区间［0,1)的常数。②若蚂蚁k无可行域，说明蚂蚁进入一条死路，此时实施回退策略，即将蚂蚁回退到前一记忆节点，且标记节点i为障碍格。⑷将蚂蚁k分配在廿点j上，同时将肖点j加入tabuk,若©>rmax,P++,并按式(5)进行g感觉适应操作，按(6)式作局部信息素更新。若kvm,k廿，返回(2)。否则，转到(5)。检查是否有gcndeA｝,若无，令K=l,返回(2)。否则，保存本次路径为path,并与已保存的历史最优路径bestpath比较，若pathvbestpath,令bestpath二path0按式(7)做全局信息素更新。⑺令迭代计数器n++,若不等于MAX滞空禁忌表tabuk(k=\,2....m),重复上述过程，直到n=MAX为止。bestpath即为最优路径。3.6.4基于MATLAB的仿真实验及结果分析3.7蚁群算法的优点缺点及英改进3.7.1蚁群算法的优点：蚁群算法能较好地解决复杂优化问题。蚁群算法是一种结合了分布式计算、正反馈机制和贪婪式搜索的算法。在求解复杂优化问题中，蚁群算法具有很强的搜索较优解的能力。正反馈机制，使得蚁群可以快速的发现较优的解。分布式计算避免了蚁群算法出现的早熟收敛。而贪婪式搜索有助于在搜索工程中早期就找出可接受的解，提高系统的运行效率。蚁群算法具有很强的并行性。蚁群算法适用于并行操作，在求解复杂优化问题时，不仅可以从算法自身的改进出发来提高求解效率，也可以从算法的执行模式出发来进行优化。蚁群算法具有很好的可扩充性。因为蚁群算法可以不通过蚂蚁个体之间直接通信，而是通过信息素进行间接通信，所以蚁群算法就具有很好的可扩充性。蚁群算法具有较强的鲁棒性。蚁群算法模型稍加改进，就可以应用于英他问题中。在研究蚁群算法的过程中，许多研究者都通过了求解TSP问题来研究蚁群算法。蚁群算法还具有易于与其他方法融合的特性。如可以将蚁群算法与遗传算法和模拟退火算法相结合。而且这种融合可以改善算法的性能，是蚁群算法优化方法中的一种。3.7.2蚁群算法的缺点：对于大规模复杂优化问题，蚁群算法需要较长的搜索时间。蚁群中蚂蚁个体的运动时随机的，虽然通过信息素的间接协调，能够让蚁群向较优的路径，但是当问题规模很大时，蚁群很难在较短时间内从大量杂乱无章的路径中找出一条较好的路径。这主要是因为在蚁群搜索早期各个路径上的信息素浓度明显高于其他路径上的信息素浓度。所以对于大规模复杂优化问题，算法的收敛需要较长时间。蚁群容易出现停滞现象，出现早熟收敛。也就是当搜索进行到一上时间后，所有蚂蚁个体所发现的解完全一致，不能进一步对解进行搜索，所以不利于发现更好的解。因此很多研究者对蚁群算法进行改进，以期望避免算法早熟收敛，以搜索更优的解。蚁群算法还没有严格的数学解释。目前还未能提出一种完善的理论分析，对蚁群算法的有效性进行论证。蚁群算法作为一种模拟进化算法，苴研究也才刚刚开始，有很多问题有待进一步的研究，如算法的收敛性和理论依据等。3.7.3.改进的蚁群算法及其应用针对蚁群算法的不足，大批学者用绕如何改进蚁群算法，提高算法的性能做了大量工作。其中应用广泛且具有代表性的改进蚁群算法主要有：⑴带精英策略的蚂蚁系统(AS虹它是最早的改进蚂蚁系统。因为在某些方而它类似于遗传算法中的带精英策略，因此把它称作带精英策略的蚂蚁系统。基于排序的蚂蚁系统。它是将遗传算法中排序的概念扩展应用到蚂蚁系统中得到的。基本思想是：先是根据适应度对种群进行分类，然后被选择的概率取决于个体的排序。适应度越高，个体在种群中的排名越靠前，被选择概率越大。蚁群系统(ACs),它是As算法的改进型版本，它与As算法的主要区别是：在选择下一座城市时，ACS算法更多地利用当前的较好解：当蚂蚁从城市m爬行到城市n时，m城市边上的信息素将会适当的减少。但Acs算法的缺点是搜索效率低、质量差。最大一最小蚂蚁系统(MMAs)。它是通过对AS算法改进后得到的，是目前求解1、sP和QAP等问题最好的蚁群算法模型。与英他寻优算法相比，仍然属于最好的方法之一。最优一最差蚂蚁系统。该算法的思想是对最优解增强，对最差解削弱，使属于最优路径的边与属于最差路径的边之间信息素浓度差异增大，从而使蚂蚁集中于最优解的附近进行搜索活动。4基于蚁群算法的路径规划4.1环境建模4.2算法的描述4.3算法的步骤5仿真实验与结果分析5.1仿真实验5.2结果分析6结束语参考文献致谢附录A基于蚁群算法路径规划Matlab程序function[ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q)%蚁群算法动态寻路算法%输入参数列表%G 地形图为01矩阵，如果为1表示障碍物%Tail 初始信息素矩阵(认为前而的觅食活动中有残留的信息素)% K 迭代次数(指蚂蚁出动多少波)% M 蚂蚁个数(每一波蚂蚁有多少个)% S 起始点(最短路径的起始点)% E 终止点(最短路径的目的点)% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子重要程度的参数% Rho 信息素蒸发系数% Q 信息素增加强度系数%%输出参数列表%ROUTES每一代的每一只蚂蚁的爬行路线%PL 每一代的每一只蚂蚁的爬行路线长度%Tau 输出动态修正过的信息素%% 变量初始化 %loadD=G2D(G);N=size(D,l);%N表示问题的规模(象素个数)MM二size(GJ);a=l;%小方格象素的边长Ex二a*(mod(E,MM)4).5);%终止点横坐标ifEx==-0.5Ex二MM-0.5;endEy=a*(MM+0.5-ceil(EA4M));%终止点纵坐标Eta二zeros(l,N);%启发式信息，取为至目标点的直线距离的倒数%下而构造启发式信息矩阵fori=l:Nifix==-0.5ix二MM-0.5;endiy二a*(MM+0.5-ceil(i/MM));ifi-=EEta(Li)=l/((ix-Ex)A2+(iy-Ey)A2)A0.5;elseEta(Li)=100;endendROUTES=cell(K.M);%用细胞结构存储每一代的每一只蚂蚁的爬行路线PL=zeros(K.M);%用矩阵存储每一代的每一只蚂蚁的爬行路线长度%% 启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁 fork=l:Kdisp(k);form=l:M%%第一步：状态初始化w=s；%当前节点初始化为起始点Path二S;%爬行路线初始化PLkm=0;%爬行路线长度初始化TABUkm=ones(l,N);%禁忌表初始化TABUkm(S)=0;%已经在初始点了，因此要排除DD=D;%邻接矩阵初始化%%第二步：下一步可以前往的节点DW二DD(W,:);DWl=find(DWforj=l:length(DWl)ifTABUkm(DWl(j))==ODW(j)=inf;endendUD=find(DW)Len_UD=length(UD);%可选节点的个数%% 觅食停止条件：蚂蚁未遇到食物或者陷入死胡同whileW〜=E&&Len_UD>=l%% 第三步：转轮赌法选择下一步怎么走PP二zeros(1,Len_UD);fori=l:Len_LJDPP(i)=(Tau(W.UD(i))AAlpha)*(Eta(UD(i))ABeta);endPP=PP/(sum(PP));%建立概率分布Pcum=cumsuin(PP);Select二find(Pcum>=rand);%% 第四步：状态更新和记录Path=[Path,to_visit];%路径增加PLkm=PLkm+DD(W,to_visit);%路径长度增加W=to_visit;%蚂蚁移到下一个节点forkk=l:NifTABUkm(kk)==ODD(W,kk)二inf;DD(kk,W)二inf;endendTABUkm(W)=0;%已访问过的*i'j点从禁忌表中删除forj=l:length(DWl)ifTABUkm(DWl(j))=ODW(j)=inf;endendLJD=find(DWLen_UD=length(UD);%可选节点的个数end%%第五步：记下每一代每一只蚂蚁的觅食路线和路线长度ROUTES{k,m}=Path;ifPath(end)二二EPL(k,m)=PLkm:elsePL(k,m)二inf;endend%%第六步：更新信息素Delta_Tau=zeros(N,N);%更新量初始化form=l:MifPL(k,m) ROUT二ROUTES{k,m};TS=length(ROUT)-l;%跳数PL_km=PL(k.m);fors=l:TSx=ROUT(s);Dclta_Tau(x,y)=Dclta_Tau(x,y)+Q/PL_kni;Delta_Tau(y,x)=Dclta_Tau(y,x)+Q/PL_km;endendendTau=(1-Rho).*Tau+Delta_Tau;%信息素挥发一部分，新增加一部分end%% 绘图 plotif=1是否绘图的控制参数ifplotif==l%绘收敛曲线meanPL二zeros(1,K);minPL二zeros(l,K);fori=l:KPLK二PL(i,:);Nonzero=find(PLKPLKPLK=PLK(Nonzero);mcanPL(i)=mean(PLKPLK);minPL(i)=min(PLKPLK);endfigured)plot(minPL);holdonplot(meanPL);gridontitleC1收敛曲线(平均路径长度和最小路径长度)•)：xlabel(迭代次数')；ylabclC路径长