经典遗传算法原理与应用.ppt
,遗传算法原理与应用,SN:SNO:,主要内容,遗传算法概述,1,1、优化方法,遗传算法概述,传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法 GA、漫步法（Random Walk）、模拟退火法,2、遗传算法优点,遗传算法（GA）模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。,遗传算法基本原理,1、基本思想 模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。,2、遗传算法的基本运算,选择运算,交换操作,变异,选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法适应度比例法（转轮法）某染色体被选的概率：Pc,xi 为种群中第i个染色体，f(xi)为第i个染色体的适应度值。,具体步骤,1）计算各染色体适应度值,2）累计所有染色体适应度值，记录中间累加值S-mid 和最后累加值 sum=f(xi),3）产生一个随机数 N，0 N sum,4）选择对应中间累加值S-mid 的第一个染色体进入交换集,5）重复（3）和（4），直到获得足够的染色体。,举例：具有6个染色体的二进制编码、适应度值、Pc累计值。,染色体的适应度和所占的比例,用转轮方法进行选择,染色体被选的概率,被选的染色体个数,交换操作,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体:A 11010001 B 01011110,变异,模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.,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）（10）（14）,2、计算适应度,3、选择,0.086957,0.054348,0.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174,3、选择,0.086957,0.054348,0.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174,0.086957,0.141304,0.163043,0.2717390.3478260.4782610.5326090.7391300.8478261.000000,3、选择,在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.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174,0.2717390.3478260.4782610.5326090.7391300.8478261.000000,0.163043,4、交叉,0001100000 1110010110 1100000001 1001110100 10101010101110010110 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）知识的编码,二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。,2）适应度函数 适应度函数值必须非负，根据情况做适当的处理。,如图,3）全局最优和收敛性。根据图式定理，对于具有“欺骗性”函数，GA有可能落入局部最优点。,举例：3位欺骗函数,Thank you!,
