智能优化算法.ppt
智能优化算法,绪论-最优化的历史 微积分中函数极值，最早的无约束函数优化。拉格朗日乘子法是最早的约束优化方法。二战时运筹学(Operation Research)，解决受多个约束条件限制时，目标函数值的最大化(最小化).其方法有线性规划(单纯型法)、动态规划、博弈论、排队论、存储论等，这些方法在二次世界大战后，被运用到了经济等诸多领域。,传统最优化的解法 1、选择一个初始解 该解必须是一个可行解。2、判断停止准则是否满足一般为最优性条件。如单纯型方法是最下一行的值均为非负。3、向改进方向移动 由于采用迭代方法，当不满足停止条件时，需要不断修改当前解。,传统最优化的解法的缺陷1、单点运算方式，一个初始解出发，迭代只对一个点进行计算，无法并行计算、多核计算。崽多好打架！无法群狼战略！2、向改进方向移动,限制了跳出局部最优的能力,都使得目标函数降低，即不具备“爬山”能力,没有全局搜索能力.3、停止条件只是局部最优性的条件,只有当解的可行域凸集、目标函数凸函数时才全局最优。4、目标函数、约束函数必须连续可微，甚至还要高阶可微,一些新现象1、目标函数与约束条件不连续，可能离散，可能含有规则、条件和逻辑关系。2、计算的效率优先,如TSP问题，本身是一个NP完全问题，更关注算效率，而非最优解。3、传统方法计算终止可能得到的解,连可行解都不是。但问题要求达到限定迭代次数后就停机，希望此时得到的解是比较优化的解。4、优化计算中的数据可能不精确，初始解可能不是可行解，甚至远离可行解。数据可能是随机变量、模糊集合。,智能优化方法的历史1975年、Holland、Genetic Algorithms(遗传算法)：模仿生物种群中优胜劣汰适者生成机制，通过种群中优势个体的繁殖进化来实现优化。通过选择、交叉、变异来寻优，常用于非线性最优化和复杂的组优化或整数规划问题、管道优化设计(网络流)、通风网络的设计、飞机外形设计、图像处理、VLSI设计。1977年、Glover、Tabu Search(禁忌搜索算法)：将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，这在图论中最短路径的disjktra算法等都用过，从而大大提高寻优过程的搜索效率。,智能优化方法的历史197X年、Jerne、Artificial immune System(人工免疫系统)。通过进化学习辨别危险的外部物体(细菌、病毒等)和体内自身的细胞(或分子)，通过从不同种类的抗体中，构造处理外部物体的方法或物质。具有并行、分布、自适应性、学习、识别、记忆和特征提取能力。用于模式识别、信息安全、智能优化、机器学习、数据挖掘、自动控制、故障诊断等领域。1999年、Hunt、Clone(克隆选择算法)，只有识别抗原的细胞的能进行clone扩增，同时克隆产生的细胞又高频变异，满足生物的多样性要求，使之具有爬山的能力，全局搜索呀！。,智能优化方法的历史1983年、Kirkpatrick、Simulated Annealing(模拟退火算法)。热力学中退火使金属原子达到能量最低状态的机制，按Boltzmann方程计算状态向量间的转移概率，来引导搜索，从而使算法具有很好的全局搜索能力。199X年、Dorigo、Ant Colony Optimization(蚁群算法)，模拟蚂蚁群体利用信息素来实现路径优化的机理，通过忘记路径将信息素的变化来解决离散数据的最优化(函数是离散的，约束条件也是离散的，称为组合优化问题，如TSP、0-1背包问题、生产调度问题等)。,智能优化方法的历史1995年、Kenedy、Eberhart、Particle Swarm Optimization(粒子群优化)，模拟鸟群、渔群集体觅食迁徙中，个体与群体协调一致的机理，群过群体最优化方向、个体最优方法和惯性方向协调来实现最优化。1999年、Linhares、Predatory Search(捕食搜索)，模拟猛兽捕食中大范围搜索(大步确定大体范围)和局部蹲守(小碎步寻优)的特点，通过设置全避搜索和局部搜索间变换的阈值，来协调两种不同的搜索方式，从而实现对全局搜索与局部搜索的兼顾。,智能优化方法的历史2000年、Passino、Bacteria Foraging(细菌觅食算法)。模拟大肠杆菌的觅食过程。(1)寻找可能存在食物源的区域；(2)决定是否进入此区域；(3)在所选定的区域中寻找食物源；(4)消耗掉一定的量的食物后，决定是否继续在此区域寻找食物或迁移到另一个更理想的区域。电网电力预测、电压控制、多Agent系统和车间调度。1989年、Moscato、Memetic(文化算法)，meme(文化基因)表示存在于人脑中可以传递给他人的信息模式，是人们进行文化或思想交流时传播的信息单元。Memetic是指模拟meme的复制、传播和进化的理论，是局部启发式搜索与交叉算子的结合体，适合于多指令的并行计算和分布计算系统(parallel genetic algorithms)，也是我比较感兴趣的问题，研究人脑本身的机制用于电脑。,智能优化方法的历史1982年、Feynman、按照量子力学原理建造新的计算机，1985年oxford的Deutsh利用量子态的相干叠加性可实现并行的量子计算，1995年Grover提出了Grover算法，可用于解决TSP问题，但现在仍有相当的难度。1982年、Hopfiled在前人的基础上，在前人青工式神经元模型(MP)、多层感知机、自适应线性单元模型及自适应理论ART，引入能量函数的概念，研究网络的动力学特性，并用电子线路设计出相应的网络，使得BP可用于联想记忆和优化计算，后人在此基础上提出了PDP理论、多层向前网络的BP算法，成为比较好的学习算法，用于控制工程、机器学习、信号处理、模式识别和经济领域。但最近几年好像又不热了。,智能优化方法的历史1972年、E.N.洛伦兹(MIT)、chaos(混沌)，原意是混乱、无序，在现代非线性理论中，混沌是泛指在确定体系中出现的貌似无规则的、类随机的运动。(1)随机性：类似随机变量的杂乱表现；(2)遍历性。不重复地历经一定范围内的所有状态；(3)规律性：混沌是由确定性的迭代式产生。介于确定性和随机性之间，混沌具有丰富的时空动态，系统的演变可导致吸引子的转移，遍历性可作为搜索过程中避免陷入局部极小化的陷阱，可爬山。相空间、混沌运动、分形和分维、不动点、吸引子、奇异吸引子、分叉和分叉点、周期解、初值敏感性。,学习智能优化方法的策略1、要解决实际问题。尽管智能优化算法，对各类复杂的优化总是有很强的适应性，当解决你在研究中遇到的具体问题时，可能有一定的难度，因为同一个问题可能多种智能优化方法，需要一定的智慧。2、算法改进有很大的创新空间 只给基本的计算思想和步骤，提高计算性能的细节方面有很大的创新空间。中国发论文，对前人或牛人经典算法的改进，是最多也是最容易的！中国只需要改进型创新，不需要真正的原创的创新，因为中国杂志的审稿人就是这类型。退火三函数、遗传选择、交叉与变异算子需要对待解决的问题有全面的了解，对各智能算法非常熟练，我们上这门课的目标是解决后面这个问题。,学习智能优化方法的策略3、不提倡刻意去追求理论成果 不是一门严谨的学科，是一门实验学科，最好利用matlab去做实验。4、算法性能的测算是一项要下真功夫的工作 算法性能的评价标准是大量不同规划的例题，必须喜欢编程，喜欢在计算机上工作，后面将介绍组合优化的常见问题、连续优化的常见问题。网上题库中的例题、文献中的例题。优于文献中报道的性能指标。5、主要性能指标(1)达优率：多次从不同随机种子出发的计算中，达到最优解的次数或百分比。(2)计算速度：迭代次数(3)计算大规模问题的能力。,智能优化方法的分类1、函数优化：对象在一定区间内的连续变量。2、组合优化：解空间的离散状态，如TSP函数优化的经典问题n元函数f(x1,x2,xn)，x1,x2,xn是实数，其定义域S为Rn上的有界子集，函数值也是实数，函数优化是求函数f(x1,x2,xn)在定义域S中的最小值。算法的性能比较，通常是基于一些称为Benchmark(基准测试)典型问题展开的。,组合优化问题义域为解空间，即自变量的各种可能取值，记为=s1,s2,sn，C(si)为状态si对应的目标函数值，组合优化(极小值)是寻求中，使得目标函数C(si)最小的状态si*即最优解。常表现为排序、分类、筛选等问题，如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)汪定传等 智能优化方法 高教社 研材 电子版(2)黄友锐智能优化算法及其应用 国防工业出版社 图书馆有借(3)王凌智能优化算法及其应用 清华大学出版社 有电子版(4)梁艳春群智能优化算法理论与应用 网上有买(5)周明遗传算法原理及应用 国防社 有电子版(6)史峰等 matlab智能优化算法30个案例分析 北航,伪随机数Pseudo Random Number Generator(RNG)1、用途(1)遗传算法：随机产生初始种群，用旋转法选择个体、选择交叉点，选择变异点。(2)禁忌搜索：随机选择初始解，选择多阶段禁忌搜索的初始解。(3)模拟退火：随机选择领域解，按概率作转移决定。(4)蚊群算法：随机产生初始蚁群。(5)粒子群算法：随机产生初始粒子群，随机选择初始移动方向,伪随机数Pseudo Random Number Generator(RNG)2、产生方法(1)乘同余法：Sk+1=mod(ASk,m)当位数为L时，取模m=2L，S0为奇数，A=4t+1(t为正整数)时，可得到长度为2L-2的随机整数。如L=6时，M=64，A=4*3+1=13，S0=1，则1,13,mod(13*13,64)，,伪随机数Pseudo Random Number Generator(RNG)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=6时，M=64，A=4*3+1=13，S0=1，C=5，则1,mod(13*1+5,64)=18,mod(13*18+5,64，),伪随机数Pseudo Random Number Generator(RNG)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、概念 时间复杂性T(n)，空间复杂性S(n)，只考虑前者 将求解问题的关键操作，算法执行基本操作的次数为时间复杂性，若该次数是n多项式，则称该算法为多项式算法，否则为指数算法。2、P类问题：具有多项时间求解算法的问题类。2、判定问题：一个问题的每个实例，只有“是”或“否”两种回答。3、问题A可判断：若存在一个多项式函数g(x)和一个算法H，对A的任何一个“是”的实例I，都存在一个字符串S是I的“回答”，d(S)g(d(I)，且验证S是I的“是”回答的计算时间g(d(I)，则称A为非多项式确定问题，简称为NP。显然PNP,计算复杂性3、A1可多项式转换为A2 若存在一个多项式函数g(x)和一个字符串，满足：(1)对A1的每个实例I1，在其输入长试的多项式时间g(d(I1)内构造A2的任何一个实例I2，使其长度不超过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、若A2存在多项式算法，则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问题，都可多项式归约为A，则称问题A是NP难的。7、若问题A是NP难的，并且A也是NP问题，则A是NP完全的即NPC PNP NPCNP，但NP难与NP之间包含关系！TSP，3SAT，团，背包问题是NPC！若这3个问题可归约到某个新问题A，则A是NP难，若A是NP的。,拟讲内容1、模拟退火算法2、混沌动态优化算法3、神经网络算法4、遗传算法5、禁忌搜索算法6、免疫算法7、蚁群算法8、粒子群算法9、细菌算法10、文化基因算法11、量子计算,
