智能优化算法学习培训课件.ppt

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

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

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

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

5、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、按照量子力学原理建造新的计算、按照量子力学原理建造新的计算机，机，198

13、5年年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、算法改进有很大的创新空间算法改进有很大的创新空间 只给基本的计算思想和步骤，提高计算性能的细节方只给基本

17、的计算思想和步骤，提高计算性能的细节方面有很大的创新空间。中国发论文，对前人或牛人经面有很大的创新空间。中国发论文，对前人或牛人经典算法的改进，是最多也是最容易的！典算法的改进，是最多也是最容易的！中国只需要改进型创新，不需要真正的原创的创新，中国只需要改进型创新，不需要真正的原创的创新，因为中国杂志的审稿人就是这类型。因为中国杂志的审稿人就是这类型。退火三函数、遗传选择、交叉与变异算子退火三函数、遗传选择、交叉与变异算子需要对待解决的问题有全面的了解，对各智能算法非需要对待解决的问题有全面的了解，对各智能算法非常熟练，我们上这门课的目标是解决后面这个问题。常熟练，我们上这门课的目标是解决后面

18、这个问题。3、不提倡刻意去追求理论成果不提倡刻意去追求理论成果 不是一门严谨的学科，是一门实验学科，最好利用不是一门严谨的学科，是一门实验学科，最好利用matlab去做实验。去做实验。4、算法性能的测算是一项要下真功夫的工作算法性能的测算是一项要下真功夫的工作 算法性能的评价标准是大量不同规划的例题，必须算法性能的评价标准是大量不同规划的例题，必须喜欢编程，喜欢在计算机上工作，后面将介绍组合优喜欢编程，喜欢在计算机上工作，后面将介绍组合优化的常见问题、连续优化的常见问题。化的常见问题、连续优化的常见问题。网上题库中的例题、文献中的例题。优于文献中报网上题库中的例题、文献中的例题。优于文献中报道

19、的性能指标。道的性能指标。5、主要性能指标主要性能指标(1)达优率：多次从不同随机种子出发的计算中，达到达优率：多次从不同随机种子出发的计算中，达到最优解的次数或百分比。最优解的次数或百分比。(2)计算速度：迭代次数计算速度：迭代次数(3)计算大规模问题的能力。计算大规模问题的能力。1、函数优化：对象在一定区间内的连续变量。函数优化：对象在一定区间内的连续变量。2、组合优化：解空间的离散状态，如组合优化：解空间的离散状态，如TSP函数优化的经典问题函数优化的经典问题n元函数元函数f(x1,x2,xn)，x1,x2,xn是实数，其定义域是实数，其定义域S为为Rn上的有界子集，函数值也是实数，函数

20、优化是求函上的有界子集，函数值也是实数，函数优化是求函数数f(x1,x2,xn)在定义域在定义域S中的最小值。中的最小值。算法的性能比较，通常是基于一些称为算法的性能比较，通常是基于一些称为Benchmark(基基准测试准测试)典型问题展开的。典型问题展开的。义域为解空间，即自变量的各种可能取值，记为义域为解空间，即自变量的各种可能取值，记为=s1,s2,sn，C(si)为状态为状态si对应的目标函数值，组对应的目标函数值，组合优化合优化(极小值极小值)是寻求是寻求中，使得目标函数中，使得目标函数C(si)最小最小的状态的状态si*即最优解。即最优解。常表现为排序、分类、筛选等问题，如常表现为

21、排序、分类、筛选等问题，如TSP(traveling salesman problem 旅行商问题，最短距旅行商问题，最短距离的离的Hamilton问题问题)、SP(scheduling problem 加工调度问题加工调度问题 Flow-show、job-shop)、0-1KP(knapsack problem背包问题背包问题)、BPP(bin packing problem)、GCP(graph coloring problem 图着色问题图着色问题)、CP(clustering problem 聚类问题聚类问题)(1)汪定传等汪定传等 智能优化方法智能优化方法 高教社高教社 研材研材 电

22、子版电子版(2)黄友锐黄友锐智能优化算法及其应用智能优化算法及其应用 国防工业出版社国防工业出版社 图书馆有借图书馆有借(3)王凌王凌智能优化算法及其应用智能优化算法及其应用 清华大学出版社清华大学出版社 有电子版有电子版(4)梁艳春梁艳春群智能优化算法理论与应用群智能优化算法理论与应用 网上有买网上有买(5)周明周明遗传算法原理及应用遗传算法原理及应用 国防社国防社 有电子版有电子版(6)史峰等史峰等 matlab智能优化算法智能优化算法30个案例分析个案例分析 北航北航1、用途、用途 (1)遗传算法：随机产生初始种群，用旋转法选择个遗传算法：随机产生初始种群，用旋转法选择个体、选择交叉点，

23、选择变异点。体、选择交叉点，选择变异点。(2)禁忌搜索：随机选择初始解，选择多阶段禁忌搜索禁忌搜索：随机选择初始解，选择多阶段禁忌搜索的初始解。的初始解。(3)模拟退火：随机选择领域解，按概率作转移决定。模拟退火：随机选择领域解，按概率作转移决定。(4)蚊群算法：随机产生初始蚁群。蚊群算法：随机产生初始蚁群。(5)粒子群算法：随机产生初始粒子群，随机选择初始粒子群算法：随机产生初始粒子群，随机选择初始移动方向移动方向2、产生方法、产生方法(1)乘同余法：乘同余法：Sk+1=mod(ASk,m)当位数为当位数为L时，取模时，取模m=2L，S0为奇数，为奇数，A=4t+1(t为正为正整数整数)时，

