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

遗传算法原理与应用SN:SNO:主要内容遗传算法基本原理2遗传算法概述1遗传算法的应用及一些问题31、优化方法遗传算法概述传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法GA、漫步法（RandomWalk）、模拟退火法2、遗传算法优点遗传算法（GA）模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。遗传算法基本原理1、基本思想模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。2、遗传算法的基本运算⑴选择运算⑵交换操作⑶变异选择运算从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法——适应度比例法（转轮法）某染色体被选的概率：Pc)()(iicxfxfPxi为种群中第i个染色体，f(xi)为第i个染色体的适应度值。具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=∑f(xi)3）产生一个随机数N，0〈N〈sum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。举例：⒈具有6个染色体的二进制编码、适应度值、Pc累计值。染色体的适应度和所占的比例用转轮方法进行选择染色体被选的概率染色体编号12345678910适应度8217721211737被选概率0.10.020.220.090.020.160.140.090.030.09适应度累计8102734364859666976被选的染色体个数随机数2349761312757所选染色体号码37103137交换操作方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A’11010001B’01011110变异模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.GA流程简单遗传算法（GA）的基本参数①种群规模P:参与进化的染色体总数.②代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0G1③选择方法:转轮法,精英选择法,竞争法.④交换率:Pc一般为60~100%.⑤变异率:Pm一般为0.1~10%实例1、产生初始种群00011000000101111001000000010110011101001010101010（8）（5）（2）（10）（7）1110010110100101101111000000011001110100000101001（12）（5）（19）（10）（14）2、计算适应度3、选择个体染色体适应度选择概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.0869570.05434858＋5＋2＋10＋7＋12＋5＋19＋10＋140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521743、选择个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000003、选择在0～1之间产生一个随机数：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰4、交叉0001100000111001011011000000011001110100101010101011100101101001011011100111010011000000010001010011000110000011100101101100000001100111010000011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100115、变异00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100116、至下一代，适应度计算→选择→交叉→变异，直至满足终止条件。遗传算法的应用及一些问题1、遗传算法的应用领域（1）组合优化（2）函数优化（3）自动控制（4）生产调度（5）图像处理（6）机器学习（7）人工生命（8）数据挖掘2、遗传算法在应用中的一些问题1）知识的编码二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。12minmaxlUUQ精度2）适应度函数适应度函数值必须非负，根据情况做适当的处理。如图3）全局最优和收敛性。根据图式定理，对于具有“欺骗性”函数，GA有可能落入局部最优点。举例：3位欺骗函数Thankyou!