蚁群算法课件.ppt

1、蚁群算法及其应用 算法的背景与意义算法的背景与意义 一国内外研究现状国内外研究现状二 研究内容与方法研究内容与方法三蚁群算法的应用蚁群算法的应用四预期结果预期结果五背景2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广各种改进算法的提出，应用领域更广 引起学者关注，在应用领域得到拓宽ACO首次被系统的提出首次被系统的提出自然界中真实蚁群集体行为Macro Dorigou 从自然界中蚁群的的觅食行为中受启发，M Dorigo于20世纪90年代处提出了蚁群系统。针对该算法的不足，一些学者提出了许多改进的蚁群优化算法，如蚁群系统，最大-最小蚂蚁系

2、统，最优保留蚁群系统等。近年来，一些学者提出了蚁群优化元启发式这一求解复杂问题的统一框架，这一框架为蚁群优化算法的理论研究和设计提供了技术上的保障。u 我国最早研究蚁群算法的是东北大学的张纪会博士和徐心和教授。背景有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能要好于遗传算法等算法。蚁群算法是一种基于种群的启发式搜索算法。蚁群算法广泛应用于求解TSP问题，Job-Shop调度问题，二次指派问题，背包问题等。蚁群算法蚁群算法 是一种很有发展前景的优化算法 意义u对蚁群算法的研究虽然刚刚起步，但初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。蚁群算法正

3、在受到越来越多的人的研究和注意，应用范围已由当初单一的TSP领域渗透到了多个应用领域。u 从当前可以检索到的文献情况看，研究和应用蚁群优化算法的学者主要集中在比利时，意大利，英国，法国和德国等欧洲国家。日本和美国在这两年也开始启动对蚁群算法的研究。目前，蚁群优化算法在启发式方法范畴内已逐渐成为一个独立的分支。u 尽管蚁群优化的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种新型的寻优思想无疑是具有十分光明的前景更多深入细致的工作还有待于进一步展开。国内外研究现状o 蚁群算法(ant colony optimization,ACO)，又称蚂蚁算法，是一种用

4、来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。什么是蚁群算法o 信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。o 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁如何找到最短路径o当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上

5、来，最短的路径就近似找到了。蚁群算法的基本思想蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的TSPTSP问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系统很难在可接受的循环次数内找出最优解。统很难在可接受的循环次数内找出最优解。蚁群系统做了三个方面的改进：状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法；全局更新规则只应用于最优的蚂蚁路径上；在建立问题解决方案的过程中，应用局部信息素更新规则。蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质

