[工学]第六章 现代最优化方法.ppt

研究生课程工程数学之“最优化方法” 现 代 最 优 化 方 法 能源与动力工程学院 College of Energy and Power Engineering 现代优化算法包括随机试验法、禁忌搜索算法、模拟退火算 法、遗传算法、神经网络算法和拉格朗日松弛算法等，这些算法涉 及生物进化、人工智能、数学和物理科学、神经系统和统计力学等 概念。都是以一定的直观基础而构造的算法，通常称之为启发式算 法。 启发式算法的兴起与计算复杂性理论的形成有密切的联系。 1. 对目标函数和约束函数不必附加可解析性条件，对于目标函 数而言甚至可以不要求有显示表达式； 2. 对于约束变量可以去离散值或特殊整数如0和1等； 3. 在通常情况下，这些算法能够求解全局最优解。 第一节 随 机 试 验 法 一、基本思想 用随机的方法产生试验点，再从试验点中选出满足约束条件的 点，进而求出最优点的一种方法。 二、 随机试验法 成立的最优解x* 设问题 首先用随机方法产生试验点 ，然后从中找出满足约束条件 的点 ,求出使得 一、基本思想 禁忌搜索法(Tabu search)是一种人工智能方法，是局部邻域 搜索算法的推广，是人工智能在组合优化中的一个成功应用。 其基本思想是：标记已经得到的局部最优解，并在进一步的 迭代中避开这些局部最优解。所谓的禁忌就是禁止重复前面的工 作，为了避开局部邻域搜索陷入局部最优，禁忌搜索算法设计了 一种禁忌表，记录已达到过的局部最优点。在下一次的搜索中， 就利用禁忌表中的信息，不再或者有选择地搜索这些点，以此跳 出局部最优点。 第二节 禁 忌 搜 索 法 1. 算法的提出 模拟退火算法最早的思想由Metropolis等（1953）提出，1983年 Kirkpatrick等将其应用于组合优化。 2. 算法的目的 解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。 一、物理退火过程 第三节 模 拟 退 火 算 法 3.物理退火过程 什么是退火? 退火是指将固体加热到足够高的温度，使分子呈随机排列状态， 然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某 种稳定状态。 第三节 模 拟 退 火 算 法 物理退火过程 加温过程增强粒子的热运动，消除系统原先可能存 在的非均匀态； 等温过程对于与环境换热而温度不变的封闭系统， 系统状态的自发变化总是朝自由能减少的方向进行，当 自由能达到最小时，系统达到平衡态； 冷却过程使粒子热运动减弱并渐趋有序，系统能量 逐渐下降，从而得到低能的晶体结构。 第三节 模 拟 退 火 算 法 4. 数学表述 在温度T，分子停留在状态r满足Boltzmann概率分布 第三节 模 拟 退 火 算 法 在同一个温度T，选定两个能量E10 第三节 模 拟 退 火 算 法 若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合 ： 当温度很高时，每个状态概率基本相同，接近平均值1/|D|； 状态空间存在超过两个不同能量时，具有最低能量状态的概率超 出平均值1/|D| ； 当温度趋于0时，分子停留在最低能量状态的概率趋于1。 能量最低状态 非能量最低状态 第三节 模 拟 退 火 算 法 Metropolis准则(1953)以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法(计 算机随机模拟方法)加以模拟，虽然该方法简单，但必须大量采 样才能得到比较精确的结果，计算量很大。 第三节 模 拟 退 火 算 法 若在温度T，当前状态i 新状态j 若Ej=randrom0,1 s=sj; Until 抽样稳定准则满足； 退温tk+1=update(tk)并令k=k+1； Until 算法终止准则满足； 输出算法搜索结果。 第三节 模 拟 退 火 算 法 7. 影响优化结果的主要因素分析 给定初温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 初始温度 第三节 模 拟 退 火 算 法 二、 模拟退火算法的马氏链描述 1.马氏链定义 第三节 模 拟 退 火 算 法 一步转移概率： n步转移概率： 若解空间有限，称马尔可夫链为有限状态； 若 ，称马尔可夫链为时齐的。 第三节 模 拟 退 火 算 法 模拟退火算法对应了一个马尔可夫链 模拟退火算法：新状态接受概率仅依赖于新状态和当前 状态，并由温度加以控制。 若固定每一温度，算法均计算马氏链的变化直至平稳分 布，然后下降温度，则称为时齐算法； 若无需各温度下算法均达到平稳分布，但温度需按一定 速率下降，则称为非时齐算法。 第三节 模 拟 退 火 算 法 二、模拟退火算法关键参数和操作的设计 1. 状态产生函数 p原则 产生的候选解应遍布全部解空间 p方法 在当前状态的邻域结构内以一定概率方式（均匀分布 、正态分布、指数分布等）产生 第三节 模 拟 退 火 算 法 2. 状态接受函数 原则 (1)在固定温度下，接受使目标函数下降的候选解的概率 要大于使目标函数上升的候选解概率； (2)随温度的下降，接受使目标函数上升的解的概率要逐 渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。 方法 具体形式对算法影响不大， 一般采用min1,exp(-C/t) 第三节 模 拟 退 火 算 法 3. 初温 p收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题 时难以得到精确的参数； 初温应充分大； p实验表明 初温越大，获得高质量解的机率越大，但花费较多的计 算时间； 第三节 模 拟 退 火 算 法 p方法 (1) 均匀抽样一组状态，以各状态目标值得方差为初温； (2) 随机产生一组状态，确定两两状态间的最大目标值差 ，根据差值，利用一定的函数确定初温； (3) 利用经验公式。 第三节 模 拟 退 火 算 法 4 温度更新函数 p时齐算法的温度下降函数 (1) ，越接近1温度下降越慢，且其大 小可以不断变化； (2) ，其中t0为起始温度，K为算法温度下降的总次数 。 第三节 模 拟 退 火 算 法 p非时齐模拟退火算法 每个温度下只产生一个或少量候选解 p时齐算法常用的Metropolis抽样稳定准则 （1）检验目标函数的均值是否稳定； （2）连续若干步的目标值变化较小； （3）按一定的步数抽样。 5 内循环终止准则 第三节 模 拟 退 火 算 法 p常用方法 （1）设置终止温度的阈值； （2）设置外循环迭代次数； （3）算法搜索到的最优值连续若干步保持不变； （4）概率分析方法。 6 外循环终止准则 第三节 模 拟 退 火 算 法 p模拟退火算法的优点 质量高； 初值鲁棒性强； 简单、通用、易实现。 p模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终止温度， 以及各温度下足够多次的抽样，因此优化过程较长。 三、 模拟退火算法的优缺点 第三节 模 拟 退 火 算 法 p换热器模型 两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目 标函数通常是多峰(谷)的，具有很多局部最优解。 四、模拟退火算法的应用 第三节 模 拟 退 火 算 法 p优化目标 以换热器系统的总费用年值最小作为优化设计的目标。 其中，f1 (X)是两级换热器的初始投资， f2 (X)是两级换热器年维护 费(包括除垢、保养、维修等)， f3 (X)是冷却水资源费以及管程压 降能耗费， f4 (X)是壳程压降能耗费。 第三节 模 拟 退 火 算 法 p优化目标 经过分析，优化问题的独立变量共12个，分别是一级换热器工质出 口温度t2、冷却水流量G1、两个换热器的管内径d1，d2和管间距S1 ，S2、折流板间距B1，B2、折流板开口角1，2、单管长度L1，L2 。 第三节 模 拟 退 火 算 法 p应用模拟退火算法解决优化设计 状态表示12个变量的实数表示； 初始温度100； 结束温度0.001； 状态产生函数 ，为扰动幅度参数，为随 机扰动变量，随机扰动可服从柯西、高斯、均匀分布。 降温因子0.98； 马氏链长度1200。 第三节 模 拟 退 火 算 法 p优化结果 优化目标值 0.25565E06 独立变量取值 t2 G1 Kg/s d1 mm S1 mm B1 m 1 弧度 64.4194 1 5.97166 15.5716 3 34.0971 6 0.92436 1.93421 L1 m d2 mm S2 mm B2 m 2 弧度 L2 m 5.94234 16.7793 5 27.7401 2 0.72953 2.19928 5.78314 第三节 模 拟 退 火 算 法 一、遗传算法简介 第四节 遗 传 算 法 早在50年代，一些生物学家开始研究运用数字计算机模拟生物的 自然遗传与自然进化过程； 1963年，德国柏林技术大学的I. Rechenberg和H. P. Schwefel，做 风洞实验时，产生了进化策略的初步思想； 60年代， L. J. Fogel在设计有限态自动机时提出进化规划的思想 。1966年Fogel等出版了基于模拟进化的人工智能，系统阐 述了进化规划的思想。 60年代中期，美国Michigan大学的J. H. Holland教授提出借鉴生 物自然遗传的基本原理用于自然和人工系统的自适应行为研究和 串编码技术； 1967年，他的学生J. D. Bagley在博士论文中首次提出“遗传算法 (Genetic Algorithms)”一词； 1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生。 第四节 遗 传 算 法 70年代初，Holland提出了“模式定理”（Schema Theorem），一般 认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基 础； 1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际 遗传算法学会(ISGA，International Society of Genetic Algorithms) ； 1989年，Holland的学生D. J. Goldherg出版了“Genetic Algorithms in Search, Optimization, and Machine Learning”，对遗传算法及其 应用作了全面而系统的论述； 1991年，L. Davis编辑出版了遗传算法手册，其中包括了遗传 算法在工程技术和社会生活中大量的应用实例。 第四节 遗 传 算 法 二、几个名词概念 1. 进化计算： 由于遗传算法、进化规划和进化策略是不同领域的研究人员分 别独立提出的，在相当长的时期里相互之间没有正式沟通。直 到90年代，才有所交流。 他们发现彼此的基本思想具有惊人的相似之处，于是提出将这 类方法统称为“进化计算” ( Evolutionary Computation ) 。 第四节 遗 传 算 法 2. 计算智能： 计算智能主要包括神经计算、进化计算和模糊计算等。它们分 别从不同的角度模拟人类的智能活动，以使计算机具有智能。 通常将基于符号处理的传统人工智能称为符号智能，以区别于 正在兴起的计算智能。 符号智能的特点是以知识为基础，偏重于逻辑推理，而计算智 能则是以数据为基础，偏重于数值计算。 第四节 遗 传 算 法 三、达尔文的自然选择说 遗传（heredity）：子代和父代具有相同或相似的性状，保证物 种的稳定性； 变异（variation）：子代与父代，子代不同个体之间总有差异， 是生命多样性的根源； 生存斗争和适者生存：具有适应性变异的个体被保留，不具适应 性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。 第四节 遗 传 算 法 p自组织、自适应和自学习性 在编码方案、适应度函数及遗传 算子确定后，算法将利用进化过 程中获得的信息自行组织搜索。 p本质并行性 内在并行性与内含并行性 p不需求导 只需目标函数和适应度函数 p概率转换规则 强调概率转换规则，而不是确定 的转换规则 四、 遗传算法的思路与特点 第四节 遗 传 算 法 1. 适应度计算： 按比例的适应度函数（proportional fitness assignment） 基于排序的适应度计算（Rank-based fitness assignment） 2.选择算法： 轮盘赌选择（roulette wheel selection） 随机遍历抽样（stochastic universal selection） 局部选择（local selection） 截断选择（truncation selection） 锦标赛选择（tournament selection） 五、 遗传算法的基本操作 第四节 遗 传 算 法 3. 交叉或基因重组 实值重组（real valued recombination）： 离散重组（discrete recombination） 中间重组（intermediate recombination） 线性重组（linear recombination） 扩展线性重组（extended linear recombination） 二进制交叉（binary valued crossover）： 单点交叉（single-point crossover） 多点交叉（multiple-point crossover） 均匀交叉（uniform crossover） 洗牌交叉（shuffle crossover） 缩小代理交叉（crossover with reduced surrogate） 第四节 遗 传 算 法 4. 变异 实值变异 二进制变异 第四节 遗 传 算 法 5.简单实例 Step1. 产生初始种群 Step2. 计算适应度 0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 （8） （5） （2） （10） （7） （12） （5） （19） （10） （14） 第四节 遗 传 算 法 Step3. 选择 个体染色体适应度选择概率累积概率 100011000008 201011110015 300000001012 4100111010010 510101010107 6111001011012 710010110115 8110000000119 9100111010010 10000101001114 8 852107125191014 0.086957 5 852107125191014 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174 第四节 遗 传 算 法 个体染色体适应度选择概率累积概率 100011000008 201011110015 300000001012 4100111010010 510101010107 6111001011012 710010110115 8110000000119 9100111010010 10000101001114 0.086957 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174 0.086957 0.141304 0.163043 0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000 第四节 遗 传 算 法 在01之间产生一个 随机数： 个体染色体适应度选择概率累积概率 100011000008 201011110015 300000001012 4100111010010 510101010107 6111001011012 710010110115 8110000000119 9100111010010 10000101001114 0.086957 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174 0.086957 0.141304 0.163043 0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000 0.070221 0.545929 0.784567 0.446930 0.507893 0.291198 0.716340 0.270901 0.371435 0.854641 淘汰！淘汰！ 第四节 遗 传 算 法 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 Step4. 交叉 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011 0001 1110 100000 010110111 100 0010110 1011011110000 100111 0100 0001 1001110100 1100000001 1010101 0001010 010 011 第四节 遗 传 算 法 Step5. 变异 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001 1110 100000 010110111 100 0010110 1011011110000 100101 0100 0001 1001110100 1100000001 1010101 0001010 010 011 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001 1110 100000 010110111 100 0010110 1011011110000 100111 0100 0001 1001110100 1100000001 1010101 0001010 010 011 第四节 遗 传 算 法 Step6. 至下一代，适应度计算选择交叉变异，直至满足终止 条件。 第四节 遗 传 算 法 p函数优化 是遗传算法的经典应用领域; p组合优化 实践证明，遗传算法对于组合优化中的NP完全问题非常有效; p自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨 识、利用遗传算法进行人工神经网络的结构优化设计和权值学习 等; 六、 遗传算法的应用领域 第四节 遗 传 算 法 p机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、 机器人逆运动学求解、细胞机器人的结构优化和行动协调等; p组合图像处理和模式识别 目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到 了应用; p人工生命 基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗 传算法已在其进化模型、学习模型、行为模型等方面显示了初步 的应用能力； p遗传程序设计 Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的 编码方法，基于对一种树型结构所进行的遗传操作自动生成计算 机程序; 第四节 遗 传 算 法 一、发展简介 第五节 神经网络优化算法 p“神经网络”与“人工神经网络” p1943年，Warren McCulloch和Walter Pitts建立了第一个人工神 经网络模型； p1969年，Minsky和Papert发表Perceptrons； p20世纪80年代，Hopfield将人工神经网络成功应用在组合优化问 题。 1. McCulloch-Pitts神经元 现代的神经网络开始于McCulloch, Pitts(1943)的先驱工作； 他们的神经元模型假定遵循有-无模型律； 如果如此简单的神经元数目足够多和适当设置连接权值并且同步 操作, McCulloch 一般情况下网络是对称的（wij=wji）且无自反馈（wjj=0）; 整个网络的状态可用向量s表示： 第五节 神经网络优化算法 p工作方式 串行（异步，asynchronous）:任一时刻只有一个单元改变状态，其 余单元保持不变； 并行（同步，synchronous）：某一时刻所有神经元同时改变状态。 p稳定状态 如果从t=0的任一初始态s(0)开始变化，存在某一有限时刻t，从此以 后网络状态不再变化，即s(t+1)=s(t)，则称网络达到稳定状态。 第五节 神经网络优化算法 p能量函数的定义 异步方式： 同步方式： 第五节 神经网络优化算法 p能量函数 能量是有界的： 从任一初始状态开始，若在每次迭代时都满足E0，则网络的能 量将越来越小，最后趋向于稳定状态E0 。 第五节 神经网络优化算法 p网络结构 与电子线路对应： 放大器神经元 电阻、电容神经元的时间常数 电导（电阻的倒数）权系数 2. 2. 连续连续HopfieldHopfield神经网络神经网络 第五节 神经网络优化算法 p网络的微分方程 p能量函数 可证明，若g-1为单调增且连续，Cj0，Tji=Tij，则有dE/dt0，当且仅 当dvi/dt=0时dE/dt=0。 第五节 神经网络优化算法 p能量函数 将动力系统方程 简单记为： 如果 ，则称ve是动力系统的平衡点，也称ve为吸 引子。 随着时间的增长，神经网络在状态空间中的解轨迹总是向能量函 数减小的方向变化，且网络的稳定点就是能量函数的极小点。 第五节 神经网络优化算法 p能量函数 当从某一初始状态变化时，网络的演变是使E下降，达到某一局部 极小时就停止变化。这些能量的局部极小点就是网络的稳定点或称 吸引子。 第五节 神经网络优化算法 pHopfield网络设计 当Hopfield用于优化计算时，网络的权值是确定的，应将目标 函数与能量函数相对应，通过网络的运行使能量函数不断下降 并最终达到最小，从而得到问题对应的极小解。 3. Hopfield神经网络在TSP 中的应用 (Travelling Salesman Problem) 第五节 神经网络优化算法 pHopfield网络设计 通常需要以下几方面的工作： （1）选择合适的问题表示方法，使神经网络的输出与问题的解相 对应； （2）构造合适的能量函数，使其最小值对应问题的最优解； （3）由能量函数和稳定条件设计网络参数，如连接权值和偏置参 数等； （4）构造相应的神经网络和动态方程； （5）用硬件实现或软件模拟。 第五节 神经网络优化算法 p问题的表示 将TSP问题用一个nn矩阵表示，矩阵的每个元素代表一个神经 元。 代表商人行走顺序为：3124 每一行、每一列的和各为1。 1为是，0为否第1站第2站第3站第4站 城市10100 城市20010 城市31000 城市40001 第五节 神经网络优化算法 p能量函数的构建 每个神经元接收到的值为zij，其输出值为yij