现代优化算法幻灯片.ppt

《现代优化算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《现代优化算法幻灯片.ppt（162页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现代优化算法课件第1页，共162页，编辑于2022年，星期一目录o现在优化算法概论o模拟退火算法(SA)o遗传算法(GA)第2页，共162页，编辑于2022年，星期一Part 1 概论概论 主要是说明现代优化算主要是说明现代优化算法的重要性。法的重要性。第3页，共162页，编辑于2022年，星期一现代优化算法现代优化算法 o现代优化算法现代优化算法 遗传算法遗传算法 模拟退火算法模拟退火算法 禁忌搜索算法禁忌搜索算法 人工神经网络人工神经网络 蚁群算法蚁群算法 粒子群算法粒子群算法 差分进化算法差分进化算法 特点：特点：o基于客观世界中的一些自然基于客观世界中的一些自然现象；现象；o建立在计算

2、机迭代计算的基建立在计算机迭代计算的基础上；础上；o具有普适性，可解决实际应用具有普适性，可解决实际应用问题。问题。第4页，共162页，编辑于2022年，星期一数学建模竞赛中的算法数学建模竞赛中的算法(1)93A 非线性交调的频率设计非线性交调的频率设计:拟合、规划拟合、规划93B 足球队排名次足球队排名次:矩阵论、图论、层次分析法、整数矩阵论、图论、层次分析法、整数规划规划94A 逢山开路逢山开路:图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题:图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题:非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉

3、的作业调度天车与冶炼炉的作业调度:非线性规划、动态规划、非线性规划、动态规划、层次分析法、层次分析法、PETRI方法、图论方法、排队论方法方法、图论方法、排队论方法96A 最优捕鱼策略最优捕鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划第5页，共162页，编辑于2022年，星期一96B 节水洗衣机节水洗衣机：非线性规划非线性规划97A 零件参数设计零件参数设计：微积分、非线性规划、随机模拟微积分、非线性规划、随机模拟97B 截断切割截断切割：组合优化、几何变换、枚举、蒙特卡罗、递组合优化、几何变换、枚举、蒙特卡罗、递归、最短路归、最短路98A 投资收益与风险投资收益与风险：线性规

4、划、非线性规划线性规划、非线性规划98B 灾情巡视灾情巡视：最小生成树、最小生成树、Hamilton圈、旅行商问题圈、旅行商问题99A 自动化车床自动化车床：积分、概率分布、随机模拟、分布拟合度积分、概率分布、随机模拟、分布拟合度检验检验数学建模竞赛中的算法数学建模竞赛中的算法(2)第6页，共162页，编辑于2022年，星期一99B 钻井布局钻井布局：几何变换、枚举、最大完全子图、混合几何变换、枚举、最大完全子图、混合整数规划整数规划00A DNA分类分类：神经网络、最小二乘拟合、统计分类神经网络、最小二乘拟合、统计分类00B 管道订购管道订购：最短路、二次规划最短路、二次规划01A 血管的三

5、维重建血管的三维重建：数据挖掘、曲面重建与拟合数据挖掘、曲面重建与拟合01B 公交车调度公交车调度：非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计：最优化最优化02B 彩票中的数学彩票中的数学：概率与优化概率与优化数学建模竞赛中的算法数学建模竞赛中的算法(3)第7页，共162页，编辑于2022年，星期一97年年A 题用模拟退火算法题用模拟退火算法00年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国89年年A 题也和题也和BP 算法算法有关系美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算算法最

6、佳的是遗传算法法最佳的是遗传算法。最优化理论的三大非经典算法最优化理论的三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。第14页，共162页，编辑于2022年，星期一优化模型优化模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1

7、整数规划整数规划一般整数规划一般整数规划连续规划连续规划第19页，共162页，编辑于2022年，星期一最优化问题最优化问题(Optimization Problem)最优化问题最优化问题:组合优化问题组合优化问题(Combinatorial Optimization Problem):最优化问题中的解空间X或S由离散集合构成。其中很多问题是NP完全(Nondeterministic Polynomial Completeness)问题.第20页，共162页，编辑于2022年，星期一o待解决的问题待解决的问题 连续性问题，以微积分为基础，连续性问题，以微积分为基础，规模较小规模较小o传统的优化方

8、法传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、动态理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。决策论等。o传统的评价方法传统的评价方法 算法收敛性、收敛速度算法收敛性、收敛速度 传统优化方法传统优化方法传统优化方法传统优化方法 第21页，共162页，编辑于2022年，星期一现代优化算法现代优化算法现代优化算法现代优化算法又称智能优化算法智能优化算法或现代启发式现代启发式算法算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具

