现代优化算法最新课件

《现代优化算法最新课件》由会员分享，可在线阅读，更多相关《现代优化算法最新课件（162页珍藏版）》请在金锄头文库上搜索。

1、现代优化算法潘克家 2011-8-8 2目录o现在优化算法概论o模拟退火算法(SA)o遗传算法(GA)3Part 1 概论概论 主要是说明现代优化算主要是说明现代优化算法的重要性。法的重要性。4现代优化算法现代优化算法 o现代优化算法现代优化算法 遗传算法遗传算法 模拟退火算法模拟退火算法 禁忌搜索算法禁忌搜索算法 人工神经网络人工神经网络 蚁群算法蚁群算法 粒子群算法粒子群算法 差分进化算法差分进化算法 特点：特点：基于客观世界中的一些自基于客观世界中的一些自然现象；然现象；建立在计算机迭代计算的建立在计算机迭代计算的基础上；基础上；具有普适性，可解决实际具有普适性，可解决实际应用问题。应用

2、问题。5数学建模竞赛中的算法数学建模竞赛中的算法(1)93A 非线性交调的频率设计非线性交调的频率设计: 拟合、规划拟合、规划93B 足球队排名次足球队排名次: 矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A 逢山开路逢山开路: 图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题: 图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题 : 非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉的作业调度天车与冶炼炉的作业调度: 非线性规划、动态非线性规划、动态规划、层次分析法、规划、层次分析法、PETRI方法、图论方法、排队论方法

3、、图论方法、排队论方法方法96A 最优捕鱼策略最优捕鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划696B 节水洗衣机节水洗衣机：非线性规划非线性规划97A 零件参数设计零件参数设计：微积分、非线性规划、随机模拟微积分、非线性规划、随机模拟97B 截断切割截断切割：组合优化、几何变换、枚举、蒙特卡组合优化、几何变换、枚举、蒙特卡罗、递归、最短路罗、递归、最短路98A 投资收益与风险投资收益与风险：线性规划、非线性规划线性规划、非线性规划98B 灾情巡视灾情巡视：最小生成树、最小生成树、Hamilton圈、旅行商圈、旅行商问题问题99A 自动化车床自动化车床：积分、概率分布、随机模

4、拟、分布积分、概率分布、随机模拟、分布拟合度检验拟合度检验数学建模竞赛中的算法数学建模竞赛中的算法(2)799B 钻井布局钻井布局：几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00A DNA分类分类：神经网络、最小二乘拟合、统计分神经网络、最小二乘拟合、统计分类类00B 管道订购管道订购：最短路、二次规划最短路、二次规划01A 血管的三维重建血管的三维重建：数据挖掘、曲面重建与拟合数据挖掘、曲面重建与拟合01B 公交车调度公交车调度：非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计：最优化最优化02B 彩票中的数学彩票中的数学：概率与优化概率

5、与优化数学建模竞赛中的算法数学建模竞赛中的算法(3)1497年年A 题用模拟退火算法题用模拟退火算法00年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国89年年A 题也和题也和BP 算法算法有关系美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法算法最佳的是遗传算法。 最优化理论的三大非经典算法最优化理论的三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。19优化模型优化模型

6、实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x) 0约束条约束条件件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划一般整数规划一般整数规划连续规划连续规划20最优化问题最优化问题(Optimization Problem)最优化问题最优化问题:组合优化问题组合优化问题(Combinatorial Optimization Problem ) :最优化问题中的解空间X或S由离散集合构成。其中很多问

7、题是NP完全(Nondeterministic Polynomial Completeness)问题.21o待解决的问题待解决的问题 连续性问题，以微积分为基础，连续性问题，以微积分为基础，规模较小规模较小o传统的优化方法传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。论、对策论、决策论等。 o传统的评价方法传统的评价方法 算法收敛性、收敛速度算法收敛性、收敛速度 传统优化方法传统优化方法传统优化方法传统优化方法 22

8、现代优化算法现代优化算法现代优化算法现代优化算法又称智能优化算法智能优化算法或现代启现代启发式算法发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。23o待解决的问题待解决的问题 离散性、连续的、不确定性、离散性、连续的、不确定性、大规模大规模o现代的优化方法现代的优化方法 启发式算法（启发式算法（heuristic algorithm） 追求满意（近似解）追求满意（近似解） 实用性强（解决实际工程问题）实用性强（解决实际工程问题） o现代的评价方法现代的评价方法 算法复杂

9、性算法复杂性 现代优化方法现代优化方法现代优化方法现代优化方法 24现代优化算法的特点现代优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。25全局优化全局优化(RastriginsFunction)全局最小点全局最小点(0,0)26现代优化算法现代优化算法特点：1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续的要求;容易实现，求解稳健。3)但收敛速度慢，能获得全局最优；适合于求解空间不知的情况。4)SA、GA可应用于大规模、多峰多态函数、含离散变量等全局优化

