智能优化算法.ppt

《智能优化算法.ppt》由会员分享，可在线阅读，更多相关《智能优化算法.ppt（31页珍藏版）》请在优知文库上搜索。

1、智能优化算法智能优化算法 微积分中函数极值，最早的无约束函数优化。微积分中函数极值，最早的无约束函数优化。 拉格朗日乘子法是最早的约束优化方法。拉格朗日乘子法是最早的约束优化方法。 二战时运筹学二战时运筹学(Operation Research)，解决受，解决受多个约束条件限制时，目标函数值的最大化多个约束条件限制时，目标函数值的最大化(最最小化小化). 其方法有线性规划其方法有线性规划(单纯型法单纯型法)、动态规划、动态规划、博弈论、排队论、存储论等，博弈论、排队论、存储论等， 这些方法在二次世界大战后，被运用到了经这些方法在二次世界大战后，被运用到了经济等诸多领域。济等诸多领域。 1、选择

2、一个初始解、选择一个初始解 该解必须是一个可行解。该解必须是一个可行解。2、判断停止准则是否满足、判断停止准则是否满足一般为最优性条件。如单纯型方法是最下一行一般为最优性条件。如单纯型方法是最下一行的值均为非负。的值均为非负。 3、向改进方向移动、向改进方向移动 由于采用迭代方法，当不满足停止条件时，由于采用迭代方法，当不满足停止条件时，需要不断修改当前解。需要不断修改当前解。1、单点运算方式，一个初始解出发，迭代只、单点运算方式，一个初始解出发，迭代只对一个点进行计算，无法并行计算、多核计算。对一个点进行计算，无法并行计算、多核计算。崽多好打架！无法群狼战略！崽多好打架！无法群狼战略！2、向

3、改进方向移动、向改进方向移动,限制了跳出局部最优的能限制了跳出局部最优的能力力,都使得目标函数降低，即不具备都使得目标函数降低，即不具备“爬山爬山”能能力力,没有全局搜索能力没有全局搜索能力.3、停止条件只是局部最优性的条件、停止条件只是局部最优性的条件, 只有当解只有当解的可行域凸集、目标函数凸函数时才全局最优。的可行域凸集、目标函数凸函数时才全局最优。4、目标函数、约束函数必须连续可微，甚至、目标函数、约束函数必须连续可微，甚至还要高阶可微还要高阶可微1、目标函数与约束条件不连续，可能离散，、目标函数与约束条件不连续，可能离散，可能含有规则、条件和逻辑关系。可能含有规则、条件和逻辑关系。2

4、、计算的效率优先、计算的效率优先, 如如TSP问题，本身是一个问题，本身是一个NP完全问题，更关注算效率，而非最优解。完全问题，更关注算效率，而非最优解。3、传统方法计算终止可能得到的解、传统方法计算终止可能得到的解,连可行解连可行解都不是。但问题要求达到限定迭代次数后就停都不是。但问题要求达到限定迭代次数后就停机，希望此时得到的解是比较优化的解。机，希望此时得到的解是比较优化的解。4、优化计算中的数据可能不精确，初始解可、优化计算中的数据可能不精确，初始解可能不是可行解，甚至远离可行解。数据可能是能不是可行解，甚至远离可行解。数据可能是随机变量、模糊集合。随机变量、模糊集合。1975年、年、

5、Holland、Genetic Algorithms(遗传算遗传算法法)：模仿生物种群中优胜劣汰适者生成机制，：模仿生物种群中优胜劣汰适者生成机制，通过种群中优势个体的繁殖进化来实现优化。通过种群中优势个体的繁殖进化来实现优化。通过选择、交叉、变异来寻优，常用于非线性通过选择、交叉、变异来寻优，常用于非线性最优化和复杂的组优化或整数规划问题、管道最优化和复杂的组优化或整数规划问题、管道优化设计优化设计(网络流网络流)、通风网络的设计、飞机外形、通风网络的设计、飞机外形设计、图像处理、设计、图像处理、VLSI设计。设计。1977年、年、Glover、Tabu Search(禁忌搜索算法禁忌搜索算

6、法)：将记忆功能引入到最优解的搜索过程中，通过将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，这在图论设置禁忌区阻止搜索过程中的重复，这在图论中最短路径的中最短路径的disjktra算法等都用过，从而大大算法等都用过，从而大大提高寻优过程的搜索效率。提高寻优过程的搜索效率。197X年、年、Jerne、Artificial immune System(人人工免疫系统工免疫系统)。通过进化学习辨别危险的外部物。通过进化学习辨别危险的外部物体体(细菌、病毒等细菌、病毒等)和体内自身的细胞和体内自身的细胞(或分子或分子)，通过从不同种类的抗体中，构造处理外部物体通过从不同种类的