24、可得到长度为时，可得到长度为2L-2的随机整数。的随机整数。如如L=6时，时，M=64，A=4*3+1=13，S0=1，则，则1,13,mod(13*13,64)，2、产生方法、产生方法(1)乘同余法：乘同余法：Sk+1=mod(ASk,m)当位数为当位数为L时，取模时，取模m=2L，S0为奇数，为奇数，A=4t+1(t为正为正整数整数)时，可得到长度为时，可得到长度为2L-2的随机整数。的随机整数。(2)混合同余法混合同余法Sk+1=mod(ASk+C，m)当当m=2L，S0奇，奇，A=4t+1(同上同上)，mod(C,M)=1，可得到长度为，可得到长度为2L的随机整数。的随机整数。如如L=

25、6时，时，M=64，A=4*3+1=13，S0=1，C=5，则，则1,mod(13*1+5,64)=18,mod(13*18+5,64，)2、产生方法、产生方法(1)乘同余法：乘同余法：Sk+1=mod(ASk,m)(2)混合同余法：混合同余法：Sk+1=mod(ASk+C，m)当当m=2L，S0奇，奇，A=4t+1(同上同上)，mod(C,M)=1，长度为，长度为2L的随机整数。的随机整数。(3)0-1均匀分布：随机数序列均匀分布：随机数序列Sk+1，则，则xk=Sk/M为为0-1之间的随机均匀分布。之间的随机均匀分布。matlab可产生更加复杂的随机数可产生更加复杂的随机数1、概念、概念

26、时间复杂性时间复杂性T(n)，空间复杂性，空间复杂性S(n)，只考虑前者只考虑前者 将求解问题的关键操作，算法执行基本操作的次数将求解问题的关键操作，算法执行基本操作的次数为时间复杂性，若该次数是为时间复杂性，若该次数是n多项式，则称该算法为多多项式，则称该算法为多项式算法，否则为指数算法。项式算法，否则为指数算法。2、P类问题：具有多项时间求解算法的问题类。类问题：具有多项时间求解算法的问题类。2、判定问题：一个问题的每个实例，只有判定问题：一个问题的每个实例，只有“是是”或或“否否”两种回答。两种回答。3、问题问题A可判断：可判断：若存在一个多项式函数若存在一个多项式函数g(x)和一个算法

27、和一个算法H，对对A的任何一个的任何一个“是是”的实例的实例I，都存在一个字符串都存在一个字符串S是是I的的“回答回答”，d(S)g(d(I)，且验，且验证证S是是I的的“是是”回答的计算时间回答的计算时间 g(d(I)，则称，则称A为非多为非多项式确定问题，简称为项式确定问题，简称为NP。显然显然P NP3、A1可多项式转换为可多项式转换为A2 若存在一个多项式函数若存在一个多项式函数g(x)和一个字符串，满足：和一个字符串，满足：(1)对对A1的每个实例的每个实例I1，在其输入长试的多项式时间，在其输入长试的多项式时间g(d(I1)内构造内构造A2的任何一个实例的任何一个实例I2，使其长度

28、不超过，使其长度不超过g(d(I1)；(2)由此构造使得实例由此构造使得实例I1和和I2的解一一对应，的解一一对应，d1是是I1的的“是是”解解d1的对象是的对象是I2的的“是是”解。解。4、A1可多项式归约为可多项式归约为A2 若存在多项式函数若存在多项式函数g1(x)和和g2(x)，使得对使得对A1的任何一的任何一个实例个实例I，在多项式时在多项式时 间内构造间内构造A2的实例，其输入长的实例，其输入长度不超过度不超过g1(d(I1)，并对并对A2的每个算法的每个算法H2，都存在，都存在A1的一个算法的一个算法H1，计算时间计算时间fH1(d(I)g2(fH2(g1(d(I1)。5、若若A

29、2存在多项式算法，则存在多项式算法，则A1肯定存在算法。肯定存在算法。4、A1可多项式归约为可多项式归约为A2 若存在多项式函数若存在多项式函数g1(x)和和g2(x)，使得对使得对A1的任何一的任何一个实例个实例I，在多项式时在多项式时 间内构造间内构造A2的实例，其输入长的实例，其输入长度不超过度不超过g1(d(I1)，并对并对A2的每个算法的每个算法H2，都存在，都存在A1的一个算法的一个算法H1，计算时间计算时间fH1(d(I)g2(fH2(g1(d(I1)。5、若若A2存在多项式算法，则存在多项式算法，则A1肯定存在算法。肯定存在算法。6、若已知的每个若已知的每个NP问题，都可多项式

30、归约为问题，都可多项式归约为A，则称则称问题问题A是是NP难的。难的。7、若问题若问题A是是NP难的，并且难的，并且A也是也是NP问题，则问题，则A是是NP完全的即完全的即NPC P NP NPC NP，但但NP难与难与NP之间包含关系！之间包含关系！TSP，3SAT，团，背包问题是团，背包问题是NPC！若这若这3个问题可个问题可归约到某个新问题归约到某个新问题A，则则A是是NP难，若难，若A是是NP的。的。1、模拟退火算法、模拟退火算法2、混沌动态优化算法混沌动态优化算法3、神经网络算法神经网络算法4、遗传算法遗传算法5、禁忌搜索算法禁忌搜索算法6、免疫算法免疫算法7、蚁群算法蚁群算法8、粒子群算法粒子群算法9、细菌算法细菌算法10、文化基因算法文化基因算法11、量子计算量子计算