智能算法及应用.ppt

《智能算法及应用.ppt》由会员分享，可在线阅读，更多相关《智能算法及应用.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、智能优化算法及应用智能优化算法及应用Intelligent Optimization Algorithms西安工程大学贺兴时西安工程大学贺兴时智能优化算法智能优化算法 智能优化算法又称为现代启发式算智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。时间内找到最优解或近似最优解。智能优化算法的特点智能优化算法的特点 它

2、们的共同特点：都是从任一解出发，它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局空间扩展到整个问题空间，因而具有全局优化性能。优化性能。背背 景景传统实际问题的特点：传统实际问题的特点：连续性问题主要以微积分为基础，且问题规模较小传统的方法（运筹学）传统的方法（运筹学）：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。追求准确精确解 理论的完美结果漂亮传统的评价方法：传统的评价方法：算法收敛性

3、（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）传统方法面临的挑战传统方法面临的挑战现代问题的特点 离散性问题主要以组合优化理论为基础 不确定性问题随机性数学模型 半结构或非结构化的问题计算机模拟、决策支持系统 大规模问题并行计算、大型分解理论、近似理论现代优化方法追求满意近似解；实用性强解决实际问题现代优化算法的评价方法 算法复杂性内容简介内容简介1 1、组合优化问题是组合优化问题是解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。典型的优化问题：典型的优化问题：0-10

4、-1背包问题，旅行商问题，背包问题，旅行商问题，机器排序问题等机器排序问题等内容简介内容简介2 2、模拟退火算法模拟退火算法（simulated annealing）退火是一种物理过程，金属物体在加热至一退火是一种物理过程，金属物体在加热至一定的温度后，它的所有分子在状态空间中自定的温度后，它的所有分子在状态空间中自由运动。随着温度的下降，这些分子逐渐停由运动。随着温度的下降，这些分子逐渐停留在不同的状态。在温度最低时，分子重新留在不同的状态。在温度最低时，分子重新以一定的结构排列。模拟退火算法的直观理以一定的结构排列。模拟退火算法的直观理解是：在一个给定的温度，搜索从一个状态解是：在一个给定

5、的温度，搜索从一个状态随机的变化到另一个状态，每一个状态到达随机的变化到另一个状态，每一个状态到达的次数服从一个概率分布。当温度很低时，的次数服从一个概率分布。当温度很低时，以概率以概率1 1停留在最优解。停留在最优解。内容简介内容简介3 3、遗传算法遗传算法（genetic algorithms）遗传算法主要借用生物进化中遗传算法主要借用生物进化中“适者生存适者生存”的规律而设计。遗传算法包含以下主要的规律而设计。遗传算法包含以下主要步骤：第一是对优化问题的解进行编码；步骤：第一是对优化问题的解进行编码；第二是适应函数的构造和应用，适应函数第二是适应函数的构造和应用，适应函数基本上依据优化问

6、题的目标函数而定；基本上依据优化问题的目标函数而定；第三是染色体的结合；最后是变异。第三是染色体的结合；最后是变异。内容简介内容简介3 3、蚁群优化算法（蚁群优化算法（Ant_Algorithm）的基本）的基本思想是模仿蚂蚁依赖信息素进行通信而显示出思想是模仿蚂蚁依赖信息素进行通信而显示出的社会行为。蚂蚁在行动中，会在他们经过的的社会行为。蚂蚁在行动中，会在他们经过的地方留下一些化学物质，称之为地方留下一些化学物质，称之为“信息素信息素”，这些物质能被同一蚁群中后来的蚂蚁感受到，这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后者的行动，蚂蚁选择这并作为一种信号影响后者的行动，蚂蚁选