10、问题；求解速度和质量远超过常规方法。27常用的现代优化算法常用的现代优化算法遗传算法遗传算法GeneticAlgorithm，简称GA模拟退火算法模拟退火算法SimulatedAnnealing，简称SA禁忌搜索算法禁忌搜索算法 TabuSearch，简称TS神经网络算法神经网络算法NeuralNetworkAlgorithm，简称NNA粒子群算法粒子群算法 ParticleSwarmOptimization，简称PSO差分进化算法差分进化算法DifferentialEvolution，简称DE28搜索示例：三个孩子的年龄搜索示例：三个孩子的年龄(1)两个多年未见的朋友相遇，聊了很多事情。A：

11、既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆祝生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们的情况。A：好的，我给你一些提示，他们三个年龄之积是36.B：很好，但我还需要更多提示。29三个孩子的年龄三个孩子的年龄(2)A：我的大儿子的眼睛是蓝色的。B考虑了一下说，但是，我还有一点信息来解决你的这个难题。B：哦，够了，B给出了正确的答案，即三个小孩的年龄。A：他们三个年龄之和等于那幢房子的窗户个数。A指着对面的一幢房子说。30三个孩子的年龄三个孩子的年龄(3)根据对话信息，用搜索的方法来解此问题。信息信息1:三个小孩年龄之积为三个小孩年龄之积为36只有

12、以下8种可能，搜索范围减少至8种情况:第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄1111212331三个孩子的年龄三个孩子的年龄(4)信息信息2:三个小孩年龄之和等于窗户数三个小孩年龄之和等于窗户数第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123窗户数窗户数: 38 21 16 14 13 13 11 10如果窗户数为38、21、16、14、11、10即可得出答案B还需信息，即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色的得答案：(9、2、2)32o典型问题典型问题旅行商问题（

13、旅行商问题（Traveling salesman problem, TSP） 123412181032搜索示例：搜索示例：TSP问题问题 给定给定n个城市和两两个城市和两两 城市之间的距离，要城市之间的距离，要 求确定一条经过各城求确定一条经过各城 市当且仅当一次的最市当且仅当一次的最 短路线。短路线。33o典型问题典型问题旅行商问题旅行商问题 城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困难的搜索的困难计算复杂度：指数灾难计算复杂度：指数灾难34Part 2 模拟退火法模拟退火

14、法353637模拟退火算法及模型模拟退火算法及模型 o算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等（等（1953）提）提出，出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。物理退火过程物理退火过程物理退火过程物理退火过程o算法的目的算法的目的 解决解决NP复杂性复杂性问题；问题； 克服优化过程陷入局部极小；克服优化过程陷入局部极小； 克服初值依赖性。克服初值依赖性。38o什么是退火：什么是退火： 退火是指将固体加热到足够高的温度，使分子呈随机排退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使

15、之冷却，最后分子以低能状列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。态排列，固体达到某种稳定状态。 物理退火过程物理退火过程物理退火过程物理退火过程39模拟退火算法及模型模拟退火算法及模型 等温过程等温过程对于与环境换热而温度不变的封闭系统，对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；由能达到最小时，系统达到平衡态；o物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动，消除系统原先可能增强粒子的热运动，消除系统原先可能存在的非均匀态

16、；存在的非均匀态； 冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能量使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。逐渐下降，从而得到低能的晶体结构。4041模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算o数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分布概率分布物理退火过程物理退火过程物理退火过程物理退火过程42模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算o数学表述数学表述 在在同一个温度同一个温度T，选定两个能量，选定两个能量E1E2，有，有 物理退火过程物理退火过程物理退火过程物

17、理退火过程0 在同一个温度，分子停留在能量小的状态的概率比停留在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。在能量大的状态的概率要大。43智能优化计算智能优化计算 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具有最低能量的状是具有最低能量的状态集合：态集合： 1、当温度很高时，每个状态概率基本相同，接近平均值、当温度很高时，每个状态概率基本相同，接近平均值1/|D|； 2、状态空间存在超过两个不同能量时，具有最低能量状、状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值态的概率超出平均值1/|D| ； 3、当温度趋于、当温度趋于0

18、时，分子停在最低能量状态概率趋于时，分子停在最低能量状态概率趋于1。模拟退火算法模拟退火算法模拟退火算法模拟退火算法能量最低状态能量最低状态非能量最低状态非能量最低状态o数学表述数学表述44模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算oMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 物理退火过程物理退火过程物理退火过程物理退火过程 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法方法（计算机随机模拟方法）加以模拟，虽然该方法简（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到

19、比较精确的结果，计算量单，但必须大量采样才能得到比较精确的结果，计算量很大。很大。45模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算 否则，以概率否则，以概率 p=exp-(Ej-Ei)/kBT 接受接受j 为当前状态。为当前状态。物理退火过程物理退火过程物理退火过程物理退火过程oMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，当前状态，当前状态i 新状态新状态j 若若Ej=randrom0,1 s=sj; Until 抽样稳定准则满足；抽样稳定准则满足； 退温退温tk+1=update(tk)并令并令k=k+1； Until 算

