第六章 现代最优化方法.pptx

1、研究生课程工程数学之“最优化方法”现 代 最 优 化 方 法College of Energy and Power Engineering 1 现代优化算法包括随机试验法、禁忌搜索算法、模拟退火算法、遗传算法、神经网络算法和拉格朗日松弛算法等，这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念。都是以一定的直观基础而构造的算法，通常称之为启发式算法。 启发式算法的兴起与计算复杂性理论的形成有密切的联系。 1. 对目标函数和约束函数不必附加可解析性条件，对于目标函数而言甚至可以不要求有显示表达式； 2. 对于约束变量可以去离散值或特殊整数如0和1等； 3. 在通常情况下，这

2、些算法能够求解全局最优解。2第一节 随 机 试 验 法 一、基本思想 用随机的方法产生试验点，再从试验点中选出满足约束条件的点，进而求出最优点的一种方法。二、 随机试验法 成立的最优解x*设问题首先用随机方法产生试验点 ，然后从中找出满足约束条件的点 ,求出使得3一、基本思想 禁忌搜索法(Tabu search)是一种人工智能方法，是局部邻域搜索算法的推广，是人工智能在组合优化中的一个成功应用。 其基本思想是：标记已经得到的局部最优解，并在进一步的迭代中避开这些局部最优解。所谓的禁忌就是禁止重复前面的工作，为了避开局部邻域搜索陷入局部最优，禁忌搜索算法设计了一种禁忌表，记录已达到过的局部最优点

3、。在下一次的搜索中，就利用禁忌表中的信息，不再或者有选择地搜索这些点，以此跳出局部最优点。第二节 禁 忌 搜 索 法 41. 算法的提出 模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。2. 算法的目的 解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。一、物理退火过程第三节 模 拟 退 火 算 法 53.物理退火过程 什么是退火? 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。 第三节 模 拟 退 火 算 法 6物理退火过程 加温

4、过程增强粒子的热运动，消除系统原先可能存在的非均匀态； 等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态； 冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。第三节 模 拟 退 火 算 法 74. 数学表述 在温度T，分子停留在状态r满足Boltzmann概率分布第三节 模 拟 退 火 算 法 8在同一个温度T，选定两个能量E1E2， 在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。0第三节 模 拟 退 火 算 法 9 若|D|为状态空间D中状态的个数，D0是具有最

5、低能量的状态集合： 当温度很高时，每个状态概率基本相同，接近平均值1/|D|； 状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D| ； 当温度趋于0时，分子停留在最低能量状态的概率趋于1。能量最低状态 非能量最低状态第三节 模 拟 退 火 算 法 10Metropolis准则(1953)以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法(计算机随机模拟方法)加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。第三节 模 拟 退 火 算 法 若在温度T，当前状态i 新状态j 若Ej=randrom0,1 s=sj;

6、Until 抽样稳定准则满足； 退温tk+1=update(tk)并令k=k+1； Until 算法终止准则满足； 输出算法搜索结果。第三节 模 拟 退 火 算 法 147. 影响优化结果的主要因素分析 给定初温t=t0，随机产生初始状态s=s0，令k=0； Repeat Repeat 产生新状态sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽样稳定准则满足； 退温tk+1=update(tk)并令k=k+1； Until 算法终止准则满足； 输出算法搜索结果。函数1函数2函数3准则1准则2初始温度第三节 模 拟

7、 退 火 算 法 15二、 模拟退火算法的马氏链描述 1.马氏链定义 第三节 模 拟 退 火 算 法 16 一步转移概率： n步转移概率： 若解空间有限，称马尔可夫链为有限状态； 若 ，称马尔可夫链为时齐的。第三节 模 拟 退 火 算 法 17模拟退火算法对应了一个马尔可夫链 模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。 若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法； 若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。第三节 模 拟 退 火 算 法 18二、模拟退火算法关键参数和操作的设计1. 状态产生函