9、有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。第22页，共162页，编辑于2022年，星期一o待解决的问题待解决的问题 离散性、连续的、不确定性、离散性、连续的、不确定性、大规模大规模o现代的优化方法现代的优化方法 启发式算法（启发式算法（heuristic algorithm）追求满意（近似解）追求满意（近似解）实用性强（解决实际工程问题）实用性强（解决实际工程问题）o现代的评价方法现代的评价方法 算法复杂性算法复杂性 现代优化方法现代优化方法现代优化方法现代优化方法 第23页，共162页，编辑于2022年，星期一现代优化算法的特点现代优化算法的特

10、点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。第24页，共162页，编辑于2022年，星期一全局优化全局优化(RastriginsFunction)全局最小点全局最小点(0,0)ohttp:/ TabuSearch，简称TS神经网络算法神经网络算法NeuralNetworkAlgorithm，简称NNA粒子群算法粒子群算法 ParticleSwarmOptimization，简称PSOo差分进化算法差分进化算法DifferentialEvolution，简称DE第27页，共162页，编辑

11、于2022年，星期一搜索示例：三个孩子的年龄搜索示例：三个孩子的年龄(1)两个多年未见的朋友相遇，聊了很多事情。A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆祝生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们的情况。A：好的，我给你一些提示，他们三个年龄之积是36.B：很好，但我还需要更多提示。第28页，共162页，编辑于2022年，星期一三个孩子的年龄三个孩子的年龄(2)A：我的大儿子的眼睛是蓝色的。B考虑了一下说，但是，我还有一点信息来解决你的这个难题。B：哦，够了，B给出了正确的答案，即三个小孩的年龄。A：他们三个年龄之和等于那幢房子的窗户个数

12、。A指着对面的一幢房子说。第29页，共162页，编辑于2022年，星期一三个孩子的年龄三个孩子的年龄(3)根据对话信息，用搜索的方法来解此问题。信息信息1:三个小孩年龄之积为三个小孩年龄之积为36只有以下8种可能，搜索范围减少至8种情况:第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123第30页，共162页，编辑于2022年，星期一三个孩子的年龄三个孩子的年龄(4)信息信息2:三个小孩年龄之和等于窗户数三个小孩年龄之和等于窗户数第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123窗户数窗户数:38 21

13、16 14 13 13 11 10如果窗户数为38、21、16、14、11、10即可得出答案B还需信息，即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色的得答案：(9、2、2)第31页，共162页，编辑于2022年，星期一o典型问题典型问题旅行商问题（旅行商问题（Traveling salesman problem,TSP）123412181032搜索示例：搜索示例：TSP问题问题 给定给定n个城市和两两个城市和两两 城市之间的距离，要城市之间的距离，要 求确定一条经过各城求确定一条经过各城 市当且仅当一次的最市当且仅当一次的最 短路线。短路线。第32页，共162

14、页，编辑于2022年，星期一o典型问题典型问题旅行商问题旅行商问题 城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困难的搜索的困难计算复杂度：指数灾难计算复杂度：指数灾难第33页，共162页，编辑于2022年，星期一Part 2 模拟退火法模拟退火法第34页，共162页，编辑于2022年，星期一第35页，共162页，编辑于2022年，星期一第36页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 o算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法

15、最早的思想由Metropolis等（等（1953）提出，）提出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。物理退火过程物理退火过程物理退火过程物理退火过程o算法的目的算法的目的 解决解决NP复杂性复杂性问题；问题；克服优化过程陷入局部极小；克服优化过程陷入局部极小；克服初值依赖性。克服初值依赖性。第37页，共162页，编辑于2022年，星期一o什么是退火：什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排状态，然后逐步降温使之冷却，最后分子以低能状态

16、排列，固体达到某种稳定状态。列，固体达到某种稳定状态。物理退火过程物理退火过程物理退火过程物理退火过程第38页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 等温过程等温过程对于与环境换热而温度不变的封闭系统，系统状态的对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；达到平衡态；o物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动，消除系统原先可能存在的增强粒子的热运动，消除系统原先可能存在的非均匀态；非均匀态；冷却过程冷却过程使

17、粒子热运动减弱并渐趋有序，系统能量逐渐下降，使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。从而得到低能的晶体结构。第39页，共162页，编辑于2022年，星期一第40页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算o数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分布概率分布物理退火过程物理退火过程物理退火过程物理退火过程第41页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算o数学表述数学表述 在在同一个温度同一个温

