遗传算法实验报告.ppt

1、实 验 报 告,遗传算法,1.遗传算法的背景 2.遗传算法的国内外发展情况 3.遗传算法的原理 4.遗传算法的步骤 5.算法的结构 6.总结,1.遗传算法的背景,生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。生物的进化过程，主要是通过染色体之间的交叉和变异来完成的。它通过选择淘汰，突然变异，基因遗传等规律产生适应环境的优良物种。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。,自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物

2、的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法就是模仿自然界的生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。,2.遗传算法的国内外发展情况,进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜

3、索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。,这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。 二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。 三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构,的研究都是十分重要的。 四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会

4、发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。,3. 遗传算法的原理,遗传算法的思想源于生物遗传学和适者生存的自然规律， 是具有“ 生存+ 检测” 的迭代过程的搜索算法。 它以一种群体中的所有个体为对象， 并利用随机化技术指导对一个被编码的参数空间进行高效搜索。 其中， 选择、 交叉和变异构成了遗传算法的遗传操作;参数编码、 初始群体的设定、 适应度函数的设计、 遗传操作设计、 控制参数设定五个要素,组成了遗传算法的核心内容。 遗传算法的流程为: 开始 选择编码方式;

5、产生初始群体; 计算初始群体的适应度; 若不满足结束条件则循环执行: 选择操作; 交换操作; 变异操作; 计算新一代群体的适应度; 结束,由此可以看出， 从搜索角度， 遗传算法与传统的搜索方法相比具有如下独特的优点: 搜索过程不直接作用在变量上， 不必非常明确描述问题的全部特征， 可直接对结构对象(集合、序列、 矩阵、 树、 图、 链和表)进行操作， 通用性强， 能很快适应问题和环境的变化。 采用概率的变迁规则来指导搜索方向， 而不采用确定性,搜索规则;对搜索空间没有任何特殊要求(如连通性、 凸性等)， 只利用适应性信息， 不需要连续性、 可导或单峰等其它辅助信息， 适应范围更广。 搜索过程是

6、从一组解迭代到另一组解， 采用同时处理群体中多个个体的方法， 从多点进行搜索，搜索的全局性强， 降低了陷入局部最优解的可能性;具有隐并行性， 非常适合于并行计算。,4.遗传算法的步骤,1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验,2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规

7、模而确定。确定的。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率(cP)挑选的每两个父代通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而,没什么意义），从而产生新的个体。可以得到新一代个体，新个体组。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。合了其父辈个体的特性。交换体现了信息交换的思想。,5.选择（selection）：选择的目的是为了从交换后的群体中选出优良的个体，使它们有机会

8、作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献的概率大，选择实现了达尔文的适者生存原则。本文直接选取交换后的群体中具有最大适应度的前N个个体作为下一代进行繁殖。这一步骤的存在使得当前群体是所有搜索过的解之中是最优的前N个的集合。,6.变异（mutation）：变异首先在群体中随机选择一定数量个体，对于选中的个体以一定的概率（成为变异概率mP）随机地改变串结构数据中某个基因的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。 7.中止。规则有三种情况： (1)给定一个最大的遗传代数M

9、AXGEN(人为事先确定)，算法,迭代在达MAXGEN时停止。 (2)给定问题一个下界的计算方法，当进化中达到要求的 偏差时，算法终止。 (3)当监控得到的算法再进化已无法改进解的性能，即解 的适应度无法再提高，此时停止计算。,5.算法的构成,结构体 struct individual char chromchromlength+1; double value; double fitness; /适应度 bestindividual/*最佳个体*/,worstindividual/*最差个体*/,currentbest/*当前最佳*/,populationPOPSIZE/*全部个体*/;,种群

10、初始化 void generateinitialpopulation( ) int i,j; for (i=0;ipopsize; i+) for(j=0;jchromlength;j+) populationi.chromj=(rand()%105)?0:1; populationi.chromchromlength=0; ,计算函数值 void calculateobjectvalue() int i; long temp1,temp2; double x1,x2; for (i=0; ipopsize; i+) temp1=decodechromosome(populationi.chr

11、om,0,length1); temp2=decodechromosome(populationi.chrom,length1,length2); x1=4.096*temp1/1023.0-2.048;/temp的最大取值为1023，将其最大值换算为2.048 x2=4.096*temp2/1023.0-2.048;/temp的最小取值为0，将其最小值算为-2.048populationi.value=100*(x1*x1-x2)* (x1*x1-x2)+(1-x1)*(1-x1);,比例选择算法 void selectoperator() int i,index; double p,sum

12、=0.0; double cfitnessPOPSIZE; struct individual newpopulationPOPSIZE; for(i=0;ipopsize;i+) sum+=populationi.fitness; for(i=0;ipopsize; i+) cfitnessi=populationi.fitness/sum; for(i=1;ipopsize; i+) cfitnessi=cfitnessi-1+cfitnessi;,for (i=0;icfitnessindex) index+; newpopulationi=populationindex; for(i=

13、0;ipopsize; i+) populationi=newpopulationi; ,交叉算法 void crossoveroperator() int i,j; int indexPOPSIZE; int point,temp; double p; char ch; for (i=0;ipopsize;i+) indexi=i; for (i=0;ipopsize;i+) point=rand()%(popsize-i); temp=indexi;,indexi=indexpoint+i; indexpoint+i=temp; for (i=0;ipopsize-1;i+=2) p=ra

14、nd()%1000/1000.0; if (ppc) point=rand()%(chromlength-1)+1;/随机交叉互换的一个点 for (j=point; jchromlength;j+) ch=populationindexi.chromj; populationindexi.chromj=populationindexi+1.chromj; populationindexi+1.chromj=ch;,变异操作 void mutationoperator() int i,j; double p; for (i=0;ipopsize;i+) for(j=0;jchromlength;j+) p=rand()%1000/1000.0; if (ppm) populationi.chromj=(populationi.chromj=0)?1:0; ,6.总结,其实这次实验对于我们来说还是很困难