7、择这条路径的可能性比选择没有这些物质的路径的条路径的可能性比选择没有这些物质的路径的可能性大，后到者留下的信息素会对原有的信可能性大，后到者留下的信息素会对原有的信息素进行加强，这样越短的路径会被越多的蚂息素进行加强，这样越短的路径会被越多的蚂蚁访问，这个过程一直持续到所有的蚂蚁都走蚁访问，这个过程一直持续到所有的蚂蚁都走最短的那一条路径为止。最短的那一条路径为止。内容简介内容简介4 4、粒子群优化算法粒子群优化算法(Particle Swarm optimization)是是一种进化计算技术一种进化计算技术(Evolutionary Computation)，由，由Eberhart博士和博士

8、和Kennedy博士发明。源于对博士发明。源于对鸟群捕食的行为研究。鸟群捕食的行为研究。PSO中，每个优化问题的中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为解都是搜索空间中的一只鸟。我们称之为“粒子粒子”。所有的粒子都有一个由被优化的函数决定的。所有的粒子都有一个由被优化的函数决定的适应值适应值(fitness value)，每个粒子还有一个速度决，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。前的最优粒子在解空间中搜索。内容简介内容简介5 5、人工神经网络人工神经网络(ARTIFICIAL NE

9、URAL(ARTIFICIAL NEURAL NETWORKNETWORK，简称，简称ANN)ANN)是在对人脑组织结构和运是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。神经网络的基本原理为：行为的一种工程系统。神经网络的基本原理为：大脑皮层每一点的活力是由其他点势能释放的大脑皮层每一点的活力是由其他点势能释放的综合效能产生。这一势能同下面的因数有关：综合效能产生。这一势能同下面的因数有关：相关其他点的兴奋次数；兴奋的强度；与其不相关其他点的兴奋次数；兴奋的强度；与其不相连的其他点所接受的能量。人工神经网络的相连的其他

10、点所接受的能量。人工神经网络的建立和应用可以归结为三个步骤：网络结构的建立和应用可以归结为三个步骤：网络结构的确定，关联权的确定和工作阶段。确定，关联权的确定和工作阶段。参考资料1.吴启迪吴启迪 智能蚁群算法及应用智能蚁群算法及应用，上海科技出版社，上海科技出版社 从基本结构、算法特点、改进方法、突破途径、从基本结构、算法特点、改进方法、突破途径、实现模式及应用模式等方面进行了论述。实现模式及应用模式等方面进行了论述。主要内容：蚁群算法的由来、研究成果、应用综主要内容：蚁群算法的由来、研究成果、应用综述、算法的具体描述及改进、算法的典型优化问述、算法的具体描述及改进、算法的典型优化问题求解模式

11、、算法的典型应用及拓展应用。题求解模式、算法的典型应用及拓展应用。参考资料2.李士勇李士勇 蚁群算法及其应用，蚁群算法及其应用，哈工大出版社哈工大出版社 系统地阐述蚁群算法的基本原理、基本蚁群算系统地阐述蚁群算法的基本原理、基本蚁群算法及改进算法，蚁群算法与遗传、免疫算法的法及改进算法，蚁群算法与遗传、免疫算法的融合，自适应蚁群算法，并行蚁群算法，蚁群融合，自适应蚁群算法，并行蚁群算法，蚁群算法的收敛性与理论模型及其在优化问题中的算法的收敛性与理论模型及其在优化问题中的应用。应用。参考资料3.王凌王凌 微粒子群优化与调度算法，微粒子群优化与调度算法，清华大学出清华大学出版社版社 系统地阐述粒子

12、群算法的基本原理、特点、流系统地阐述粒子群算法的基本原理、特点、流程和相关研究进展，程和相关研究进展，PSOPSO的收敛问题和应用。的收敛问题和应用。参考资料4.邢文训，谢金星邢文训，谢金星 现代优化计算方法，清华大现代优化计算方法，清华大学出版社，学出版社，2005。5.康立山，谢云尤矢勇等康立山，谢云尤矢勇等 模拟退火算法，科学模拟退火算法，科学出版社，出版社，19946.朱大奇朱大奇 人工神经网络原理及应用，科学出版人工神经网络原理及应用，科学出版社，社，2006一、现代优化计算方法概述一、现代优化计算方法概述1.1 组合优化问题1.2 计算复杂性的概念1.3 启发式算法1.1 组合优化

