蚁群算法最全集课件

蚁群算法及其应用马文强欢迎下载1蚁群算法及其应用马文强1在非洲的大草原上，如果你发现羚羊在奔逃，那一定是狮子来了；如果见到狮子在躲避，那一定是象群在发怒了；如果见到成百上千的狮子和大象集体逃命的壮观景象，那是什么来了呢？

——蚂蚁军团来了2在非洲的大草原上，如果你发现羚羊在奔逃，那一定是狮子来了；如33

算法的背景与意义

一国内外研究现状二

研究内容与方法三蚁群算法的应用四4算法的背景与意义一国内外研究现状二研究内容与方法三蚁群算法背景与意义5算法背景与意义5背景2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为MacroDorigo6背景2001年至今1996年-2001年意大利学者启发各种改从自然界中蚁群的的觅食行为中受启发，于1991年，由意大利学者M.Dorigo在其博士论文中提出，并成功的解决了旅行商(TSP)问题。针对该算法的不足，一些学者提出了许多改进的蚁群优化算法，如蚁群系统，最大-最小蚂蚁系统，最优保留蚁群系统等。近年来，一些学者提出了蚁群优化元启发式这一求解复杂问题的统一框架，这一框架为蚁群优化算法的理论研究和设计提供了技术上的保障。我国最早研究蚁群算法的是东北大学的张纪会博士和徐心和教授。背景7从自然界中蚁群的的觅食行为中受启发，于1991年，由意大利有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能要好于遗传算法等算法。蚁群算法是一种基于种群的启发式搜索算法。蚁群算法广泛应用于求解TSP问题，Job-Shop调度问题，二次指派问题，背包问题等。蚁群算法是一种很有发展前景的优化算法意义8有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。从当前可以检索到的文献情况看，研究和应用蚁群优化算法的学者主要集中在比利时，意大利，英国，法国和德国等欧洲国家。日本和美国在这两年也开始启动对蚁群算法的研究。目前，蚁群优化算法在启发式方法范畴内已逐渐成为一个独立的分支。尽管蚁群优化的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种新型的寻优思想无疑是具有十分光明的前景，更多深入细致的工作还有待于进一步展开。国内外研究现状9目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。什么是蚁群算法10什么是蚁群算法10信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁如何找到最短路径11蚂蚁如何找到最短路径11当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。蚁群算法的基本思想12当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的TSP问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系统很难在可接受的循环次数内找出最优解。蚁群系统做了三个方面的改进：状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法；全局更新规则只应用于最优的蚂蚁路径上；在建立问题解决方案的过程中，应用局部信息素更新规则。蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生。MMAS能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能1.基本蚁群算法2.蚁群系统3.最大-最小蚂蚁系统基本蚁群算法以及改进算法13蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的TS基本蚁群算法蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设Pijk(t)表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：14基本蚁群算法蚂蚁k(k=1,2，…,m)根据各个城市间连接路其中，表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列中的城市集合，是一个启发式信息，通常由直接计算，表示边(i,j)上的信息素量。由公式（1）可知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是两个预先设置的参数，用来控制启发式信息（路径的能见度）与信息浓度（路径的轨迹）作用的权重关系。当时，算法演变成传统的随机贪婪算法，最邻近城市被选种的概率最大，当时，蚂蚁完全只根据信息度浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕，实验表明，在AS中设置比较合适。15其中，表示从城市i可以直接到达的且又不在蚂基本蚁群算法信息更新公式为：在算法初始化时，问题空间中所有边上的信息素都被初始化为，如果太小，算法容易早熟，即蚂蚁很快就完部集中在一个局部最优的路径上，反之，如果太大，信息素对搜索方向的指导作用太低，也会影响算法的性能。对AS来说，我们使用，n是蚂蚁的个数，是由贪婪算法构造的路径长度。16基本蚁群算法信息更新公式为：在算法初始化时，问题空间中所有边基本蚁群算法信息素更新的每一轮中，问题空间中的所有路径上的信息素都会发生蒸发，信息素蒸发是自然界本身固有的特征，在算法中能避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差路径。随后所有的蚂蚁根据自己构建路径长度在它们本轮经过的边释放信息素。蚂蚁构建的路径越短、释放的信息素就越多；一条被蚂蚁爬过的边的次数越多、它所获得的信息素也越多。n表示蚂蚁的个数,是信息素的蒸发率，规定，一般设置为0.5.是第k只蚂蚁在它经过的边上释放的信息素量。17基本蚁群算法信息素更新的每一轮中，问题空间中的所有路径上的信基本蚁群算法针对蚂蚁释放信息是问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：1.蚁周系统模型(初始时置为0)2.蚁量系统模型(初始时置为0)3.蚁密系统模(初始时置为0)18基本蚁群算法针对蚂蚁释放信息是问题，M.Dorigo等人曾给P、NP、NP-C、NP-hard问题P类问题所有可用DTM(Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合。简记为O(p(n))即P={L:存在一个多项式时间DTM程序M，使得L=LM},其中LM表示程序M所识别的语言。若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题Π，即L[Π,e]∈P,则称该判定问题属于P类问题。19P、NP、NP-C、NP-hard问题P类问题19P、NP、NP-C、NP-hard问题NP类问题(Non-deterministicPolynomial)若存在一个多项式函数g(x)和一个验证算法H,对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I)),其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I)),则称判定问题A为非多项式确定问题。NP类问题是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合20P、NP、NP-C、NP-hard问题NP类问题(Non-P、NP、NP-C、NP-hard问题NP-C类问题(NP-Complete)是NP类中最困难的一类问题。有重要实际意义和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard类问题NP-CNP-hardNPPNP-hardNP-C21P、NP、NP-C、NP-hard问题NP-C类问题(NP基本蚁群算法模型基本假设蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。22基本蚁群算法模型基本假设22蚁群算法的应用23蚁群算法的应用23TSP问题旅行商问题（TSP,travelingsalesmanproblem）1960年首先提出。问题描述：

一商人去n个城市销货，所有城市走一遍再回到

起点，使所走路程最短。TSP在许多工程领域具有广泛的应用价值 例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。24TSP问题旅行商问题（TSP,travelingsales蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题25蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题26蚁群系统在TSP问题中的应用30城市TSP问题48城市TSPTSP问题的数学描述TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为其中，，为城市1,2，…n的一个排列，。27TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=下面以TSP为例说明基本蚁群算法模型。首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:蚁群算法求解TSP问题其中：

表示边（i，j）上的信息素浓度；

是启发信息，d是城市i和j之间的距离；

α和β反映了信息素与启发信息的相对重要性；

表示蚂蚁k已经访问过的城市列表。28下面以TSP为例说明基本蚁群算法模型。蚁群算法求解TSP问题当所有蚂蚁完成周游后，按以下公式进行信息素更新。蚁群算法求解TSP问题其中，ρ为小于1的常数，表示信息的持久性。其中，

Q为常数；表示第k只蚂蚁在本次迭代中走过的路径，为路径长度。29当所有蚂蚁完成周游后，按以下公式进行信息素更新。蚁群算法求解3030实现过程31实现过程31323233333434蚁群算法的应用举例2网络路由问题将蚁群算法应用于解决受限路由问题，目前可以解决包括带宽、延时、丢包率和最小花费等约束条件在内的QoS组播路由问题，比现有的链路状态路由算法有明显的优越性35蚁群算法的应用举例2网络路由问题35蚁群算法的应用举例3电力系统领域电力系统的许多优化问题本质上是属于组合优化问题。36蚁群算法的应用举例3电力系统领域36蚁群算法的应用举例4航迹规划问题

航迹规划是指在特定的约束条件下，寻找运动体从初始点到目标点满足某种性能指标最优的运动轨迹。37蚁群算法的应用举例4航迹规划问题375混流装配线调度混流装配线(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定时间内，在一条生产线上生产出多种不同型号的产品，产品的品种可以随顾客需求的变化而变化。SMMAL是车间作业调度问题(job-shopschedulingproblem,JSP)的具体应用之一。蚁群算法的应用385混流装配线调度混流装配线(sequencingmixe问题描述以汽车组装为例，即在组装所有车辆的过程中，所确定的组装顺序应使各零部件的使用速率均匀化。如果不同型号的汽车消耗零部件的种类大致相同，那么原问题可简化为单级SMMAL调度问题。39问题描述以汽车组装为例，即在组装所有车辆的过程中，所确定的组问题描述i表示车型数的标号n表示需要装配的车型数m表示装配线上需要的零部件种类总数p表示生产调度中子装配的标号表示零部件p的理想使用速率j表示车型调度结果(即排序位置)的标号D表示在一个生产循环中需要组装的各种车型的总和40问题描述i表示车型数的标号40问题描述di表示在一个生产循环中车型i的数量bip表示生产每辆i车型需要零部件p的数量表示在组装线调度中前j-1台车消耗零部件p的数量和41问题描述di表示在一个生产循环中车型i的数量416蚁群算法在SMMAL中的应用假设有3种车型A、B、C排序，每个生产循环需A型车3辆，B型车2辆，C型车1辆，则每个循环共需生产6辆车。采用下图的搜索空间定义，列表示6个排序阶段，行表示有3种车型可以选择。蚁群算法就是不断改变圆圈的大小，最终寻找到满意的可行解。搜索的初始状态426蚁群算法在SMMAL中的应用假设有3种车型A、B、C排序简单SMMAL排序的搜索空间举例经过若干次迭代之后，搜索空间变化，此时最可能的可行解为B-A-C-A-B-A若干次迭代后的状态43简单SMMAL排序的搜索空间举例经过若干次迭代之后，搜索空局部搜索()的计算局部搜索采用的是贪心策略基本思路：每一步均从当前可选择策略中选取，使目标函数值增加最少的策略，即在确定第j个位置组装的车型时，如果有多种车型可供选择，则从中选择一种车型i，使第j个位置组装车型i时各零部件的使用速率最为均匀。44局部搜索()的计算局部搜索采用的是贪心策略基本思状态转移概率状态转移概率公式如下45状态转移概率状态转移概率公式如下45信息素更新规则LB表示目标函数的下限值表示当前目标函数的平均值Zcutr表示当前的目标函数值这种动态标记的方法可在搜索过程中加大可行解间信息素的差别，避免算法早熟46信息素更新规则LB表示目标函数的下限值46实验数据47实验数据47实验参数设置蚂蚁系统蚂蚁数量N_ant=5最大循环周期Ncmax=400=0.2Q=20000=0.9LB=0.0蚁群系统q0=0.5全局更新规则中的

和局部更新规则中的均取0.148实验参数设置蚂蚁系统蚁群系统48实验参数设置最大-最小蚂蚁系统选取全局最优解带有精英策略的蚂蚁系统精英蚂蚁数量:1只49实验参数设置最大-最小蚂蚁系统带有精英策略的蚂蚁系统49实验结果50实验结果50实验结果分析直接用贪心策略求解结果：3293.4375蚂蚁系统求解SMMAL问题的性能较差对于这个具体的问题，带精英策略的蚂蚁系统的求解性能并不好于蚂蚁系统蚁群系统的性能相对于前两者而言，有了很大幅度的提高最大-最小蚂蚁系统的性能最好，大多数情况下的求解结果已达到实际的最优解51实验结果分析直接用贪心策略求解结果：51蚁群的规模和停止规则蚁群大小

一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。终止条件 1给定一个外循环的最大数目； 2当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。52蚁群的规模和停止规则蚁群大小52蚁群算法的缺点蚁群算法的缺点 1）收敛速度慢 2）易于陷入局部最优53蚁群算法的缺点蚁群算法的缺点53Questions?54Questions?54个人观点供参考，欢迎讨论个人观点供参考，欢迎讨论蚁群算法及其应用马文强欢迎下载56蚁群算法及其应用马文强1在非洲的大草原上，如果你发现羚羊在奔逃，那一定是狮子来了；如果见到狮子在躲避，那一定是象群在发怒了；如果见到成百上千的狮子和大象集体逃命的壮观景象，那是什么来了呢？

——蚂蚁军团来了57在非洲的大草原上，如果你发现羚羊在奔逃，那一定是狮子来了；如583

算法的背景与意义

一国内外研究现状二

研究内容与方法三蚁群算法的应用四59算法的背景与意义一国内外研究现状二研究内容与方法三蚁群算法背景与意义60算法背景与意义5背景2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为MacroDorigo61背景2001年至今1996年-2001年意大利学者启发各种改从自然界中蚁群的的觅食行为中受启发，于1991年，由意大利学者M.Dorigo在其博士论文中提出，并成功的解决了旅行商(TSP)问题。针对该算法的不足，一些学者提出了许多改进的蚁群优化算法，如蚁群系统，最大-最小蚂蚁系统，最优保留蚁群系统等。近年来，一些学者提出了蚁群优化元启发式这一求解复杂问题的统一框架，这一框架为蚁群优化算法的理论研究和设计提供了技术上的保障。我国最早研究蚁群算法的是东北大学的张纪会博士和徐心和教授。背景62从自然界中蚁群的的觅食行为中受启发，于1991年，由意大利有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能要好于遗传算法等算法。蚁群算法是一种基于种群的启发式搜索算法。蚁群算法广泛应用于求解TSP问题，Job-Shop调度问题，二次指派问题，背包问题等。蚁群算法是一种很有发展前景的优化算法意义63有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。从当前可以检索到的文献情况看，研究和应用蚁群优化算法的学者主要集中在比利时，意大利，英国，法国和德国等欧洲国家。日本和美国在这两年也开始启动对蚁群算法的研究。目前，蚁群优化算法在启发式方法范畴内已逐渐成为一个独立的分支。尽管蚁群优化的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种新型的寻优思想无疑是具有十分光明的前景，更多深入细致的工作还有待于进一步展开。国内外研究现状64目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。什么是蚁群算法65什么是蚁群算法10信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁如何找到最短路径66蚂蚁如何找到最短路径11当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。蚁群算法的基本思想67当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的TSP问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系统很难在可接受的循环次数内找出最优解。蚁群系统做了三个方面的改进：状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法；全局更新规则只应用于最优的蚂蚁路径上；在建立问题解决方案的过程中，应用局部信息素更新规则。蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生。MMAS能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能1.基本蚁群算法2.蚁群系统3.最大-最小蚂蚁系统基本蚁群算法以及改进算法68蚂蚁系统是最早的蚁群优化算法。蚂蚁算法在解决一些小规模的TS基本蚁群算法蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设Pijk(t)表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：69基本蚁群算法蚂蚁k(k=1,2，…,m)根据各个城市间连接路其中，表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列中的城市集合，是一个启发式信息，通常由直接计算，表示边(i,j)上的信息素量。由公式（1）可知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是两个预先设置的参数，用来控制启发式信息（路径的能见度）与信息浓度（路径的轨迹）作用的权重关系。当时，算法演变成传统的随机贪婪算法，最邻近城市被选种的概率最大，当时，蚂蚁完全只根据信息度浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕，实验表明，在AS中设置比较合适。70其中，表示从城市i可以直接到达的且又不在蚂基本蚁群算法信息更新公式为：在算法初始化时，问题空间中所有边上的信息素都被初始化为，如果太小，算法容易早熟，即蚂蚁很快就完部集中在一个局部最优的路径上，反之，如果太大，信息素对搜索方向的指导作用太低，也会影响算法的性能。对AS来说，我们使用，n是蚂蚁的个数，是由贪婪算法构造的路径长度。71基本蚁群算法信息更新公式为：在算法初始化时，问题空间中所有边基本蚁群算法信息素更新的每一轮中，问题空间中的所有路径上的信息素都会发生蒸发，信息素蒸发是自然界本身固有的特征，在算法中能避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差路径。随后所有的蚂蚁根据自己构建路径长度在它们本轮经过的边释放信息素。蚂蚁构建的路径越短、释放的信息素就越多；一条被蚂蚁爬过的边的次数越多、它所获得的信息素也越多。n表示蚂蚁的个数,是信息素的蒸发率，规定，一般设置为0.5.是第k只蚂蚁在它经过的边上释放的信息素量。72基本蚁群算法信息素更新的每一轮中，问题空间中的所有路径上的信基本蚁群算法针对蚂蚁释放信息是问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：1.蚁周系统模型(初始时置为0)2.蚁量系统模型(初始时置为0)3.蚁密系统模(初始时置为0)73基本蚁群算法针对蚂蚁释放信息是问题，M.Dorigo等人曾给P、NP、NP-C、NP-hard问题P类问题所有可用DTM(Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合。简记为O(p(n))即P={L:存在一个多项式时间DTM程序M，使得L=LM},其中LM表示程序M所识别的语言。若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题Π，即L[Π,e]∈P,则称该判定问题属于P类问题。74P、NP、NP-C、NP-hard问题P类问题19P、NP、NP-C、NP-hard问题NP类问题(Non-deterministicPolynomial)若存在一个多项式函数g(x)和一个验证算法H,对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I)),其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I)),则称判定问题A为非多项式确定问题。NP类问题是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合75P、NP、NP-C、NP-hard问题NP类问题(Non-P、NP、NP-C、NP-hard问题NP-C类问题(NP-Complete)是NP类中最困难的一类问题。有重要实际意义和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard类问题NP-CNP-hardNPPNP-hardNP-C76P、NP、NP-C、NP-hard问题NP-C类问题(NP基本蚁群算法模型基本假设蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。77基本蚁群算法模型基本假设22蚁群算法的应用78蚁群算法的应用23TSP问题旅行商问题（TSP,travelingsalesmanproblem）1960年首先提出。问题描述：

一商人去n个城市销货，所有城市走一遍再回到

起点，使所走路程最短。TSP在许多工程领域具有广泛的应用价值 例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。79TSP问题旅行商问题（TSP,travelingsales蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题80蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题81蚁群系统在TSP问题中的应用30城市TSP问题48城市TSPTSP问题的数学描述TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为其中，，为城市1,2，…n的一个排列，。82TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=下面以TSP为例说明基本蚁群算法模型。首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:蚁群算法求解TSP问题其中：

表示边（i，j）上的信息素浓度；

是启发信息，d是城市i和j之间的距离；

α和β反映了信息素与启发信息的相对重要性；

表示蚂蚁k已经访问过的城市列表。83下面以TSP为例说明基本蚁群算法模型。蚁群算法求解TSP问题当所有蚂蚁完成周游后，按以下公式进行信息素更新。蚁群算法求解TSP问题其中，ρ为小于1的常数，表示信息的持久性。其中，

Q为常数；表示第k只蚂蚁在本次迭代中走过的路径，为路径长度。84当所有蚂蚁完成周游后，按以下公式进行信息素更新。蚁群算法求解8530实现过程86实现过程31873288338934蚁群算法的应用举例2网络路由问题将蚁群算法应用于解决受限路由问题，目前可以解决包括带宽、延时、丢包率和最小花费等约束条件在内的QoS组播路由问题，比现有的链路状态路由算法有明显的优越性90蚁群算法的应用举例2网络路由问题35蚁群算法的应用举例3电力系统领域电力系统的许多优化问题本质上是属于组合优化问题。91蚁群算法的应用举例3电力系统领域36蚁群算法的应用举例4航迹规划问题

航迹规划是指在特定的约束条件下，寻找运动体从初始点到目标点满足某种性能指标最优的运动轨迹。92蚁群算法的应用举例4航迹规划问题375混流装配线调度混流装配线(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定时间内，在一条生产线上生产出多种不同型号的产品，产品的品种可以随顾客需求的变化而变化。SMMAL是车间作业调度问题(job-shopschedulingproblem,JSP)的具体应用之一。蚁群算法的应用935混流装配线调度混流装配线(sequencingmixe问题描述以汽车组装为例，即在组装所有车辆的过程中，所确定的组装顺序应使各零部件的使用速率均匀化。如果不同型号的汽车消耗零部件的种类大致相同，那么原问题可简化为单级SMMAL调度问题。94问题描述以汽车组装为例，即在组装所有车辆的过程中，所确定的组问题描述i表示车型数的标号n表示需要装配的车型数m表示装配线上需要的零部件种类总数p表示生产调度中子装配的标号表示零部件p的理想使用速率j表示车型调度结果(即排序位置)的标