资源描述：
《蚁群算法在路径优化中的应用3改》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、蚁群算法在路径优化中的应用作者：孙阳阳指导老师：刘冲摘要针对蚁群算法在路径中的优化问题，本文首先介绍了蚁群算法的概念及其原理，利用数学形式建立算法模型.根据蚁群算法计算的基本步骤来分析蚁群算法在交通路径优化、TSP问题等3个方面的应用，由实验结果可知蚁群算法在路径优化中具有很好的可行性和优越性，能起到很好的效果.关键词蚁群算法算法模型算法步骤分析应用1引言路径规划是指在具有障碍物的环境下，在符合某种评价条件中，寻找到一条从起始地点到目标地点最优的路径.蚁样算法是近儿年优化领域屮新出现的一种启发式仿生类并行儕能进化系统，
2、计算法釆用分布式并行计算和止反馈机制，且易丁•其它算法结合，目前已有许多关于其在路径规划方面的文献.建立蚁群算法模型M2I,解决城市交通路径优化问题，实验结果表血在搜索效率和搜索最优解的能力两方而都有很人的提高•但是传统蚁样算法易陷入局部最优解和收敛速度较慢，为此在机器人路径规划的应用中片门，将传统蚁酬算法进行改进，例如与栅格法相结合、在几何模型下建立模型等•提高了算法的有效性和鲁棒性，解决了蚁群过早陷入局部最优解的问题，扩人了蚂蚁的搜索空间，增强了蚁群算法在机器人路径规划屮的适应能力.本文通过对蚁样算法的研究以及解决
3、儿实际路径规划问题,得出了蚁群算法是有其可行性和优越性的，说明了该算法可以在众多优化领域中得到广泛的应用.2蚁群算法蚁群算法(antcolonyoptimization),又称蚂蚁算法，简称ACO.是由Dorigom>Maniezzov^Colomi等人在1992年所发表的论文提出的，其灵感來源于蚂蚁在寻找食物屮发现路径的行为•它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流为合作不断排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径.2.1蚁群算法的基本原理蚂蚁在搜寻食物过程中总能找到一条从蚁穴到
4、到食物的最优路径,这是因为蚂蚁在捜寻路径上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路径越短，信息素浓度越大；反正路径越长信息素堆积的越少•则过一段时间蚂蚁选择信息素浓度高的路径的概率越来越人，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小,这一就形成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径.2.2蚁群算法的数学模型2.2.1问题的描述求解两地间最优路径，即为求某两地间用时最少的行进路
5、线•如在一个城市中，冇A、B两个地点，从4到B有多条路径线路可选，即求一条从A到B用时最少的路线.又比如在当今热门研究项目机器人路径规划问题中，-其本质为在规划空间内依据环境信息，在某些评价标准下，找出从出发点到冃标点最优的路线，比较有代表的问题是喷涂机器人，即在一个复杂曲面上如何规划喷涂机器人的路径，使其喷涂效率最高.这些问题都符合蚁群算法的思想，因此可以用蚁群算法來求解.2.2.2模型的建立百先将蚂蚁觅食与路径优化问题进行对照如表1所示表1蚂蚁觅食和路径优化对照表蚂蚁觅食路径优化问题蚂蚁要遍历的各个路径各个状态整个
6、蚁群经过的一•条完幣的路径解最愆路径最优解侑息素的浓度各状态的吸引度信息素的更新状态更新路径的长度口标函数以旅行商问题(TSP)为例來构建模型，定义路与路段的交义口为节点，路段为边.即TSP问题可描述为给定"个节点和每两个节点Z间的距离，要寻找到一条路径，从某个节点出发周游到其它节点一次且仅一次，最终回到出发节点的封闭环路径长度最短.设节点数为宀蚂蚁的数目为加，蚂蚁从一个节点到另一个节点逐步完成搜索的过程.蚂蚁*伙=1,2,3..肋)，根据概率转换的规则选择F—个节点.由此可以生成一个由〃个节点组成的行动路线，并伴有信
7、息素的不断更新勺⑴表示位于/时刻节点/的蚂蚁数则有：m=b{(0+优⑴+...+bn(t)djj(i,j=1,2,3•…,n)d表示两个节点i和j之间的距离在基木蚁样算法模型中，人工智能蚂蚁有以下特点：(1)人工智能蚂蚁具冇记忆功能.每一个蚂蚁心=1,2,3,….加)都冇一个禁忌表(加如)，即蚂蚁经过节点i(zw〃)后，不能再经过节点i.(2)两个节点的距离越近，能见度则越大，被选择的期望也就越高，由此来指引人工智能蚂蚁的搜索.定义%=+，被称为期望因了，所以蚂蚁鸟在r时刻从节点i转移到节点j的概率可表示为:咖)二工
8、阮⑴］%⑴丫(1)sejk(/)o,j电Jk(0其中tubers)表示禁忌例表中第s个元素，即蚂蚁所走过的第s个节点；Jk(z)为蚂蚁所允许到达的节点的集合，人(0={1,2…/}-血“；期望因子％表示对边〈门〉上的期望程度;a表示信息素的相对重要程度；0表示启发式因了的相对重要程度.这里需要垂点说明一下:当Q取较大值吋，蚂蚁在选