13、问题组合优化问题组合优化的数学模型：1.1 组合优化问题组合优化问题组合优化问题的三参数表示：1.1 组合优化问题组合优化问题 例例1 0-1背包问题（背包问题（0-1 knapsack problem）1.1 组合优化问题组合优化问题1.1 组合优化问题组合优化问题例2 旅行商问题（TSP,traveling salesman problem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。1.1 组合优化问题组合优化问题1.1 组合优化问题组合优化问题例例3 装箱问题（装箱问题（bin packing）尺寸

14、为尺寸为1的箱子有若干个，怎样用最少的箱的箱子有若干个，怎样用最少的箱子装下子装下n个尺寸不超过个尺寸不超过1 的物品，物品集合的物品，物品集合为：为：。1.1 组合优化问题组合优化问题1.2 计算复杂性的概念计算复杂性的概念对该研究有兴趣可参考如下文献：计算复杂性,作者：作者：Christos，Papadimitriou清华大学出版社，清华大学出版社，2004年年9月第月第1版版计算复杂性导论，作者：堵丁柱等，作者：堵丁柱等，高等教育出版社，高等教育出版社，2002年年8月第月第1版版1.2 计算复杂性的概念计算复杂性的概念评价算法的好坏计算时间的多少、解的偏离程度例：非对称距离TSP问题的

15、算法实现，所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：1.2 计算复杂性的概念计算复杂性的概念 随城市增多，计算时间增加很快。到随城市增多，计算时间增加很快。到随城市增多，计算时间增加很快。到随城市增多，计算时间增加很快。到3131个城市时，个城市时，个城市时，个城市时，要计算要计算要计算要计算325325年。描述算法的好坏年。描述算法的好坏年。描述算法的好坏年。描述算法的好坏计算复杂性计算复杂性计算复杂性计算复杂性讨论计算时间与问题规模之间的关系。以目前二讨论计算时间与问题规模之间的关系。以目前

16、二讨论计算时间与问题规模之间的关系。以目前二讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式进制计算机中的存储和计算为基础，以理论的形式进制计算机中的存储和计算为基础，以理论的形式进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。系统描述，是评估算法性能的基础。系统描述，是评估算法性能的基础。系统描述，是评估算法性能的基础。城市城市城市城市数数数数2 24 42525262627272828292930303131计算计算计算计算时间时间时间时间1 1secsec2424secsec1010minmin4.34.3hourhour

17、4.94.9dayday136.5136.5dayday10.810.8yearyear325325yearyear1.3 启发式算法启发式算法 启发式算法（启发式算法（heuristic algorithmheuristic algorithm）定义1.基于基于直观或经验构造的算法，在可接受构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个问题的每个实例的一个可行解，该可行解与最，该可行解与最优解偏差事先不一定可以预计优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计启发式算法是一种技术，在可接受的计算

18、费用内寻找最好解，但不保证该解的可行性算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.1.3 启发式算法启发式算法 优点：（1）有可能比简化数学模型解的误差小；）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算）可用于某些最优化算法（如分支定界算 法）之中的估界；法）之中的估界；（4）直观易行；（）直观易行；（5）速度较快；）速度较快；（6）程序简单，

19、易修改。）程序简单，易修改。1.3 启发式算法启发式算法不足：（1）不能保证求得全局最优解；）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术）算法设计与问题、设计者经验、技术 有关，有关，缺乏规律性；缺乏规律性；（4）不同算法之间难以比较。）不同算法之间难以比较。1.3 启发式算法启发式算法分类：（1）一步算法（2）改进算法（迭代算法）（3）数学规划算法（4）解空间松弛法1.3 启发式算法启发式算法（5）现代优化算法：80年代初兴起年代初兴起 禁忌搜索（禁忌搜索（tabu search）模拟退火（模拟退火（si