20、法终止准则满足；算法终止准则满足； 输出算法搜索结果。输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤56模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算o影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温t=t0，随机产生初始状态，随机产生初始状态s=s0，令，令k=0； Repeat Repeat 产生新状态产生新状态sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽样稳定准则满足；抽样稳定准则满足； 退

21、温退温tk+1=update(tk)并令并令k=k+1； Until 算法终止准则满足；算法终止准则满足； 输出算法搜索结果。输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤三函数两准则三函数两准则初始温度初始温度573.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算华东理工大学自动化系 2007年 o原则原则 产生的候选解应遍布全部解空间产生的候选解应遍布全部解空间(保证全局最优解保证全局最优解)o方法方法 在当前状态的邻域结构内以一定概率方式（均匀分布、在当前状态

22、的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生正态分布、指数分布等）产生状态产生函数状态产生函数状态产生函数状态产生函数58模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o原则原则 (1)在固定温度下，接受使目标函数下降的候选解的概率在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；要大于使目标函数上升的候选解概率； (2)随温度的下降，接受使目标函数上升的解的概率要逐随温度的下降，接受使目标函数上升的解的概率要逐渐减小；渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。当温度趋于零时，只能接受目

23、标函数下降的解。o方法方法 具体形式对算法影响不大具体形式对算法影响不大, 一般采用一般采用min1,exp(-C/t)状态接受函数状态接受函数状态接受函数状态接受函数59模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o收敛性分析收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；时难以得到精确的参数； 初温应充分大；初温应充分大；o实验表明实验表明 初温越大，获得高质量解的机率越大，但花费较多的计初温越大，获得高质量解的机率越大，但花费较多的计算时间；算时间；初温初温初温初

24、温60模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o方法方法 （1）均匀抽样一组状态，以各状态目标值得方差为初温；）均匀抽样一组状态，以各状态目标值得方差为初温； （2）随机产生一组状态，确定两两状态间的最大目标值）随机产生一组状态，确定两两状态间的最大目标值 差，根据差值，利用一定的函数确定初温；差，根据差值，利用一定的函数确定初温； （3）利用经验公式。）利用经验公式。初温初温初温初温61模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o时齐算法的温度下降函数时齐算法的温度下降函数 （1） ，越接近越接近1

25、 1温度下降越温度下降越慢，且其大小可以不断变化；慢，且其大小可以不断变化； （2） ，其中，其中t0为起始温度，为起始温度，K为算法温度下为算法温度下降的总次数。降的总次数。温度更新函数温度更新函数温度更新函数温度更新函数o若固定每一温度，算法均计算至平稳分布，然后下降温度，则称为若固定每一温度，算法均计算至平稳分布，然后下降温度，则称为时齐算法；时齐算法；o若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。则称为非时齐算法。62模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能

26、优化计算o非时齐模拟退火算法非时齐模拟退火算法 每个温度下只产生一个或少量候选解每个温度下只产生一个或少量候选解o时齐算法时齐算法常用的常用的Metropolis抽样稳定准则抽样稳定准则 （1）检验目标函数的均值是否稳定；）检验目标函数的均值是否稳定； （2）连续若干步的目标值变化较小；）连续若干步的目标值变化较小； （3）按一定的步数抽样。）按一定的步数抽样。内循环终止准则内循环终止准则内循环终止准则内循环终止准则63模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算o常用方法常用方法 （1）设置终止温度的阈值；）设置终止温度的阈值； （2）设置外循环迭

27、代次数；）设置外循环迭代次数； （3）算法搜索到的最优值连续若干步保持不变；）算法搜索到的最优值连续若干步保持不变； （4）概率分析方法。）概率分析方法。外循环终止准则外循环终止准则外循环终止准则外循环终止准则64智能优化计算智能优化计算o模拟退火算法的优点模拟退火算法的优点 质量高；质量高； 初值鲁棒性强；初值鲁棒性强； 简单、通用、易实现。简单、通用、易实现。o模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过止温度，以及各温度下足够多次的抽样，因此优化过程较长

28、。程较长。模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点65模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算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 7

29、8;87 76;18 40;13 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 506667智能优化计算智能优化计算o算法流程算法流程 68模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o初始温度的计算初始温度的计算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0)/log(0.9); 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D

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

31、28359146728359146728159346728341956723598146770模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o参数设定参数设定 截止温度截止温度 tf=0.01; 退温系数退温系数 alpha=0.90; 内循环次数内循环次数 L=200*CityNum;3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=423.741 by D B Fogel） 71模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSP

32、TSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=423.741 by D B Fogel） 72模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=423.741 by D B Fogel） 73模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=4

33、23.741 by D B Fogel） 74模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=423.741 by D B Fogel） 75模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算o运行过程运行过程 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=423.741 by D B Fogel） 76模拟退火算法的实现与应用模拟退火算法的实现

34、与应用智能优化计算智能优化计算o运行结果运行结果 3030城市城市城市城市TSPTSP问题（问题（问题（问题（d d* *=423.741 by D B Fogel=423.741 by D B Fogel） 77模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的可行方案改进的可行方案 （1）设计合适的状态产生函数；）设计合适的状态产生函数； （2）设计高效的退火历程；）设计高效的退火历程； （3）避免状态的迂回搜索；）避免状态的迂回搜索； （4）采用并行搜索结构；）采用并行搜索结构； （5）避免陷入局部极小，改进对温度的控制方式；）避免陷入局部极小，改进对温度的控制方式；

