经典遗传算法原理与应用PPT.ppt

1、,遗传算法原理与应用,SN: SNO:,主要内容,遗传算法概述,1,1、优化方法,遗传算法概述,传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 GA、漫步法（Random Walk）、模拟退火法,2、遗传算法优点,遗传算法（GA）模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。,遗传算法基本原理,1、基本思想 模拟自然界优胜劣汰的进化现象，把搜索

2、空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。 通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。,2、遗传算法的基本运算, 选择运算, 交换操作, 变异,选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法适应度比例法（转轮法） 某染色体被选的概率：Pc,xi 为种群中第i个染色体，f(xi )为第i个染色体的适应度值。,具体步骤,1）计算各染色体适应度值,2）累计所有染色体适应度值，记录中间累加值S - mid 和最后累加值 sum = f(xi),3）产生一个随机数 N，0 N

3、sum,4）选择对应中间累加值S - mid 的第一个染色体进入交换集,5） 重复（3）和（4），直到获得足够的染色体。,举例：具有6个染色体的二进制编码、适应度值、Pc累计值。,染色体的适应度和所占的比例,用转轮方法进行选择,染色体被选的概率,被选的染色体个数,交换操作,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体: A 11010001 B 01011110,变异,模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变

4、的概率很低.,GA流程,简单遗传算法（GA）的基本参数,种群规模 P: 参与进化的染色体总数. 代沟G: 二代之间不相同的染色体数目,无重叠G = 1;有重叠 0 G 1 选择方法: 转轮法,精英选择法,竞争法. 交换率: Pc 一般为60100%. 变异率: Pm 一般为0.110%,实例,1、产生初始种群,0001100000 0101111001 0000000101 1001110100 1010101010 （8） （5） （2） （10） （7） 1110010110 1001011011 1100000001 1001110100 000101001 （12） （5） （19）

5、（10） （14）,2、计算适应度,3、选择,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,3、选择,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,3、

6、选择,在01之间产生一个 随机数：,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,0.086957,0.086957,0.054348,0.141304,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,0.163043,4、交叉,0001100000 11100

7、10110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011,0001100000 1110010110 1100000001 1001110100,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,5、变异,6、至下一代，适应度计算选择交叉变异，直至满足终止条件。,遗传算法的应用及一些问题,1、遗传算法的应用领域,（1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度 （5）图像处理 （6）机器学习 （7）人工生命 （8）数据挖掘,2、遗传算法在应用中的一些问题,1）知识的编码,二进制和十进制的比较：二进制有更多图式和更大的搜