20、mulated annealing）遗传算法（遗传算法（genetic algorithms）神经网络（神经网络（neural networks）蚂蚁算法（蚂蚁算法（Ant Algorithm，群体（群集）智能，群体（群集）智能，Swarm Intelligence）（6）其他算法：多种启发式算法的集成多种启发式算法的集成.1.3 启发式算法启发式算法性能分析：性能分析：（1）最坏情形分析）最坏情形分析（worst case analysis）利用最坏实例分析计算复杂性、解的效果。利用最坏实例分析计算复杂性、解的效果。(2）概率分析）概率分析（probability analysis）用最坏情

21、况分析，会因一个最坏实例影响总体用最坏情况分析，会因一个最坏实例影响总体评价评价.在实例数据服从一定概率分布情形下，研究算在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果法复杂性和解的效果.(3)大规模计算分析大规模计算分析 通过大量实例计算，评价算法效果通过大量实例计算，评价算法效果.注意数据的随机性和代表性注意数据的随机性和代表性.二、二、蚁群优化算法蚁群优化算法2.1 蚁群优化算法概念2.2 蚁群优化算法研究现状2.3 带精英策略的蚂蚁系统带精英策略的蚂蚁系统2.4 算法模型和收敛性分析2.5 算法实现的技术问题2.6 应用蚁群优化算法20202020世纪世纪世纪世纪90909

22、090年代意大利学者年代意大利学者年代意大利学者年代意大利学者M M M MDorigoDorigoDorigoDorigo，V V V VManiezzoManiezzoManiezzoManiezzo，A A A AColorniColorniColorniColorni等从生物进化的机制中受到启发，通过模等从生物进化的机制中受到启发，通过模等从生物进化的机制中受到启发，通过模等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟自然界蚂蚁搜索路径的行为，提出来一种新型

23、的模拟进化算法拟进化算法拟进化算法拟进化算法 蚁群算法，是群智能理论研究领域蚁群算法，是群智能理论研究领域蚁群算法，是群智能理论研究领域蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解的一种主要算法。用该方法求解的一种主要算法。用该方法求解的一种主要算法。用该方法求解TSPTSPTSPTSP问题、分配问题、问题、分配问题、问题、分配问题、问题、分配问题、job-shopjob-shopjob-shopjob-shop调度问题，取得了较好的试验结果特别蚁调度问题，取得了较好的试验结果特别蚁调度问题，取得了较好的试验结果特别蚁调度问题，取得了较好的试验结果特别蚁群算法在求解复杂优化问题（

24、特别是离散优化问题）群算法在求解复杂优化问题（特别是离散优化问题）群算法在求解复杂优化问题（特别是离散优化问题）群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，方面有一定优势，方面有一定优势，方面有一定优势，2.1 蚁群优化算法概念 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。2.1

25、 蚁群优化算法概念蚂蚁搜寻食物的具体过程：蚂蚁搜寻食物的具体过程：在蚁群寻找食物时，它们总能找到一条从食物在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低路径越长，释放的激索浓度越低.当后来的蚂蚁再当后来的蚂蚁再次碰到这个路口的

26、时候选择激素浓度较高路径概次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。最优路径。2.1 蚁群优化算法概念蚂蚁从蚂蚁从蚂蚁从蚂蚁从A A点出发，速度相同，食物在点出发，速度相同，食物在点出发，速度相同，食物在点出发，速度相同，食物在D D点，可能随机选择路线点，可能随机选择路线点，可能随机选择路线点，可能随机选择路线ABDABD或或

27、或或ACDACD。假设初始时每条分配路线一只蚂蚁，每个时。假设初始时每条分配路线一只蚂蚁，每个时。假设初始时每条分配路线一只蚂蚁，每个时。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过间单位行走一步，本图为经过间单位行走一步，本图为经过间单位行走一步，本图为经过9 9个时间单位时的情形：走个时间单位时的情形：走个时间单位时的情形：走个时间单位时的情形：走ABDABD的蚂蚁到达终点，而走的蚂蚁到达终点，而走的蚂蚁到达终点，而走的蚂蚁到达终点，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到的蚂蚁刚好走到的蚂蚁刚好走到C C点，为一点，为一点，为一点，为一半路程。半路程。半路程。半路

28、程。2.1 蚁群优化算法概念本图为从开始算起，经过本图为从开始算起，经过本图为从开始算起，经过本图为从开始算起，经过1818个时间单位时的情形：个时间单位时的情形：个时间单位时的情形：个时间单位时的情形：走走走走ABDABD的蚂蚁到达终点后得到食物又返回了起点的蚂蚁到达终点后得到食物又返回了起点的蚂蚁到达终点后得到食物又返回了起点的蚂蚁到达终点后得到食物又返回了起点A A，而走，而走，而走，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到的蚂蚁刚好走到的蚂蚁刚好走到D D点。点。点。点。2.1 蚁群优化算法概念 假设蚂蚁每经过一处所留下的信息素为一个单位，假设蚂蚁每经过一处所留下的信息素为一个单位

29、，则经过则经过3636个时间单位后，所有开始一起出发的蚂蚁都个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从经过不同路径从D D点取得了食物，此时点取得了食物，此时ABDABD的路线往的路线往返了返了2 2趟，每一处的信息素为趟，每一处的信息素为4 4个单位，而个单位，而 ACDACD的路线的路线往返了一趟，每一处的信息素为往返了一趟，每一处的信息素为2 2个单位，其比值为个单位，其比值为2 2：1 1。寻找食物的过程继续进行，则按信息素的指导，寻找食物的过程继续进行，则按信息素的指导，蚁群在蚁群在ABDABD路线上增派一只蚂蚁（共路线上增派一只蚂蚁（共2 2只），而只），而ACDACD路

30、线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过3636个时间单位后，两个时间单位后，两条线路上的信息素单位积累为条线路上的信息素单位积累为1212和和4 4，比值为，比值为3 3：1 1。2.1 蚁群优化算法概念 若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABDABD路线上再增派一路线上再增派一只蚂蚁（共只蚂蚁（共3 3只），而只），而ACDACD路线上仍然为一只蚂蚁。路线上仍然为一只蚂蚁。再经过再经过3636个时间单位后，两条线路上的信息素单位积个时间单位后，两条线路上的信息素单位积累为累为2424和和6 6，比值为，比值为4 4：1 1。若继续进行，则按信息素的指导，最终所有

31、的蚂若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃蚁会放弃ACDACD路线，而都选择路线，而都选择ABDABD路线。这也就是前路线。这也就是前面所提到的正反馈效应。面所提到的正反馈效应。2.1 蚁群优化算法概念 TSPTSP问题表示为一个问题表示为一个问题表示为一个问题表示为一个N N个城市的有向图个城市的有向图个城市的有向图个城市的有向图G=G=（N N，A A），），），），其中其中其中其中城市之间距离城市之间距离城市之间距离城市之间距离目标函数为目标函数为目标函数为目标函数为 ，其中其中其中其中 为城市为城市为城市为城市1,21,2，nnnn的的的的一个排列，一个排列，一个排列，一个

32、排列，。2.1 蚁群优化算法概念 TSPTSP问题的人工蚁群算法中，假设问题的人工蚁群算法中，假设问题的人工蚁群算法中，假设问题的人工蚁群算法中，假设mm只蚂蚁在图的只蚂蚁在图的只蚂蚁在图的只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。相邻节点间移动，从而协作异步地得到问题的解。相邻节点间移动，从而协作异步地得到问题的解。相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类每只蚂蚁的一步转移概率由图中的每条边上的两类每只蚂蚁的一步转移概率由图中的每条边上的两类每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：参数决定：参数决定：参数决定：1 1

33、 信息素值信息素值信息素值信息素值 也称信息素痕迹。也称信息素痕迹。也称信息素痕迹。也称信息素痕迹。2 2 可见度，可见度，可见度，可见度，即先验值。即先验值。即先验值。即先验值。信息素的更新方式有信息素的更新方式有信息素的更新方式有信息素的更新方式有2 2种，一是挥发，也就是所种，一是挥发，也就是所种，一是挥发，也就是所种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自有路径上的信息素以一定的比率进行减少，模拟自有路径上的信息素以一定的比率进行减少，模拟自有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给然蚁群的信息素随时间挥发的过程；二

34、是增强，给然蚁群的信息素随时间挥发的过程；二是增强，给然蚁群的信息素随时间挥发的过程；二是增强，给评价值评价值评价值评价值“好好好好”(有蚂蚁走过有蚂蚁走过有蚂蚁走过有蚂蚁走过)的边增加信息素。的边增加信息素。的边增加信息素。的边增加信息素。2.1 蚁群优化算法概念 蚂蚁向下一个目标的运动是通过一个随机原则来蚂蚁向下一个目标的运动是通过一个随机原则来蚂蚁向下一个目标的运动是通过一个随机原则来蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算实现的，也就是运用当前所在节点存储的信息，计算实现的，也就是运用当前所在节点存储的信息，计算实现的，也就是运用当前所在

35、节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，出下一步可达节点的概率，并按此概率实现一步移动，出下一步可达节点的概率，并按此概率实现一步移动，出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。逐此往复，越来越接近最优解。逐此往复，越来越接近最优解。逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估蚂蚁在寻找过程中，或者找到一个解后，会评估蚂蚁在寻找过程中，或者找到一个解后，会评估蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在该解或解的一部分的优化程度，并把评价信息保存在该解或解的一部分

36、的优化程度，并把评价信息保存在该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。相关连接的信息素中。相关连接的信息素中。相关连接的信息素中。2.1 蚁群优化算法概念初始的蚁群算法是基于图的蚁群算法，初始的蚁群算法是基于图的蚁群算法，初始的蚁群算法是基于图的蚁群算法，初始的蚁群算法是基于图的蚁群算法，graph-based graph-based ant system,ant system,简称为简称为简称为简称为GBASGBAS，是由，是由，是由，是由Gutjahr W JGutjahr W J在在在在20002000年的年的年的年的Future Generation Comp

37、uting Future Generation Computing SystemsSystems提出的提出的提出的提出的.算法步骤如下：算法步骤如下：算法步骤如下：算法步骤如下：STEP 0STEP 0 对对对对n n个城市的个城市的个城市的个城市的TSPTSP问题，问题，问题，问题，城市间的距离矩阵为城市间的距离矩阵为城市间的距离矩阵为城市间的距离矩阵为 ，给，给，给，给TSPTSP图中的每图中的每图中的每图中的每一条弧一条弧一条弧一条弧 赋信息素初值赋信息素初值赋信息素初值赋信息素初值 ，假设，假设，假设，假设mm只蚂蚁在工作，所有蚂蚁都从同一城市只蚂蚁在工作，所有蚂蚁都从同一城市只蚂蚁在

38、工作，所有蚂蚁都从同一城市只蚂蚁在工作，所有蚂蚁都从同一城市 出发。出发。出发。出发。当前最好解是当前最好解是当前最好解是当前最好解是。2.1 蚁群优化算法概念STEP 1STEP 1 （外循环）如果满足算法的停止规则，则停止计算并（外循环）如果满足算法的停止规则，则停止计算并（外循环）如果满足算法的停止规则，则停止计算并（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁输出计算得到的最好解。否则使蚂蚁输出计算得到的最好解。否则使蚂蚁输出计算得到的最好解。否则使蚂蚁s s从起点从起点从起点从起点 出发，用出发，用出发，用出发，用 表示蚂蚁表示蚂蚁表示蚂蚁表示蚂蚁s

39、s行走的城市集合，初始行走的城市集合，初始行走的城市集合，初始行走的城市集合，初始 为空集，为空集，为空集，为空集，。STEP 2STEP 2 (内循环内循环内循环内循环)按蚂蚁按蚂蚁按蚂蚁按蚂蚁 的顺序分别计算。当的顺序分别计算。当的顺序分别计算。当的顺序分别计算。当蚂蚁在城市蚂蚁在城市蚂蚁在城市蚂蚁在城市i i，若，若，若，若 完成第完成第完成第完成第s s只蚂蚁的计算。否则，若只蚂蚁的计算。否则，若只蚂蚁的计算。否则，若只蚂蚁的计算。否则，若，则以概率，则以概率，则以概率，则以概率，到达到达到达到达j j，；若；若；若；若则到达则到达则到达则到达 重复重复重复重复STEP 2STEP 2

40、。2.1 蚁群优化算法概念STRP 3STRP 3 对对对对 ，若，若，若，若 ，按，按，按，按 中城市的顺中城市的顺中城市的顺中城市的顺序计算路径程度；若序计算路径程度；若序计算路径程度；若序计算路径程度；若 ，路径长度置为一个，路径长度置为一个，路径长度置为一个，路径长度置为一个无穷大值（即不可达）。比较无穷大值（即不可达）。比较无穷大值（即不可达）。比较无穷大值（即不可达）。比较mm只蚂蚁中的路径长只蚂蚁中的路径长只蚂蚁中的路径长只蚂蚁中的路径长度，记走最短路径的蚂蚁为度，记走最短路径的蚂蚁为度，记走最短路径的蚂蚁为度，记走最短路径的蚂蚁为t t。若若若若 ，则，则，则，则 。用如下公式

41、对。用如下公式对。用如下公式对。用如下公式对WW路径上的信息素痕迹加强，对其他路径上的信息路径上的信息素痕迹加强，对其他路径上的信息路径上的信息素痕迹加强，对其他路径上的信息路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。素进行挥发。素进行挥发。素进行挥发。得到新的得到新的得到新的得到新的 ，重复步骤，重复步骤，重复步骤，重复步骤STEP 1STEP 1。2.1 蚁群优化算法概念在在在在STEP 3STEP 3 中，挥发因子中，挥发因子中，挥发因子中，挥发因子 对于一个固定的对于一个固定的对于一个固定的对于一个固定的 ，满足满足满足满足并且并且并且并且 经过经过经过经过k k次挥发，非最

42、优路径的信息素逐渐减少至消。次挥发，非最优路径的信息素逐渐减少至消。次挥发，非最优路径的信息素逐渐减少至消。次挥发，非最优路径的信息素逐渐减少至消。2.1 蚁群优化算法概念 以上算法中，在蚂蚁的搜寻过程中，以信息素的以上算法中，在蚂蚁的搜寻过程中，以信息素的以上算法中，在蚂蚁的搜寻过程中，以信息素的以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市概率分布来决定从城市概率分布来决定从城市概率分布来决定从城市i i到城市到城市到城市到城市j j的转移。的转移。的转移。的转移。算法中包括信息素更新的过程算法中包括信息素更新的过程算法中包括信息素更新的过程算法中包括信息素更新的过程 1

43、1 信息素挥发（信息素挥发（信息素挥发（信息素挥发（evaporation):evaporation):信息素痕迹的挥发过信息素痕迹的挥发过信息素痕迹的挥发过信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的程是每个连接上的信息素痕迹的浓度自动逐渐减弱的程是每个连接上的信息素痕迹的浓度自动逐渐减弱的程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由过程，由过程，由过程，由 表示，这个挥发过程主要表示，这个挥发过程主要表示，这个挥发过程主要表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜用于避免算法过快地向局部最优区域集中，有助于搜用于避免算法过快地向局部最

