现代优化算法--课件.ppt

《现代优化算法--课件.ppt》由会员分享，可在线阅读，更多相关《现代优化算法--课件.ppt（174页珍藏版）》请在三一文库上搜索。

1、现代优化算法,许志军 2010-8-1,目录,Part 1 概论 Part 2 模拟退火算法 Part 3 遗传算法,Part 1 概论 主要是说明现代优化算法的重要性。,现代优化算法,现代优化算法 禁忌搜索算法 模拟退火算法 遗传算法 人工神经网络 蚁群算法 粒子群算法 混合算法,特点： 基于客观世界中的一些自然现象； 建立在计算机迭代计算的基础上； 具有普适性，可解决实际应用问题。,如何解决问题？,经典数学理论的解法： Viete 定理： 由公理、定理形成的演绎逻辑体系 优点：准确、快速、有明确数学意义 不足：只能解决有限问题、解法是特定 的无法解决高次问题及更复杂问题。,考虑一个一元方

2、程：,数值解法： 通过引入一些假设来获得问题的近似解 取初始值为1，代入得： 1 1.58053 1.57702 1.57705 优点：可求解问题的范围比较广泛 不足：解法的特殊性，要求迭代收敛,如何解决问题？,（1）,传统算法的局限,解法是特定的 - 不同的问题需要使用不同的解法 所能解决的问题是有限的 - 和数学工具直接相关，若没有解 决问题的数学方法，则难以解决,数学建模竞赛中的算法(1),93A 非线性交调的频率设计: 拟合、规划 93B 足球队排名次: 矩阵论、图论、层次分析法、整数规划 94A 逢山开路: 图论、插值、动态规划 94B 锁具装箱问题: 图论、组合数学 95A 飞行管

3、理问题 : 非线性规划、线性规划 95B 天车与冶炼炉的作业调度: 非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法 96A 最优捕鱼策略：微分方程、积分、非线性规划,96B 节水洗衣机：非线性规划 97A 零件参数设计：微积分、非线性规划、随机模拟 97B 截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路 98A 投资收益与风险：线性规划、非线性规划 98B 灾情巡视：最小生成树、Hamilton圈、旅行商问题 99A 自动化车床：积分、概率分布、随机模拟、分布拟合度检验,数学建模竞赛中的算法(2),99B 钻井布局：几何变换、枚举、最大完全子图、混合整数规划

4、 00A DNA分类：神经网络、最小二乘拟合、统计分类 00B 管道订购：最短路、二次规划 01A 血管的三维重建：数据挖掘、曲面重建与拟合 01B 公交车调度：非线性规划 02A 车灯光源优化设计：最优化 02B 彩票中的数学：概率与优化,数学建模竞赛中的算法(3),1. 蒙特卡罗方法(Monte-Carlo方法, MC),数学建模竞赛常用算法(1),该算法又称计算机随机性模拟方法，也称统计试验 方法。MC方法是一种基于“随机数”的计算方法，能够 比较逼真地描述事物的特点及物理实验过程，解决一些 数值方法难以解决的问题。,MC方法的雏型可以追溯到十九世纪后期的蒲丰随机 投针试验，即著名的蒲丰

5、问题。 MC方法通过计算机仿 真(模拟)解决问题，同时也可以通过模拟来检验自己 模型的正确性，是比赛中经常使用的方法。,97年的A题 每个零件都有自己的标定值，也都有自 己的容差等级，而求解最优的组合方案将要面对着的是一 个极其复杂的公式和108种容差选取方案，根本不可能去求 解析解，那如何去找到最优的方案呢？随机性模拟搜索最 优方案就是其中的一种方法，在每个零件可行的区间中按 照正态分布随机的选取一个标定值和选取一个容差值作为 一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从 中选取一个最佳的。 02年的B题 关于彩票第二问，要求设计一种更好的方 案，首先方案的优劣取决于很多复杂的因素，同

