蚁群算法在路径优化中的应用3改

1、蚁群算法在路径优化中的应用作者：孙阳阳 指导老师：刘冲摘要 针对蚁群算法在路径中的优化问题，本文首先介绍了蚁群算法的概念及其原理，利用数学 形式建立算法模型.根据蚁群算法计算的基本步骤来分析蚁群算法在交通路径优化、TSP问题等3 个方面的应用，由实验结果可知蚁群算法在路径优化中具有很好的可行性和优越性，能起到很 好的效果.关键词 蚁群算法 算法模型 算法步骤 分析应用1 引言路径规划是指在具有障碍物的环境下，在符合某种评价条件中，寻找到一条从起始地 点到目标地点最优的路径.蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智 能进化系统,计算法采用分布式并行计算和正反馈机制，且易于其它算法结合，目前已有许 多关于其在路径规划方面的文献.建立蚁群算法模型12，解决城市交通路径优化问题，实验结果表面在搜索效率和搜索最优解的能力两方面都有很大的提高 .但是传统蚁群算法易陷入局部最优解和收敛速度较 慢，为此在机器人路径规划的应用中4 7 ，将传统蚁群算法进行改进，例如与栅格法相结合、 在几何模型下建立模型等.提高了算法的有效性和鲁棒性，解决了蚁群过早陷入局部最优解 的问题，扩大了蚂蚁的搜索

2、空间，增强了蚁群算法在机器人路径规划中的适应能力.本文通过对蚁群算法的研究以及解决几实际路径规划问题，得出了蚁群算法是有其可行 性和优越性的，说明了该算法可以在众多优化领域中得到广泛的应用.2 蚁群算法蚁群算法(ant colony optimization),又称蚂蚁算法，简称 AC0.是由 Dorigom、Maniezzov、 Colorni等人在1992年所发表的论文提出的，其灵感来源于蚂蚁在寻找食物中发现路径的行 为.它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流与合作不断 排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径.2.1 蚁群算法的基本原理蚂蚁在搜寻食物过程中总能找到一条从蚁穴到到食物的最优路径，这是因为蚂蚁在搜寻 路径上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条 路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路 径越短，信息素浓度越大；反正路径越长信息素堆积的越少.则过一段时间蚂蚁选择信息素 浓度高的路径的概率越来越大，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小 这一就形

3、成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径.2.2 蚁群算法的数学模型2.2.1 问题的描述求解两地间最优路径，即为求某两地间用时最少的行进路线.如在一个城市中，有 A、B 两个地点，从A到B有多条路径线路可选，即求一条从A到B用时最少的路线.又比如在当 今热门研究项目机器人路径规划问题中，其本质为在规划空间内依据环境信息，在某些评价 标准下，找出从出发点到目标点最优的路线，比较有代表的问题是喷涂机器人，即在一个复 杂曲面上如何规划喷涂机器人的路径，使其喷涂效率最高.这些问题都符合蚁群算法的思想，因此可以用蚁群算法来求解.2.2.2 模型的建立首先将蚂蚁觅食与路径优化问题进行对照如表1 所示表 1 蚂蚁觅食和路径优化对照表蚂蚁觅食路径优化问题蚂蚁要遍历的各个路径各个状态整个蚁群经过的一条完整的路径解最短路径最优解信息素的浓度各状态的吸引度信息素的更新状态更新路径的长度目标函数以旅行商问题(TSP)为例来构建模型，定义路与路段的交叉口为节点，路段为边即TSP 问题可描述为给定 n 个节点和每两个节点之间的距离，要寻找到一条路径，从某个节点出发 周游到其它节点一次且仅