44、优区域集中，有助于搜用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。索区域的扩展。索区域的扩展。索区域的扩展。2.1 蚁群优化算法概念 2 2 信息素增强（信息素增强（信息素增强（信息素增强（reinforcement):reinforcement):增强过程是蚁群优增强过程是蚁群优增强过程是蚁群优增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在化算法中可选的部分，称为离线更新方式（还有在化算法中可选的部分，称为离线更新方式（还有在化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法线更新方式）。这种方式可以实现由单个蚂蚁无法线更新方

45、式）。这种方式可以实现由单个蚂蚁无法线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察实现的集中行动。也就是说，增强过程体现在观察实现的集中行动。也就是说，增强过程体现在观察实现的集中行动。也就是说，增强过程体现在观察蚁群（蚁群（蚁群（蚁群（mm只蚂蚁）中每只蚂蚁所找到的路径，并选只蚂蚁）中每只蚂蚁所找到的路径，并选只蚂蚁）中每只蚂蚁所找到的路径，并选只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过择其中最优路径上的弧进行信息素的增强，挥发过择其中最优路径上的弧进行信息素的增强，挥发过择其中最优路径上的弧进行信息素的增强，挥

46、发过程是所有弧都进行的，不于蚂蚁数量相关。这种增程是所有弧都进行的，不于蚂蚁数量相关。这种增程是所有弧都进行的，不于蚂蚁数量相关。这种增程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更。强过程中进行的信息素更新称为离线的信息素更。强过程中进行的信息素更新称为离线的信息素更。强过程中进行的信息素更新称为离线的信息素更。在在在在STEP 3STEP 3中，蚁群永远记忆到目前为止的最优解。中，蚁群永远记忆到目前为止的最优解。中，蚁群永远记忆到目前为止的最优解。中，蚁群永远记忆到目前为止的最优解。2.1 蚁群优化算法概念可以验证，下式满足：可以验证，下式满足：可以