18、度T，选定两个能量，选定两个能量E1E2，有，有 物理退火过程物理退火过程物理退火过程物理退火过程0 在同一个温度，分子停留在能量小的状态的概率比停留在在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。能量大的状态的概率要大。第42页，共162页，编辑于2022年，星期一智能优化计算智能优化计算 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具有最低能量的状态集合：是具有最低能量的状态集合：1、当温度很高时，每个状态概率基本相同，接近平均值、当温度很高时，每个状态概率基本相同，接近平均值1/|D|；2、状态空间存在超过两个不同能量时，具有最低能量状态

19、的概率、状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值超出平均值1/|D|；3、当温度趋于、当温度趋于0时，分子停在最低能量状态概率趋于时，分子停在最低能量状态概率趋于1。模拟退火算法模拟退火算法模拟退火算法模拟退火算法能量最低状态能量最低状态非能量最低状态非能量最低状态o数学表述数学表述第43页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算oMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 物理退火过程物理退火过程物理退火过程物理退火过程 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达

20、到热平衡的过程可以用Monte Carlo方法方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。大量采样才能得到比较精确的结果，计算量很大。第44页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算 否则，以概率否则，以概率 p=exp-(Ej-Ei)/kBT 接受接受j 为当前状态。为当前状态。物理退火过程物理退火过程物理退火过程物理退火过程oMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，

21、当前状态，当前状态i 新状态新状态j 若若Ej=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤第55页，共162页，编辑于2022年，星期一模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算o影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温t=t0，随机产生初始状态，随机产生初始状态s

22、=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 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤三函数两准则三函数两准则初始温度初始温度第56页，共162页，编辑于2022年，星期一3.3 模拟退火算法关键参数和

23、操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算华东理工大学自动化系 2007年 o原则原则 产生的候选解应遍布全部解空间产生的候选解应遍布全部解空间(保证全局最优解保证全局最优解)o方法方法 在当前状态的邻域结构内以一定概率方式（均匀分布、正态分在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生布、指数分布等）产生状态产生函数状态产生函数状态产生函数状态产生函数第57页，共162页，编辑于2022年，星期一模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o原则原则 (1)在固定温度下，接受使目标函数下降的候选解

24、的概率要大于在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐随温度的下降，接受使目标函数上升的解的概率要逐渐减小；减小；(3)当温度趋于零时，只能接受目标函数下降的解。当温度趋于零时，只能接受目标函数下降的解。o方法方法 具体形式对算法影响不大具体形式对算法影响不大,一般采用一般采用min1,exp(-C/t)状态接受函数状态接受函数状态接受函数状态接受函数第58页，共162页，编辑于2022年，星期一模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能

25、优化计算o收敛性分析收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题时难通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；以得到精确的参数；初温应充分大；初温应充分大；o实验表明实验表明 初温越大，获得高质量解的机率越大，但花费较多的计算时间；初温越大，获得高质量解的机率越大，但花费较多的计算时间；初温初温初温初温第59页，共162页，编辑于2022年，星期一模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o方法方法 （1）均匀抽样一组状态，以各状态目标值得方差为初温；）均匀抽样一组状态，以各状态目标值得方差为初温；（2）

26、随机产生一组状态，确定两两状态间的最大目标值）随机产生一组状态，确定两两状态间的最大目标值 差，根据差差，根据差值，利用一定的函数确定初温；值，利用一定的函数确定初温；（3）利用经验公式。）利用经验公式。初温初温初温初温第60页，共162页，编辑于2022年，星期一模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o时齐算法的温度下降函数时齐算法的温度下降函数 （1），越接近越接近1 1温度下降越慢，且其大小可温度下降越慢，且其大小可以不断变化；以不断变化；（2），其中，其中t0为起始温度，为起始温度，K为算法温度下降的总次数。为算法温度下降的总次数。温度

27、更新函数温度更新函数温度更新函数温度更新函数o若固定每一温度，算法均计算至平稳分布，然后下降温度，则称为时齐算法；若固定每一温度，算法均计算至平稳分布，然后下降温度，则称为时齐算法；o若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。法。第61页，共162页，编辑于2022年，星期一模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o非时齐模拟退火算法非时齐模拟退火算法 每个温度下只产生一个或少量候选解每个温度下只产生一个或少量候选解o时齐算法时齐算法常用的常

28、用的Metropolis抽样稳定准则抽样稳定准则 （1）检验目标函数的均值是否稳定；）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；）连续若干步的目标值变化较小；（3）按一定的步数抽样。）按一定的步数抽样。内循环终止准则内循环终止准则内循环终止准则内循环终止准则第62页，共162页，编辑于2022年，星期一模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o常用方法常用方法 （1）设置终止温度的阈值；）设置终止温度的阈值；（2）设置外循环迭代次数；）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；）算法搜索到的最优值连续若干

