1、1蚁群算法及其应用马文强欢迎下载2o在非洲的大草原上，如果你发现羚羊在奔逃，那一定是狮子来了；如果见到狮子在躲避，那一定是象群在发怒了；如果见到成百上千的狮子和大象集体逃命的壮观景象，那是什么来了呢？ 蚂蚁军团来了34 算法的背景与意义算法的背景与意义 一国内外研究现状国内外研究现状二 研究内容与方法研究内容与方法三蚁群算法的应用蚁群算法的应用四5算法背景与意义6背景2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广各种改进算法的提出，应用领域更广 引起学者关注，在应用领域得到拓宽ACO首次被系统的提出首次被系统的提出自然界中真实蚁群集体行
2、为Macro Dorigo7u 从自然界中蚁群的的觅食行为中受启发， 于1991年，由意大利学者M.Dorigo在其博士论文中提出，并成功的解决了旅行商(TSP)问题 。针对该算法的不足，一些学者提出了许多改进的蚁群优化算法，如蚁群系统，最大-最小蚂蚁系统，最优保留蚁群系统等。近年来，一些学者提出了蚁群优化元启发式这一求解复杂问题的统一框架，这一框架为蚁群优化算法的理论研究和设计提供了技术上的保障。u 我国最早研究蚁群算法的是东北大学的张纪会博士和徐心和教授。背景8有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能要好于遗传算法等算法。蚁群算法是一种基于种群的启发式搜索算法 。蚁群算
3、法广泛应用于求解TSP问题，Job-Shop调度问题，二次指派问题，背包问题等。蚁群算法蚁群算法 是一种很有发展前景的优化算法 意义9u 目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决一维静态优化问题一维静态优化问题发展到解决多维动态组合优化多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。u 从当前可以检索到的文献情况看，研究和应用蚁群优化算法的学者主要集中在比利
4、时，意大利，英国，法国和德国等欧洲国家。日本和美国在这两年也开始启动对蚁群算法的研究。目前，蚁群优化算法在启发式方法范畴内已逐渐成为一个独立的分支。u 尽管蚁群优化的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种新型的寻优思想无疑是具有十分光明的前景，更多深入细致的工作还有待于进一步展开。国内外研究现状10o 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 什么是蚁
5、群算法11o 信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。o 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁如何找到最短路径12o当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。蚁群算法的基本思想13蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的蚂蚁系统是最早的蚁群优化算法。蚂蚁算法
6、在解决一些小规模的TSPTSP问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系统很难在可接受的循环次数内找出最优解。统很难在可接受的循环次数内找出最优解。蚁群系统做了三个方面的改进：状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法；全局更新规则只应用于最优的蚂蚁路径上；在建立问题解决方案的过程中，应用局部信息素更新规则。蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生。 MMAS能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在
7、一起，从而使算法获得最优的性能1.基本蚁群算法基本蚁群算法2.蚁群系统蚁群系统3.最大最大-最小蚂蚁系统最小蚂蚁系统基本蚁群算法以及改进算法14基本蚁群算法o 蚂蚁k(k=1,2，,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设Pijk(t)表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为： ( ) ( , ) ( , ),( ) ( , ) ( , )( , )(1)0,kkks Jii ji jif jJii si sPi jotherwiseo 其中， 表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列 中的城市集合， 是一个启发式信息，通常由 直接计算，
8、表示边(i,j)上的信息素量。 由公式（1）可知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。 和 是两个预先设置的参数，用来控制启发式信息（路径的能见度）与信息浓度（路径的轨迹）作用的权重关系。当 时，算法演变成传统的随机贪婪算法，最邻近城市被选种的概率最大，当 时，蚂蚁完全只根据信息度浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕，实验表明，在AS中设置 比较合适。( )kJikR( , )i j( ,)1 /iji jd( , )i j001 2,a 2 516基本蚁群算法o信息更新公式为：1(1)(1)( ),01ijijij
9、nkijijktt o 在算法初始化时，问题空间中所有边上的信息素都被初始化为 ，如果 太小，算法容易早熟，即蚂蚁很快就完部集中在一个局部最优的路径上，反之，如果 太大，信息素对搜索方向的指导作用太低，也会影响算法的性能。对AS来说，我们使用 ，n是蚂蚁的个数， 是由贪婪算法构造的路径长度。00/nn CnC0017基本蚁群算法o 信息素更新的每一轮中，问题空间中的所有路径上的信息素都会发生蒸发，信息素蒸发是自然界本身固有的特征，在算法中能避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差路径。随后所有的蚂蚁根据自己构建路径长度在它们本轮经过的边释放信息素。蚂蚁构建的路径越短、释放的信
10、息素就越多；一条被蚂蚁爬过的边的次数越多、它所获得的信息素也越多。o n表示蚂蚁的个数, 是信息素的蒸发率，规定 ，一般设置为0.5. 是第k只蚂蚁在它经过的边上释放的信息素量。01ij18基本蚁群算法o针对蚂蚁释放信息是问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：1.蚁周系统模型(初始时置为0)2.蚁量系统模型(初始时置为0)3.蚁密系统模(初始时置为0)ij/kij0,kijQ d，第 只蚂蚁从城市 访问城市其他kij0,kijQ，第 只蚂蚁从城市 访问城市其他/kij0,kkijQ L，第 只蚂蚁从城市 访问城市其他19P、NP、N
11、P-C、NP-hard问题o P类问题n 所有可用DTM (Deterministic one-tape Turing Machine) 在多项式时间内求解的判定问题的集合。简记为O(p(n)n 即 P=L: 存在一个多项式时间DTM程序M，使得L=LM , 其中LM表示程序M所识别的语言。n 若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题，即L, eP,则称该判定问题属于P类问题。20P、NP、NP-C、NP-hard问题o NP类问题 (Non-deterministic Polynomial)n 若存在一个多项式函数 g(x) 和一个验证算法H, 对一类判定问题A的任何一
12、个“是”回答，满足其输入长度d(s)不超过g(d(I), 其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I), 则称判定问题A为非多项式确定问题。n NP类问题是所有可用NDTM (Non-Deterministic one-tape Turing Machine)在多项式时间内求解的判定问题的集合21P、NP、NP-C、NP-hard问题o NP-C类问题 (NP-Complete)n是NP类中最困难的一类问题。n有重要实际意义和工程背景nTSP (Traveling Salesman Problem)o Symmetric; Asymmetrico NP
13、-hard类问题nNP-C NP-hardNPPNP-hardNP-C22基本蚁群算法模型o 基本假设n 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；n 蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体n 在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。23蚁群算法的应用24TSP问题o 旅行商问题旅行商问题（TSP,traveling salesman problem）1960年首先提出。o 问题描述问题描述：一商人去n个城市销货，所有城市走
14、一遍再回到起点，使所走路程最短。o TSP在许多工程领域具有广泛的应用价值例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。o TSP的求解是NP-hardNP-hard问题问题。随着城市数目的增多,问题空间将呈指数级增长。 25蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题26蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题27TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为其中， ，为城市1,2，n的一个排列， 。nnijd)(nliilldwf11)(),(21niiiw11iinN1,2,.,n
15、 A(i ,j)| ,i jN12( , , )nwi ii28o下面以TSP为例说明基本蚁群算法模型。o首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为: 蚁群算法求解TSP问题) 1 (,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskko其中：表示边（i，j）上的信息素浓度； 是启发信息，d是城市i和j之间的距离； 和反映了信息素与启发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。),(ji),(/1),(jidjiktabu29o 当所有蚂蚁完成周游后，按以下公式进行信息素更新。蚁群算法求解TSP
16、问题)2()()(1mkkijijijijijtnto 其中，为小于1的常数，表示信息的持久性。) 3(0otherwiselijLQkkkijo 其中， Q为常数； 表示第k只蚂蚁在本次迭代中走过的路径， 为路径长度。 kLkLkLkL31实现过程3235蚁群算法的应用举例o 2网络路由问题o 将蚁群算法应用于解决受限路由问题，目前可以解决包括带宽、延时、丢包率和最小花费等约束条件在内的QoS组播路由问题，比现有的链路状态路由算法有明显的优越性36蚁群算法的应用举例o 3电力系统领域o 电力系统的许多优化问题本质上是属于组合优化问题。37蚁群算法的应用举例o 4航迹规划问题 o 航迹规划是指
17、在特定的约束条件下，寻找运动体从初始点到目标点满足某种性能指标最优的运动轨迹。385 混流装配线调度混流装配线(sequencing mixed models on an assembly line, SMMAL)是指一定时间内，在一条生产线上生产出多种不同型号的产品，产品的品种可以随顾客需求的变化而变化。SMMAL是车间作业调度问题(job-shop scheduling problem, JSP)的具体应用之一。蚁群算法的应用39问题描述o 以汽车组装为例，即在组装所有车辆的过程中，所确定的组装顺序应使各零部件的使用速率均匀化。如果不同型号的汽车消耗零部件的种类大致相同，那么原问题可简化为
18、单级SMMAL调度问题。21,111min()Dnmpipjpjijipjbx1,0,jiijx如果车型 在调度中的 位置否则iipipd bD40问题描述o i表示车型数的标号o n表示需要装配的车型数o m表示装配线上需要的零部件种类总数o p表示生产调度中子装配的标号o 表示零部件p的理想使用速率o j表示车型调度结果(即排序位置)的标号o D表示在一个生产循环中需要组装的各种车型的总和p41问题描述o di表示在一个生产循环中车型i的数量o bip表示生产每辆i车型需要零部件p的数量o 表示在组装线调度中前j-1台车消耗零部件p的数量和1,0,0jpjpjiippx b且1,jp426
19、 蚁群算法在SMMAL中的应用o 假设有3种车型A、B、C排序，每个生产循环需A型车3辆，B型车2辆，C型车1辆，则每个循环共需生产6辆车。采用下图的搜索空间定义，列表示6个排序阶段，行表示有3种车型可以选择。蚁群算法就是不断改变圆圈的大小，最终寻找到满意的可行解。搜索的初始状态43 简单SMMAL排序的搜索空间举例o 经过若干次迭代之后，搜索空间变化，此时最可能的可行解为B-A-C-A-B-A若干次迭代后的状态44局部搜索( )的计算ij21,1()ijmpipkppQjbo 局部搜索 采用的是贪心策略ijo 基本思路：每一步均从当前可选择策略中选取，使目标函数值增加最少的策略，即在确定第j
20、个位置组装的车型时，如果有多种车型可供选择，则从中选择一种车型i，使第j个位置组装车型i时各零部件的使用速率最为均匀。45状态转移概率o 状态转移概率公式如下(1),(1)( )0,kijijkkijijijj tabuitabupt 若否则46信息素更新规则o LB表示目标函数的下限值o 表示当前目标函数的平均值o Zcutr表示当前的目标函数值o 这种动态标记的方法可在搜索过程中加大可行解间信息素的差别，避免算法早熟Z0(1),0,cutrkijZLBijZLB如果车型 在调度中的 位置否则_1nantkijijk()(1)( )ijijijtnt 47实验数据48实验参数设置o 蚂蚁系统
21、n蚂蚁数量N_ant = 5n最大循环周期Ncmax = 400n = 0.2nQ = 20000n = 0.9nLB = 0.0o 蚁群系统nq0 = 0.5n全局更新规则中的 和局部更新规则中的 均取0.149实验参数设置o 最大-最小蚂蚁系统n 选取全局最优解()bestf smin0max00,1,LD L 是利用贪心策略算得的目标函数值o 带有精英策略的蚂蚁系统n精英蚂蚁数量:1只50实验结果51实验结果分析o 直接用贪心策略求解结果：n 3293.4375o 蚂蚁系统求解SMMAL问题的性能较差o 对于这个具体的问题，带精英策略的蚂蚁系统的求解性能并不好于蚂蚁系统o 蚁群系统的性能相对于前两者而言，有了很大幅度的提高o 最大-最小蚂蚁系统的性能最好，大多数情况下的求解结果已达到实际的最优解52蚁群的规模和停止规则o 蚁群大小蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。o 终止条件终止条件1 给定一个外循环的最大数目；2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。53蚁群算法的缺点o 蚁群算法的缺点蚁群算法的缺点1 1）收敛速度慢）收敛速度慢2 2）易于陷入局部最优）易于陷入局部最优54Questions?个人观点供参考，欢迎讨论