47、验证，下式满足：可以验证，下式满足：即即即即 是一个随机矩阵。是一个随机矩阵。是一个随机矩阵。是一个随机矩阵。四个城市的非对称四个城市的非对称四个城市的非对称四个城市的非对称TSPTSP问题，距离矩阵和城市图示如下：问题，距离矩阵和城市图示如下：问题，距离矩阵和城市图示如下：问题，距离矩阵和城市图示如下：2.1 蚁群优化算法概念假设共假设共假设共假设共4 4只蚂蚁，所有蚂蚁都从城市只蚂蚁，所有蚂蚁都从城市只蚂蚁，所有蚂蚁都从城市只蚂蚁，所有蚂蚁都从城市A A出发，挥发因子出发，挥发因子出发，挥发因子出发，挥发因子 。此时，观察。此时，观察。此时，观察。此时，观察GBASGBAS的计算过程。的计

48、算过程。的计算过程。的计算过程。矩阵共有矩阵共有矩阵共有矩阵共有1212条弧，初始信息素记忆矩阵为：条弧，初始信息素记忆矩阵为：条弧，初始信息素记忆矩阵为：条弧，初始信息素记忆矩阵为：2.1 蚁群优化算法概念执行执行执行执行GBASGBAS算法的步骤算法的步骤算法的步骤算法的步骤2 2，设蚂蚁的行走路线分别为：，设蚂蚁的行走路线分别为：，设蚂蚁的行走路线分别为：，设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是当前最优解为，这个解是截止到当前的最优解，碰巧是当前最优解为，这个解是截止到当前的最优解，碰巧是当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解实际最优

49、解实际最优解实际最优解2.1 蚁群优化算法概念按算法步骤按算法步骤按算法步骤按算法步骤3 3的信息素更新规则，得到更新矩阵的信息素更新规则，得到更新矩阵的信息素更新规则，得到更新矩阵的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。这是第一次外循环结束的状态。这是第一次外循环结束的状态。这是第一次外循环结束的状态。2.1 蚁群优化算法概念 重复外循环，由于上一次得到的重复外循环，由于上一次得到的W2已经是全局已经是全局最优解，因此按算法步骤最优解，因此按算法步骤3的信息素更新规则，的信息素更新规则，无论蚂蚁如何行走，都只是对无论蚂蚁如何行走，都只是对W2路线上的城市路线上的城市信息素进

50、行增强，其他的城市信息素进行挥发。信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵得到更新矩阵这是第一次外循环结束的状态。这是第一次外循环结束的状态。2.1 蚁群优化算法概念 重复外循环，由于重复外循环，由于W2全局最优解，全局最优解，GBAS只记只记录第一个最优解，因此一但得到了全局最优解，录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：挥发。第三次外循环后得到的信息素矩阵为：2.1 蚁群优化算