35、（6）选择合适的初始状态；）选择合适的初始状态； （7）设计合适的算法终止准则。）设计合适的算法终止准则。 改进内容改进内容改进内容改进内容78 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的方式改进的方式 （1）增加升温或重升温过程，避免陷入局部极小；）增加升温或重升温过程，避免陷入局部极小； （2）增加记忆功能（记忆）增加记忆功能（记忆“Best so far”状态）；状态）； （3）增加补充搜索过程（以最优结果为初始解）；）增加补充搜索过程（以最优结果为初始解）； （4）对每一当前状态，采用多次搜索策略，以概率接受）对每一当前状态，采用多次搜索策略，以概率接受区域内

36、的最优状态；区域内的最优状态； （5）结合其它搜索机制的算法；）结合其它搜索机制的算法； （6）上述各方法的综合。）上述各方法的综合。 改进内容改进内容改进内容改进内容79 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的思路改进的思路 （1）记录）记录“Best so far”状态，并即时更新；状态，并即时更新； （2）设置双阈值，使得在尽量保持最优性的前提下减少）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续计算量，即在各温度下当前状态连续 m1 步保持不变则步保持不变则认为认为Metropolis抽样稳定，若连续抽样稳定，若连续 m2 次

37、退温过程中所得次退温过程中所得最优解不变则认为算法收敛。最优解不变则认为算法收敛。 一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法80 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算o改进的退火过程改进的退火过程 （1）给定初温）给定初温t0，随机产生初始状态，随机产生初始状态s，令初始最优解，令初始最优解s*=s，当前状态，当前状态为为s(0)=s，i=p=0； （2）令）令t=ti，以，以t，s*和和s(i)调用改进的抽样过程，返回其所得最优解调用改进的抽样过程，返回其所得最优解s*和当前状态和当前状态s(k)，令当前状态，令当前状态

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

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

40、)进化算法(EvolutionaryAlgorithm)84遗传算法遗传算法(GA)Darwin(1859):“物竟天择，适者生存物竟天择，适者生存”JohnHolland(universityofMichigan,1975)Adaptation in Natural and Artificial System遗传算法作为一种有效的工具，已广泛地应用于最遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中优化问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自

41、然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。85遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制遗传算法的搜索机制86局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)87We have a dream!We have a dream!I am at the I am at the toptopHeight is .H

42、eight 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代88Dead oneDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代89Not at the top, Not at the top, Come Up!Come Up!遗传算法遗传算法(GA)GA-第?代90I am the I am the BESTBEST ! !遗传算法遗传算法(GA)GA-第

43、N代91适者生存适者生存(SurvivaloftheFittest)GA主要采用的进化规则是主要采用的进化规则是“适者生存适者生存”较好的解保留，较差的解淘汰较好的解保留，较差的解淘汰遗传算法遗传算法(GA)92基本遗传算法基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。93SGA实例实例1：函数最值：函数最值SGA参数:编码方式: 二进制码 e.g.

44、00000e.g. 000000; 0; 01101 01101 13; 1111113; 111113131种群规模: 4随机初始群体“转盘赌”选择一点杂交, 二进制变异 求函数f(x)=x2的最大值，x为自然数且0x31.o手工方式完成演示SGA过程94SGA实例实例1 max x2 : 选择操作选择操作95SGA实例实例1 max x2 : 交叉操作交叉操作96SGA实例实例1 max x2 : 变异操作变异操作97SGA实例实例2 : 连续函数最值连续函数最值求下列函数的最大值：98SGA实例实例2 : 编码编码高精度高精度编码 x,y 0,1L 必须可逆(一个表现型对应一个基因型)

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

46、627888 = -1+3x(11111000101) 2 /(222-1) = -1+3x3674053/(222-1)100SGA实例实例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.250650101SGA实例实例2 :遗传操作遗传操作选择操作(“轮盘赌

47、”选择)交叉操作(单点交叉)交叉前交叉前(父父):s1=s2=交叉后交叉后(子子):s1=s2=适应值适应值:f(s1)=f(-0.998113)=1.940865f(s2)=f(1.666028)=3.459245s2的适应值比其双亲个体的适应值高。102SGA实例实例2 :遗传操作遗传操作变异操作变异前变异前(父父):s2=变异后变异后(子子):s2=适应值适应值 f(s2)=f(1.721638)=0.917743比f(s2)小变异前变异前(父父):s2=变异后变异后(子子):s”2=适应值适应值f(s”2)=f(1.630818)=3.343555比f(s2)大变异操作有变异操作有”扰

