遗传算法综述及简单应用实例的Matlab程序.ppt

《遗传算法综述及简单应用实例的Matlab程序.ppt》由会员分享，可在线阅读，更多相关《遗传算法综述及简单应用实例的Matlab程序.ppt（186页珍藏版）》请在装配图网上搜索。

1、智能优化计算 华东理工大学自动化系 2010年 1 遗传算法 综述及简单应用实例 及 Matlab程序 智能优化计算 华东理工大学自动化系 2010年 2 4.1 遗传算法简介 4.1.1 遗传算法的产生与发展 4.1.2 生物进化理论和遗传学的基本知识 4.1.3 遗传算法的思路与特点 4.1.4 遗传算法的基本操作 4.1.5 遗传算法的应用 4.2 基本遗传算法 4.2.1 简单函数优化的实例 4.2.2 遗传基因型 4.2.3 适应度函数及其尺度变换 4.2.4 遗传操作 选择 4.2.5 遗传操作 交叉 /基因重组 4.2.6 遗传操作 变异 4.2.7 算法的设计与实现 4.2.8

2、 模式定理 智能优化计算 华东理工大学自动化系 2010年 3 4.1 遗传算法简介 产生 早 在 50年代 ， 一些生物学家开始研究运用数字计算 机模拟生物的自然遗传 与自然进化过程 ； 1963年 ，德国柏林技术大学的 I. Rechenberg和 H. P. Schwefel，做风洞实验时，产生了 进化策略 的初步 思想； 60年代， L. J. Fogel在设计有限态自动机时提出 进 化规划 的思想。 1966年 Fogel等出版了 基于模拟 进化的人工智能 ，系统阐述了进化规划的思想。 4.1.1 遗传算法的产生与发展 智能优化计算 华东理工大学自动化系 2010年 4 4.1 遗传

3、算法简介 产生 60年代中期， 美国 Michigan大学的 J. H. Holland教 授 提出 借鉴生物自然遗传的基本原理 用于自然 和人工系统的自适应行为研究和串编码技术； 1967年，他的学生 J. D. Bagley在博士论文中首次提 出“遗传算法 (Genetic Algorithms)”一词 ； 1975年 ， Holland出版了著名的“ Adaptation in Natural and Artificial Systems”，标志 遗传算法的 诞生 。 4.1.1 遗传算法的产生与发展 智能优化计算 华东理工大学自动化系 2010年 5 4.1 遗传算法简介 发展 70年

4、代初， Holland提出了“模式定理”（ Schema Theorem），一般认为是“遗传算法的基本定理”， 从而奠定了遗传算法研究的理论基础； 1985年，在美国召开了第一届遗传算法国际会议， 并且成立了国际遗传算法学会 (ISGA， International Society of Genetic Algorithms)； 4.1.1 遗传算法的产生与发展 智能优化计算 华东理工大学自动化系 2010年 6 4.1 遗传算法简介 发展 1988年， Holland的学生 D. J. Goldherg出版了 “ Genetic Algorithms in Search, Optimizat

5、ion, and Machine Learning”，对遗传算法及其应用作了全 面而系统的论述； 1991年， L. Davis编辑出版了 Handbook of genetic algorithms ，其中包括了遗传算法在工程 技术和社会生活中大量的应用实例。 4.1.1 遗传算法的产生与发展 智能优化计算 华东理工大学自动化系 2010年 7 4.1 遗传算法简介 达尔文的自然选择说 遗传（ heredity）：子代和父代具有相 同或相似的性状，保证物种的稳定性； 变异（ variation）：子代与父代，子代不同个体之 间总有差异，是生命多样性的根源； 生存斗争和适者生存：具有适应性变异

6、的个体被保 留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。 4.1.2 生物进化理论和遗传学的基本知识 智能优化计算 华东理工大学自动化系 2010年 8 4.1 遗传算法简介 遗传学 (Genetics)基本 概念与术语 染色体（ chromosome）：遗传物质的载体； 脱氧核糖核酸（ DNA）：大分子有机聚合物，双 螺旋结构； 遗传因子（ gene）： DNA或 RNA长链结构中占有 一定位臵的基本遗传单位； 4.1.2 生物进化理论和遗传学的基本知识 智能优化计算 华东理工大学自动化系 2010年 9 4.1 遗传算法简介 遗传学基本概念与术语 基因型（

