遗传算法实验报告

..信息与管理科学学院计算机科学系实验报告课程名称：人工智能实验名称：遗传算法问题XX：鹏海贾美丽妍汉昭学号：15100030631510003024班级：计科实验室：软件技术实验室指导教师：慧日期：2016.11.09&&遗传算法问题实验目的1．熟悉和掌握遗传算法的原理、实质；2．学会使用遗传算法解决问题；3．学会编写遗传算法程序寻找函数最值；实验原理遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化构成进展的数学方式仿真。在遗传算法中染色体对应的是一系列符号序列，在标准的遗传算法(即根本遗传算法)中，通常用0,1组成的位串表示，串上各个位置对应基因座，各位置上的取值对应等位基因。遗传算法对染色体进展处理，染色体称为基因个体。一定数量的基因个体组成基因种群。种群中个体的数目为种群的规模，各个体对环境的适应程度称为适应度。实验容用遗传算法求根号2，也就是求方程f(x)=x*x-2=0的正整数解，x=1时f(1)<0，x=2时f(2)>0，由介值定理，那么1到2中间存在一个根，根据代数根本定理和根的对称性知这就是我们要找的根，由目标函数得到适应度函数，我们选择个体都在[1,2]之间，那适应度函数我可以取j(x)=40/(2+|x*x-2|)-10，由x的取值围知j的围是(0,10)

x和y穿插就用取平均(x+y)/2，穿插概率取0.9，变异概率为0，步骤分析选择目标函数，确定变量定义域及编码精度，形成编码方案随机产生一个规模为〔即该种群中含有个体〕的种群2个体评价：计算群体P(t)中各个个体适应度选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对穿插产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估根底上的。〔选择运算用轮盘赌算法〕对被选择进入匹配池中的个体进展穿插操作，形成新种群以小概率在种群中选择个体进展变异操作形成新种群计算每个个体的适值根据适值概率选择新个体形成新种群检查完毕条件，假设满足那么算法完毕，当前种群中适值最高的个体即所求解；否那么转3选择操作：首先要知道适应度函数，所谓的适应度函数就是评价函数，通常是问题的目的函数〔或它的倒数〕，它描述了个体的优劣程度同时也决定了选择操作的概率，设fi表示第i个个体的适应度值，那选择第i个个体的概率就是fi/∑fj，简单来说，这个概率的大小就决定了该个体是被淘汰还是被保存。通常的具体做法是用类似赌盘的方法，每个个体占它的适应度那么宽的转盘大小，每次掷色子，落到哪一格就选哪一格对应的个体。穿插操作：穿插操作就是让2个以上的染色体进展穿插产生后代的过程，具体的穿插操作要看具体的问题。不过我觉得有一个原那么，就是要有对称性，穿插得到的后代中的基因要来源于父代的所有个体中，也就是说n个个体进展穿插是和它们的排列没关系，这样子代才有时机得到更优秀的基因。穿插操作是遗传算法中最重要的操作。最简单的根本方式是交换父代中染色体片段。变异操作：生物可以突变，有时候突变是好的，有时候却是坏的，但正是因为有了突变才让有限的种群中基因库可以非常丰富，也保证了种群的适应能力。变异操作通常是翻转个体中某段染色体，编码后的染色体在计算机中都是01串，也就可以随机的翻转某个〔或多个〕bit上的值。穿插和变异不是一定要发生在选择了的个体上，而是按一定控制概率发生的，穿插概率比拟高通常是0.6~0.95，而变异概率比拟低通常是0.001~0.01。五、实验程序#include<stdio.h>#include<time.h>#include<stdlib.h>typedefstruct_indi//个体{doublecode;//染色体doubledegree;//适应度}Indi;Indigroup[40];//种群规模为40//------------------------------------------------------//适应度算法voidJudge(Indi&x)//适应度算法{doubletmp=x.code*x.code-2.0;if(tmp>=0)x.degree=40.0/(2.0+tmp)-10.0;elsex.degree=40.0/(2.0-tmp)-10.0;}//------------------------------------------------------inthappened(doublep)//是否发生一个概率在p=0~1的事件{returnrand()<(int)(p*RAND_MAX);}//------------------------------------------------------//穿插操作voidCross(Indi&x,Indi&y)//穿插操作，产生一个子代取代父代中最次的一个{Indiz;z.code=(x.code+y.code)/2.0;//穿插只进展了取平均值Judge(z);if(x.degree<y.degree){if(z.degree<=x.degree)return;//如果新个体不如双亲，淘汰之x=z;//否那么，替代父代中最次的一个}else{if(z.degree<=y.degree)return;y=z;}}//------------------------------------------------------voidmain(){srand(time(NULL));//设置随机数种子inti,j,best,x,y,c;doublesum,strick;for(i=0;i<40;++i)//随机得到初始种群{group[i].code=1.0+(double)rand()/RAND_MAX;Judge(group[i]);}for(i=1;i<=10;++i)//固定进化10代{for(sum=0.0,best=0,j=0;j<40;++j){sum+=group[j].degree;//求总的适应度sumif(group[j].degree>group[best].degree)best=j;//求当前最优个体}printf("第%2d代中最优个体为%10f(适应度%10f)平均适应度为%10f\n",i,group[best].code,group[best].degree,sum/40.0);for(c=40;c;--c)//轮盘赌法选择个体{strick=(double)rand()/RAND_MAX*sum;//赌盘中的色子，选择个体x,yfor(x=0;x<40&&strick>=group[x].degree;++x)strick-=group[x].degree;strick=(double)rand()/RAND_MAX*sum;for(y=0;y<40&&strick>=group[y].degree;++y)strick-=group[y].degree;if(happened(0.9))//穿插率为0.9Cross(group[x],group[y]);//穿插}}}实验结果：六、实验心得本次人工智能实验是以小组任务来完成，小组中的几个成员分工明确，各有所长，就我们组所选择的人工智能遗传算法而言，从拿到题目不知所措到问题一一解决，例如程序运行错误，流程图难以画出等。重要的是在遗传算法实验过程