经典遗传算法原理与应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,遗传算法原理与应用,SN:,SNO:,主要内容,遗传算法基本原理,2,遗传算法概述,1,遗传算法的应用及一些问题,3,1,、优化方法,遗传算法概述,传统的优化方法（局部优化）,共轭梯度法、拟牛顿法、单纯形方法,全局优化方法,GA,、漫步法（,Random Walk,）、模拟退火法,2,、遗传算法优点,遗传算法（,GA,）模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子,(,选择、交叉和变异,),对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。,遗传算法,基本原理,1,、基本思想,模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量,染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。,2,、遗传算法的基本运算,选择运算,交换操作,变异,选择运算,从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法,适应度比例法（转轮法）,某染色体被选的概率：,P,c,x,i,为种群中第,i,个染色体，,f(,xi,),为第,i,个染色体的适应度值。,具体步骤,1,）计算各染色体适应度值,2,）累计所有染色体适应度值，记录中间累加值,S,-mid,和最后累加值,sum=,f(xi),3,）产生一个随机数,N,，,0 N,sum,4,）选择对应中间累加值,S,-mid,的第一个染色体进入交换集,5,）重复（,3,）和（,4,），直到获得足够的染色体。,举例：,具有,6,个染色体的二进制编码、适应度值、,P,c,累计值。,染色体的适应度和所占的比例,用转轮方法进行选择,染色体被选的概率,染色体编号,1,2,3,4,5,6,7,8,9,10,适应度,8,2,17,7,2,12,11,7,3,7,被选概率,0.1,0.02,0.22,0.09,0.02,0.16,0.14,0.09,0.03,0.09,适应度累计,8,10,27,34,36,48,59,66,69,76,被选的染色体个数,随机数,23,49,76,13,1,27,57,所选染色体号码,3,7,10,3,1,3,7,交换操作,方法,:,随机选择二个染色体,(,双亲染色体,),随机指定一点或多点,进行交换,可得二个新的染色体,(,子辈染色体,).,新的子辈染色体,:A,11010001,B,01011110,变异,模拟生物在自然界环境变化,引起基因的突变,.,在染色体二进制编码中,1,变成,0;,或,0,变成,1.,突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低,.,GA,流程,简单遗传算法（,GA,）的基本参数,种群规模,P:,参与进化的染色体总数,.,代沟,G:,二代之间不相同的染色体数目,无重叠,G=1;,有重叠,0 G 1,选择方法,:,转轮法,精英选择法,竞争法,.,交换率,:,P,c,一般为,60100%.,变异率,:,P,m,一般为,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,、选择,个体,染色体,适应度,选择概率,累积概率,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,8,8,5,2,10,7,12,5,19,10,14,0.086957,0.054348,5,8,5,2,10,7,12,5,19,10,14,0.021739,0.108696,0.076087,0.130435,0.054348,0.206522,0.108696,0.152174,3,、选择,个体,染色体,适应度,选择概率,累积概率,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.108696,0.152174,0.086957,0.141304,0.163043,0.271739,0.347826,0.478261,0.532609,0.739130,0.847826,1.000000,3,、选择,在,0,1,之间产生一个,随机数：,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,个体,染色体,适应度,选择概率,累积概率,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.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 1110010110 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,、变异,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,1001,1,1,0100,0001,1001110100,1100000001,1010101,0001010,010,011,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,1001,0,1,0100,0001,1001110100,1100000001,1010101,0001010,010,011,6,、至下一代，适应度计算选择交叉变异，直至满足终止条件,。,遗传算法的应用及一些问题,1,、,遗传算法的应用领域,（,1,）组合优化 （,2,）函数优化,（,3,）自动控制 （,4,）生产调度,（,5,）图像处理 （,6,）机器学习,（,7,）人工生命 （,8,）数据挖掘,2,、遗传算法在应用中的一些问题,1,）知识的编码,二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。,2,）适应度函数,适应度函数值必须非负,，,根据情况做适当的处理,。,如图,3,）全局最优和收敛性。,根据图式定理，对于具有,“,欺骗性,”,函数，,GA,有可能落入局部最优点。,举例：,3,位欺骗函数,Thank you!,