《智能算法及应用.ppt》由会员分享，可在线阅读，更多相关《智能算法及应用.ppt（67页珍藏版）》请在三一办公上搜索。
1、智能优化算法及应用,Intelligent Optimization Algorithms,西安工程大学贺兴时,智能优化算法,智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。,智能优化算法的特点,它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。,背 景,传统实际问题的特点：连续性问题主要以微积分为基础，且问题规模较小传统的方法（运筹学）：线性与非
2、线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。追求准确精确解 理论的完美结果漂亮传统的评价方法：算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）,传统方法面临的挑战,现代问题的特点 离散性问题主要以组合优化理论为基础 不确定性问题随机性数学模型 半结构或非结构化的问题计算机模拟、决策支持系统 大规模问题并行计算、大型分解理论、近似理论现代优化方法追求满意近似解；实用性强解决实际问题现代优化算法的评价方法 算法复杂性,内容简介,1、组合优化问题是解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉
3、及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。典型的优化问题：0-1背包问题，旅行商问题，机器排序问题等,内容简介,2、模拟退火算法（simulated annealing）退火是一种物理过程，金属物体在加热至一定的温度后，它的所有分子在状态空间中自由运动。随着温度的下降，这些分子逐渐停留在不同的状态。在温度最低时，分子重新以一定的结构排列。模拟退火算法的直观理解是：在一个给定的温度，搜索从一个状态随机的变化到另一个状态，每一个状态到达的次数服从一个概率分布。当温度很低时，以概率1停留在最优解。,内容简介,3、遗传算法（genetic algorithms）遗传算法主要借用生物
4、进化中“适者生存”的规律而设计。遗传算法包含以下主要步骤：第一是对优化问题的解进行编码；第二是适应函数的构造和应用，适应函数基本上依据优化问题的目标函数而定；第三是染色体的结合；最后是变异。,内容简介,3、蚁群优化算法（Ant_Algorithm）的基本思想是模仿蚂蚁依赖信息素进行通信而显示出的社会行为。蚂蚁在行动中，会在他们经过的地方留下一些化学物质，称之为“信息素”，这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后者的行动，蚂蚁选择这条路径的可能性比选择没有这些物质的路径的可能性大，后到者留下的信息素会对原有的信息素进行加强，这样越短的路径会被越多的蚂蚁访问，这个过程一直持续到
5、所有的蚂蚁都走最短的那一条路径为止。,内容简介,4、粒子群优化算法(Particle Swarm optimization)是一种进化计算技术(Evolutionary Computation)，由Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为研究。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。,内容简介,5、人工神经网络(ARTIFICIAL NEURAL NETWORK，简称ANN
6、)是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。神经网络的基本原理为：大脑皮层每一点的活力是由其他点势能释放的综合效能产生。这一势能同下面的因数有关：相关其他点的兴奋次数；兴奋的强度；与其不相连的其他点所接受的能量。人工神经网络的建立和应用可以归结为三个步骤：网络结构的确定，关联权的确定和工作阶段。,参考资料,1.吴启迪 智能蚁群算法及应用，上海科技出版社 从基本结构、算法特点、改进方法、突破途径、实现模式及应用模式等方面进行了论述。主要内容：蚁群算法的由来、研究成果、应用综述、算法的具体描述及改进、算法的典型优化问题求解模式、算法的典型应用及拓展应用。,参
7、考资料,2.李士勇 蚁群算法及其应用，哈工大出版社 系统地阐述蚁群算法的基本原理、基本蚁群算法及改进算法，蚁群算法与遗传、免疫算法的融合，自适应蚁群算法，并行蚁群算法，蚁群算法的收敛性与理论模型及其在优化问题中的应用。,参考资料,3.王凌 微粒子群优化与调度算法，清华大学出版社 系统地阐述粒子群算法的基本原理、特点、流程和相关研究进展，PSO的收敛问题和应用。,参考资料,4.邢文训，谢金星 现代优化计算方法，清华大学出版社，2005。5.康立山，谢云尤矢勇等 模拟退火算法，科学出版社，19946.朱大奇 人工神经网络原理及应用，科学出版社，2006,一、现代优化计算方法概述,1.1 组合优化问
8、题1.2 计算复杂性的概念1.3 启发式算法,1.1 组合优化问题,组合优化的数学模型：,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）尺寸为1的箱子有若干个，怎样用
9、最少的箱子装下n个尺寸不超过1 的物品，物品集合为：。,1.1 组合优化问题,1.2 计算复杂性的概念,对该研究有兴趣可参考如下文献：计算复杂性,作者：Christos，Papadimitriou清华大学出版社，2004年9月第1版计算复杂性导论，作者：堵丁柱等，高等教育出版社，2002年8月第1版,1.2 计算复杂性的概念,评价算法的好坏计算时间的多少、解的偏离程度例：非对称距离TSP问题的算法实现，所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：,1.2 计算复杂性的概念,随城市增多，计算时间增加
10、很快。到31个城市时，要计算325年。描述算法的好坏计算复杂性讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。,1.3 启发式算法,启发式算法（heuristic algorithm）定义1.基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的
11、偏离程度.,1.3 启发式算法,优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算 法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。,1.3 启发式算法,不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术 有关，缺乏规律性；（4）不同算法之间难以比较。,1.3 启发式算法,分类：（1）一步算法（2）改进算法（迭代算法）（3）数学规划算法（4）解空间松弛法,1.3 启发式算法,（5）现代优化算法：80年代初兴起禁忌搜索（tabu search）模
12、拟退火（simulated annealing）遗传算法（genetic algorithms）神经网络（neural networks）蚂蚁算法（Ant Algorithm，群体（群集）智能，Swarm Intelligence）（6）其他算法：多种启发式算法的集成.,1.3 启发式算法,性能分析：（1）最坏情形分析（worst case analysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析（probability analysis）用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.(3)大规模计算分析 通过大量实例计
13、算，评价算法效果.注意数据的随机性和代表性.,二、蚁群优化算法,2.1 蚁群优化算法概念2.2 蚁群优化算法研究现状2.3 带精英策略的蚂蚁系统2.4 算法模型和收敛性分析2.5 算法实现的技术问题2.6 应用,蚁群优化算法,20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果特别蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，,2.1
14、 蚁群优化算法概念,蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,2.1 蚁群优化算法概念,蚂蚁搜寻食物的具体过程：在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此
15、同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。,2.1 蚁群优化算法概念,蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。,2.1 蚁群优化算法概念,本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到
16、达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。,2.1 蚁群优化算法概念,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。,2.1 蚁群优化算法概念,若按以上规则继续，蚁群在ABD路线上再增派一只
17、蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。,2.1 蚁群优化算法概念,TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为，其中 为城市1,2，n的一个排列，。,2.1 蚁群优化算法概念,TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值 也称信息素痕迹。2 可见度，即先验
18、值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。,2.1 蚁群优化算法概念,蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,2.1 蚁群优化算法概念,初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，
19、是由Gutjahr W J在2000年的Future Generation Computing Systems提出的.算法步骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为，给TSP图中的每一条弧 赋信息素初值，假设m只蚂蚁在工作，所有蚂蚁都从同一城市 出发。当前最好解是。,2.1 蚁群优化算法概念,STEP 1（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点 出发，用 表示蚂蚁s行走的城市集合，初始 为空集，。STEP 2(内循环)按蚂蚁 的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率，到达j，；若则到达 重
20、复STEP 2。,2.1 蚁群优化算法概念,STRP 3 对，若，按 中城市的顺序计算路径程度；若，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若，则。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。得到新的，重复步骤STEP 1。,2.1 蚁群优化算法概念,在STEP 3 中，挥发因子 对于一个固定的，满足并且 经过k次挥发，非最优路径的信息素逐渐减少至消。,2.1 蚁群优化算法概念,以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程 1 信息素挥发（evaporation
21、):信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。,2.1 蚁群优化算法概念,2 信息素增强（reinforcement):增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更。在STEP 3中，蚁群永远记忆到目前为止的
22、最优解。,2.1 蚁群优化算法概念,可以验证，下式满足：即 是一个随机矩阵。四个城市的非对称TSP问题，距离矩阵和城市图示如下：,2.1 蚁群优化算法概念,假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子。此时，观察GBAS的计算过程。矩阵共有12条弧，初始信息素记忆矩阵为：,2.1 蚁群优化算法概念,执行GBAS算法的步骤2，设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解,2.1 蚁群优化算法概念,按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。,2.1 蚁群优化算法概念,重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步
23、骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。,2.1 蚁群优化算法概念,重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：,2.1 蚁群优化算法概念,蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP 3 完成，并随K而变化。假设第K次外循环后得到信息素矩阵，得到当前最优解。第K次循环前的信息素和最优解为，经过第K次外循环后，
24、得到。由于蚂蚁的一步转移概率是随机的，从 到 也是随机的，是一个马尔可夫过程。,2.1 蚁群优化算法概念,一般蚁群算法的框架和GBAS基本相同，有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式。,2.2 蚁群优化算法研究现状,90年代Dorigo最早提出了蚁群优化算法-蚂蚁系统（Ant System,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程
25、中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。,2.2 蚁群优化算法研究现状,最初提出的AS有三种版本：Ant-density、Ant-quantity和Ant-cycle。Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的
26、启发式算法相比，在不大于75城市的TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，AS的解题能力大幅度下降。,2.2 蚁群优化算法研究现状,改进方法是精英策略(Elitist Strategy)，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为Tgb(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。,2.2 蚁群优化算法研究现状,蚂蚁向下一个
27、目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,2.2蚁群优化算法研究现状,AS中暴露出的问题，提出了蚁群系统(Ant Colony System,ACS)。该系统的提出是以Ant-Q算法为基础的。Ant-Q将蚂蚁算法和一种增强型学习算法Q-learning有机的结合了起来。ACS与AS之间存在三方面的主要差异：首先，ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路
28、径上的信息素。其中，01是信息素挥发参数，是从寻路开始到当前为止全局最优的路径长度。,2.2 蚁群优化算法研究现状,引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选择的概率。,2.2 蚁群优化算法研究现状,在对AS进行直接完善的方法中，MAX-MIN Ant System是一个典型代表。该算法修改了AS的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞，路径上的信息素浓度被限制在MAX，MIN 范围内，另外，信息素的初始值被设为其取
29、值上限，这样有助于增加算法初始阶段的搜索能力。,2.2 蚁群优化算法研究现状,蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,2.2 蚁群优化算法研究现状,对AS的进一步改进的算法是Rank-based Version AS。与“精英策略”相似，在此算法中总是更新更好进程上的信息素，选择的标准是其行程长度 决定的排序，且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定，其中，为每次迭代后放置信息素的蚂蚁总数。,
