《最经典的遗传算法教程资料》由会员分享，可在线阅读，更多相关《最经典的遗传算法教程资料（29页珍藏版）》请在金锄头文库上搜索。
1、遗传算法,传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法（Random Walk）、模拟退火法、GA,关于优化问题,比较：,传统的优化方法,1）依赖于初始条件。 2）与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数； 共轭梯度法隐含地依赖于梯度。,全局优化方法,1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求 解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况, 选择运算
2、交换操作 变异,遗传算法的基本运算,遗传算法基本原理,模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传 空间，把可能的解编码成一个向量染色体，向量的每个 元素称为基因。 通过不断计算各染色体的适应值，选择最好的染色体，获 得最优解。,选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲 区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc,xi 为种群中第i个染色体，,具体步骤,1）计算各染色体适应度值 2）累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值
3、 sum = f(xi) 3） 产生一个随机数 N，0 N sum 4） 选择对应中间累加值S - mid 的第一个染色体进入交换集 5） 重复（3）和（4），直到获得足够的染色体。,举例： 具有6个染色体的二进制编码、适应度值、Pc累计 值。,染色体的 适应度和所占的比例,用转轮方法进行选择,染色体被选的概率,被选的染色体个数,10个染色体种群按比例的选择过程,交换操作,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体: A 11010001 B 01011110,模拟生物在自然界环境变化,引起基因的突变.在染色体二进
4、制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.,变异,复制不能创新,交换解决染色体的创新,GA的流程,简单遗传算法（GA）的基本参数,种群规模 P: 参与进化的染色体总数. 代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 G 1 选择方法: 转轮法,精英选择法,竞争法. 交换率: Pc 一般为60100%. 变异率: Pm 一般为0.110%,举例:,变异概率取0.001,初始种群和它的适应度值,染色体的交换操纵,举例：,14,步骤1）编码：确定二进制的位数；组成个体（染色体）,步骤2）选择种群数P 和初始个体
5、，计算适应度值， P = 20；,步骤3）确定选择方法；交换率PC；变异率Pm。 选择方法用竞争法； PC = 0.7, Pm = 0.05,计算结果： 8代后，f(x,y) =0.998757, 41代后，f(x,y) =1.00000, x =3.000290, y =2.999924. 160次适应度计算，达到最优值。,遗传算法的基本数学问题,一个重要的定理图式定理,什么叫图式？,描述种群中染色体相似性的字符串。,（插入演示）,演示,12,（*为通配符）,图式的描述：, 定义长度（H)H左右二端有定义位置之间的距离；, 图式的阶次(或固定长度)O(H）H中非*位（有定义位） 的个数。,图
6、式定理的推导,图式在选择过程中的增加.,经过选择,在t+1代,图式H的数量m(H,t+1)为:,图式在交换中的破坏,图式在变异中的破坏,经过选择、交换、变异后在t+1中，图式H的数量：,图式定理：在选择、交换、变异的作用下，阶次低、定义长度短、适应度高的图式（模块）将按指数增长的规律，一代一代地增长。,遗传算法在应用中的一些基本问题,1）知识的编码,2）适应度函数。 a) 适应度函数值必须非负。根据情况做适当的处理,二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。,3）全局最优和收敛性。 根据图式定理，对于具有“欺骗性”函数，GA有可能落入局部最优点。,b）为保
7、持种群的多样性，防止“超级”染色体“统治”种群。,欺骗性函数,图式划分：指引相互之间竞争的定义位为同一集合的一组图式。 如#表示定义位，则H1=*1*0*，H2=*0*1* ，H3=*1*1*， H4=*0*0* 同属于划分*#*#*。,总平均适应度（OAF）：对一个给定图式，OAF即为其成员 的平均适应度。,欺骗性函数包含全局最优的图式其OAF不如包含局部最优的OAF，这种划分称为欺骗划分，它会使GA陷入局部最优。如最高阶欺骗函数有k个定义位，则此函数称k阶欺骗。,举例：3位欺骗函数, 高级GA算法,1）操作的改进,2）算法的改进,选择方法改进：精英法（竞赛法）、置换式和非置换式 随机选择法，排序法。,交换方法的改进：多点交换；重组运算,微种群遗传算法（GA）,双种群遗传算法（DPGA）,重组运算：解决染色体分布过于集中问题。把适应度函数做进一步处理。,终止条件：1）达到预定指标；2）达到预定代数。,GA算法,双种群算法（ DPGA）,基本思想：利用人类社会分工合作的机理。,分成：全局种群粗搜索，寻找可能存在的最优区域； 局部种群 精搜索在全局划定的区域内，寻找最优点。,测试函数：,遗传算法的应用：1）神经网络结构参数的选择 2）滑模控制中应用 3）倒立摆控制中应用,