48、动扰动”作用，同时具有增加种群作用，同时具有增加种群多多样性的效果。样性的效果。103SGA实例实例2 :模拟结果模拟结果遗传算法的参数:种群规模种群规模: 50 染色体长度染色体长度: L=22 最大进化代数最大进化代数: 150 交叉概率交叉概率: Pc=0.25 变异概率变异概率: Pm=0.01104SGA实例实例2 :模拟结果模拟结果( (最佳个体进化情况最佳个体进化情况最佳个体进化情况最佳个体进化情况) )世代数染色体编码变量x适应值141117344054718915010110001111111010011111101100111111011001111100110011111

49、1011001111110110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.850274105 遗传算法简介遗传算法简介 智能优化计算智能优化计算o遗传算法的基本思路遗传算法的基本思路 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 106 遗传算法简介遗传算法简介 智能优化计算智能优化计算

50、o自组织、自适应和自学习性自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法将利在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。用进化过程中获得的信息自行组织搜索。 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 o概率转换规则概率转换规则 强调概率转换规则，而不是确定的转换规则强调概率转换规则，而不是确定的转换规则o不需求导不需求导 只需目标函数和适应度函数只需目标函数和适应度函数o本质并行性本质并行性 内在并行性与内含并行性内在并行性与内含并行性107生物进化与遗传算法对应关系生物进化与遗传算法对应关

51、系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程生存能力适应函数108遗传算法的基本操作遗传算法的基本操作选择选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间的

52、部分染色体。变异变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。109如何设计遗传算法如何设计遗传算法如何进行编码？如何进行编码？如何产生初始种群？如何产生初始种群？如何定义适应函数？如何定义适应函数？如何进行遗传操作如何进行遗传操作(复制、交叉、变异复制、交叉、变异)？如何产生下一代种群？如何产生下一代种群？如何定义停止准则如何定义停止准则？110编码编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间 = 0,1L01110100101000100

53、1111选择选择(Selection)选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中主要思想:适应值较高的染色体体有较大的选择机会实现1：“轮盘赌”选择(Roulettewheelselection)将种群中所有染色体编号，并根据各自适应值计算按比例分配的概率依次计算染色体累加概率产生(0,1)之间随机数，若其最多能大于序列中第m个值，则第m个染色体被随机选择112选择选择(Selection)设种群的规模为Nxi是i为种群中第i个染色体AC1/6 = 17%3/6 = 50%B2/6 = 33%fitness(A) = 3fitness(B) = 1fitness

54、(C) = 2染色体xi被选概率113选择选择(Selection)染色体的适应值和所占的比例染色体的适应值和所占的比例轮盘赌选择114选择选择(Selection)随机数23491338627所选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16累加概率82325304250染色体被选的概率被选的染色体115选择选择(Selection)轮轮盘盘上上的的片片分分配配给给群群体体的的染染色色体体，使

55、使得得每每一一个个片片的的大大小小与与对对于于染染色体的适应值成比例色体的适应值成比例从从群群体体中中选选择择一一个个染染色色体体可可视视为为旋旋转转一一个个轮轮盘盘，当当轮轮盘盘停停止止时时，指针所指的片对于的染色体就时要选的染色体。指针所指的片对于的染色体就时要选的染色体。模拟模拟“轮盘赌轮盘赌” 算法算法：(1)r=random(0, 1)，s=0，i=0；(2)如果如果sr，则转则转(4)；(3)s=s+p(xi)，i=i+1, 转转(2)(4)xi即为被选中的染色体，输出即为被选中的染色体，输出I(5)结束结束116选择选择(Selection)其他选择法其他选择法：随机遍历抽样随机

56、遍历抽样(Stochastic universal sampling)局部选择局部选择(Local selection)截断选择截断选择(Truncation selection)竞标赛选择竞标赛选择(Tournament selection)特点特点： 选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。117交叉交叉(crossover, Recombination)遗传

57、交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同, 每个子染色体都带有双亲染色体的遗传基因。118单点交叉单点交叉(1-point crossover)在双亲的父代染色体中随机产生一个交叉点位置在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代

58、染色体互换交叉点位置右边的基因码产生两个子代染色体交叉概率交叉概率Pc 一般范围为一般范围为(60%, 90%)，平均约，平均约80%1 11 11 11 11 11 11 11 1父代父代父代父代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 0子代子代子代子代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 11 11 11 11 1交叉点位置交叉点位置交叉点位置交叉点位置119交叉交叉(crossover, Recombination)单点交叉操作可以产生与父代染色体完全不同

59、的单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作因。但当双亲染色体相同时，交叉操作是不起作用的。用的。假如交叉概率Pc50%,则交配池中50%的染色体(一半染色体)将进行交叉操作，余下的50%的染色体进行选择(复制)操作。GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体120变异变异(Mutation)以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。变异概率Pm 一般介于1/种群规模与1/染色体长度之间，平均约

60、1-2%1 11 10 01 10 01 10 00 0父代父代父代父代0 01 10 01 10 01 10 01 1子代子代子代子代变异基因变异基因变异基因变异基因变异基因变异基因变异基因变异基因121变异变异(Mutation)比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复群体中失去的多样性多样性方面具有潜在的作用。在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个

61、位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。122适应函数适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应

