遗传算法实验报告.

实验报告遗传算法遗传算法1.遗传算法的背景2.遗传算法的国内外发展情况3.遗传算法的原理4.遗传算法的步骤5.算法的结构6.总结1.遗传算法的背景生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。生物的进化过程，主要是通过染色体之间的交叉和变异来完成的。它通过选择淘汰，突然变异，基因遗传等规律产生适应环境的优良物种。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法就是模仿自然界的生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。2.遗传算法的国内外发展情况进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（EvolutionProgramming,EP）以及进化策略（EvolutionStrategy,ES）等进化计算理论日益结合。3.遗传算法的原理遗传算法的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。它以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。遗传算法的流程为:开始{选择编码方式;产生初始群体;计算初始群体的适应度;若不满足结束条件则循环执行:{选择操作;交换操作;变异操作;计算新一代群体的适应度;}}结束由此可以看出，从搜索角度，遗传算法与传统的搜索方法相比具有如下独特的优点:①搜索过程不直接作用在变量上，不必非常明确描述问题的全部特征，可直接对结构对象(集合、序列、矩阵、树、图、链和表)进行操作，通用性强，能很快适应问题和环境的变化。②采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则;对搜索空间没有任何特殊要求(如连通性、凸性等)，只利用适应性信息，不需要连续性、可导或单峰等其它辅助信息，适应范围更广。③搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，从多点进行搜索，搜索的全局性强，降低了陷入局部最优解的可能性;具有隐并行性，非常适合于并行计算。4.遗传算法的步骤1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。确定的。3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率(cP)挑选的每两个父代通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组。4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。合了其父辈个体的特性。交换体现了信息交换的思想。5.选择（selection）：选择的目的是为了从交换后的群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献的概率大，选择实现了达尔文的适者生存原则。本文直接选取交换后的群体中具有最大适应度的前N个个体作为下一代进行繁殖。这一步骤的存在使得当前群体是所有搜索过的解之中是最优的前N个的集合。6.变异（mutation）：变异首先在群体中随机选择一定数量个体，对于选中的个体以一定的概率（成为变异概率mP）随机地改变串结构数据中某个基因的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。7.中止。规则有三种情况：(1)给定一个最大的遗传代数MAXGEN(人为事先确定)，算法迭代在达MAXGEN时停止。(2)给定问题一个下界的计算方法，当进化中达到要求的偏差ε时，算法终止。(3)当监控得到的算法再进化已无法改进解的性能，即解的适应度无法再提高，此时停止计算。5.算法的构成结构体structindividual{charchrom[chromlength+1];doublevalue;doublefitness;//适应度}bestindividual/*最佳个体*/,worstindividual/*最差个体*/,currentbest/*当前最佳*/,population[POPSIZE]/*全部个体*/;种群初始化voidgenerateinitialpopulation(){inti,j;for(i=0;ipopsize;i++){for(j=0;jchromlength;j++){population[i].chrom[j]=(rand()%105)?'0':'1';}population[i].chrom[chromlength]='\0';}}计算函数值voidcalculateobjectvalue(){inti;longtemp1,temp2;doublex1,x2;for(i=0;ipopsize;i++){temp1=decodechromosome(population[i].chrom,0,length1);temp2=decodechromosome(population[i].chrom,length1,length2);x1=4.096*temp1/1023.0-2.048;//temp的最大取值为1023，将其最大值换算为2.048x2=4.096*temp2/1023.0-2.048;//temp的最小取值为0，将其最小值算为-2.048population[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);}}比例选择算法voidselectoperator(){inti,index;doublep,sum=0.0;doublecfitness[POPSIZE];structindividualnewpopulation[POPSIZE];for(i=0;ipopsize;i++){sum+=population[i].fitness;}for(i=0;ipopsize;i++){cfitness[i]=population[i].fitness/sum;}for(i=1;ipopsize;i++){cfitness[i]=cfitness[i-1]+cfitness[i];}for(i=0;ipopsize;i++){p=rand()%1000/1000.0;index=0;while(pcfitness[index]){index++;}newpopulation[i]=population[index];}for(i=0;ipopsize;i++){population[i]=newpopulation[i];}}交叉算法voidcrossoveroperator(){inti,j;intindex[POPSIZE];intpoint,temp;doublep;charch;for(i=0;ipopsize;i++){index[i]=i;}for(i=0;ipopsize;i++){point=rand()%(popsize-i);temp=index[i];index[i]=index[point+i];index[point+i]=temp;}for(i=0;ipopsize-1;i+=2){p=rand()%1000/1000.0;if(ppc){point=rand()%(chromlength-1)+1;//随机交叉互换的一个点for(j=point;jchromlength;j++){ch=population[index[i]].chrom[j];population[index[i]].chrom[j]=population[index[i+1]].chrom[j];population[index[i+1]].chrom[j]=ch;}}}}变异操作voidmutationoperator(){inti,j;doublep;for(i=0;ipopsize;i++){for(j=0;jchromlength;j++){p=rand()%1000/1000.0;if(ppm){population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';}}}}6.总结其实这次实验对于我们来说还是很困难的，毕竟来说别人用接近一生的时间发明出来的算法我们不到一个月时间来研究。不过在经过这段时间我们小组的努力之后，首先我们收获最大的并不是对于这个算法的研究，而是团队的协作精神，如何去分配工作，一起经历谈论，一起商量，一起研究，还一边进行辩论，我们很喜欢这种气氛。其次对于遗传算法我们也都有了各自的看法，这些理解都是完全属于我们自己的。拥有这团队的感觉就是不一样，大家一起来解决问题，再大的困难都不是事！！！实训很好，获益良多啊。感谢老师让我们有了这种机会。