6、样不可能 刻画出一个模型进行求解，只能靠随机仿真模拟。,数学建模竞赛常用算法,98 年美国赛A 题 生物组织切片的三维插值处理 94 年A 题逢山开路 山体海拔高度的插值计算,数学建模竞赛常用算法(2),2. 数据拟合、参数估计、插值等数据处理算法,比赛中通常会遇到大量的数据需要处理，而处理数 据的关键就在于这些算法，通常使用MATLAB 作为工 具。与图形处理有关的问题很多与拟合有关系。,此类问题在MATLAB中有很多函数可以调用，只有熟 悉MATLAB，这些方法才能用好。,98年B 题 用很多不等式完全可以把问题刻画清楚,数学建模竞赛常用算法(3),3. 规划类问题算法,此类问题主要有线性

7、规划、整数规划、多元规划、 二次规划等。竞赛中很多问题都和数学规划有关，可以 说不少的模型都可以归结为一组不等式作为约束条件、 几个函数表达式作为目标函数的问题，遇到这类问题， 求解就是关键了。,因此列举出规划后用Lindo、Lingo 等软件来进行解决 比较方便，所以还需要熟悉这两个软件。,98 年B 题、00年B 题、95 年锁具装箱等问题体现了图论问题的重要性。,数学建模竞赛常用算法(4),4. 图论问题,这类问题算法有很多，包括：Dijkstra、Floyd、 Prim、Bellman-Ford，最大流，二分匹配等问题。,92 年B 题用分枝定界法 97 年B 题是典型的动态规划问题

8、98 年B 题体现了分治算法,数学建模竞赛常用算法(5),5. 计算机算法设计中的问题,计算机算法设计包括很多内容：动态规划、回溯搜 索、分治算法、分枝定界等计算机算法.,这方面问题和ACM 程序设计竞赛中的问题类似， 可看一下与计算机算法有关的书。,97年A 题用模拟退火算法 00年B 题用神经网络分类算法 01年B 题这种难题也可以使用神经网络 美国89年A 题也和BP 算法有关系 美国03年B 题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。,数学建模竞赛常用算法(6),6. 最优化理论的三大非经典算法: 模拟退火法(SA)、神经网络(NN)、遗传算法(GA),近几年的赛题越来

9、越复杂，很多问题没有什么很好的 模型可以借鉴，于是这三类算法很多时候可以派上用场。,97 年A 题、99 年B 题都可以用网格法搜索,数学建模竞赛常用算法(7),网格算法和穷举法一样，只是网格法是连续问题的穷 举。此类算法运算量较大。,7. 网格算法和穷举算法,这种方法最好在运算速度较快的计算机中进行，还有 要用高级语言来做，最好不要用MATLAB 做网格，否则 会算很久的。,很多问题都是实际来的，数据可以是连续的，而计 算机只能处理离散的数据，因此需要将连续问题进行 离散化处理后再用计算机求解。比如差分代替微分、 求和代替积分等思想都是把连续问题离散化的常用方 法。,数学建模竞赛常用算法(8

10、),8. 连续问题离散化的方法,数值分析研究各种求解数学问题的数值计算方法， 特别是适合于计算机实现方法与算法。,数学建模竞赛常用算法(9),9. 数值分析方法,它的主要内容包括函数的数值逼近、数值微分与数 值积分、非线性方程的数值解法、数值代数、常微分方 程数值解等。数值分析是计算数学的一个重要分支，把 理论与计算紧密结合,是现代科学计算的基础 。,MATLAB等数学软件中已经有很多数值分析的函 数可以直接调用。,01年A 题中需要你会读BMP 图象 98年美国A 题需要你知道三维插值计算 03年B 题要求更高，不但需要编程计算还要进行处理,数学建模竞赛常用算法(10),10. 图象处理算法

11、,赛题中有一类问题与图形有关，即使问题与图形无 关，论文中也会需要图片来说明问题，这些图形如何展 示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。,数模论文中也有很多图片需要展示，解决这类问题 要熟悉MATLAB图形图像工具箱。,最优化问题(Optimization Problem),最优化问题:,组合优化问题(Combinatorial Optimization Problem ) : 最优化问题中的解空间X或S由离散集合构成。其中很 多问题是NP完全(Nondeterministic Polynomial Completeness)问题.,待解决的问题 连续性问题，以微积

