基于蚁群算法的路径最优研究 毕业答辩

导师:王康平答辩人:刘媛媛专

业:计算机科学与技术基于蚁群算法的路径最优问题研究论文的结构和主要内容第一部分

选题的背景与意义第二部分

国内外研究现状第三部分

研究内容与方法第四部分

研究中可能存在的问题第五部分

预期结果一选题背景与意义

2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为一选题背景与意义蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。二国内外研究现状目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。三研究内容与方法

1.基本蚁群算法及其改进算法（1）基本蚁群算法（2）蚁群系统（3）最大-最小蚂蚁系统2.蚁群算法与TSP应用（1）蚁群算法的思想、原理（2）蚁群算法的实现方式（3）TSP应用举例

3.1.1蚁群算法的基本思想

在自然界中，蚂蚁的食物源往往随机散布于蚁巢周围，通过观察可以发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。自然界中的蚂蚁虽然视觉能力十分有限，但它们在觅食过程中，却能够通过播撒、感知信息素与其它同伴建立起通讯关系，并以此相互协调、分工、合作来找到食物源和巢穴之间的最短路径。并且在相同的时间内，路径越短则遗留的信息素浓度就越大，而蚂蚁在选择路径时，倾向于那些信息素浓度较高的路径，这样选择较短路径的蚂蚁也随之增多。因此，由大量蚂蚁组成的蚁群集体觅食行为表现出了一种正反馈现象：一条路径上走过的蚂蚁越多，则后来者选择这条路径的概率就越高。蚂蚁个体之间就是通过这种信息素的交流机制，来搜索食物，并最终找到最短路径。

3.1.2蚂蚁觅食原理：自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后，它们仍然能很快重新找到新的最佳路线。蚂蚁觅食原理这是因为在蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的。蚂蚁在运动过程中，不但能够在它所经过的路径上留下该物质，而且能够感知这种物质的存在及其强度，并朝着该物质强度高的方向移动，为此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要多于较长路径，而某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。蚁群算法的基本原理简单来说就是：1、蚂蚁在路径上释放信息素。2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。4、最优路径上的信息素浓度越来越大．5、最终蚁群找到最优寻食路径。3.1.3蚁群算法的优缺点蚁群算法的优点不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优解的优化能力。该算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制、易于与其他方法相结合等诸多优点。

蚁群算法的缺点：蚁群算法的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题，它没有坚实的数学基础；蚁群算法的模型普适性不强，其模型不能直接应用于实际优化问题；蚁群算法的局部搜索能力较弱，易于出现停滞和局部收敛、收敛速度慢等问题，因而往往需要嵌入一些专门的辅助技巧；长时间花费在解的构造上，从而导致搜索时间过长，算法最先基于离散问题，不能直接解决连续优化问题。3.2自然蚁群与人工蚁群

蚁群算法都是从自然界中真实蚂蚁寻找食物行为得到启发提出来的。人们只有通过对蚁群行为的一种模拟来满足实际问题的求解需要。所以人工蚁群与真实蚁群之间存在一定的异同。

相似之处在于：都是优先选择信息素浓度大的路径。两者的区别：（1）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。（2）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在TSP问题中，可以预先知道当前城市到下一个目的地的距离。3.3.1基本蚁群算法蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：

信息更新公式为：针对蚂蚁释放信息是问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：1.蚁周系统模型2.蚁量系统模型3.蚁密系统模型其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度。d为城市间的距离。3.3.2蚁群系统蚁群系统的状态转移规则

一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s：其中，S根据下列公式得到q是在[0,1]区间均匀分布的随机数q0的大小决定了利用先验知识与探索新路径之间的相对重要性。

蚂蚁系统全局更新原则只有全局最优的蚂蚁才被允许释放信息素。目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。全局更新在所有蚂蚁都完成它们的路径之后执行，试用下式对所建立的路径进行更新：为信息素挥发因数，0<<1。为到目前为止找出的全局最优路径。

蚁群系统局部更新原则蚂蚁应用下列局部更新原则对它们所经过的边进行激素更新：

实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的一个路径长度。局部