matlab蚁群算法精讲及仿真图

蚁群算法matlab精讲及仿真4.1基本蚁群算法4.1.1基本蚁群算法的原理蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由MarcoDorigo首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】该算法的特点：(1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。(2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。(3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。(4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。4.1.2基本蚁群算法的生物仿真模型a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见,蚂蚁之间的信息交换是一个正反馈过程,蚂蚁的觅食过程就是一个寻优路径过程。蚂蚁没有视觉,只能靠在行走过的路径上释放出的信息素来寻找路径,因此,蚂蚁走的路径越长,则释放的信息量越小。当后来的蚂蚁再次碰到这条路径时,选择信息量较大路径的概率相对较大,此时形成了一个正反馈机制。最短路径上的信息素t越来越大,而其他路径上的信息素t就会随着时间的流逝越来越少直至消失,最终蚂蚁群会找出最短的一条路径。当在路径上出现障碍物时,蚂蚁能够很快适应环境重新找到最优路径。蚁群算法就是根据蚂蚁这一智能群体的自组织觅食行为寻找出一种新的智能计算模式。4.2蚁群算法的数学模型4.2.2基本蚁群算法的实现首先引入如下记号：m为蚁群中蚂蚁的数量；),...2,1,(njidij为城市i和城市j之间的距离；)(tij为t时刻路径),(ji上的信息素数量；n为城市的数量。初始时刻，每条路径上的信息素相等，设Aij)0(（A为常数），蚂蚁),......2,1(mkk在移动中根据路径上信息素的多少来决定下一次前进的方向。基本蚁群算法一般采取随机比例规则，其表示在当前城市i的蚂蚁k转移到下一个城市j的概率。()kijpt为t时刻蚂蚁k由城市i转移到城市j的状态转移概率如式4.1所示：[()][()][()][()]()0kijijkkijijijsallowdttjallowdttpt若否则(4.1)其中，={0,1,...,n-1}-tabukkallowd表示蚂蚁k当前选择的城市集合；tabuk为禁忌表，它记录了蚂蚁k走过的城市；为信息启发因子；()ijt为t时刻城市的能见度；为期望启发因子，表示能见度的重要性。为避免信息素残留过多而影响后面蚂蚁对启发信息的识别，每只蚂蚁移动一次或者周游所有的城市以后，必须要更新路径上留下的信息素。经过n个时刻，所有蚂蚁完成一次循环。各路径上的信息素按式(4.2)和(4.3)更新：()(1)()()ijijijtntt1()mkijijkt其中，表示信息素挥发系数，1为信息残留因子，通常10；kij表示本次循环中路径),(ji上的信息素增量；kij表示蚂蚁k留在路径),(ji的信息素。由于信息素的更新方式繁多，M.Dorigo提出了三种不同的基本蚁群算法模型，分为Ant-Cycle模型，Ant-Quantity模型和Ant-Density模型，其差别在于kij的数学运算方式不一样。Ant-Cycle模型中i,j0kkijQkL若第只蚂蚁在本次循环中经过（）否则其中，Q表示信息素强度，特定情形下是算法收敛性的体现；kL表示蚂蚁k在本次循环中所走路径的总长。Ant-Quantity模型中i,jd0kijijQk若第只蚂蚁在t和t+1之间经过（）否则i,j0kijQk若第只蚂蚁在t和t+1之间经过（）否则(4.2)(4.3)式和利用的是局部信息，即蚂蚁完成一步后对这条路径上的信息素进行更新；而式利用的是全局信息，即蚂蚁完成一个迭代后对所有路径上的信息素进行更新。【基于蚁群算法的机器人路径规划张美玉黄翰郝志峰杨晓伟】蚂蚁不仅利用了路径上的信息素,而且用到了城市间距离的倒数作为启发式因子4.2.3蚁群算法的实现(1)蚁群参数状态初始化：①当前节点初始化为起始点②爬行路线初始化③爬行路径长度初始化④初始化禁忌表⑤初始化邻接矩阵⑥将m只蚂蚁放到n个城市中(2)确定每一次迭代时蚂蚁下一步可以前往的节点；(3)按照概率公式选择下一个节点(4)状态更新：路径增加，路径长度增加，更新禁忌表；(5)判断是否满足终止条件：①蚂蚁找到食物则终止，输出最短路径，否则继续迭代。②蚂蚁限入陷阱，用轮赌法选择其他节点。其算法流程图如下图所示【基于蚁群算法的移动机器人路径规划算法研究】：蚁群算法流程图开始信息初始化，将m只蚂蚁放到n个城市将蚂蚁所在初始城市放到各自的禁忌表是否达到最大循环或以收敛对所有的蚂蚁计算下一步状态转移概率，选择下一个城市，将该城市加入禁忌表中各禁忌表的中的城市数更新最优路径，并更新所有路径上的信息素循环次数加1，清空所有禁忌表结束输出最佳路径NYNY根据栅格法建立的复杂环境模型（图），在matlab环境下进行仿真，机械手的起始坐标为(0.5,29.5),终点坐标为(26.5,0.5)。黑色栅格表示障碍物，白色栅格表示自由空间，仿真结果如图所示。Figure1为基本蚁群算法实现机械手在静态环境中的自动避障路径规划得到的路径051015202530051015202530RoutesthatAlltheantsPassedFigure2为基本蚁群算法实现机械手在静态环境中的自动避障路径规划最短路径图3为基本蚁群算法的自动避障路径规划的平均路径长度和最小路径长度051015202530354045504045505560657075808590收敛曲线（平均路径长度和最小路径长度）迭代次数路径长度平均路径长度最小路径长度4.2.4基本蚁群算法的评价指标算法的时间复杂度和空间复杂度是算法性能的主要评价。但是为了更加全面的衡量基本蚁群算法性能的好坏程度，在这里例举出了三个基本指标来评价基本蚁群算法。(1)相对误差这里将E定义为最优性能指标，公式如所示。**100%bccEc其中，bc表示算法运行后得到的最优值，*c为想要得到的理想最优值。如果一开始理想最优值是未知的，这时就可以用bc来代替*c。相对误差E表示算法经过多次运行所得到的结果与理想值之间的差异程度，所以它越小就代表着算法的性能越好。(2)时间性能指标定义蚁群算法的时间性能指标TE如式4.4所示。0max100%aTITEI其中，aI是算法满足结束条件时的平均迭代次数，maxI是之前人为给定的迭代次数的最大值，0T是算法完成一次迭代运行的平均时间。基本蚁群算法的收敛性就是通过时间性能指标来衡量的，当maxI的值固定时，TE越小就代表着算法的收敛速度越快。(3)适应性指标定义基本蚁群算法的适应性指标RE如式4.5所示。**100%aRccEc其中，ac是算法运行后得到的平均值，*c为想要得到的理想最优值。基本蚁群(4.5)(4.6)(4.4)算法对初始值和操作的依赖程度是通过适应性来衡量的。因此，基本蚁群算法的综合性能指标E就可以用上面三个性能指标来表示:TTRREEEE其中，,,TR分别代表三个性能指标的加权系数，并且它们满足：1TRE值越小，基本蚁群算法的综合性能就越好。基本蚁群算法的不足之处从上面针对路由选择优化问题的分析可以看出，虽然蚁群算法已经被证明是一种有效的解决组合优化问题的方法，但是由于问世的时间比较短，还存在如下不足：(1)限于局部最优解．从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解．(2)工作过程的中间停滞问题．和算法开始时收敛速度快一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近发生停滞．(3)较长的搜索时间．尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索时间．虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍．【基本蚁群算法及其改进孔令军，张兴华，陈建国。】4.3改进后的蚁群算法及其仿真实现4.3.1基于人工势场的改进后的蚁群算法机器人路径规划的势场蚁群算法(antcolonyoptimlzationwithpotentialfield，ACOPF)，其思想是，利用机器人受到的人工势场力及其距目标的距离构造综合启发信息，以蚁群算法作为全局路径搜索策略。势场力启发信息可以有效引导机器人规避障碍物，向目标方向行进。距离启发信息除了引导最优路径搜索外还保证了机器人在势场合力为零的局部极值点上仍然可以有效进行至目标位置的最优路径搜索，从而避免失去搜索方向。最后，通过仿真实验表明了所提算法的有效性。【基于势场蚁群算法的机器人路径规划罗德林，吴顺祥】根据前面的基本蚁群算法，经常在机械手遇到如图所示的障碍物环境时，会看到其路径会是这样选择，根据机械手碰撞分析知，遇到障碍物时会和栅格有点接触或者线接触，其运动的安全性不高。012345678012345678