6、量和收敛速度，从而改进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生。MMAS能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能1.基本蚁群算法基本蚁群算法2.蚁群系统蚁群系统3.最大最大-最小蚂蚁系统最小蚂蚁系统基本蚁群算法以及改进算法基本蚁群算法o蚂蚁k(k=1,2，,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设Pijk(t)表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：()(),()()()0,kisiskkisisijx allowkttsallowttPtsallowo信息更新公式为：1(1)(1)(),01ij

7、ijijnkijiiktt 基本蚁群算法o针对蚂蚁释放信息是问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：1.蚁周系统模型2.蚁量系统模型3.蚁密系统模型ij/kij0,kiiQ d，第 只蚂蚁从城市 访问城市其他kij0,kiiQ，第 只蚂蚁从城市 访问城市其他/kij0,kkiiQ L，第 只蚂蚁从城市 访问城市其他蚁群系统o 蚁群系统(Ant Colony System,ACS)是由Dorigo和Gambardella在1996年提出的o 蚁群系统做了三个方面的改进：n状态转移规则为更好更合理地利用新路径和利用关于问状态转移规则为更好

8、更合理地利用新路径和利用关于问题的先验知识提供了方法题的先验知识提供了方法n全局更新规则只应用于最优的蚂蚁路径上全局更新规则只应用于最优的蚂蚁路径上n在建立问题解决方案的过程中，应用局部信息素更新规在建立问题解决方案的过程中，应用局部信息素更新规则则蚁群系统状态转移规则o 一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s0arg max (,)(,),ku allowedr ur uqqsS如果按先验知识选择路径否则其中，S根据下列公式得到()(),()()()0,kijijkkisisijs allowedttjallowedttPtotherwise蚁群系统状态转移规

9、则o q是在0,1区间均匀分布的随机数o q0的大小决定了利用先验知识与探索新路径之间的相对重要性。o 上述状态转移规则被称为伪随机比例规则o 特点：倾向于选择短的且有着大量信息素的边作为移动方向蚁群系统全局更新规则o 只有全局最优的蚂蚁才被允许释放信息素o 目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径的领域内o 全局更新在所有蚂蚁都完成它们的路径之后执行，使用下式对所建立的路径进行更新(,)(1)(,)(,)r sr sr s1,(,)0,gbLr s如果(r,s)全局最优路径否则蚁群系统全局更新规则o 为信息素挥发参数，0 1o 为到目前为止找出的全局最优路径gbLo 全局更新

10、规则的另一个类型称为迭代最优n区别:使用 代替 ，为当前迭代(循环)中的最优路径长度n这两种类型对蚁群系统性能的影响差别很小，全局最优的性能要稍微好一些gbLibLibL蚁群系统局部更新规则o 类似于蚁密和蚁量模型中的更新规则o 蚂蚁应用下列局部更新规则对它们所经过的边进行激素更新(,)(1)(,)(,)01r sr sr s其中,为一个参数,01nnn Lo 实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的一个路径长度nnLo 局部更新规则可以有效地避免蚂蚁收敛到同一路径最大-最小蚂蚁系统o 蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改

11、进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生o 最大-最小蚂蚁系统(Max-Min Ant System,MMAS)能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能最大-最小蚂蚁系统o MMAS和AS主要有三个方面不同：n 为了充分利用循环最优解和到目前为止找出的最优解，在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁n 为避免搜索的停滞，在每个解的元素上的的信息素轨迹量的值域范围被限制在 区间内n 将信息素轨迹初始化为maxminmax,信息素轨迹更新o 在MMAS中，只

12、有一只蚂蚁用于在每次循环后更新信息轨迹o 经修改的轨迹更新规则如下：(1)()ijbestijijtt1()ijbestbestf so 表示迭代最优解或全局最优解的值o 在蚁群算法中主要使用全局最优解，而在MMAS中则主要使用迭代最优解()bestf s信息素轨迹的限制o 不管是选择迭代最优还是全局最优蚂蚁来进行信息素更新，都可能导致搜索的停滞。o 停滞现象发生的原因：在每个选择点上一个选择的信息素轨迹量明显高于其他的选择。o 避免停滞状态发生的方法：影响用来选择下一解元素的概率，它直接依赖于信息素轨迹和启发信息。通过限制信息素轨迹的影响，可以很容易地避免各信息素轨迹之间的差异过大。信息素轨

13、迹的限制o MMAS对信息素轨迹的最小值和最大值分别施加了 和 的限制，从而使得对所有信息素轨迹 ，有minmax()ijtm inm ax()ijto MMAS收敛：在每个选择点上，其中一个解元素上的轨迹量为 ，而所有其他可选择的解元素上的轨迹量为 。minmaxo 若MMAS收敛，通过始终选择信息素量最大的解元素所构造的解将与算法找出的最优解相一致信息素轨迹的限制o 的选取maxm ax11()()ijttio p titfsopt其中,f(s)为对于一个具体问题的最优解gbopt渐进的最大值估计通过使用f(s)代替f(s)来实现o 的选取要基于两点假设n最优解在搜索停滞发生之前不久被找出

14、n对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定min信息素轨迹的限制o 在一个选择点上选择相应解元素的概率Pdec直接取决于 和minmaxo 在每个选择点上蚂蚁需在avg=n/2个解元素中选择maxmaxmin(1)decPavgo 蚂蚁构造最优解，需作n次正确的决策d e cnb e stPPmaxmaxmin(1)(1)(1)(1)nbestdecndecbestPPavgPavgP信息素轨迹的初始化o 在第一次循环后所有信息素轨迹与 相一致max(1)o 通过选择对这种类型的轨迹初始化来增加在算法的第一次循环期间对新解的探索o 当将信息素轨迹初始化为 时，选择概率将增

15、加得更加缓慢o 实验表明，将初始值设为 可以改善最大-最小蚂蚁系统的性能maxmax(1)信息素轨迹的平滑化o 基本思想：通过增加选择有着低强度信息素轨迹量解元素的概率以提高探索新解的能力*max()()()()ijijijtttt*()()ijijtt其中,01,和分别为平滑化之前和之后的信息素轨迹量o 平滑机制有助于对搜索空间进行更有效的探索TSP问题o 旅行商问题旅行商问题（TSP,traveling salesman problem）1960年首先提出。o 问题描述问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。o TSP在许多工程领域具有广泛的应用价值例如电

16、路板布线、VLSI芯片设计、机器人控制、交通路由等。o TSP的求解是NP-hardNP-hard问题问题。随着城市数目的增多,问题空间将呈指数级增长。蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为其中，为城市1,2，n的一个排列，。,|j),(iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iino下面以TSP为例说明基本蚁群算法模型。o首先将m只蚂蚁随机放置在n个城市，

17、位于城市i的第k只蚂蚁选择下一个城市j的概率为:蚁群算法求解TSP问题)1(,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskko其中：表示边（i，j）上的信息素浓度；是启发信息，d是城市i和j之间的距离；和反映了信息素与启发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。),(ji),(/1),(jidjiktabuo 当所有蚂蚁完成周游后，按以下公式进行信息素更新。蚁群算法求解TSP问题)2()()(1mkkijijijijijtnto 其中，为小于1的常数，表示信息的持久性。)3(0otherwiselijLQkkkijo 其中，Q

18、为常数；Lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。求解TSP算法步骤初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节点置入禁忌表中;迭代过程k=1while k=ItCount do(执行迭代)for i=1 to m do (对m只蚂蚁循环)for j=1 to n-1 do (对n个城市循环)根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j;将j置入禁忌表,蚂蚁转移到j;end for end for 计算每只蚂蚁的路径长度;根据式(2)更新所有蚂蚁路径上的信息量;k=k+1;end while输出结果,结束算法.TSP问题java程序验证输入项：需要输入迭代次数，就是搜索次数 2000 蚂蚁数量 50城市数量 50信息素矩阵每单元都是0.1城市的编号和坐标放在文件中（如右图）TSP问题java程序验证结果显示如下：蚁群的规模和停止规则o 蚁群大小蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。o 终止条件终止条件1 给定一个外循环的最大数目；2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。蚁群算法的缺点o 蚁群算法的缺点蚁群算法的缺点1 1）收敛速度慢）收敛速度慢2 2）易于陷入局部最优）易于陷入局部最优