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

《蚁群算法在路径优化中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、安庆师范学院数学与计算科学学院2015届毕业论文蚁群算法在路径优化中的应用作者：孙阳阳指导老师：刘冲摘要如何在繁杂的道路系统中选择最优的路径是蚁群算法在路径优化中的重要问题.本文在理解蚁群算法概念和原理的基础上，用数学形式给出了蚁群算法的数学模型，得到蚁群算法在应用中的基本步骤.通过解决几路径规划的问题，分析蚁群算法的优缺点，就其发展现状对该算法未来研究方向做展望.关键词蚁群算法算法模型分析应用发展现状及趋势1引言随着社会的飞速发展和信息的不断交流，生活中越来越多的事情要求在短时间内完成.如城市化的速度加快，如何选择城市交通的最佳路径已成为一个亟待解决的问题、以车载导航系统

2、为代表的路径搜说问题以及近些年研究热门（机器人路径规划问题）都需要一个最优路径解决方案.当然随着科学研究的发展，已经有越来越多的方法来解决路径优化问题如：遗传算法，A*算法，神经网络算法，人工势场法，模糊逻辑法.但是这些算法都有不小的弊端：遗传算法具有随机优化的特点，但是其局部搜素能力并不强，容易出现早熟现象；A*算法虽然往往能得到最优的路径，但是其局限性比较差而且算式中的启发式函数如果选择错误会使得在搜索中进入一个死循环；神经网络算法虽然具有学习能力很强的特点，但是训练过程比较困难，操作不太容易；模糊逻辑算法的适应能力比较差.为此我们利用蚁群算法来解决实际应用问题，研究和

3、相关文献得出算法的可行性和优越性.运用蚁群算法在几路径规划上的应用，掌握其解决实际问题的过程及应用.2蚁群算法2.1蚁群算法的概念蚁群算法(antcolonyoptimization),又称蚂蚁算法，简称ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所发表的论文提出的，其灵感来源于蚂蚁在寻找食物中发现路径的行为.它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流与合作不断排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径.2.2蚁群算法的基本原理蚂蚁在搜寻食物过程中总能找到一条从蚁穴到到食物的最优路径，这是因为蚂蚁在搜寻路径

4、上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路径越短，信息素浓度越大；反正路径越长信息素堆积的越少.则过一段时间蚂蚁选择信息素浓度高的路径的概率越来越大，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小，这一就形成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径.2.3蚁群算法数学模型2.3.1问题的描述求解两地间最优路径，即为求某两地间用时最少的行进路线.如在一个城市中，有A、B第14页共14页安庆师范学院数学与计算科学学院2015届毕业论文两个地

5、点，从A到B有多条路径线路可选，即求一条从A到B用时最少的路线.又比如在当今热门研究项目机器人路径规划问题中，其本质为在规划空间内依据环境信息，在某些评价标准下，找出从出发点到目标点最优的路线，比较有代表的问题是喷涂机器人，即在一个复杂曲面上如何规划喷涂机器人的路径，使其喷涂效率最高.这些问题都符合蚁群算法的思想，因此可以用蚁群算法来求解.2.3.2模型的建立首先将蚂蚁觅食与路径优化问题进行对照如表1所示表1蚂蚁觅食路径优化问题蚂蚁要遍历的各个路径各个状态整个蚁群经过的一条完整的路径解最短路径最优解信息素的浓度各状态的吸引度信息素的更新状态更新路径的长度目标函数以旅行商问题

6、（TSP）为例来构建模型，定义路与路段的交叉口为节点，路段为边.即TSP问题可描述为给定n个节点和每两个节点之间的距离，要寻找到一条路径，从某个节点出发周游到其它节点一次且仅一次，最终回到出发节点的封闭环路径长度最短.设节点数为n，蚂蚁的数目为m，蚂蚁从一个节点到另一个节点逐步完成搜索的过程.蚂蚁k(k=1,2,3...m)，根据概率转换的规则选择下一个节点.由此可以生成一个由n个节点组成的行动路线，并伴有信息素的不断更新.表示位于t时刻节点i的蚂蚁数目.则有：d表示两个节点i和j之间的距离在基本蚁群算法模型中，人工智能蚂蚁有以下特点：(1)人工智能蚂蚁具有记忆功能.每一个

7、蚂蚁k(k=1,2,3,....m)都有一个禁忌表()，即蚂蚁经过节点i()后，不能再经过节点i.(2)两个节点的距离越近，能见度则越大，被选择的期望也就越高，由此来指引人工智能蚂蚁的搜索.定义，被称为期望因子，所以蚂蚁k在t时刻从节点i转移到节点j的概率可表示为：（1）其中表示禁忌例表中第s个元素，即蚂蚁所走过的第s个节点；第14页共14页安庆师范学院数学与计算科学学院2015届毕业论文为蚂蚁所允许到达的节点的集合，；期望因子表示对边上的期望程度；表示信息素的相对重要程度；表示启发式因子的相对重要程度.这里需要重