4、一次，最终回到出发节点的封闭环路径长度最短.设节点数为n，蚂 蚁的数目为m,蚂蚁从一个节点到另一个节点逐步完成搜索的过程.蚂蚁k(k=l,2,3.m),根 据概率转换的规则选择下一个节点.由此可以生成一个由n个节点组成的行动路线，并伴有 信息素的不断更新.b.(t)表示位于t时刻节点i的蚂蚁数目则有：im = b (t) + b (t) +. + b (t); d (i, j 二 1,2,3., n)l 2n ijd 表示两个节点 i 和 j 之间的距离 在基本蚁群算法模型中，人工智能蚂蚁有以下特点：(1)人工智能蚂蚁具有记忆功能每一个蚂蚁k(k=1,2,3,.m)都有一个禁忌表(tube k)，即 蚂蚁经过节点i(i e n )后，不能再经过节点i.(2) 两个节点的距离越近，能见度则越大，被选择的期望也就越高，由此来指引人工智 能蚂蚁的搜索.定义耳=亠，被称为期望因子，所以蚂蚁k在t时刻从节点i转移到节点jij dij的概率可表示为：T (t) a(t)|Ppk (t)= 工 It (t)_kb (t* A J(1)ijisisseJ/i)0, j J (i)k其中tube (s)

5、表示禁忌例表中第s个元素，即蚂蚁所走过的第s个节点；J (i)为蚂蚁所允 kk许到达的节点的集合，J (i) = 1,2., n-tabu ；期望因子耳表示对边fi, j上的期望程度; kkja表示信息素的相对重要程度；B表示启发式因子的相对重要程度.这里需要重点说明一下:当a取较大值时，蚂蚁在选择路径的过程中路上的信息素非常重要；当a取较小值时蚁群算法变成随机的贪婪算法.P取较大值时会使整个蚁群陷入随机搜索，这样的话收敛速度 较慢，很难找到最优的结果， B 取较小值时虽然加快了收敛速度，这样会很快得到一个最 优解但是容易陷入局部最优的状况.(3) 在蚁群算法中有一个非常重要的参数指标，就是信息素浓度.蚁群在节点 i 到节点 j 时，算法会在路径 ij 上遗留信息素，而信息素是时时刻刻动态变化的，它的多少决定蚁群 选择该路径的概率大小下面我们给出信息素浓度公式，设工jt)表示t时刻:；i, j上的信息数 浓度，则在 t+n 时刻此路径上的信息素浓度为2)t (t + n) = (1-p )t (t) +At k (t)ijijijk=1式中，p(OVpVl)它表示信息物质的保留率；At

6、 k(t)表示时刻t在蚂蚁k在路径ij上信息ij素的增量.At k (t ) =ijQ LkO,若蚂蚁k在本次周游中经过ij否则3)式中，Q表示蚂蚁释放的信息素量;L表示蚂蚁k在本次周游遍历中所经过边的总和长度,Lk表示本次遍历中蚂蚁所用的时间总和.以上 4 个因素即禁忌列表、期望因子、概率转换规则、信息素浓度蚁群系统路径选择的 实现和信息素更新策略，两者互相配合，实现模型的正反馈机制，促进人工智能蚂蚁收敛于 最优解.根据信息素更新策略的不同，又出现了3种不同的模型：蚁量模型、蚁密模型、蚁周模 型. 蚁量模型QAt k (t, t +1) = dij 4)丁,蚂蚁k在时刻t和t +1经过ijij0,否则在式中，Q为常量，信息素的增加量与边ij的长度有关. 蚁密模型At k (t,t +1) =ijQ0，蚂蚁k在时刻t和t+1经过ij 否则在式中，Q为常量，也就是说信息素增加量只是个固定值，与边ij的距离无关. 蚁周模型ij0,蚂蚁k在本次周游中经过边ij否则6)在式中，Q是常量表示k只蚂蚁的周游路线，即如果蚂蚁经过边ij信息素的增加量为一个常量除以蚂蚁k循环路线长度这里信息素的增加量只