7、genotype）：遗传因子组合的模型； 表现型（ phenotype）：由染色体决定性状的外部 表现； 4.1.2 生物进化理论和遗传学的基本知识 1 1 1 1 1 1 1 1 1 1 0 1 1 1 智能优化计算 华东理工大学自动化系 2010年 10 4.1 遗传算法简介 遗传学基本概念与术语 基因座（ locus）：遗传基因在染色体中所占据的 位臵，同一基因座可能有的全部基因称为等位基因 （ allele）； 个体（ individual）：指染色体带有特征的实体； 种群（ population）：个体的集合，该集合内个体 数称为种群的大小； 4.1.2 生物进化理论和遗传学的基本知

8、识 智能优化计算 华东理工大学自动化系 2010年 11 4.1 遗传算法简介 遗传学基本概念与术语 进化（ evolution）：生物在其延续生存的过程中， 逐渐适应其生存环境，使得其品质不断得到改良， 这种生命现象称为进化； 适应度（ fitness）：度量某个物种对于生存环境的 适应程度。对生存环境适应程度较高的物种将获得 更多的繁殖机会，而对生存环境适应程度较低的物 种，其繁殖机会就会相对较少，甚至逐渐灭绝 ; 4.1.2 生物进化理论和遗传学的基本知识 智能优化计算 华东理工大学自动化系 2010年 12 4.1 遗传算法简介 遗传学基本概念与术语 选择（ selection）：指决

9、定以一定的概率从种群中 选择若干个体的操作 ； 复制（ reproduction）：细胞在分裂时，遗传物质 DNA通过复制而转移到新产生的细胞中，新的细 胞就继承了旧细胞的基因 ; 交叉（ crossover）：在两个染色体的某一相同位臵 处 DNA被切断，其前后两串分别交叉组合形成两 个新的染色体。又称基因重组，俗称“杂交” ; 4.1.2 生物进化理论和遗传学的基本知识 智能优化计算 华东理工大学自动化系 2010年 13 4.1 遗传算法简介 遗传学基本概念与术语 变异（ mutation）：在细胞进行复制时可能以很小 的概率产生某些复制差错，从而使 DNA发生某种 变异，产生出新的染色

10、体，这些新的染色体表现出 新的性状 ; 编码（ coding）：表现型到基因型的映射； 解码（ decoding）：从基因型到表现型的映射。 4.1.2 生物进化理论和遗传学的基本知识 智能优化计算 华东理工大学自动化系 2010年 14 4.1 遗传算法简介 进化论与遗传学的融合 1930 1947年，达尔文进化论与遗传学走向融合， Th. Dobzhansky1937年发表的 遗传学与物种起源 是融合进化论与遗传学的代表作。 生物进化与智能学的关系 生物物种作为复杂系统，具有奇妙的自适应、自组 织和自优化能力，这是一种生物在进化过程中体现 的智能，也是人工系统梦寐以求的功能。 4.1.2

11、生物进化理论和遗传学的基本知识 智能优化计算 华东理工大学自动化系 2010年 15 4.1 遗传算法简介 遗传算法的基本思路 4.1.3 遗传算法的思路与特点 智能优化计算 华东理工大学自动化系 2010年 16 4.1 遗传算法简介 自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法 将利用进化过程中获得的信息自行组织搜索。 本质并行性 内在并行性与内含并行性 不需求导 只需目标函数和适应度函数 概率转换规则 强调概率转换规则，而不是确定的转换规则 4.1.3 遗传算法的思路与特点 智能优化计算 华东理工大学自动化系 2010年 17 4.1 遗传算法简介 简单实例 1

12、. 产生初始种群 2. 计算适应度 4.1.4 遗传算法的基本操作 0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 （ 8） （ 5） （ 2） （ 10） （ 7） （ 12） （ 5） （ 19） （ 10） （ 14） 智能优化计算 华东理工大学自动化系 2010年 18 4.1 遗传算法简介 简单实例 3. 选择 4.1.4 遗传算法的基本操作 个体 染色体 适应度 选择概率 累积概率 1 0001100000 8

13、2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 8 8 5 2 10 7 12 5 19 10 14 0.086957 5 8 5 2 10 7 12 5 19 10 14 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174 智能优化计算 华东理工大学自动

14、化系 2010年 19 4.1 遗传算法简介 简单实例 3. 选择 4.1.4 遗传算法的基本操作 个体 染色体 适应度 选择概率 累积概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 0.086957 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0

15、.108696 0.152174 0.086957 0.141304 0.163043 0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000 智能优化计算 华东理工大学自动化系 2010年 20 4.1 遗传算法简介 简单实例 3. 选择 在 0 1之间产生一个 随机数： 4.1.4 遗传算法的基本操作 个体 染色体 适应度 选择概率 累积概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 1