7、抗体中，构造处理外部物体的方法或物质。具有并行、分布、自适应性、的方法或物质。具有并行、分布、自适应性、学习、识别、记忆和特征提取能力。学习、识别、记忆和特征提取能力。 用于模式识别、信息安全、智能优化、机器用于模式识别、信息安全、智能优化、机器学习、数据挖掘、自动控制、故障诊断等领域。学习、数据挖掘、自动控制、故障诊断等领域。1999年、年、Hunt、Clone(克隆选择算法克隆选择算法)，只有识，只有识别抗原的细胞的能进行别抗原的细胞的能进行clone扩增，同时克隆产扩增，同时克隆产生的细胞又高频变异，满足生物的多样性要求，生的细胞又高频变异，满足生物的多样性要求，使之具有爬山的能力，全局

8、搜索呀！。使之具有爬山的能力，全局搜索呀！。1983年、年、Kirkpatrick、Simulated Annealing(模模拟退火算法拟退火算法)。热力学中退火使金属原子达到能。热力学中退火使金属原子达到能量最低状态的机制，按量最低状态的机制，按Boltzmann方程计算状态方程计算状态向量间的转移概率，来引导搜索，从而使算法向量间的转移概率，来引导搜索，从而使算法具有很好的全局搜索能力。具有很好的全局搜索能力。199X年、年、Dorigo、Ant Colony Optimization(蚁蚁群算法群算法)，模拟蚂蚁群体利用信息素来实现路径，模拟蚂蚁群体利用信息素来实现路径优化的机理，通过

9、忘记路径将信息素的变化来优化的机理，通过忘记路径将信息素的变化来解决离散数据的最优化解决离散数据的最优化(函数是离散的，约束条函数是离散的，约束条件也是离散的，称为组合优化问题，如件也是离散的，称为组合优化问题，如TSP、0-1背包问题、生产调度问题等背包问题、生产调度问题等)。1995年、年、Kenedy、Eberhart、Particle Swarm Optimization(粒子群优化粒子群优化)，模拟鸟群、渔群集，模拟鸟群、渔群集体觅食迁徙中，个体与群体协调一致的机理，体觅食迁徙中，个体与群体协调一致的机理，群过群体最优化方向、个体最优方法和惯性方群过群体最优化方向、个体最优方法和惯性

10、方向协调来实现最优化。向协调来实现最优化。1999年、年、Linhares、Predatory Search(捕食搜捕食搜索索)，模拟猛兽捕食中大范围搜索，模拟猛兽捕食中大范围搜索(大步确定大体大步确定大体范围范围)和局部蹲守和局部蹲守(小碎步寻优小碎步寻优)的特点，通过设的特点，通过设置全避搜索和局部搜索间变换的阈值，来协调置全避搜索和局部搜索间变换的阈值，来协调两种不同的搜索方式，从而实现对全局搜索与两种不同的搜索方式，从而实现对全局搜索与局部搜索的兼顾。局部搜索的兼顾。2000年、年、Passino、Bacteria Foraging (细菌觅食算法细菌觅食算法)。模拟大肠杆菌的觅食过程

11、。模拟大肠杆菌的觅食过程。(1)寻找可能存在食物源的寻找可能存在食物源的区域；区域；(2)决定是否进入此区域；决定是否进入此区域；(3)在所选定的区域中在所选定的区域中寻找食物源；寻找食物源；(4)消耗掉一定的量的食物后，决定是否消耗掉一定的量的食物后，决定是否继续在此区域寻找食物或迁移到另一个更理想的区域。继续在此区域寻找食物或迁移到另一个更理想的区域。电网电力预测、电压控制、多电网电力预测、电压控制、多Agent系统和车间调度。系统和车间调度。1989年、年、Moscato、Memetic(文化算法文化算法)，meme(文化文化基因基因)表示存在于人脑中可以传递给他人的信息模式，表示存在于