7、与蚂蚁的循环路线和Q有关，与/没有 ij关系.在该模型中采用了全局信息的更新，较前两种模型性能更优.原因是蚁周模型利用整体 信息，即蚂蚁在历经一个循环路径所释放的信息素量与所得解的质量成正比.周游路径长度 越短的蚂蚁，释放在该路径上的信息素量越多，而前两种模型在搜索解时，只使用了局部更 新信息，没有用到任何解的信息.2.2.3 选参原则讨论的参数包括a,卩，p,m,Q .上文已经提到信息素的相对重要程度和启发式因子的重要程度0对算法模型的影响，这里主要说下信息素蒸发系数P，蚂蚁数目m以及蚂蚁释 放的信息数量Q对搜索过程的影响.P增大，残留信息素1-P减少，负反馈机制增强，随机 性增强，利与发现更多最优解，但是收敛性降低反之P增大，残留信息素增加，正反馈加 强，虽然收敛性加快，但是随机性减弱容易陷入一个范围狭小的搜索圈，所以搜索质量并不 高蚂蚁数m较小时，会使为走过路径上的信息素减小为0,即搜索的随机性能会降低，虽 然加快了收敛性，但是搜索的全局性能降低，算法稳定性差，容易陷入过早的停滞.m较大 时，会使搜索路径上的信息素浓度过于平均，收敛速度变慢对于蚂蚁释放的信息素量Q来 说是一个常量

8、，Q越大，路径信息素积累越多，收敛速度越快显然可见，参数的选择对于 搜索的准确性是很重要的，这里选参原则如下：(1)确定蚂蚁数目m，可参照“问题规模数约为蚂蚁数目的1.5倍”参数a, 0的粗调，常用的几种组合有(a =1，卩=1),(a =1，卩=2),(a 二 I0 二 5 迫=0.爭,=5 ) 参数P细调，P通常设定在0.5以下.2.3 蚁群算法的基本步骤(流程)这里主要是以蚁周算法为例，总结蚁群算法的基本步骤.流程框图如下所示：注:(1)在流程图中整个算法的迭代过程是以N为刻度，1 N N ( N 为最大迭 max max代次数).在迭代过程中以时间t为刻度(1 t n)，蚂蚁k根据概率转换公式选择下一个节点.(2)禁忌表(tube):禁忌表是为了避免蚂蚁走进同一个节点的数据结构.设tube为蚂蚁k k的禁忌列表，则蚂蚁 k 走过节点 i 后就将该节点加入到自己的禁忌列表 tube 中，表示下一 k次不能再走节点i,用tube (s)表示禁忌列表中第s个元素，即蚂蚁k所走过的第s个节点, k3 蚁群算法在路径规划中的应用蚁群算法在优化领域的应用是很广泛的，下面我们给出几个例子进行

9、分析，需要说明一 下这些结果是基于实际情况和仿真实验的基础上得出的.3.1 利用计算机仿真实验求两地最短路径蚁群算法在搜寻最短路径时，对于每一步的扩展，蚂蚁在下个节点的选择上需要遵循以 下两个原则：每次所选的节点n在地图上是可以移动的，在已访问过的节点中不包括节 点n.实验步骤按照上文所给的基本步骤来求解.本实验是在VC+ +6.0的环境下进行的，实验采用的是美国某州的电子拓扑图，所选参数 按照选参原则，最大循环的次数即迭代次数N100.将20只蚂蚁放置于起始节点，对于c所有蚂蚁用式(1)计算出蚂蚁选择路径的转换概率，利用赌轮法选择出满足原则的路径, 并根据公式(2)(4)对路径上的信息素进行更新 .重复这一步骤直到所有蚂蚁搜寻到最短路径 时结束或者达到最大的迭代次数，循环结束时输出最短路径和长度.在拓扑图上选择 A.B 两 点，利用蚁群算法求出两地之间的最短路径，最终得出的结果如图2 中粗线所示.因为 20只 蚂蚁搜寻路径的节点序列表比较大，这里就不在给出.图 2 蚂蚁觅食拓扑图从计算的序列表格中可以看出20 只蚂蚁最终有17 只蚂蚁找到了最短路径，另外 3 只蚂蚁找到的虽然不是最短的路径，但是都接近最短路径，有可能是第n(n二1,2,.)短的路线，对于最优路径的搜寻引导仍具有利用价值.我们还将设计的参数数值做出了如下改变，在前50次循环中取a = 0.5, B 1,p 0.7，在后50次循环中取参数为a 1,卩=5, p = 0.9 .这 样做是为了防止最优路径上的

《蚁群算法在路径优化中的应用3改》由会员re****.1分享，可在线阅读，更多相关《蚁群算法在路径优化中的应用3改》请在金锄头文库上搜索。