29、步保持不变；（4）概率分析方法。）概率分析方法。外循环终止准则外循环终止准则外循环终止准则外循环终止准则第63页，共162页，编辑于2022年，星期一智能优化计算智能优化计算o模拟退火算法的优点模拟退火算法的优点 质量高；质量高；初值鲁棒性强；初值鲁棒性强；简单、通用、易实现。简单、通用、易实现。o模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终止温度，由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。以及各温度下足够多次的抽样，因此优化过程较长。模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺

30、点模拟退火算法的优缺点第64页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）oTSP Benchmark 问题问题 41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13

31、40;82 7;62 32;58 35;45 21;41 26;44 35;4 50第65页，共162页，编辑于2022年，星期一第66页，共162页，编辑于2022年，星期一智能优化计算智能优化计算o算法流程算法流程 第67页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o初始温度的计算初始温度的计算 for i=1:100 route=randperm(CityNum);fval0(i)=CalDist(dislist,route);end t0=-(max(fval0)-min(fval0)/log(0.9);3030城市城

32、市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第68页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o状态产生函数的设计状态产生函数的设计 （1）互换操作，随机交换两个城市的顺序；）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。）插入操作，随机选择某点插入某随机位置。3030城市城市城市城市TSPTSP问题（问题（问题（问题（d

33、 d*=423.741 by D B Fogel=423.741 by D B Fogel）283591467283591467283591467281593467283419567235981467第69页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o参数设定参数设定 截止温度截止温度 tf=0.01;退温系数退温系数 alpha=0.90;内循环次数内循环次数 L=200*CityNum;3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D

34、B Fogel）第70页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第71页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）

35、第72页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第73页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第74页，共16

36、2页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第75页，共162页，编辑于2022年，星期一模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行结果运行结果 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第76页，共162页，编辑于20

37、22年，星期一模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的可行方案改进的可行方案 （1）设计合适的状态产生函数；）设计合适的状态产生函数；（2）设计高效的退火历程；）设计高效的退火历程；（3）避免状态的迂回搜索；）避免状态的迂回搜索；（4）采用并行搜索结构；）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；）选择合适的初始状态；（7）设计合适的算法终止准则。）设计合适的算法终止准则。改进内容改进内容改进内容改进内容第77页，共162页，编辑于2022年，星期一 模拟退火算法的改进模拟退火

38、算法的改进智能优化计算智能优化计算o改进的方式改进的方式 （1）增加升温或重升温过程，避免陷入局部极小；）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆）增加记忆功能（记忆“Best so far”状态）；状态）；（3）增加补充搜索过程（以最优结果为初始解）；）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；的最优状态；（5）结合其它搜索机制的算法；）结合其它搜索机制的算法；（6）上述各方法的综合。）上述各方法的综合。改进内容改进内容改进内容改进内容第78页，共16

39、2页，编辑于2022年，星期一 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的思路改进的思路 （1）记录）记录“Best so far”状态，并即时更新；状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续即在各温度下当前状态连续 m1 步保持不变则认为步保持不变则认为Metropolis抽抽样稳定，若连续样稳定，若连续 m2 次退温过程中所得最优解不变则认为算次退温过程中所得最优解不变则认为算法收敛。法收敛。一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火

40、算法一种改进的模拟退火算法第79页，共162页，编辑于2022年，星期一 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的退火过程改进的退火过程 （1）给定初温）给定初温t0，随机产生初始状态，随机产生初始状态s，令初始最优解，令初始最优解s*=s，当前状态为，当前状态为s(0)=s，i=p=0；（2）令）令t=ti，以，以t，s*和和s(i)调用改进的抽样过程，返回其所得最优解调用改进的抽样过程，返回其所得最优解s*和当前状和当前状态态s(k)，令当前状态，令当前状态s(i)=s(k)；（3）判断）判断C(s*)m2?若是，则转第若是，则转第(6)步；否则，返回第步；否则

41、，返回第(2)步；步；（6）以最优解）以最优解s*作为最终解输出，停止算法。作为最终解输出，停止算法。一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法第80页，共162页，编辑于2022年，星期一 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的抽样过程改进的抽样过程 （1）令）令k=0时的初始当前状态为时的初始当前状态为s(0)=s(i)，q=0；（2）由状态）由状态s通过状态产生函数产生新状态通过状态产生函数产生新状态s，计算增量，计算增量C=C(s)-C(s)；（3）若）若CC(s)?若是，则令若是，则令s*=s，q=0；否则，

42、令；否则，令q=q+1。若。若C0，则以概率，则以概率exp(-C/t)接受接受s作为下作为下一当前状态；一当前状态；（4）令）令k=k+1，判断，判断qm1?若是，则转第若是，则转第(5)步；否则，返回第步；否则，返回第(2)步；步；（5）将当前最优解）将当前最优解s*和当前状态和当前状态s(k)返回改进退火过程。返回改进退火过程。一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法第81页，共162页，编辑于2022年，星期一Part 3 遗传算法遗传算法第82页，共162页，编辑于2022年，星期一遗传算法遗传算法(Genetic Algorithm)

43、进化算法(EvolutionaryAlgorithm)第83页，共162页，编辑于2022年，星期一遗传算法遗传算法(GA)Darwin(1859):“物竟天择，适者生存物竟天择，适者生存”JohnHolland(universityofMichigan,1975)Adaptation in Natural and Artificial System遗传算法作为一种有效的工具，已广泛地应用于最优化遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适应遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。全局优化概率

44、搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。第84页，共162页，编辑于2022年，星期一遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制遗传算法的搜索机制第85页，共162页，编辑于2022年，星期一局部局部全局全局遗传算法遗传算法(GA)第86页，共162页，编辑于2022年，星期

45、一We have a dream!We have a dream!I am at the I am at the toptopHeight is.Height is.I am not at the top.I am not at the top.My high is better!My high is better!I will continueI will continue遗传算法遗传算法(GA)GA-第0代第87页，共162页，编辑于2022年，星期一Dead oneDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代第88页，共162页，编辑于2022年，星期

46、一Not at the top,Not at the top,Come Up!Come Up!遗传算法遗传算法(GA)GA-第?代第89页，共162页，编辑于2022年，星期一I am the I am the BESTBEST !遗传算法遗传算法(GA)GA-第N代第90页，共162页，编辑于2022年，星期一适者生存适者生存(SurvivaloftheFittest)oGA主要采用的进化规则是主要采用的进化规则是“适者生存适者生存”o较好的解保留，较差的解淘汰较好的解保留，较差的解淘汰遗传算法遗传算法(GA)第91页，共162页，编辑于2022年，星期一基本遗传算法基本遗传算法基本遗传算法

47、（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。第92页，共162页，编辑于2022年，星期一SGA实例实例1：函数最值：函数最值SGA参数:编码方式:二进制码 e.g.00000e.g.000000;0;01101 01101 13;1111113;111113131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异 求函数f(x)=x2的最大值，x为自然数且0 x3

48、1.o手工方式完成演示SGA过程第93页，共162页，编辑于2022年，星期一SGA实例实例1 max x2 :选择操作选择操作第94页，共162页，编辑于2022年，星期一SGA实例实例1 max x2 :交叉操作交叉操作第95页，共162页，编辑于2022年，星期一SGA实例实例1 max x2 :变异操作变异操作第96页，共162页，编辑于2022年，星期一SGA实例实例2:连续函数最值连续函数最值求下列函数的最大值：第97页，共162页，编辑于2022年，星期一SGA实例实例2:编码编码高精度高精度编码 x,y 0,1L 必须可逆(一个表现型对应一个基因型)解码算子解码算子：:0,1L

49、 x,y 染色体长度染色体长度L决定可行解的最大精度决定可行解的最大精度长染色体长染色体(慢进化慢进化)实数问题：变量z为实数，如何把a1,aL 0,1Lzx,y第98页，共162页，编辑于2022年，星期一SGA实例实例2:编码编码设定求解精确到设定求解精确到6位小数，因区间长度为位小数，因区间长度为2-(-1)=3,则需将区则需将区间分为间分为3X106等份。因等份。因 2097152221 3X1062224194304。故编码的二进制串长。故编码的二进制串长L=22。将一个二进制串将一个二进制串(b21b20b0)转化为转化为10进制数：进制数：e.g.-1;2 1.627 888 1

50、.627888=-1+3x(1110000000111111000101)2/(222-1)=-1+3x3674053/(222-1)第99页，共162页，编辑于2022年，星期一SGA实例实例2:初始化种群、适应函数初始化种群、适应函数随机初始化种群随机初始化种群适应函数适应函数本实例目标函数在定义域内均大于0，且是求函数最大值，故直接引用目标函数作为适应函数：f(s)=f(x)其中二进制串s对于变量x的值。e.g.s1=x1=-0.958973适应值适应值:f(s1)=f(x1)=1.078878s2=x2=1.627888适应值适应值:f(s2)=f(x2)=3.250650第100页，