8、数原则 产生的候选解应遍布全部解空间方法 在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生第三节 模 拟 退 火 算 法 192. 状态接受函数原则 (1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率； (2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。方法具体形式对算法影响不大， 一般采用min1,exp(-C/t)第三节 模 拟 退 火 算 法 203. 初温收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数； 初温应充分大；实验表明 初温越

9、大，获得高质量解的机率越大，但花费较多的计算时间；第三节 模 拟 退 火 算 法 21方法 (1) 均匀抽样一组状态，以各状态目标值得方差为初温； (2) 随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温； (3) 利用经验公式。第三节 模 拟 退 火 算 法 224 温度更新函数时齐算法的温度下降函数 (1) ，越接近1温度下降越慢，且其大小可以不断变化； (2) ，其中t0为起始温度，K为算法温度下降的总次数。第三节 模 拟 退 火 算 法 23非时齐模拟退火算法 每个温度下只产生一个或少量候选解时齐算法常用的Metropolis抽样稳定准则 （1）检验目标

10、函数的均值是否稳定； （2）连续若干步的目标值变化较小； （3）按一定的步数抽样。5 内循环终止准则第三节 模 拟 退 火 算 法 24常用方法 （1）设置终止温度的阈值； （2）设置外循环迭代次数； （3）算法搜索到的最优值连续若干步保持不变； （4）概率分析方法。6 外循环终止准则第三节 模 拟 退 火 算 法 25模拟退火算法的优点 质量高； 初值鲁棒性强； 简单、通用、易实现。模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。 三、 模拟退火算法的优缺点第三节 模 拟 退 火 算 法 26换热器模型 两级管壳式换热

11、器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰(谷)的，具有很多局部最优解。 四、模拟退火算法的应用第三节 模 拟 退 火 算 法 27优化目标 以换热器系统的总费用年值最小作为优化设计的目标。 其中，f1 (X)是两级换热器的初始投资， f2 (X)是两级换热器年维护费(包括除垢、保养、维修等)， f3 (X)是冷却水资源费以及管程压降能耗费， f4 (X)是壳程压降能耗费。第三节 模 拟 退 火 算 法 28优化目标 经过分析，优化问题的独立变量共12个，分别是一级换热器工质出口温度t2、冷却水流量G1、两个换热器的管内径d1，d2和管间距S1，S2、折流板间距B1，B2、折

12、流板开口角1，2、单管长度L1，L2。第三节 模 拟 退 火 算 法 29应用模拟退火算法解决优化设计 状态表示12个变量的实数表示； 初始温度100； 结束温度0.001； 状态产生函数 ，为扰动幅度参数，为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。 降温因子0.98； 马氏链长度1200。第三节 模 拟 退 火 算 法 30优化结果 优化目标值 0.25565E06 独立变量取值t2G1Kg/sd1mmS1mmB1m1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2m2弧度L2m5.9423416.779352

13、7.740120.729532.199285.78314第三节 模 拟 退 火 算 法 31一、遗传算法简介第四节 遗 传 算 法 早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I. Rechenberg和H. P. Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代， L. J. Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了基于模拟进化的人工智能，系统阐述了进化规划的思想。 3260年代中期，美国Michigan大学的J. H. Holland教授提出借鉴生物自然遗传的基本原理

14、用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J. D. Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词；1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生。第四节 遗 传 算 法 3370年代初，Holland提出了“模式定理”（Schema Theorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，Internati

15、onal Society of Genetic Algorithms)；1989年，Holland的学生D. J. Goldherg出版了“Genetic Algorithms in Search, Optimization, and Machine Learning”，对遗传算法及其应用作了全面而系统的论述；1991年，L. Davis编辑出版了遗传算法手册，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。第四节 遗 传 算 法 34二、几个名词概念 1. 进化计算：由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。直到90年代

16、，才有所交流。他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为“进化计算” ( Evolutionary Computation ) 。第四节 遗 传 算 法 352. 计算智能：计算智能主要包括神经计算、进化计算和模糊计算等。它们分别从不同的角度模拟人类的智能活动，以使计算机具有智能。 通常将基于符号处理的传统人工智能称为符号智能，以区别于正在兴起的计算智能。符号智能的特点是以知识为基础，偏重于逻辑推理，而计算智能则是以数据为基础，偏重于数值计算。第四节 遗 传 算 法 36三、达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变

17、异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。第四节 遗 传 算 法 37自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。本质并行性 内在并行性与内含并行性不需求导 只需目标函数和适应度函数概率转换规则 强调概率转换规则，而不是确定的转换规则四、 遗传算法的思路与特点 第四节 遗 传 算 法 381. 适应度计算：按比例的适应度函数（proportional fitness a

18、ssignment）基于排序的适应度计算（Rank-based fitness assignment）2.选择算法：轮盘赌选择（roulette wheel selection）随机遍历抽样（stochastic universal selection）局部选择（local selection）截断选择（truncation selection）锦标赛选择（tournament selection）五、 遗传算法的基本操作 第四节 遗 传 算 法 393. 交叉或基因重组实值重组（real valued recombination）：离散重组（discrete recombination）中间

19、重组（intermediate recombination）线性重组（linear recombination）扩展线性重组（extended linear recombination）二进制交叉（binary valued crossover）：单点交叉（single-point crossover）多点交叉（multiple-point crossover）均匀交叉（uniform crossover）洗牌交叉（shuffle crossover）缩小代理交叉（crossover with reduced surrogate）第四节 遗 传 算 法 404. 变异 实值变异 二进制变异第四

20、节 遗 传 算 法 415.简单实例Step1. 产生初始种群Step2. 计算适应度0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）第四节 遗 传 算 法 42Step3. 选择个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100

21、1011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174第四节 遗 传 算 法 43个体染色体适应度选择概率累积概率100011000008201011110015300000001012410011101001051010101010761110010110127100101101158110000000119

22、9100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第四节 遗 传 算 法 44在01之间产生一个随机数：个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101

23、101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘

24、汰！第四节 遗 传 算 法 450001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011Step4. 交叉0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100110000100111010000011001110100110

25、0000001010011第四节 遗 传 算 法 46Step5. 变异0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001111010000001011011110011000010010101000001100111010011000000010100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 11000000

26、01 1001110100 0001010011000111101000000101101111001100001001110100000110011101001100000001010011第四节 遗 传 算 法 47Step6. 至下一代，适应度计算选择交叉变异，直至满足终止条件。第四节 遗 传 算 法 48函数优化 是遗传算法的经典应用领域;组合优化 实践证明，遗传算法对于组合优化中的NP完全问题非常有效;自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;六、 遗传算法的应用领域 第四节 遗 传 算 法 49机器

27、人智能控制 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别 目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用;人工生命 基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；遗传程序设计 Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;第四节 遗 传 算 法 50一、发展简介第五节 神经网络优化算法 “神经网络”与“人工神经网络”1943年，

28、Warren McCulloch和Walter Pitts建立了第一个人工神经网络模型；1969年，Minsky和Papert发表Perceptrons；20世纪80年代，Hopfield将人工神经网络成功应用在组合优化问题。511. McCulloch-Pitts神经元 现代的神经网络开始于McCulloch, Pitts(1943)的先驱工作； 他们的神经元模型假定遵循有-无模型律； 如果如此简单的神经元数目足够多和适当设置连接权值并且同步操作, McCulloch & Pitts证明这样构成的网络原则上可以计算任何可计算函数； 标志着神经网络和人工智能的诞生。二、基本概念第五节 神经网络

29、优化算法 52McCulloch-Pitts神经元结构 McCulloch-Pitts输出函数定义为：InputsignalSynapticweightsSummingfunctionActivationfunctionOutputyx1x2xnw2wnw1-第五节 神经网络优化算法 532. 网络的构建 Y=F(X) x1y1输出层隐藏层输入层x2y2ymxn第五节 神经网络优化算法 543. 网络结构的确定网络的拓扑结构 前向型、反馈型等神经元激活函数 阶跃函数 线性函数 Sigmoid函数f(x)x0+1第五节 神经网络优化算法 55确定的内容 权值wi和确定的方式 学习（训练） 有指导

30、的学习：已知一组正确的输入输出结果的条件下，神经网络依据这些数据，调整并确定权值； 无指导的学习：只有输入数据，没有正确的输出结果情况下，确定权值。 4. 关联权值的确定第五节 神经网络优化算法 56学习与工作的关系 先学习再工作5. 工作阶段第五节 神经网络优化算法 57多层 两层以上前向 无反馈1. 一般结构三 、 多层前向神经网络x1y1输出层隐藏层输入层x2y2ymxn第五节 神经网络优化算法 58目的 确定权值方法 反向推导2 反向传播算法第五节 神经网络优化算法 59一般结构 各神经元之间存在相互联系分类 连续系统：激活函数为连续函数 离散系统：激活函数为阶跃函数四 、反馈型神经网

31、络第五节 神经网络优化算法 60Hopfield神经网络 1982年提出Hopfield反馈神经网络（HNN），证明在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。 是典型的全连接网络，通过引入能量函数，使网络的平衡态与能量函数极小值解相对应。第五节 神经网络优化算法 61网络结构 N为网络节点总数。1. 离散Hopfield神经网络s1(t+1)s2(t+1)sn(t+1)s1(t)s2(t)sn(t)w12w1nw21w2nwn1wn2第五节 神经网络优化算法 62 一般认为vj(t)=0时神经元保持不变sj(t+1)=sj(t); 一般情况下网络是对称的（wij=wji）且无

32、自反馈（wjj=0）; 整个网络的状态可用向量s表示：第五节 神经网络优化算法 63工作方式 串行（异步，asynchronous）:任一时刻只有一个单元改变状态，其余单元保持不变； 并行（同步，synchronous）：某一时刻所有神经元同时改变状态。稳定状态 如果从t=0的任一初始态s(0)开始变化，存在某一有限时刻t，从此以后网络状态不再变化，即s(t+1)=s(t)，则称网络达到稳定状态。第五节 神经网络优化算法 64能量函数的定义 异步方式： 同步方式：第五节 神经网络优化算法 65能量函数 能量是有界的： 从任一初始状态开始，若在每次迭代时都满足E0，则网络的能量将越来越小，最后趋

33、向于稳定状态E0 。第五节 神经网络优化算法 66网络结构 与电子线路对应： 放大器神经元 电阻、电容神经元的时间常数 电导（电阻的倒数）权系数 2. 连续Hopfield神经网络第五节 神经网络优化算法 67网络的微分方程能量函数 可证明，若g-1为单调增且连续，Cj0，Tji=Tij，则有dE/dt0，当且仅当dvi/dt=0时dE/dt=0。第五节 神经网络优化算法 68能量函数 将动力系统方程 简单记为： 如果 ，则称ve是动力系统的平衡点，也称ve为吸引子。 随着时间的增长，神经网络在状态空间中的解轨迹总是向能量函数减小的方向变化，且网络的稳定点就是能量函数的极小点。第五节 神经网络

34、优化算法 69能量函数 当从某一初始状态变化时，网络的演变是使E下降，达到某一局部极小时就停止变化。这些能量的局部极小点就是网络的稳定点或称吸引子。第五节 神经网络优化算法 70Hopfield网络设计 当Hopfield用于优化计算时，网络的权值是确定的，应将目标函数与能量函数相对应，通过网络的运行使能量函数不断下降并最终达到最小，从而得到问题对应的极小解。3. Hopfield神经网络在TSP 中的应用(Travelling Salesman Problem)第五节 神经网络优化算法 71Hopfield网络设计 通常需要以下几方面的工作： （1）选择合适的问题表示方法，使神经网络的输出与问题的解相对应； （2）构造合适的能量函数，使其最小