16、2 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 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

17、0.716340 0.270901 0.371435 0.854641 淘汰！ 淘汰！ 智能优化计算 华东理工大学自动化系 2010年 21 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 4.1 遗传算法简介 简单实例 4. 交叉 4.1.4 遗传算法的基本操作 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1001

18、110100 1100000001 0001010011 0001 1 0 100000 01 110 111 100 0 01 0 1 10 1 00111 0100 0001 1001110100 1 0000001 1010101 0001010 010 011 智能优化计算 华东理工大学自动化系 2010年 22 4.1 遗传算法简介 简单实例 5. 变异 4.1.4 遗传算法的基本操作 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0

19、001010011 0001 1 0 100000 01 110 111 100 0 01 0 1 10 1 1001 1 0100 0001 1001110100 1 0000001 1010101 0001010 010 011 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001 1 0 100000 01 110 111 100 0 01 0 1 10 1 100111 0100 0001 1001110100

20、1 0000001 1010101 0001010 010 011 智能优化计算 华东理工大学自动化系 2010年 23 4.1 遗传算法简介 简单实例 6. 至下一代，适应度计算 选择 交叉 变异，直 至满足终止条件。 4.1.4 遗传算法的基本操作 智能优化计算 华东理工大学自动化系 2010年 24 4.1 遗传算法简介 选择 1.适应度计算 ： 按比例的适应度函数（ proportional fitness assignment） 基于排序的适应度计算（ Rank-based fitness assignment） 4.1.4 遗传算法的基本操作 智能优化计算 华东理工大学自动化系 2

21、010年 25 4.1 遗传算法简介 选择 2.选择算法 ： 轮盘赌选择（ roulette wheel selection） 随机遍历抽样（ stochastic universal selection） 局部选择（ local selection） 截断选择（ truncation selection） 锦标赛选择（ tournament selection） 4.1.4 遗传算法的基本操作 智能优化计算 华东理工大学自动化系 2010年 26 4.1 遗传算法简介 交叉或基因重组 实值重组（ real valued recombination） ： 离散重组（ discrete reco

22、mbination） 中间重组（ intermediate recombination） 线性重组（ linear recombination） 扩展线性重组（ extended linear recombination） 4.1.4 遗传算法的基本操作 智能优化计算 华东理工大学自动化系 2010年 27 4.1 遗传算法简介 交叉或基因重组 二进制交叉（ binary valued crossover） ： 单点交叉（ single-point crossover） 多点交叉（ multiple-point crossover） 均匀交叉（ uniform crossover） 洗牌交叉（

23、 shuffle crossover） 缩小代理交叉（ crossover with reduced surrogate） 4.1.4 遗传算法的基本操作 智能优化计算 华东理工大学自动化系 2010年 28 4.1 遗传算法简介 变异 实值变异 二进制变异 4.1.4 遗传算法的基本操作 智能优化计算 华东理工大学自动化系 2010年 29 4.1 遗传算法简介 函数优化 是遗传算法的经典应用领域 ; 组合优化 实践证明，遗传算法对于组合优化中的 NP完全问 题非常有效 ; 自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传 算法的参数辨识、利用遗传算法进行人工神经网络 的结构优化设计和

24、权值学习等 ; 4.1.5 遗传算法的应用 智能优化计算 华东理工大学自动化系 2010年 30 4.1 遗传算法简介 机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人 运动轨迹规划、机器人逆运动学求解、细胞机器人 的结构优化和行动协调等 ; 组合图像处理和模式识别 目前已在图像恢复、图像边缘持征提取、几何形状 识别等方面得到了应用 ; 4.1.5 遗传算法的应用 智能优化计算 华东理工大学自动化系 2010年 31 4.1 遗传算法简介 人工生命 基于遗传算法的进化模型是研究人工生命现象的重 要理论基础，遗传算法已在其进化模型、学习模型、 行为模型等方面显示了初步的应用能力； 遗

25、传程序设计 Koza发展了遗传程序设计的慨念，他使用了以 LISP语言所表示的编码方法，基于对一种树型结 构所进行的遗传操作自动生成计算机程序。 4.1.5 遗传算法的应用 智能优化计算 华东理工大学自动化系 2010年 32 4.1 遗传算法简介 4.1.1 遗传算法的产生与发展 4.1.2 生物进化理论和遗传学的基本知识 4.1.3 遗传算法的思路与特点 4.1.4 遗传算法的基本操作 4.1.5 遗传算法的应用 4.2 基本遗传算法 4.2.1 简单函数优化的实例 4.2.2 遗传基因型 4.2.3 适应度函数及其尺度变换 4.2.4 遗传操作 选择 4.2.5 遗传操作 交叉 /基因重