12、分为基础，规模较小 传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性、收敛速度,传统优化方法,现代优化算法,现代优化算法又称智能优化算法或现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。,待解决的问题 离散性、不确定性、大规模 现代的优化方法 启发式算法（heuristic algorithm） 追求满意（近似解） 实用性强（解决实际工程问题） 现代的评价

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

14、Genetic Algorithm，简称GA 模拟退火算法 Simulated Annealing，简称SA 禁忌搜索算法 Tabu Search，简称TS ,常用的现代优化算法（续） 神经网络算法 群智能算法，包括蚁群算法(Ant Colony Optimization)、粒子群算法(Particle Swarm Optimization) 微分进化算法（Differential Evolution）,智能优化计算,搜索示例：三个孩子的年龄(1),两个多年未见的朋友相遇，聊了很多事情。,A：既然你是数学教授，那你帮我算这个题，今天是 个特殊日子：我三个儿子都在今天庆祝生日！那么你 能算出他们

15、都有多大吗？,B：好，但你得跟我讲讲他们的情况。,A：好的，我给你一些提示，他们三个年龄之积是36.,B：很好，但我还需要更多提示。,三个孩子的年龄(2),A：我的大儿子的眼睛是蓝色的。,B考虑了一下说，但是，我还有一点信息来解决你的这 个难题。,B：哦，够了，,B给出了正确的答案，即三个小孩的年龄。,A：他们三个年龄之和等于那幢房子的窗户个数。,A指着对面的一幢房子说。,三个孩子的年龄(3),根据对话信息，用搜索的方法来解此问题。,信息1:三个小孩年龄之积为36,只有以下8种可能，搜索范围减少至8种情况:,三个孩子的年龄(4),信息2:三个小孩年龄之和等于窗户数,窗户数: 38 21 16

16、14 13 13 11 10,如果窗户数为38、21、16、14、11、10即可得出答案,B还需信息，即窗户数为13.,则可能为(9、2、2)或(6、6、1),信息2:大儿子眼睛是蓝色的,得答案：(9、2、2),典型问题旅行商问题（Traveling salesman problem, TSP） 给定n个城市和两两 城市之间的距离，要 求确定一条经过各城 市当且仅当一次的最 短路线。,1,2,3,4,12,1,8,10,3,2,搜索示例：TSP问题,典型问题旅行商问题（Traveling salesman problem, TSP） 计算复杂度：指数灾难,TSP的搜索的困难,Part 2 模拟

17、退火法,模拟退火算法及模型,算法的提出 模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。 算法的目的 解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。,物理退火过程,物理退火过程 什么是退火： 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,物理退火过程,模拟退火算法及模型,智能优化计算,物理退火过程 加温过程增强粒子的热运动，消除系统原先可能存在的非均匀态； 等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自

18、由能减少的方向进行，当自由能达到最小时，系统达到平衡态； 冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,物理退火过程,模拟退火算法及模型,智能优化计算,数学表述 在温度T，分子停留在状态r满足Boltzmann概率分布,物理退火过程,模拟退火算法及模型,智能优化计算,数学表述 在同一个温度T，选定两个能量E1E2，有 在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。,物理退火过程,1,0,模拟退火算法及模型,智能优化计算,数学表述 若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合： 当温度很高时，每个状态概率基本相同，接

19、近平均值1/|D|； 状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D| ； 当温度趋于0时，分子停留在最低能量状态的概率趋于1。,物理退火过程,能量最低状态 非能量最低状态,模拟退火算法及模型,智能优化计算,Metropolis准则（1953）以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,物理退火过程,模拟退火算法及模型,智能优化计算,Metropolis准则（1953）以概率接受新状态 若在温度T，当前状态i 新状态j 若EjEi，

20、则接受 j 为当前状态； 否则，若概率 p=exp-(Ej-Ei)/kBT 大于0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。,物理退火过程,模拟退火算法及模型,智能优化计算,Metropolis准则（1953）以概率接受新状态 p=exp-(Ej-Ei)/kBT 在高温下，可接受与当前状态能量差较大的新状态； 在低温下，只接受与当前状态能量差较小的新状态。,物理退火过程,模拟退火算法及模型,智能优化计算,相似性比较,组合优化与物理退火的相似性,算法描述,案例讲解,已知敌方100个目标的经度、纬度 我方有一个基地，经度和纬度为（70,40）。假设我方飞

