混沌蚁群算法在多机器人任务规划中的应用分析

《混沌蚁群算法在多机器人任务规划中的应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕十学位论文第一章绪论员发现，当蚂蚁在树干上或地面上川流不息地忙于搬运食物的时候，它们总是沿着一条从蚁巢到食物的固定路线来回走动，通常把这条固定路线是称之为食物源和蚁巢之间的最优路径。那么它们是如何相互协调、分工、合作来完成这些任务呢?蚂蚁又是如何在它们的巢穴和食源之间开辟道路的呢?生物行为研究工作者发现，原来，在蚂蚁腹部末端有一些腺体，能分泌一种叫“踪迹信息素”的化学物质。蚂蚁在外出寻食的时候，总是走一小段路就把一小滴踪迹信息素留在路上。这样，不管走出多远都不会迷路。蚁群寻找食物时会派出一些蚂蚁在蚁巢周围随机游走并留下信息素，后面的蚂蚁根据路上已有的信息素的浓

2、度随机选择路径。同时，踪迹信息素会随着时间挥发，如果该路径上没有后续的蚂蚁来，信息素将会消失，若有更多的蚂蚁选择该路径并在路经上释放信息素，路经上的信息素浓度会增加，这样信息素会吸引越来越多的蚂蚁。如果两只蚂蚁选择不同路径找到同一食物，那么比较长的路径上的信息素的浓度会比较低，后续蚂蚁将倾向于沿另一条更近的路线前往食物源。某些路径上经过的蚂蚁越来越多时，其留下的信息素也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这样形成正反馈。经过一段时间的迭代，就可发现从巢穴到食物之间的较短路径。如图1—1所示，从蚁巢到食物源一共有三条路径，线路

3、1、线路2、线路3路径长度分别为5m、6m、8m，一单位信息素的挥发速度为'，。第一批蚂蚁是随机选择路径并原路返回，则选择3条线路的蚂蚁数相等，即留下的信息素量相等，设为g。设蚂蚁的速度均为lm／分，三条路线上的蚂蚁往返一趟所需时间分别为5分钟，6分钟，8分钟，则路径上挥发掉的信息素分别为5qv，6qv,8qv。因此，路线1上留下的信息素最多，后续蚂蚁选择路径时，会更倾向于选择路线l。图1．1蚂蚁觅食解释图1．3．2蚁群算法的基本框架看似简单的群体，通过合作能实现复杂的任务，大大超过了单只蚂蚁的能力。硕士学位论文第一章绪论因此关于蚂蚁行为的研究引起了许多科学家强

4、烈的兴趣。Dorigo和AlbertoColomi等根据蚂蚁寻找食物源的行为特征提出了蚁群算法(AntColonyAlgorithm，ACA)。．通过人工蚂蚁来模拟真实蚁群的行为特征，其通信机制受踪迹信息素的启发。通过信息素所进行的物质交流和信息交流使蚁群协同工作从而解决路径优化问题。蚁群算法基本流程如图1．2所示。否图1-2蚁群算法流程图6硕士学位论文第一章绪论1．3．3ACA在旅行商问题中的应用及其实现蚁群算法由搜索阶段和协作阶段两个基本阶段组成。在搜索阶段，各蚂蚁根据路径上积累的信息素的量搜索路径，路径上经过的蚂蚁数目越多，留下的信息素的量越大，该路径越容

5、易被选择。在协作阶段，蚂蚁问通过信息素互相交流，以期望产生性能更好的解。为了能够清楚地理解蚁群算法的基本框架，这里借助了经典的旅行商问题。旅行商问题(TravelSalesmanProblem，简称TSP)可以描述为如下形式：设净(1，，，v2,⋯，vn)为n个城市的集合，E=厂喀，lv，’，，∈矿，是城市间距离的集合，G_(杉目是y上的完全图。TSP的目标是找到一条最优路径能遍历每个城市一次。对称TSP中，如=dji，不对称TSP中，西≠办。本论文讨论的是对称TSP。TSP是应用非常广泛的NP．hard组合优化问题。为了求解TSP，首先引进如下记号：设m为蚂蚁

6、的数目，4币，j_1，2，．．．，n)表示城市f和，之间的距离，研表示边已彻上的踪迹信息素数量。初始时，每条边上的信息素均为0。蚂蚁k(拓l，2，．．．，m)在运动的过程中，根据概率pf越择下一个点直到遍历完所有的点并回到原点(即构造出一条路径)，砌与城市间的距离成反比，与信息素数量成正比。f【勺卜【劭，p：21≠‘∈口肌M矗‘【‰】口·【叩谴】∥其中allowedk={l，2，．．．，刀)．tabu。，tabu。表示蚂蚁七下一步允许选择的城市，集合tabu。=(1,2，．．．，以)用以记录蚂蚁七当前已经走过的城市，tabu。将随蚂蚁的搜索过程作动态调整。随着时

7、间的推移，以前留在路径上的信息素会逐渐消逝，用参数1一p来表示信息素的消逝程度，经过时刻n，蚂蚁完成一次循环，各条路径上的信息素要根据下式进行调整：t4j=p×t口+厶t4t1-21△勺=∑△芍(1-3)△菇表示第七只蚂蚁在本次循环中留在路径驴上的信息量，△乃表示本次循环中所有经历过路径i，的蚂蚁留在该路径上的信息素增量。峰摆肌棚tusesedge(i,j)(1-4)△《={厶“(【0otherwise其中，Q是常数(表示蚂蚁循环一周所释放的信息量)厶表示第k只蚂蚁在本次循硕士学位论文第一章绪论环中所走路径的长度。在初始时刻，％=O，Ar0．=O，口，∥分别表示

8、在蚂蚁运动过程中所积累的