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

现代优化算法包括随机试验法、禁忌搜索算法、模拟退火算现代优化算法包括随机试验法、禁忌搜索算法、模拟退火算法、遗传算法、神经网络算法和拉格朗日松弛算法等，这些算法涉法、遗传算法、神经网络算法和拉格朗日松弛算法等，这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念。都是以一定的直观基础而构造的算法，通常称之为启发式算概念。都是以一定的直观基础而构造的算法，通常称之为启发式算法。法。 启发式算法的兴起与计算启发式算法的兴起与计算复杂性理论复杂性理论的形成有密切的联系。的形成有密切的联系。 1. 对目标函数和约束函数不必附加可解析性条件，对于目标函对目标函数和约束函数不必附加可解析性条件，对于目标函数而言甚至可以不要求有显示表达式；数而言甚至可以不要求有显示表达式； 2. 对于约束变量可以去离散值或特殊整数如对于约束变量可以去离散值或特殊整数如0和和1等；等； 3. 在通常情况下，这些算法能够求解全局最优解。在通常情况下，这些算法能够求解全局最优解。第一节第一节 随随 机机 试试 验验 法法 一、基本思想一、基本思想 用随机的方法产生试验点，再从试验点中选出满足约束条件的用随机的方法产生试验点，再从试验点中选出满足约束条件的点，进而求出最优点的一种方法。点，进而求出最优点的一种方法。二、二、 随机试验法随机试验法 成立的最优解成立的最优解x*设问题设问题( )( )min. .0,1,2,.,ifstgim=xx首先用随机方法产生试验点首先用随机方法产生试验点 ，然后从中找出满足约束条件，然后从中找出满足约束条件的点的点 , ,求出使得求出使得( )( )minpp*kkff=xx kxpkx一、基本思想一、基本思想 禁忌搜索法禁忌搜索法(Tabu search)是一种人工智能方法，是局部邻域是一种人工智能方法，是局部邻域搜索算法的推广，是人工智能在组合优化中的一个成功应用。搜索算法的推广，是人工智能在组合优化中的一个成功应用。 其基本思想是：标记已经得到的局部最优解，并在进一步的其基本思想是：标记已经得到的局部最优解，并在进一步的迭代中避开这些局部最优解。所谓的禁忌就是禁止重复前面的工迭代中避开这些局部最优解。所谓的禁忌就是禁止重复前面的工作，为了避开局部邻域搜索陷入局部最优，禁忌搜索算法设计了作，为了避开局部邻域搜索陷入局部最优，禁忌搜索算法设计了一种一种禁忌表禁忌表，记录已达到过的局部最优点。在下一次的搜索中，记录已达到过的局部最优点。在下一次的搜索中，就利用禁忌表中的信息，不再或者有选择地搜索这些点，以此跳就利用禁忌表中的信息，不再或者有选择地搜索这些点，以此跳出局部最优点。出局部最优点。第二节第二节 禁禁 忌忌 搜搜 索索 法法 1. 1. 算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等（等（1953）提出，）提出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。2. 算法的目的算法的目的 解决解决NP复杂性问题；复杂性问题； 克服优化过程陷入局部极小；克服优化过程陷入局部极小； 克服初值依赖性。克服初值依赖性。一、物理退火过程一、物理退火过程第三节第三节 模模 拟拟 退退 火火 算算 法法 3.3.物理退火过程物理退火过程 什么是退火什么是退火? ? 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。种稳定状态。 第三节第三节 模模 拟拟 退退 火火 算算 法法 物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动，消除系统原先可能增强粒子的热运动，消除系统原先可能存在的非均匀态；存在的非均匀态； 等温过程等温过程对于与环境换热而温度不变的封闭系统，对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；自由能达到最小时，系统达到平衡态； 冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。量逐渐下降，从而得到低能的晶体结构。第三节第三节 模模 拟拟 退退 火火 算算 法法 4. 4. 数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分布概率分布DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随第三节第三节 模模 拟拟 退退 火火 算算 法法 在同一个温度在同一个温度T，选定两个能量，选定两个能量E1E2， 在同一个温度，分子停留在能量小的状态的概率比停留在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。在能量大的状态的概率要大。TkEETkETZEEPEEPBB12121exp1exp)(10第三节第三节 模模 拟拟 退退 火火 算算 法法 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具有最低能量的状态集合：是具有最低能量的状态集合： 当温度很高时，每个状态概率基本相同，接近平均值当温度很高时，每个状态概率基本相同，接近平均值1/|D|； 状态空间存在超过两个不同能量时，具有最低能量状态的概率超状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值出平均值1/|D| ； 当温度趋于当温度趋于0时，分子停留在最低能量状态的概率趋于时，分子停留在最低能量状态的概率趋于1。能量最低状态能量最低状态 非能量最低状态非能量最低状态第三节第三节 模模 拟拟 退退 火火 算算 法法 Metropolis准则准则(1953)以概率接受新状态以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法方法(计计算机随机模拟方法算机随机模拟方法)加以模拟，虽然该方法简单，但必须大量采加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。样才能得到比较精确的结果，计算量很大。01-(Ej-Ei)/kTp第三节第三节 模模 拟拟 退退 火火 算算 法法 若在温度若在温度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.马氏链定义马氏链定义 ) 1()(Pr) 1(,) 1 (,)0()(Pr )( )(,1021inXjnXinXiXiXjnXZnkXkkXss，满足称为马尔可夫链，若随机序列时刻状态变量的取值。为间，为所有状态构成的解空令第三节第三节 模模 拟拟 退退 火火 算算 法法 一步转移概率：一步转移概率： n步转移概率：步转移概率： 若解空间有限，称马尔可夫链为有限状态；若解空间有限，称马尔可夫链为有限状态； 若若 ，称马尔可夫链为时齐的。，称马尔可夫链为时齐的。) 1()(Pr) 1(,inXjnXnpji) 1()(,npnpZnjiji)0()(Pr)(,iXjnXpnji第三节第三节 模模 拟拟 退退 火火 算算 法法 模拟退火算法对应了一个马尔可夫链模拟退火算法对应了一个马尔可夫链 模拟退火算法：模拟退火算法：新状态接受概率仅依赖于新状态和当前新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。状态，并由温度加以控制。 若固定每一温度，算法均计算马氏链的变化直至平稳分若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为布，然后下降温度，则称为时齐算法时齐算法； 若无需各温度下算法均达到平稳分布，但温度需按一定若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为速率下降，则称为非时齐算法非时齐算法。第三节第三节 模模 拟拟 退退 火火 算算 法法 二、模拟退火算法关键参数和操作的设计二、模拟退火算法关键参数和操作的设计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为算法温度下降的总次数。为算法温度下降的总次数。10 , 0 ,1kttkk0tKkKtk第三节第三节 模模 拟拟 退退 火火 算算 法法 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)是壳程压降能耗费。是壳程压降能耗费。)()()(1)1 ()1 ()()(min4321XfXfXfiiiXfXfnn第三节第三节 模模 拟拟 退退 火火 算算 法法 p优化目标优化目标 经过分析，优化问题的独立变量共经过分析，优化问题的独立变量共12个，分别是一级换热器工质出个，分别是一级换热器工质出口温度口温度t2、冷却水流量、冷却水流量G1、两个换热器的管内径、两个换热器的管内径d1，d2和管间距和管间距S1，S2、折流板间距、折流板间距B1，B2、折流板开口角、折流板开口角1，2、单管长度、单管长度L1，L2。),()(min212121212112LLBBSSddGtfXf第三节第三节 模模 拟拟 退退 火火 算算 法法 p应用模拟退火算法解决优化设计应用模拟退火算法解决优化设计 状态表示状态表示12个变量的实数表示；个变量的实数表示； 初始温度初始温度100； 结束温度结束温度0.001； 状态产生函数状态产生函数 ，为扰动幅度参数，为扰动幅度参数，为随为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。机扰动变量，随机扰动可服从柯西、高斯、均匀分布。 降温因子降温因子0.98； 马氏链长度马氏链长度1200。)() 1(kxkx第三节第三节 模模 拟拟 退退 火火 算算 法法 p优化结果优化结果 优化目标值优化目标值 0.25565E06 独立变量取值独立变量取值t2G1Kg/sd1mmS1mmB1m1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2m2弧度L2m5.9423416.7793527.740120.729532.199285.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 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）第四节第四节 遗遗 传传 算算 法法 Step3. 选择选择个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174第四节第四节 遗遗 传传 算算 法法 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第四节第四节 遗遗 传传 算算 法法 在在01之间产生一个之间产生一个随机数：随机数：个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.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淘汰！淘汰！淘汰！淘汰！第四节第四节 遗遗 传传 算算 法法 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011Step4. 交叉交叉0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110 100000010110111100 00101101011011110000100111010000011001110100110000000110101010001010 010011第四节第四节 遗遗 传传 算算 法法 Step5. 变异变异0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110 100000010110111100 00101101011011110000100101010000011001110100110000000110101010001010 0100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110 100000010110111100 00101101011011110000100111010000011001110100110000000110101010001010 010011第四节第四节 遗遗 传传 算算 法法 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 & Pitts证明这样构成的网络原则上可以计算任证明这样构成的网络原则上可以计算任何可计算函数；何可计算函数； 标志着神经网络和人工智能的诞生。标志着神经网络和人工智能的诞生。二、基本概念二、基本概念第五节第五节 神经网络优化算法神经网络优化算法 McCulloch-Pitts神神经元结构经元结构 McCulloch-Pitts输输出函数定义为：出函数定义为：InputsignalSynapticweightsSummingfunctionActivationfunctionOutputyx1x2xnw2wnw1)(f-0, 00, 1)sgn()sgn()(1xxxxwzfyniii其中，第五节第五节 神经网络优化算法神经网络优化算法 2. 网络的构建网络的构建 Y=F(X) x1y1输出层输出层隐藏层隐藏层输入层输入层x2y2ymxn第五节第五节 神经网络优化算法神经网络优化算法 3. 网络结构的确定网络结构的确定p网络的拓扑结构网络的拓扑结构 前向型、反馈型等前向型、反馈型等p神经元激活函数神经元激活函数 阶跃函数阶跃函数 线性函数线性函数 Sigmoid函数函数baxxf)(xexf11)(f(x)x0+1第五节第五节 神经网络优化算法神经网络优化算法 p确定的内容确定的内容 权值权值wi和和p确定的方式确定的方式 学习（训练）学习（训练） 有指导的学习：已知一组正确的输入输出结果的条件下，神经网有指导的学习：已知一组正确的输入输出结果的条件下，神经网络依据这些数据，调整并确定权值；络依据这些数据，调整并确定权值； 无指导的学习：只有输入数据，没有正确的输出结果情况下，确无指导的学习：只有输入数据，没有正确的输出结果情况下，确定权值。定权值。 4. 关联权值的确定关联权值的确定第五节第五节 神经网络优化算法神经网络优化算法 p学习与工作的关系学习与工作的关系 先学习先学习再工作再工作5. 工作阶段工作阶段第五节第五节 神经网络优化算法神经网络优化算法 p多层多层 两层以上两层以上p前向前向 无反馈无反馈1. 一般结构一般结构三三 、 多层前向神经网络多层前向神经网络x1y1输出层输出层隐藏层隐藏层输入层输入层x2y2ymxn第五节第五节 神经网络优化算法神经网络优化算法 p目的目的 确定权值确定权值p方法方法 反向推导反向推导2 反向传播算法反向传播算法第五节第五节 神经网络优化算法神经网络优化算法 p一般结构一般结构 各神经元之间存在相互联系各神经元之间存在相互联系p分类分类 连续系统：激活函数为连续函数连续系统：激活函数为连续函数 离散系统：激活函数为阶跃函数离散系统：激活函数为阶跃函数四四 、反馈型神经网络、反馈型神经网络第五节第五节 神经网络优化算法神经网络优化算法 pHopfield神经网络神经网络 1982年提出年提出Hopfield反馈神经网络（反馈神经网络（HNN），证明在高强度连接），证明在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。下的神经网络依靠集体协同作用能自发产生计算行为。 是典型的全连接网络，通过引入能量函数，使网络的平衡态与能是典型的全连接网络，通过引入能量函数，使网络的平衡态与能量函数极小值解相对应。量函数极小值解相对应。第五节第五节 神经网络优化算法神经网络优化算法 p网络结构网络结构 N为网络节点总数。为网络节点总数。1. 离散离散Hopfield神经网络神经网络 0)( , 10)( , 1) 1(),(sgn) 1( )()(1tvtvtstvtstswtvjjjjjjNiijij即s1(t+1)s2(t+1)sn(t+1)s1(t)s2(t)sn(t)w12w1nw21w2nwn1wn2第五节第五节 神经网络优化算法神经网络优化算法 一般认为一般认为vj(t)=0时神经元保持不变时神经元保持不变sj(t+1)=sj(t); 一般情况下网络是对称的（一般情况下网络是对称的（wij=wji）且无自反馈（）且无自反馈（wjj=0）; 整个网络的状态可用向量整个网络的状态可用向量s表示：表示：TNssss 21第五节第五节 神经网络优化算法神经网络优化算法 p工作方式工作方式 串行（异步，串行（异步，asynchronous）:任一时刻只有一个单元改变状态，其任一时刻只有一个单元改变状态，其余单元保持不变；余单元保持不变； 并行（同步，并行（同步，sync