21、机的速度为1000公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。,模拟退火算法及模型,智能优化计算,基本步骤 给定初温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 算法终止准则满足； 输出算法搜索结果。,模拟退火算法的基本思想和

22、步骤,模拟退火算法及模型,智能优化计算,影响优化结果的主要因素 给定初温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)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概

23、率； (2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。 方法 具体形式对算法影响不大 一般采用min1,exp(-C/t),状态接受函数,模拟退火算法关键参数和操作的设计,智能优化计算,收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数； 初温应充分大； 实验表明 初温越大，获得高质量解的机率越大，但花费较多的计算时间；,初温,模拟退火算法关键参数和操作的设计,智能优化计算,方法 （1）均匀抽样一组状态，以各状态目标值得方差为初温； （2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一

24、定的函数确定初温； （3）利用经验公式。,初温,模拟退火算法关键参数和操作的设计,智能优化计算,时齐算法的温度下降函数 （1） ，越接近1温度下降越慢，且其大小可以不断变化； （2） ，其中t0为起始温度，K为算法温度下降的总次数。,温度更新函数,模拟退火算法关键参数和操作的设计,智能优化计算,非时齐模拟退火算法 每个温度下只产生一个或少量候选解 时齐算法常用的Metropolis抽样稳定准则 （1）检验目标函数的均值是否稳定； （2）连续若干步的目标值变化较小； （3）按一定的步数抽样。,内循环终止准则,模拟退火算法关键参数和操作的设计,智能优化计算,常用方法 （1）设置终止温度的阈值； （

25、2）设置外循环迭代次数； （3）算法搜索到的最优值连续若干步保持不变； （4）概率分析方法。,外循环终止准则,智能优化计算,模拟退火算法的优点 质量高； 初值鲁棒性强； 简单、通用、易实现。 模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,模拟退火算法的优缺点,模拟退火算法的实现与应用,智能优化计算,30城市TSP问题（d*=423.741 by D B Fogel）,TSP Benchmark 问题 41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;

26、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 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 50,模拟退火算法的实现与应用,智能优化计算,算法流程,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,初始温度的计算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min

27、(fval0)/log(0.9);,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,状态产生函数的设计 （1）互换操作，随机交换两个城市的顺序； （2）逆序操作，两个随机位置间的城市逆序； （3）插入操作，随机选择某点插入某随机位置。,30城市TSP问题（d*=423.741 by D B Fogel）,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,模拟退火算法的实现与应用,智能优化计算,参数设定 截止温度 tf=0.01; 退温系数 alpha=0.90; 内循环次数

28、L=200*CityNum;,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,运行过程,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,运行过程,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,运行过程,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,运行过程,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与

29、应用,智能优化计算,运行过程,30城市TSP问题（d*=423.741 by D B Fogel）,模拟退火算法的实现与应用,智能优化计算,运行结果,30城市TSP问题（d*=423.741 by D B Fogel）,算法的改进,(1) 设计合适的状态产生函数，使其根据搜索进程的需要 表现出状态的全空间分散性或局部区域性。 (2) 设计高效的退火策略。 (3) 避免状态的迂回搜索。 (4) 采用并行搜索结构。 (5) 为避免陷入局部极小，改进对温度的控制方式 (6) 选择合适的初始状态。 (7) 设计合适的算法终止准则。,算法的改进,也可通过增加某些环节而实现对模拟退火算法的改进。主要的改

30、进方式包括： (1) 增加升温或重升温过程。在算法进程的适当时机，将温度适当提 高，从而可激活各状态的接受概率，以调整搜索进程中的当前状 态，避免算法在局部极小解处停滞不前。 (2) 增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失 当前遇到的最优解，可通过增加存储环节，将“Best So Far”的状 态记忆下来。 (3) 增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为 初始状态，再次执行模拟退火过程或局部性搜索。 (4) 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优 状态，而非标准SA的单次比较方式。 (5) 结合其他搜索机制的算法，如遗传算法、混沌搜索等。

31、(6)上述各方法的综合应用。,Part 3 遗传算法,遗传算法(Genetic Algorithm),进化算法(Evolutionary Algorithm),遗传算法(GA),Darwin(1859): “物竟天择，适者生存” John Holland (university of Michigan, 1975) Adaptation in Natural and Artificial System 遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。 遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式

32、对目标空间进行随机化搜索。,遗传算法模拟自然选择和自然遗传过程中发生 的繁殖、交叉和基因突变现象，在每次迭代中 都保留一组候选解，并按某种指标从解群中选 取较优的个体，利用遗传算子(选择、交叉和变 异)对这些个体进行组合，产生新一代的候选解 群，重复此过程，直到满足某种收敛指标为止。,遗传算法的搜索机制,遗传算法(GA),We have a dream!,I am at the top Height is .,I am not at the top. My high is better!,I will continue,遗传算法(GA),GA-第0代,Dead one,New one,遗传算法

33、(GA),GA-第1代,Not at the top, Come Up!,遗传算法(GA),GA-第?代,I am the BEST !,遗传算法(GA),GA-第N代,适者生存(Survival of the Fittest) GA主要采用的进化规则是“适者生存” 较好的解保留，较差的解淘汰,遗传算法(GA),基本遗传算法,基本遗传算法（Simple Genetic Algorithms, 简称SGA）是一种统一的最基本的遗传算法，它只 使用选择、交叉、变异这三种基本遗传算子，其遗传 进化操作过程简单，容易理解，是其他一些遗传算法 的雏形和基础，它不仅给各种遗传算法提供了一个基 本框架，同时

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

35、y,染色体长度L决定可行解的最大精度,长染色体(慢进化),SGA实例2 : 编码,设定求解精确到6位小数，因区间长度位2-(-1)=3,则需将区 间分为3X106等份。因 2097152221 3X106222 4194304。故编码的二进制串长L=22。,将一个二进制串(b21b20b0)转化为10进制数：,e.g. -1; 2 1.627 888 1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3x3674053/(222-1),SGA实例2 : 初始化种群、适应函数,随机初始化种群 适应函数 本实例目标函数在定义域内均大于

36、0，且是求函数最大值，故直接引用目标函数作为适应函数： f(s) = f(x) 其中二进制串s对于变量x的值。 e.g. s1 = x1= -0.958 973 适应值: f(s1) = f(x1) =1.078 878 s2= x2= 1.627 888 适应值: f(s2) = f(x2) = 3.250 650,SGA实例2 :遗传操作,选择操作(“轮盘赌”选择) 交叉操作(单点交叉) 交叉前(父): s1= s2= 交叉后(子): s1= s2= 适应值: f(s1) = f(-0.998 113) =1.940 865 f(s2) = f(1.666 028) = 3.459 245

37、 s2的适应值比其双亲个体的适应值高。,SGA实例2 :遗传操作,变异操作 变异前(父): s2= 变异后(子): s2= 适应值 f(s2) = f(1.721 638) = 0.917 743 比 f(s2)小 变异前(父): s2= 变异后(子): s”2= 适应值 f(s”2) = f(1.630 818) = 3.343 555 比 f(s2)大,变异操作有”扰动”作用，同时具有增加种群多 样性的效果。,SGA实例2 :模拟结果,遗传算法的参数: 种群规模: 50 染色体长度: L=22 最大进化代数: 150 交叉概率: Pc=0.25 变异概率: Pm=0.01,SGA实例2 :

38、模拟结果(最佳个体进化情况),遗传算法简介,达尔文的自然选择说 遗传（heredity）：子代和父代具有相 同或相似的性状，保证物种的稳定性； 变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源； 生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 染色体（chromosome）：遗传物质的载体； 脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构； 遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位

39、；,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 基因型（genotype）：遗传因子组合的模型； 表现型（phenotype）：由染色体决定性状的外部表现；,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 基因座（locus）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）； 个体（individual）：指染色体带有特征的实体； 种群（population）：个体的集合，该集合内个体数称为种群的大小；,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 进化（evolution）：生物在其延续

40、生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化； 适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;,生物进化理论和遗传学的基本知识,遗传算法简介,智能优化计算,遗传学基本概念与术语 选择（selection）：指决定以一定的概率从种群中选择若干个体的操作 ； 复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因; 交叉（crossover）：在两个染色体的某一相

41、同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;,生物进化理论和遗传学的基本知识,遗传算法简介,智能优化计算,遗传学基本概念与术语 变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状; 编码（coding）：表现型到基因型的映射； 解码（decoding）：从基因型到表现型的映射。,生物进化理论和遗传学的基本知识,遗传算法简介,智能优化计算,进化论与遗传学的融合 19301947年，达尔文进化论与遗传学走向融合，Th. Dobzhansky1937年发表

42、的遗传学与物种起源是融合进化论与遗传学的代表作。 生物进化与智能学的关系 生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。,生物进化理论和遗传学的基本知识,遗传算法简介,智能优化计算,遗传算法的基本思路,遗传算法的思路与特点,遗传算法简介,智能优化计算,自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。 本质并行性 内在并行性与内含并行性 不需求导 只需目标函数和适应度函数 概率转换规则 强调概率转换规则，而不是确定的转换规则,遗传算法的思路与特点,遗传算法简

43、介,智能优化计算,选择 适应度计算： 按比例的适应度函数（proportional fitness assignment） 基于排序的适应度计算（Rank-based fitness assignment） 选择算法： 轮盘赌选择（roulette wheel selection）,遗传算法的基本操作,遗传算法简介,智能优化计算,选择 选择算法： 随机遍历抽样（stochastic universal selection） 局部选择（local selection） 截断选择（truncation selection） 锦标赛选择（tournament selection）,遗传算法的基本操作

44、,遗传算法简介,智能优化计算,交叉或基因重组 实值重组（real valued recombination）： 离散重组（discrete recombination） 中间重组（intermediate recombination） 线性重组（linear recombination） 扩展线性重组（extended linear recombination）,遗传算法的基本操作,遗传算法简介,智能优化计算,交叉或基因重组 二进制交叉（binary valued crossover）： 单点交叉（single-point crossover） 多点交叉（multiple-point cros

45、sover） 均匀交叉（uniform crossover） 洗牌交叉（shuffle crossover） 缩小代理交叉（crossover with reduced surrogate）,遗传算法的基本操作,遗传算法简介,智能优化计算,变异 实值变异 二进制变异,遗传算法的基本操作,生物进化与遗传算法对应关系,遗传算法的基本操作,选择(selection): 根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。 交叉(crossover): 将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc (称为交叉概率

46、，crossvoer rate)交换它们之间的部分染色体。 变异(mutation): 对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。,如何设计遗传算法,如何进行编码？ 如何产生初始种群？ 如何定义适应函数？ 如何进行遗传操作(复制、交叉、变异)？ 如何产生下一代种群？ 如何定义停止准则？,编码(Coding),选择(Selection),选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中 主要思想: 适应值较高的染色体体有较大的选择(复制)机会 实现1：”轮盘赌”选择(Roule

47、tte wheel selection) 将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率Ps 产生一个在0与总和之间的的随机数m 从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于m,选择(Selection),设种群的规模为N xi是i为种群中第i个染色体,染色体xi被选概率,选择(Selection),染色体的适应值和所占的比例,轮盘赌选择,选择(Selection),染色体被选的概率,被选的染色体,选择(Selection),轮盘上的片分配给群体的染色体，使得每一个片的大小与对于染色体的适应值成比例 从群体中选择一个染色体可视

48、为旋转一个轮盘，当轮盘停止时，指针所指的片对于的染色体就时要选的染色体。 模拟“轮盘赌” 算法： r=random(0, 1)，s=0，i=0； 如果sr，则转(4)； s=s+p(xi)，i=i+1, 转(2) xi即为被选中的染色体，输出I 结束,选择(Selection),其他选择法： 随机遍历抽样(Stochastic universal sampling) 局部选择(Local selection) 截断选择(Truncation selection) 竞标赛选择(Tournament selection) 特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体

49、，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。,交叉(crossover, Recombination),遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。 选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。 交叉产生两个子染色体，他们与其父代不同，且彼此不同, 每个子染色体都带有双