12、人脑中可以传递给他人的信息模式，是人们进行文化或思想交流时传播的信息单元。是人们进行文化或思想交流时传播的信息单元。Memetic是指模拟是指模拟meme的复制、传播和进化的理论，的复制、传播和进化的理论，是局部启发式搜索与交叉算子的结合体，适合于多指是局部启发式搜索与交叉算子的结合体，适合于多指令的并行计算和分布计算系统令的并行计算和分布计算系统(parallel genetic algorithms)，也是我比较感兴趣的问题，研究人脑本，也是我比较感兴趣的问题，研究人脑本身的机制用于电脑。身的机制用于电脑。1982年、年、Feynman、按照量子力学原理建造新的计算、按照量子力学原理建造新

13、的计算机，机，1985年年oxford的的Deutsh利用量子态的相干叠加性利用量子态的相干叠加性可实现并行的量子计算，可实现并行的量子计算，1995年年Grover提出了提出了Grover算法，可用于解决算法，可用于解决TSP问题，但现在仍有相当的难度。问题，但现在仍有相当的难度。1982年、年、Hopfiled在前人的基础上，在前人青工式神在前人的基础上，在前人青工式神经元模型经元模型(MP)、多层感知机、自适应线性单元模型及、多层感知机、自适应线性单元模型及自适应理论自适应理论ART，引入能量函数的概念，研究网络的，引入能量函数的概念，研究网络的动力学特性，并用电子线路设计出相应的网络，

14、使得动力学特性，并用电子线路设计出相应的网络，使得BP可用于联想记忆和优化计算，后人在此基础上提出可用于联想记忆和优化计算，后人在此基础上提出了了PDP理论、多层向前网络的理论、多层向前网络的BP算法，成为比较好的算法，成为比较好的学习算法，用于控制工程、机器学习、信号处理、模学习算法，用于控制工程、机器学习、信号处理、模式识别和经济领域。但最近几年好像又不热了。式识别和经济领域。但最近几年好像又不热了。1972年、年、E.N.洛伦兹洛伦兹(MIT)、chaos(混沌混沌)，原意是混乱、，原意是混乱、无序，在现代非线性理论中，混沌是泛指在确定体系无序，在现代非线性理论中，混沌是泛指在确定体系中

15、出现的貌似无规则的、类随机的运动。中出现的貌似无规则的、类随机的运动。(1)随机性：类似随机变量的杂乱表现；随机性：类似随机变量的杂乱表现；(2)遍历性。不重复地历经一定范围内的所有状态；遍历性。不重复地历经一定范围内的所有状态；(3)规律性：混沌是由确定性的迭代式产生。规律性：混沌是由确定性的迭代式产生。介于确定性和随机性之间，混沌具有丰富的时空动态，介于确定性和随机性之间，混沌具有丰富的时空动态，系统的演变可导致吸引子的转移，遍历性可作为搜索系统的演变可导致吸引子的转移，遍历性可作为搜索过程中避免陷入局部极小化的陷阱，可爬山。过程中避免陷入局部极小化的陷阱，可爬山。相空间、混沌运动、分形和

16、分维、不动点、吸引子、相空间、混沌运动、分形和分维、不动点、吸引子、奇异吸引子、分叉和分叉点、周期解、初值敏感性。奇异吸引子、分叉和分叉点、周期解、初值敏感性。1、要解决实际问题。要解决实际问题。 尽管智能优化算法，对各类复杂的优化总是有很强尽管智能优化算法，对各类复杂的优化总是有很强的适应性，当解决你在研究中遇到的具体问题时，可的适应性，当解决你在研究中遇到的具体问题时，可能有一定的难度，因为同一个问题可能多种智能优化能有一定的难度，因为同一个问题可能多种智能优化方法，需要一定的智慧。方法，需要一定的智慧。2、算法改进有很大的创新空间算法改进有很大的创新空间 只给基本的计算思想和步骤，提高计算性能的细节方只给基本的计算思想和步骤，提高计算性能的细节方面有很大的创新空间。中国发论文，对前人或牛人经面有很大的创新空间。中国发论文，对前人或牛人经典算法的改进，是最多也是最容易的！典算法的改进，是最多也是最容易的！中国只需要改进型创新，不需要真正的原创的创新，中国只需要改进型创新，不需要真正的原创的创新，因为中国杂志的审稿人就是这类型。因为中国杂志的审稿人就是这类型。退火三函数、遗传选择、交