26、组 4.2.6 遗传操作 变异 4.2.7 算法的设计与实现 4.2.8 模式定理 智能优化计算 华东理工大学自动化系 2010年 33 4.2 基本遗传算法 问题的提出 一元函数求最大值： 4.2.1 简单函数优化的实例 2,1 0.2)10s i n ()( xxxxf 智能优化计算 华东理工大学自动化系 2010年 34 4.2 基本遗传算法 问题的提出 用微分法求取 f(x)的最大值： 解有无穷多个： 4.2.1 简单函数优化的实例 xx xxxxf 10)10t a n ( 0)10c o s (10)10s i n ()( 即 的实数递减序列。一接近于 是及 ， 0 ),2,1,2

27、,1( ,2,1 , 20 12 0 ,2,1 , 20 12 0 ii i i x x i i x i ii ii 智能优化计算 华东理工大学自动化系 2010年 35 4.2 基本遗传算法 问题的提出 当 i为奇数时 xi对应局部极大值点， i为偶数时 xi对应 局部极小值。 x19即为区间 -1,2内的最大值点： 此时，函数最大值 f(x19)比 f(1.85)=3.85稍大。 4.2.1 简单函数优化的实例 191919 85.120 37 x 智能优化计算 华东理工大学自动化系 2010年 36 4.2 基本遗传算法 编码 表现型： x 基因型：二进制编码（串长取决于求解精度） 串长

28、与精度之间的关系 ： 若要求求解精度到 6位小数，区间长度为 2-(-1) 3， 即需将区间分为 3/0.000001=3 106等份。 所以编码的二进制串长应为 22位。 4.2.1 简单函数优化的实例 41 9 43 04230 0 00 00220 9 71 52 2221 智能优化计算 华东理工大学自动化系 2010年 37 4.2 基本遗传算法 产生初始种群 产生的方式：随机 产生的结果：长度为 22的二进制串 产生的数量：种群的大小（规模），如 30， 50， 1111010011100001011000 1100110011101010101110 101010001111001

29、0000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 4.2.1 简单函数优化的实例 智能优化计算 华东理工大学自动化系 2010年 38 4.2 基本遗传算法 计算适应度 不同的问题有不同的适应度计算方法 本例：直接用目标函数作为适应度函数 将某个体转化为 -1,2区间的实数： s= x=0.637197 计算 x的函数值（适应度）： f(x)=xsin(10 x)+2.0=2.586345 4.2.1 简单函数优化的实例 智能优化计算 华东理工大学自动化系 2010年 39 4.2 基本遗传

30、算法 计算适应度 二进制与十进制之间的转换 ： 第一步，将一个二进制串（ b21b20 b0）转化为 10进制 数： 第二步， x对应的区间 -1,2内的实数： 4.2.1 简单函数优化的实例 )2()( 10 21 0 202021 xbbbb i i i 12 )1(20.1 22 xx (0000000000000000000000) -1 (1111111111111111111111)2 智能优化计算 华东理工大学自动化系 2010年 40 4.2 基本遗传算法 遗传操作 选择：轮盘赌选择法； 交叉：单点交叉； 变异：小概率变异 4.2.1 简单函数优化的实例 智能优化计算 华东理工

31、大学自动化系 2010年 41 4.2 基本遗传算法 模拟结果 设臵的参数 ： 种群大小 50；交叉概率 0.75；变异概率 0.05；最大 代数 200。 得到的最佳个体 ： smax=; xmax=1.8506; f(xmax)=3.8503; 4.2.1 简单函数优化的实例 智能优化计算 华东理工大学自动化系 2010年 42 4.2 基本遗传算法 模拟结果 进化的过程 ： 4.2.1 简单函数优化的实例 世代数 自变量 适应度 1 1.4495 3.4494 9 1.8395 3.7412 17 1.8512 3.8499 30 1.8505 3.8503 50 1.8506 3.85

32、03 80 1.8506 3.8503 120 1.8506 3.8503 200 1.8506 3.8503 智能优化计算 华东理工大学自动化系 2010年 43 4.2 基本遗传算法 编码原则 完备性（ completeness）：问题空间的所有解都能 表示为所设计的基因型； 健全性（ soundness）：任何一个基因型都对应于 一个可能解； 非冗余性（ non-redundancy）：问题空间和表达空 间一一对应。 4.2.2 遗传基因型 智能优化计算 华东理工大学自动化系 2010年 44 4.2 基本遗传算法 多种编码方式 二进制编码； 浮点数编码； 格雷码编码； 符号编码； 复数

33、编码； DNA编码等。 4.2.2 遗传基因型 智能优化计算 华东理工大学自动化系 2010年 45 4.2 基本遗传算法 二进制编码与浮点数编码的比较 在交叉操作时，二进制编码比浮点数编码产生新个 体的可能性多，而且产生的新个体不受父个体所构 成的超体的限制； 在变异操作时，二进制编码的种群稳定性比浮点数 编码差。 4.2.2 遗传基因型 智能优化计算 华东理工大学自动化系 2010年 46 4.2 基本遗传算法 适应度函数的重要性 适应度函数的选取直接影响遗传算法的收敛速度以 及能否找到最优解。 一般而言，适应度函数是由目标函数变换而成的， 对目标函数值域的某种映射变换称为适应度的 尺度

34、变换 （ fitness scaling）。 4.2.3 适应度函数及其尺度变换 智能优化计算 华东理工大学自动化系 2010年 47 4.2 基本遗传算法 适应度函数的设计 单值、连续、非负、最大化 合理、一致性（能够反映解的优劣） 计算量小 通用性强 4.2.3 适应度函数及其尺度变换 智能优化计算 华东理工大学自动化系 2010年 48 4.2 基本遗传算法 几种常见的适应度函数 直接转换 若目标函数为最大化问题： Fit ( f (x) )= f (x) 若目标函数为最小化问题： Fit ( f (x) )= - f (x) 4.2.3 适应度函数及其尺度变换 智能优化计算 华东理工大

35、学自动化系 2010年 49 4.2 基本遗传算法 几种常见的适应度函数 界限构造法 1 若目标函数为最大化问题： 若目标函数为最小化问题： 4.2.3 适应度函数及其尺度变换 的最小估计值。为式中， 其他 )( ,0 )( ,)( )( m i n m i nm i n xfc cxfcxf xfFi t 的最大估计值。为式中， 其他 )( ,0 )( ),( )( m a x m a xm a x xfc cxfxfc xfF it 智能优化计算 华东理工大学自动化系 2010年 50 4.2 基本遗传算法 几种常见的适应度函数 界限构造法 2 若目标函数为最大化问题： 若目标函数为最小化

36、问题： c为目标函数的保守估计值。 4.2.3 适应度函数及其尺度变换 0)(,0 )(1 1)( xfccxfcxfFi t 0)(,0 )(1 1)( xfccxfcxfFi t 智能优化计算 华东理工大学自动化系 2010年 51 4.2 基本遗传算法 适应度函数的作用 适应度函数设计不当有可能出现欺骗问题： （ 1）进化初期，个别超常个体控制选择过程； （ 2）进化末期，个体差异太小导致陷入局部极值。 4.2.3 适应度函数及其尺度变换 智能优化计算 华东理工大学自动化系 2010年 52 4.2 基本遗传算法 适应度函数的线性变换法 f=*f+ 系数的确定满足以下条件： favg=

37、favg fmax= cmult favg cmult =1.02.0， 和 取适当值， 以保证适应度值非负。 4.2.3 适应度函数及其尺度变换 智能优化计算 华东理工大学自动化系 2010年 53 4.2 基本遗传算法 适应度函数的幂函数变换法 f= f k k与所求优化问题相关 4.2.3 适应度函数及其尺度变换 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 k 智能优化计算 华东理工大学自动化系 2010年 5

38、4 4.2 基本遗传算法 适应度函数的指数变换法 f= e-af a决定了复制的强制性。 a越大，大适应度的个体被 复制的强制性就越弱。 4.2.3 适应度函数及其尺度变换 1 2 3 4 5 6 7 8 9 10 0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 f f 智能优化计算 华东理工大学自动化系 2010年 55 4.2 基本遗传算法 几个概念 选择压力（ selection pressure） :最佳个体选中的概 率与平均个体选中概率的比值； 偏差（ bias）：个体正规化适应度与其期望再生概 率的绝对差值； 个体

39、扩展（ spread）：单个个体子代个数的范围； 多样化损失（ loss of diversity）：在选择阶段未选 中个体数目占种群的比例； 4.2.4 遗传操作 选择 智能优化计算 华东理工大学自动化系 2010年 56 4.2 基本遗传算法 几个概念 选择强度（ selection intensity） :将正规高斯分布应 用于选择方法，期望平均适应度； 选择方差（ selection variance）：将正规高斯分布 应用于选择方法，期望种群适应度的方差。 4.2.4 遗传操作 选择 智能优化计算 华东理工大学自动化系 2010年 57 4.2 基本遗传算法 个体选择概率的常用分配方

40、法 按比例的适应度分配（ proportional fitness assignment） 某个体 i，其适应度为 fi，则其被选取的概率 Pi为： 如果尺度变换不合适， 可能造成早熟。 4.2.4 遗传操作 选择 M i k i k i i f fP 1 个体 f f2 P 1 2.5 6.25 0.18 2 1.0 1.00 0.03 3 3.0 9.00 0.26 4 1.2 1.44 0.04 5 2.1 4.41 0.13 6 0.8 0.64 0.02 7 2.5 6.25 0.18 8 1.3 1.69 0.05 9 0.9 0.81 0.02 10 1.8 3.24 0.09

41、智能优化计算 华东理工大学自动化系 2010年 58 4.2 基本遗传算法 个体选择概率的常用分配方法 基于排序的适应度分配（ rank-based fitness assignment） 线性排序（ by Baker） 为种群大小， i为个体序号， max代表选择压力。 4.2.4 遗传操作 选择 m a xm i nm a xm i nm a xm a x 2,21,1 1)(1 iP i 智能优化计算 华东理工大学自动化系 2010年 59 4.2 基本遗传算法 个体选择概率的常用分配方法 基于排序的适应度分配（ rank-based fitness assignment） 非线性排序（

42、 by Michalewicz） i为个体序号， c为排序第一的个体的选择概率。 4.2.4 遗传操作 选择 1)1( ii ccP 智能优化计算 华东理工大学自动化系 2010年 60 4.2 基本遗传算法 常用选择方法 轮盘赌选择法（ roulette wheel selection） 4.2.4 遗传操作 选择 个体 1 2 3 4 5 6 7 8 9 10 11 适应度 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.1 选择概率 0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02 0.0 累计概率 0

43、.18 0.34 0.49 0.62 0.73 0.82 0.89 0.95 0.98 1.00 1.00 智能优化计算 华东理工大学自动化系 2010年 61 4.2 基本遗传算法 常用选择方法 随机遍历抽样法（ stochastic universal sampling） 4.2.4 遗传操作 选择 个体 1 2 3 4 5 6 7 8 9 10 11 适应度 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.1 选择概率 0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02 0.0 累计概率 0.18 0.3

44、4 0.49 0.62 0.73 0.82 0.89 0.95 0.98 1.00 1.00 智能优化计算 华东理工大学自动化系 2010年 62 4.2 基本遗传算法 常用选择方法 局部选择法（ local selection） (1)线形邻集 4.2.4 遗传操作 选择 智能优化计算 华东理工大学自动化系 2010年 63 4.2 基本遗传算法 常用选择方法 局部选择法（ local selection） (2)两对角邻集 4.2.4 遗传操作 选择 智能优化计算 华东理工大学自动化系 2010年 64 4.2 基本遗传算法 常用选择方法 局部选择法（ local selection） (

45、2)两对角邻集 4.2.4 遗传操作 选择 智能优化计算 华东理工大学自动化系 2010年 65 4.2 基本遗传算法 常用选择方法 截断选择法（ truncation selection） 个体按适应度排列，只有优秀个体能够成为父个体， 参数为截断阈值（被选作父个体的百分比）。 4.2.4 遗传操作 选择 截断阈值 1 10 20 40 50 80 选择强度 2.66 1.76 1.2 0.97 0.8 0.34 智能优化计算 华东理工大学自动化系 2010年 66 4.2 基本遗传算法 常用选择方法 锦标赛选择法（ tournament selection） 随机从种群中挑选一定数目个体（

46、竞赛规模），其 中最好的个体作为父个体，此过程重复进行完成个 体的选择。 4.2.4 遗传操作 选择 竞赛规模 1 2 3 5 10 30 选择强度 0 0.56 0.85 1.15 1.53 2.04 智能优化计算 华东理工大学自动化系 2010年 67 4.2 基本遗传算法 常用选择方法 早熟现象 适应度高的个体迅速繁殖，使搜索过 程过早结束； 种群中个体的适应度接近，导致进化过程陷入局部 最优点； 基本遗传算法达到收敛的代数与选择强度成反比， 较高的选择强度是很好的选择方法，但太高会导致 收敛过快。 4.2.4 遗传操作 选择 智能优化计算 华东理工大学自动化系 2010年 68 4.2

47、 基本遗传算法 实值重组 离散重组 子个体的每个变量可以按等概率随机地挑选父个体。 4.2.5 遗传操作 交叉 /基因重组 父个体 1 12 25 5 父个体 2 123 4 34 子个体 1 123 4 5 子个体 2 12 4 34 智能优化计算 华东理工大学自动化系 2010年 69 4.2 基本遗传算法 实值重组 中间重组 子个体父个体 1 （父个体 2父个体 1） 是比例因子，由 -d,1+d上均匀分布地随机数产生。 d=0时为中间重组，一般取 d=0.25。 子代的每个变量均产生一个 。 4.2.5 遗传操作 交叉 /基因重组 智能优化计算 华东理工大学自动化系 2010年 70

48、4.2 基本遗传算法 实值重组 中间重组 4.2.5 遗传操作 交叉 /基因重组 父个体 1 12 25 5 父个体 2 123 4 34 子个体 1 子个体 2 值样本 1 0.5 1.1 -0.1 值样本 2 0.1 0.8 0.5 12 0.5 （ 123 12） =67.5 67.5 25 1.1 （ 4 25） =1.9 1.9 2.1 12 0.1 （ 123 12） =23.1 23.1 8.2 19.5 智能优化计算 华东理工大学自动化系 2010年 71 4.2 基本遗传算法 实值重组 中间重组 4.2.5 遗传操作 交叉 /基因重组 智能优化计算 华东理工大学自动化系 20

49、10年 72 4.2 基本遗传算法 实值重组 线性重组 4.2.5 遗传操作 交叉 /基因重组 父个体 1 12 25 5 父个体 2 123 4 34 子个体 1 子个体 2 值样本 1 0.5 值样本 2 0.1 12 0.5 （ 123 12） =67.5 67.5 25 0.5 （ 4 25） =14.5 14.5 19.5 12 0.1 （ 123 12） =23.1 23.1 22.9 7.9 智能优化计算 华东理工大学自动化系 2010年 73 4.2 基本遗传算法 实值重组 线性重组 4.2.5 遗传操作 交叉 /基因重组 智能优化计算 华东理工大学自动化系 2010年 74

50、4.2 基本遗传算法 二进制交叉 单点交叉 4.2.5 遗传操作 交叉 /基因重组 智能优化计算 华东理工大学自动化系 2010年 75 4.2 基本遗传算法 二进制交叉 多点交叉 4.2.5 遗传操作 交叉 /基因重组 智能优化计算 华东理工大学自动化系 2010年 76 4.2 基本遗传算法 二进制交叉 均匀交叉 4.2.5 遗传操作 交叉 /基因重组 父个体 1 0 1 1 1 0 0 1 1 0 1 0 父个体 2 1 0 1 0 1 1 0 0 1 0 1 子个体 1 1 1 1 0 1 1 1 1 1 1 1 子个体 2 0 0 1 1 0 0 0 0 0 0 0 样本 1 0 1

51、 1 0 0 0 1 1 0 1 0 样本 2 1 0 0 1 1 1 0 0 1 0 1 1表示由父个体 1 提供变量值； 0表示由父个体 2 提供变量值。 智能优化计算 华东理工大学自动化系 2010年 77 4.2 基本遗传算法 实值变异 一般采用： 二进制变异 4.2.6 遗传操作 变异 为变量的取值范围。 ；，通常取值，以概率取值以概率 其中， L m mm ia ia LXX m i i 200 1 11 1 )( , 2 )( 5.0 0 智能优化计算 华东理工大学自动化系 2010年 78 4.2 基本遗传算法 主程序 4.2.7 算法的设计与实现 %用遗传算法进行简单函数的优

52、化 clear bn=22; %个体串长度 inn=50; %初始种群大小 gnmax=200; %最大代数 pc=0.75; %交叉概率 pm=0.05; %变异概率 Continue 智能优化计算 华东理工大学自动化系 2010年 79 4.2 基本遗传算法 主程序 4.2.7 算法的设计与实现 %产生初始种群 s=round(rand(inn,bn); %计算适应度 ,返回适应度 f和累积概率 p f,p=objf(s); Continue 智能优化计算 华东理工大学自动化系 2010年 80 4.2 基本遗传算法 主程序 4.2.7 算法的设计与实现 gn=1; while gngnm

53、ax+1 for j=1:2:inn %选择操作 seln=sel(s,p); %交叉操作 scro=cro(s,seln,pc); scnew(j,:)=scro(1,:); scnew(j+1,:)=scro(2,:); %变异操作 smnew(j,:)=mut(scnew(j,:),pm); smnew(j+1,:)=mut(scnew(j+1,:),pm); end Continue 智能优化计算 华东理工大学自动化系 2010年 81 4.2 基本遗传算法 主程序 4.2.7 算法的设计与实现 s=smnew; %产生了新的种群 %计算新种群的适应度 f,p=objf(s); %记录

54、当前代最好和平均的适应度 fmax,nmax=max(f); fmean=mean(f); ymax(gn)=fmax; ymean(gn)=fmean; Continue 智能优化计算 华东理工大学自动化系 2010年 82 4.2 基本遗传算法 主程序 4.2.7 算法的设计与实现 %记录当前代的最佳个体 x=n2to10(s(nmax,:); xx=-1.0+x*3/(power(2,bn)-1); xmax(gn)=xx; gn=gn+1 end gn=gn-1; Continue 智能优化计算 华东理工大学自动化系 2010年 83 4.2 基本遗传算法 主程序 4.2.7 算法的设

55、计与实现 %绘制曲线 subplot(2,1,1); plot(1:gn,ymax;ymean); title(历代适应度变化 ,fonts,10); legend(最大适应度 ,平均适应度 ); string1=最终适应度 ,num2str(ymax(gn); gtext(string1); subplot(2,1,2); plot(1:gn,xmax,r-); legend(自变量 ); string2=最终自变量 ,num2str(xmax(gn); gtext(string2); End 智能优化计算 华东理工大学自动化系 2010年 84 4.2 基本遗传算法 计算适应度和累计概率函

56、数 4.2.7 算法的设计与实现 %计算适应度函数 function f,p=objf(s); inn bn=size(s); %读取种群大小 , 有 inn个个体 ,个 体长度为 bn Continue 智能优化计算 华东理工大学自动化系 2010年 85 4.2 基本遗传算法 计算适应度和累计概率函数 4.2.7 算法的设计与实现 for i=1:inn x=n2to10(s(i,:); %将 二进制转换为十进制 xx=-1.0+x*3/(power(2,bn)-1); %转化为 -1,2区间的实数 f(i)=ft(xx); %计算函数值，即适应度 end f=f; Continue 智能

57、优化计算 华东理工大学自动化系 2010年 86 4.2 基本遗传算法 计算适应度和累计概率函数 4.2.7 算法的设计与实现 %计算选择概率 fsum=0; for i=1:inn fsum=fsum+f(i)*f(i); end for i=1:inn ps(i)=f(i)*f(i)/fsum; end Continue 智能优化计算 华东理工大学自动化系 2010年 87 4.2 基本遗传算法 计算适应度和累计概率函数 4.2.7 算法的设计与实现 %计算累积概率 p(1)=ps(1); for i=2:inn p(i)=p(i-1)+ps(i); end p=p; Back to ma

58、in.m 智能优化计算 华东理工大学自动化系 2010年 88 4.2 基本遗传算法 计算目标函数值函数 4.2.7 算法的设计与实现 %目标函数 function y=ft(x); y=x.*sin(10*pi*x)+2; Back to objf.m 2,1 0.2)10s i n ()( xxxxf 智能优化计算 华东理工大学自动化系 2010年 89 4.2 基本遗传算法 选择操作函数 4.2.7 算法的设计与实现 %“ 选择 ”操作 function seln=sel(s,p); inn=size(p,1); %从种群中选择两个个体 for i=1:2 r=rand; %产生一个随机

59、数 prand=p-r; j=1; while prand(j)0 j=j+1; end seln(i)=j; %选中个体的序号 end Back to main.m 智能优化计算 华东理工大学自动化系 2010年 90 4.2 基本遗传算法 交叉操作函数 4.2.7 算法的设计与实现 %“ 交叉 ”操作 function scro=cro(s,seln,pc); inn bn=size(s); Continue 智能优化计算 华东理工大学自动化系 2010年 91 4.2 基本遗传算法 交叉操作函数 4.2.7 算法的设计与实现 if randpc chb=ceil(rand*(bn-1); %在 1,bn-1范围内随机产生一个 交叉位 scro(1,:)=s(seln(1),1:chb) s(seln(2),chb+1:bn); scro(2,:)=s(seln(2),1:chb) s(seln(1),chb+1:bn); else scro(1,:)=s(seln(1),:); scro(2,:)=s(seln(2),:); end Back to main.m 智能优化计算 华东理工大