遗传算法改进及算法应用

《遗传算法改进及算法应用》由会员分享，可在线阅读，更多相关《遗传算法改进及算法应用（37页珍藏版）》请在装配图网上搜索。

1、主要内容遗传算法基本原理遗传算法基本原理2遗传算法概述遗传算法概述1 遗传算法的应用及一些问题遗传算法的应用及一些问题4遗传算法遗传算法改进改进3第1页/共37页1、优化方法遗传算法概述遗传算法概述传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法 GA、漫步法（Random Walk）、模拟退火法遗传算法（GA）遗传算法是模拟在自然环境中的遗传和进化过程而形成的一种全适应概率搜索算法第2页/共37页2、遗传算法优点 遗传算法（GA）模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选

2、择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。第3页/共37页GA流程第4页/共37页遗传算法基本原理1、基本思想 模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。2、遗传算法的基本运算 选择运算 交换操作 变异第5页/共37页选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法适应度比例法（转轮法）某染色体被选的概率：P

3、c)()(iicxfxfPxi 为种群中第i个染色体，f(xi)为第i个染色体的适应度值。第6页/共37页具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid 和最后累加值 sum=f(xi)3）产生一个随机数 N，0 N sum4）选择对应中间累加值S-mid 的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。第7页/共37页举例：具有6 6个染色体的二进制编码、适应度值、P Pc c累计值。染色体的适应度和所占的比例用转轮方法进行选择第8页/共37页染色体被选的概率染色体编号 1 2 3 4 5 6 7 8 910适应度 8 217 7

4、212 11 7 3 7被选概率0.1 0.020.220.090.020.160.140.090.030.09适应度累计 8 10 27 34 36 485966 69 76被选的染色体个数随机数23497613 1 2757所选染色体号码 3 710 3 1 3 7第9页/共37页交换操作 方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A 11010001 B 01011110第10页/共37页变异 模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化

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

6、（19）（10）（14）2、计算适应度第13页/共37页3、选择个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.0869570.05434858521071251910140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521

7、74第14页/共37页3、选择个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.47826

8、10.5326090.7391300.8478261.000000第15页/共37页3 3、选择在01之间产生一个随机数：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570

9、.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰第16页/共37页4、交叉 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 00010100110001100000 1110010110 11

10、00000001 1001110100 00011110100000010110 11110000101101011011 110000100111010000011001110100110000000110101010001010010011第17页/共37页5、变异0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011000111101000000101101111000010110101101111000010011101000

11、00110011101001100000001101010100010100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011第18页/共37页6、至下一代，适应度计算选择交叉变异，直至满足终止条件。第19页/共37页遗传算

12、法的改进 轮盘赌选择方式是传统遗传算法中最经常使用的选择手段,因为轮盘赌选择方式非常直观而且也很简单,所以深受欢迎。轮盘赌不足之处：首先是在遗传进化的开始阶段,这个时候可能存在适应度较高的生物个体,根据轮盘赌选择方法,那么这个个体被选中的机会就会非常大,从而会选择复制出相当数量的子代,这就容易导致种群的多样性丧失,种群中个体太单调,很难再进行遗传进化,所以也很难搜索到全局最优解。选择算子的改进第20页/共37页 其次是在遗传进化的末了阶段,这个时候种群中的所有个体之间的差异不是很大了,因而适应度也很接近,所以此时的轮盘赌选择方法已经无效,丧失了继续选择的功能,也就无法分辨种群中个体的好坏了。第

13、21页/共37页改进方法：对种群中的全部个体来一次排序,根据种群中每个个体的适应度高低对这些个体进行降序列出。把这些按顺序排列出来的所有个体从头到尾依次分成四等份。适应度最低的排在最后面的1/4比例的个体全部扔掉,也就是直接淘汰掉,不进入到下一代当中;把适应度中等的排在中间的2/4比例的个体全部拷贝一份,也就是选择到下一代当中;剩下来的适应度最高的排在最前面的1/4比例的个体全部拷贝两份,也就是把这两份都选择到下一代当中。第22页/共37页采用此种改进策略进行选择操作可以有以下几种好处:一、可以把适应度非常低的个体直接淘汰出该种群，使得这些个体没有机会进入到下一代当中，因此能够提升算法的收敛速

14、度。二、快速增加种群中适应度较好的个体的数量，使得算法更加高效实用。第23页/共37页交叉算子的改进交叉算子的改进 一些较早的遗传算法当中，关于交叉算子的操作是非常简陋的，也是有点盲目的。对于一对需要进行交叉操作的父代个体，使用一个恒定不变的交叉概率来对这对父代个体实行交叉互换，也不论这对父代个体的相似程度如何。相似度：假定有两个父代个体，它们的编码是二进制的，一个个体叫做X，另一个个体口LI做Y，则关于个体X和个体Y的相似度可以进行这样定义:s=c/n S就表示两个父代个体的相似度，C表示个体X与个体Y的最长的共同子串的长度，n叫做种群中个体染色体编码的长度。第24页/共37页 假设个体x的

15、染色体编码为10101011，个体Y的染色体编码为10101110，则个体X和个体Y的最长的共同子串就为101011。这个最长的共同子串的长度即为6，也就是C等于6，种群中个体染色体编码的长度是8，也即n等于8,因此就得到了个体X和个体Y的相似度的大小，即等于6/8。显然，种群中任意两个个体的相似度S的值是一个0,1之间的数。修正过的交叉临界值的公式为:r就表示交叉临界值，g表示该种群此时的进化代数，G表示该种群规定的总的进化代数。第25页/共37页 r是一个(1/3,2/3之间的数，并不是固定不变的，是随着当前的进化代数的增长而不断增大的。如果需要进行交叉的两个父代个体的相似度S大于或等于当

16、前的交叉临界值r时，则不准这两个父代个体进行交叉互换操作，以避免破坏它们的优良基因模式。需要进行交叉的两个父代个体的相似度S小于当前的交叉临界值r时，则允许这两个父代个体进行交叉互换操作。第26页/共37页 在种群进化的初期，由于种群中各个个体之间的差异比较大，因此它们的染色体编码也具有很大的差别，这个时候种群中各个个体之间的相似程度也会很小，所以必须给出一个相对较小的交叉临界值。随着种群的不断进化，种群中各个个体之间的差异会渐渐变小，因而各个个体之间的相似程度也会渐渐提高，所以此时必须给出一个相对较大的交叉临界值。种群中个体之间的交叉临界值随着当前进化代数动态的改变是有道理的，有助于提高遗传

17、算法的收敛性能以及收敛速度。第27页/共37页变异算子的改进变异算子的改进 基本遗传算法(SGA)中,变异概率是固定不变的，通常是一个很小的常数。在遗传进化后期,如果变异概率不发生改变，很容易造成局部收敛的情况,从而对算法的运行效率产生极大地影响。提出一种修正过的变异概率p。随适应度作自适应变化的公式：Pm为将要变异个体的变异概率，Pm_max 为最大变异概率,这里取0.2，Pm_min为最小变异概率,这里取0.001，f即为将要变异个体的适应度，f_max为种群中最大的适应度，favg为每一代种群适应度的平均值。第28页/共37页 变异的个体的适应度大于等于此时种群的平均适应度时，如果将要变

18、异个体的适应度越大，则该个体的变异概率就越小，正好符合“优胜劣汰,适者生存”的进化规律。变异的个体的适应度小于此时种群的平均适应度时，说明此个体为劣质个体或是非优良个体，不适应生存，为了扩大解空间，增强种群的多样性,需要给该个体一个较大的变异概率。这样做还可以使算法的局部搜索能力增强，有助于算法更快地达到全局收敛，因而能够很好的改善遗传算法的性能。第29页/共37页遗传算法的应用及一些问题1、遗传算法的应用领域（1）组合优化 （2）函数优化（3）自动控制 （4）生产调度（5）图像处理 （6）机器学习（7）人工生命 （8）数据挖掘 2、遗传算法在应用中的一些问题1）知识的编码 二进制和十进制的比

19、较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。12 minmaxlUUQ精度第30页/共37页基本遗传算法应用实例基本遗传算法应用实例：求函数的最大值00.511.522.533.544.5x 104050010001500200025003000350040004500 xf(x)f(x)函 数 图 像第31页/共37页遗传算法算法实现背包问题 假定背包的最大容量为W，N件物品，每件物品都有自己的价值和重量，将物品放入背包中使得背包内物品的总价值最大。背包问题是一种组合优化的NP完全问题。背包问题 可以想象这样一个场景小偷在屋子里偷东西，他带着一只背包。屋子里物品数量有限每件

20、物品都具有一定的重量和价值珠宝重量轻但价值高，桌 子重但价值低。最重要的是小偷背包容量有限。很明显，他不能把桌子分成两份或者带走珠宝的3/4。对于一件物品他只能选择带走或者不带走。第32页/共37页 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。所谓状态,是指在一定的时空范围内，问题所涉及的人、物、时间等的布局关系。通常把问题的初始布局关系称为初始状态，问题解决时到达的状态叫目标状态。知识表示知识表示状态空间第33页/共

21、37页 在背包问题中，初始状态就是有一个空包，包的重量固定为W，有N个商品，每个商品的重量为Wi,价值Ci。目标状态就是将n(n=N)个商品装入包里，包重不超过W，使得包中商品的总重量最大。状态空间就是将商品装入包的所有组合，本实验的解就是价值和最大的装包组合。3、遗传算法中的抽象概念在背包问题的具体化、遗传算法中的抽象概念在背包问题的具体化（1）基因：0或1，代表相应的商品选还是不选。（2）染色体：本实验中固定有50个商品，所以染色体就是50个基因序列，也就是40个0、1串，代表了一种往包里装商品的组合。一个染色体例：0111101101011011110101110101010101011

22、110。（3）群体：一定数量的基因个体组成了群体(population),群体中个体的数量 叫做群体大小。本实验的背包问题中，种群大小为100，代表100个往包里 装商品的组合。（4）适应度:各个个体对环境的适应程度叫做适应度。本实验的背包问题中，每染色体个体的适应度为选入包中的商品的价值和。第34页/共37页算法实现1、数据结构（1）重要参数：#define zhongqun_size 100 /种群的规模#define pc 0.8 /杂交概率#define pm 0.08 /变异概率#define chrom_length 50 /染色体长度#define max_daishu 1000 /最大进化代数（2）染色个体：struct populationunsigned int chromchrom_length;/染色体double weight;/背包重量double fitness;/适应度unsigned int parent1,parent2,cross;/双亲、交叉点;（3）种群：/新生代种群、父代种群struct population oldpopzhongqun_size,newpopzhongqun_size;第35页/共37页谢谢！第36页/共37页感谢您的观看！第37页/共37页