62、函数一般由目标函数变换而成123适应函数适应函数(Fitness Function)适应函数常见形式：适应函数常见形式：直接将目标函数转化为适应函数直接将目标函数转化为适应函数若目标函数为最大化问题： Fitness(f(x) = f(x)若目标函数为最小化问题： Fitness(f(x) = -f(x)缺点: (1)可能不满足轮盘赌选择中概率非负的要求(2)某些代求解的函数值分布上相差很大，由此得到的评价适应值可能不利于体现群体的评价性能，影响算法的性能。124适应函数适应函数(Fitness Function)界限构造法界限构造法 目标函数为最大化问题其中Cmin为f(x)的最小估计值 目

63、标函数为最小化问题其中Cmaxn为f(x)的最大估计值125停止准则停止准则(Termination Criteria)种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值126基本步骤基本步骤(Step by Step)(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步;(3)按由个体适应值所决定的某个规则选择进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群中适应度值最优的染色体作为问题的满

64、意解或最优解。127流程图流程图(Flow Chart)128SGA伪码描述伪码描述ProcedureGeneticAlgorithmbeginbegint = 0 ;初始化 P(t) ;计算 P(t) 的适应值 ;while (不满足停止准则) do begin t = t+1 ; 从P(t-1)中选择 P(t) ; % selection 重组 P(t) ; % crossover and mutation 计算 P(t) 的适应值; end end129无约束最优化问题无约束最优化问题GA编码编码：X=(x1,x2,xn)的各个变量可以按二进制编码方法分别编码。对于变量xi的上、下限约束

65、lixiui(i=1,2,n)，依据解的精度要求(有效位数)求得各个变量X=(x1,x2,xn)的二进制码位数(m1,m2,mn)(确定方法类似于SGA实例2)，因此将n个二进制位串顺序连接起来，构成一个个体的染色体编码，编码的总位数mm1+m2+mn。无约束最优化问题:130无约束最优化问题无约束最优化问题GA解码解码：解码时仍按各个变量的编码顺序分别实现常规的二进制编码解码方法。二进制遗传编码示意图如下：131约束最优化问题约束最优化问题常规解法常规解法：(1)把约束问题转化为无约束问题，在用无约束问题方法求解，如罚函数法(2)改进无约束问题的方法，再用于约束问题，如梯度投影法、广义简约梯

66、度法约束最优化问题:132约束最优化问题约束最优化问题遗传算法求解关键: 约束条件的处理等式约束可以包含到适应函数，仅考虑不等式约束。假设按无约束问题那样求解，在搜索过程中计算目标函数值，并检查是否有约束违反。如果没有违反，则表明是可行解，就根据目标函数指定一适应值；否则，就是不可行解，因而没有适应值(适应值为0)。这样的处理实际不可行，因为找到一个可行解几乎与找到最优解一样困难。133一般解法一般解法：通过引入罚函数，从不可行解中得到一些信息。将罚函数包含到适应函数中。关键是如何设计罚函数；关键是如何设计罚函数；不同问题需要设计不同的罚函数；不同问题需要设计不同的罚函数；对一般的约束处理，通

67、常很困难。对一般的约束处理，通常很困难。约束最优化问题约束最优化问题134组合最优化问题组合最优化问题典型问题：典型问题：旅行商问题旅行商问题(Traveling Salesman Problem)作业调度问题作业调度问题(Job Shop Scheduling Problem)背包问题背包问题(Knapsack Problem)图着色问题图着色问题 很多组合最优化问题是很多组合最优化问题是NPNP难问题难问题或或NPNP完全问题完全问题135旅行商问题旅行商问题(TSP)TSP，也称货郎担问题，是一个NP完全问题。TSP描述：图论图论:设图设图G=(V,E),其中其中V是顶点集，是顶点集，E

68、是边集。设是边集。设C=(cij)是与是与E相联系的距离矩阵。寻找一条通过所相联系的距离矩阵。寻找一条通过所有顶点且每个顶点只通过一次的最短距离回路有顶点且每个顶点只通过一次的最短距离回路(Hamilton回路回路)。实际应用中，。实际应用中，C也可解释为费用或也可解释为费用或旅行时间矩阵。旅行时间矩阵。实际实际:一位推销员从自己所在城市出发，必须遍访所一位推销员从自己所在城市出发，必须遍访所有城市之后又回到原来的城市，求使其旅行费用最有城市之后又回到原来的城市，求使其旅行费用最少的路径。少的路径。136巡回旅行商问题巡回旅行商问题(TSP)中国货郎担问题:城市数:40城市编号1,2,40寻找

69、一条最短路径137TSP复杂性复杂性搜索空间庞大搜索空间庞大TSP涉及求多个变量的函数的最小值，求解很困难。其可能的路径条数随着城市数目n成指数增长，如，5个城市对应12条路径；10个城市对应181440条路径；100个城市对应4.6663X10155条路径。如此庞大的搜索空间，常规解法和计算工具都遇到计算上的困难。只能寻找近似解法，如神经网络方法、模拟退火法、遗传算法等。138TSP编码编码:路径表示路径表示染色体表示成所有城市的一个排列，若有n个城市，一条可能路径编码为长度为n的整数向量(i1,i2,in),其中ik表示第ik个城市。例如:路径编码向量(517894623)直接表示一条旅行

70、路程(5-1-7-8-9-4-6-2-3)。此向量是1到n的一个排列，即从1到n的每个整数在这个向量中正好出现一次,不能有重复。这样，基本遗传算法的基因操作生成的个体不能满足这一约束条件，需寻求其他遗传操作。139TSP交叉交叉需其他方式的交叉需其他方式的交叉(重组重组)操作操作,如部分匹配交叉如部分匹配交叉(Partially Matched Crossover,PMX)、顺序交叉顺序交叉(Ordered Crossover,OX)、循环交叉循环交叉(Cycle Crossover,CX)、边重组边重组(Edge Recombination)。1 2 3 4 55 4 3 2 11 2 3

71、2 15 4 3 4 5一般的交叉操作会产生不合适的解，如一般的交叉操作会产生不合适的解，如140TSP交叉交叉1:部分匹配交叉部分匹配交叉(PMX)双亲双亲P1,P2随机选取两个交叉点，得到一个匹配段随机选取两个交叉点，得到一个匹配段,根据根据交叉点中间段给出映射关系。交叉点中间段给出映射关系。1 2 3 4 5 6 7 8 99 3 7 8 2 6 5 1 4x x x 4 5 6 7 x xx x x 8 2 6 5 x xP1P2映射关系：映射关系：4 8、5 2、7 5c1c2 交换两个交叉点之间的编码交换两个交叉点之间的编码,(X表示未定码表示未定码)141TSP交叉交叉1:部分匹

72、配交叉部分匹配交叉(PMX)子个体子个体C1，C2分别从其父个体中继承未映射城市码分别从其父个体中继承未映射城市码1 2 3 4 5 6 7 8 99 3 7 8 2 6 5 1 49 3 x 4 5 6 7 1 x1 x 3 8 2 6 5 x 9P1P2c1c2映射关系映射关系：4 8、5 2、7 59 3 2 4 5 6 7 1 81 7 3 8 2 6 5 4 9c1c2 再根据映射关系，对以上未定码，使用再根据映射关系，对以上未定码，使用最初双亲码，得到子个体的对应码。映射最初双亲码，得到子个体的对应码。映射关系存在传递关系，则选择未定码交换。关系存在传递关系，则选择未定码交换。14

73、2TSP交叉交叉2:顺序交叉顺序交叉(OX)双亲双亲P1,P2随机选取两个交叉点随机选取两个交叉点1 2 3 4 5 6 7 8 99 3 7 8 2 6 5 1 4P1P2x x x 4 5 6 7 x xx x x 8 2 6 5 x xc1c2 两个交叉点间的中间段保存不变两个交叉点间的中间段保存不变 子个体子个体C1的未定码的确定需要父个体的未定码的确定需要父个体P2的未选定城市码，的未选定城市码，子个体子个体C2的未定码的确定需要父个体的未定码的确定需要父个体P1的未选定城市码。的未选定城市码。143TSP交叉交叉2:顺序交叉顺序交叉(OX)记取父个体记取父个体P2从第二个交叉点开始

74、城市码的排列顺从第二个交叉点开始城市码的排列顺序，当到达表尾时，返回表头继续记录，直到第二序，当到达表尾时，返回表头继续记录，直到第二个交叉点。个交叉点。9 3 7 8 2 6 5 1 4P2x x x 4 5 6 7 x xc13 8 2 4 5 6 7 1 9c13 4 7 8 2 6 5 9 1c2 得到父个体得到父个体P2的排列顺序的排列顺序1-4-9-3-7-8-2-6-5,并将并将C1已有已有城市码城市码4,5,6,7从中去掉，得到排列顺序从中去掉，得到排列顺序1-9-3-8-2，再将此顺，再将此顺序复制到序复制到C1，复制点也是从第二个交叉点开始，得到，复制点也是从第二个交叉点开

75、始，得到C1。同理的同理的C2，144TSP交叉交叉3:循环交叉循环交叉(CX)CX操作中子个体中的城市码顺序根据任一父个体产生操作中子个体中的城市码顺序根据任一父个体产生确定循环编码确定循环编码 复制循环编码到子个体复制循环编码到子个体145TSP变异变异Insert Mutation随机选取个体中两个编码，然后把第二个编码放在第一个编码之后，其他编码顺次调节位置。 S随机选取个体中两个编码，然后交换它们的位置。146TSP变异变异Inversion mutation随机选取个体中一段编码，然后颠倒这段编码的顺序。 Scramble mutation随机选取个体上一段编码,然后打乱这段编码的

76、顺序。选取的编码不一定是邻接编码选取的编码不一定是邻接编码147TSP的的GA过程过程从从N个随机起点开始产生个随机起点开始产生N条路径，条路径，N为种群的规模为种群的规模;利用最优方法搜索每条路径的局部最优解利用最优方法搜索每条路径的局部最优解;选择交叉对使在平均性能之上的个体得到更多的子代选择交叉对使在平均性能之上的个体得到更多的子代;交叉和变异交叉和变异;搜索每条路径得到其极小解，如果不收敛，则回到第搜索每条路径得到其极小解，如果不收敛，则回到第3步；否则，停止。步；否则，停止。148GA的的MATLAB实现实现软件平台软件平台(Software (Software PlatformsP

77、latforms):):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox2.0.1MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美国美国NorthCarolinaStateUniversity开发开发MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox英国英国TheUniversityofSheffield开发开发MATLAB遗传算法工具箱及应用遗传算法工具箱及应用(雷英杰雷英杰等等,西安电

78、子科技西安电子科技大学大学出版社出版社,2005)基于此工具箱基于此工具箱149GAOT工具箱工具箱核心函数：(1)pop=initializega(num,bounds,eevalFN,eevalOps,options)-初始种群的生成函数【输出参数输出参数】pop-生成的初始种群【输入参数输入参数】num-种群中的个体数目bounds-代表变量的上下界的矩阵eevalFN-适应度函数eevalOps-传递给适应度函数的参数options-选择编码形式(浮点编码或是二进制编码)与精度，如typeprec，type-为1时选择浮点编码，否则为二进制编码prec-变量进行二进制编码时指定的精度，

79、默认1e-61150GAOT工具箱工具箱(2)x,endPop,bPop,traceInfo=ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)-遗传算法函数遗传算法函数【输出参数输出参数】x-求得的最优解求得的最优解 endPop-最终得到的种群最终得到的种群 bPop-最优种群的一个搜索轨迹最优种群的一个搜索轨迹 traceInfo-每代种群中最优及平均个体构成的矩阵每代种群中最优及平均个体构成的矩阵【输入参数输入参数】bounds

80、-代表变量上下界的矩阵代表变量上下界的矩阵 evalFN-适应度函数适应度函数 evalOps-传递给适应度函数的参数传递给适应度函数的参数 startPop-初始种群初始种群 151GAOT工具箱工具箱【输入参数】【输入参数】opts- epsilon prob_ops display，opts(1:2)等同于等同于initializega的的options参数，第三个参数控制是否输出，一般参数，第三个参数控制是否输出，一般为为0。如。如1e-6 1 0 termFN-终止函数的名称终止函数的名称,如如maxGenTerm termOps-传递个终止函数的参数传递个终止函数的参数,如如100

81、 selectFN-选择函数的名称选择函数的名称,如如normGeomSelect selectOps-传递个选择函数的参数传递个选择函数的参数,如如0.08 xOverFNs-交叉函数名称表，以空格分开，如交叉函数名称表，以空格分开，如arithXover heuristicXover simpleXover xOverOps-传递给交叉函数的参数表，如传递给交叉函数的参数表，如2 0;2 3;2 0 mutFNs-变异函数表，如变异函数表，如boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation mutOps-传

82、递给交叉函数的参数表传递给交叉函数的参数表,如如4 0 0;6 100 3;4 100 3;4 0 0152GAOT:函数最值函数最值(实例实例)求下列函数的最大值：153GAOT:函数最值函数最值(实例实例2)Fitness.m文件functionsol,eval=fitness(sol,options)x=sol(1);eval=x*sin(10*pi*x)+2.0;MATLAB 运行结果运行结果：154Genetic Algorithm and Direct Search Toolbox (GA&DS)包含工具:遗传算法遗传算法/直接搜索直接搜索运行方式运行方式: command lin

83、e; gatoolGA解决的问题类: 最大化问题要转化为最小化问题 最小化问题155Genetic Algorithm and Direct Search Toolbox (GA&DS)最优化问题最优化问题156案例讲解o同前一个案例讲解问题相同157算例算例2:TSP城市数：城市数：40158算例算例2:TSP城市数：城市数：100159o参考书参考书 1 邢文训邢文训, 谢金星谢金星. 现代优化计算方法现代优化计算方法. 北京北京: 清华清华大学出版社大学出版社, 2005.2 王凌王凌. 智能优化算法及其应用智能优化算法及其应用. 北京北京: 清华大学出清华大学出版社版社, 2001.3

84、 阎平凡阎平凡, 张长水张长水. 人工神经网络与模拟进化计算人工神经网络与模拟进化计算. 北京北京: 清华大学出版社清华大学出版社, 2005.160o参考书参考书 4王小平王小平, 曹立明曹立明. 遗传算法遗传算法理论、应用理论、应用与软件实现与软件实现. 西安西安: 西安交通大学出版社西安交通大学出版社, 2002.5黄席樾等黄席樾等. 现代智能算法理论及应用现代智能算法理论及应用. 北京：北京：科学出版社科学出版社, 2005.6高尚高尚, 杨静宇杨静宇. 群智能算法及其应用群智能算法及其应用. 北京北京: 中国水利水电出版社中国水利水电出版社, 2006.161 思考思考 智能优化计算智能优化计算 用遗传算法解决下面函数的极小值问题：用遗传算法解决下面函数的极小值问题：162Thank you!Thank you!Any question?Any question?