遗传算法学习.pptx

目录CONTENTS1遗 传 算 法 定 义Geneticalgorithmdefinition2遗传算法关键技术Biologicalterminology3遗传算法过程Problemimport4问题与代码实现Generalrealization5遗传算法Code第1页/共28页11-1遗传算法的科学定义1-2生物遗传1-3遗传算法图解过程遗传算法定义第2页/共28页123 遗传算法（Genetic Algorithm,GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现 以编码空间代替问题参数空间，从代表问题可能有潜在解集的一个种群出发，按照生物进化过程中适者生存、优胜略汰的原理，以适应度作为评价个体优劣的依据，重复使用选择、交叉、变异算子作用于群体，使之不断进化，逐渐接近最优解GeneticAlgorithm遗传算法科学定义遗 传 算 法第3页/共28页TITLE01TITLE02Loremipsumdolorsitamet,consectetueradipiscingelit,seddiamnonummynibheuismodtinciduntutlaoreetdoloremagnaaliquameratvolutpat.TITLE03生物遗传概念遗传算法生物遗传概念遗传算法的概念基因可行解的每一分量的特征染色体可行解的编码个体可行解种群通过适应度函数值选取的一组可行解交叉两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成产生一组新的可行解变异编码的某一分量发生变化的过程适应度度量某个物种对于生存环境的适应程度复制细胞分裂时，遗传物质通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。选择以一定概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程第4页/共28页2遗传算法关键技术2-1初始化2-2适应度函数2-3选择2-4交叉2-5变异第5页/共28页遗传算法步骤遗 传 算 法你准备要去野游1个月，但是你只能背一个限重30公斤的背包。现在你有不同的必需物品，它们每一个都有自己的生存点数。因此，你的目标是在有限的背包重量下，最大化你的生存点数。物件重量生存点数睡袋1515绳索37折叠刀210手电筒55瓶子98葡萄糖2017第6页/共28页100110001110010100011001A1A2A3A4基因染色体种群遗 传 算 法初 始 化染色体可表达为二进制数串，在这个问题中：1代表基因存在0代表基因丢失特定位置上的基因代表了上方背包问题表格中的物品。第一个位置上是睡袋第二个位置上是绳索第三个位置上是折叠刀第四个位置上是手电筒第五个位置上是瓶子第六个位置上是葡萄糖例如：染色体A1表示：1、睡袋；4、手电筒、5、瓶子第7页/共28页A1(100110)A1(001110)A1(010100)A1(011001)适应度函数遗 传 算 法物件重量生存点睡袋1515手电筒55瓶子98总和2928物件重量生存点折叠刀210手电筒55瓶子98总和1623物件重量生存点绳索37手电筒55总和812物件重量生存点绳索37折叠刀210葡萄糖2017总和2534第8页/共28页遗 传 算 法选择-轮盘赌选择染色体生存点选择概率积累概率A1280.2890.289A2230.2370.526A3160.1240.650A4340.3511.000选择用来实施适者生存的原则，即把当前的群体中的个体按照一定方法，挑选出一部分个体，用于构建交配池选择算子的作用效果是提高了群体的平均适应度。由于选择算子没有产生新个体，所以群体中最好个体的适应值不会因为选择操作而有所改变轮盘赌选择算法如图所示：选择了俩个个体A1,A4个体00.2890.5260.6501.000第1轮第2轮A1A2A3A4第9页/共28页遗 传 算 法交叉在上一个步骤中，我们已经选择出了可以产生后代的亲本染色体。那么用生物学的话说，所谓交叉，其实就是指的繁殖。现在我们来对染色体A1和A4（在上一个步骤中选出来的）进行交叉，见下图：100110011001011110100001ParentsOff-springs单点交叉100110011001101010100101多点交叉ParentsOff-springs第10页/共28页遗 传 算 法变异如果现在我们从生物学的角度来看这个问题，那么请问：由上述过程产生的后代是否有和其父母一样的性状呢？答案是否。在后代的生长过程中，它们体内的基因会发生一些变化，使得它们与父母不同。这个过程我们称为变异，它可以被定义为染色体上发生的随机变化，正是因为变异，种群中才会存在多样性。100110011001000111111000ParentsOff-springs变异在进行完一轮遗传变异之后，我们用适应度函数对这些新的后代进行验证，如果函数判定它们适应度足够，那么就会用它们从总体中替代掉那些适应度不够的染色体。第11页/共28页3遗传算法过程3-1遗传算法步骤3-2遗传算法流程图3-3遗传算法伪代码第12页/共28页遗 传 算 法遗传算法步骤evaluationselectioncrossovermutation第13页/共28页遗 传 算 法遗传算法流程图第14页/共28页ProceduresGA：伪代码begininitializeP(0);/(1)初始化t=0;/t是进化的代数，一代、二代、三代.while(t=T)do/T是最大进化代数;fori=1toMdo/M是初始种群的个体数,随机生成M个个体作为初始群体P（t）；EvaluatefitnessofP(t);/(2)个体评价计算P（t）中各个个体的适应度值；endforfori=1toMdoSelectoperationtoP(t);/(3)选择运算将选择算子作用于群体；endforfori=1toM/2doCrossoveroperationtoP(t);/(4)将交叉算子作用于群体交叉运算;endforfori=1toMdoMutationoperationtoP(t);/(5)将变异算子作用于群体变异运算;endforfori=1toMdoP(t+1)=P(t);/(6)通过以上运算得到下一代群体P（t+1）;endfort=t+1;/终止条件判断tT：tt+1转到步骤2endwhileEnd遗传算法伪代码遗 传 算 法第15页/共28页问题导入与代码实现44-1问题4-2代码实现4-3应用前景4-4案例分析第16页/共28页遗 传 算 法求函数最大值其中0=X1=50=X2=5-2=X3=2F(X)=X12X1*X2+X3设置迭代次数,种群内个体数量，交叉率，变异率 初始化种群确定适应值函数选择遗传操作算子：选择运算交叉运算变异运算：停机条件第17页/共28页#include#include#include#include#include#include#include#include#includeusingnamespacestd;#definePOPSIZE50/种群内个体数量#defineMAXGENS1000/最大的迭代次数#defineNVARS3/变量个数，即用以表示基因型的bit数#definePXOVER0.8/交换率#definePMUTATION0.15/突变率structgenotypedoublegeneNVARS;doublefitness;doubleupperNVARS;doublelowerNVARS;doublerfitness;doublecfitness;structgenotypepopulationPOPSIZE+1;/旧种群structgenotypenewpopulationPOPSIZE+1;/新种群intmain();voidcrossover(int&seed);/交叉操作。voidelitist();/储存旧的种群voidevaluate();/进化inti4_uniform_ab(inta,intb,int&seedintInt_uniform_ab(inta,intb)voidinitialize(stringfilename,int&seed);voidkeep_the_best();voidmutate(int&seed);doubler8_uniform_ab(doublea,doubleb,int&seed);doubleDou_uniform_ab(doublea,doubleb);voidreport(intgeneration);voidselector(int&seed);doubleround(doublenumber);voidtimestamp();voidXover(intone,inttwo,int&seed);第18页/共28页main()freopen(E:output.txt,w+,stdout);stringfilename=simple_ga_input.txt;intgeneration;inti;intseed;timestamp();cout“n;coutSIMPLE_GA:n;coutC+versionn;coutAsimpleexampleofageneticalgorithm.n;if(NVARS2)coutn;coutThecrossovermodificationwillnotbeavailable,n;coutsinceitrequires2=NVARS.n;seed=123456789;srand(unsigned)time(NULL);/产生伪随机数序列initialize(filename,seed);evaluate();keep_the_best();for(generation=0;generationMAXGENS;generation+)selector(seed);crossover(seed);mutate(seed);report(generation);evaluate();elitist();coutn;coutBestmemberafterMAXGENSgenerations:n;coutn;for(i=0;iNVARS;i+)coutvar(i)=populationPOPSIZE.genein;coutn;coutBestfitness=populationPOPSIZE.fitnessn;coutn;coutSIMPLE_GA:n;coutNormalendofexecution.n;coutn;timestamp();return0;第19页/共28页voidcrossover(int&seed)/交叉运算constdoublea=0.0;constdoubleb=1.0;intmem;intone;intfirst=0;doublex;for(mem=0;memPOPSIZE;+mem)x=Dou_uniform_ab(a,b);if(xPXOVER)+first;if(first%2=0)Xover(one,mem,seed);elseone=mem;return;voidelitist()inti;doublebest;intbest_mem;doubleworst;intworst_mem;best=population0.fitness;worst=population0.fitness;for(i=0;iPOPSIZE-1;+i)if(populationi+1.fitnesspopulationi.fitness)if(best=populationi.fitness)best=populationi.fitness;best_mem=i;if(populationi+1.fitness=worst)worst=populationi+1.fitness;worst_mem=i+1;第20页/共28页elseif(populationi.fitness=worst)worst=populationi.fitness;worst_mem=i;if(best=populationi+1.fitness)best=populationi+1.fitness;best_mem=i+1;if(populationPOPSIZE.fitness=best)for(i=0;iNVARS;i+)populationPOPSIZE.genei=populationbest_mem.genei;populationPOPSIZE.fitness=populationbest_mem.fitness;elsefor(i=0;iNVARS;i+)populationworst_mem.genei=populationPOPSIZE.genei;populationworst_mem.fitness=populationPOPSIZE.fitness;return;voidevaluate()/实现用户定义的评估功能intmember;inti;doublexNVARS+1;for(member=0;memberPOPSIZE;member+)for(i=0;iNVARS;i+)xi+1=populationmember.genei;populationmember.fitness=(x1*x1)-(x1*x2)+x3;return;intInt_uniform_ab(inta,intb)inttmp;tmp=(rand()%(b-a+1)+a;returntmp;第21页/共28页inti4_uniform_ab(inta,intb,int&seed)intc;constinti4_huge=2147483647;intk;floatr;intvalue;if(seed=0)cerrn;cerrI4_UNIFORM_AB-Fatalerror!n;cerrInputvalueofSEED=0.n;exit(1);if(ba)c=a;a=b;b=c;k=seed/127773;seed=16807*(seed-k*127773)-k*2836;if(seed0)seed=seed+i4_huge;r=(float)(seed)*4.656612875E-10;r=(1.0-r)*(float)a-0.5)+r*(float)b+0.5);value=round(rif(valuea)value=a;if(bvalue)value=b;returnvalue;voidinitialize(stringfilename,int&seed)/初始化种群inti;ifstreaminput;intj;doublelbound;doubleubound;input.open(filename.c_str();if(!input)cerrn;cerrINITIALIZE-Fatalerror!n;cerrCannotopentheinputfile!n;exit(1);for(i=0;ilboundubound;for(j=0;jPOPSIZE;j+)populationj.fitness=0;populationj.rfitness=0;populationj.cfitness=0;populationj.loweri=lbound;populationj.upperi=ubound;/populationj.genei=r8_uniform_ab(lbound,ubound,seed);populationj.genei=Dou_uniform_ab(lbound,ubound);input.close();return;第22页/共28页voidkeep_the_best()intcur_best;intmem;inti;cur_best=0;for(mem=0;memPOPSIZE;mem+)if(populationPOPSIZE.fitnesspopulationmem.fitness)cur_best=mem;populationPOPSIZE.fitness=populationmem.fitness;for(i=0;iNVARS;i+)populationPOPSIZE.genei=populationcur_best.genei;return;voidmutate(int&seed)/变异运算constdoublea=0.0;constdoubleb=1.0;inti;intj;doublelbound;doubleubound;doublex;for(i=0;iPOPSIZE;i+)for(j=0;jNVARS;j+)/x=r8_uniform_ab(a,b,seed);x=Dou_uniform_ab(a,b);if(xPMUTATION)lbound=populationi.lowerj;ubound=populationi.upperj;/populationi.genej=r8_uniform_ab(lbound,ubound,seed);populationi.genej=Dou_uniform_ab(lbound,ubound);return;第23页/共28页doubler8_uniform_ab(doublea,doubleb,int&seed)inti4_huge=2147483647;intk;doublevalue;if(seed=0)cerrn;cerrR8_UNIFORM_AB-Fatalerror!n;cerrInputvalueofSEED=0.n;exit(1);k=seed/127773;seed=16807*(seed-k*127773)-k*2836;if(seed0)seed=seed+i4_huge;value=(double)(seed)*4.656612875E-10;value=a+(b-a)*value;returnvalue;doubleDou_uniform_ab(doublea,doubleb)doubletmp;tmp=a+static_cast(rand()/RAND_MAX*(b-a);returntmp;voidreport(intgeneration)doubleavg;doublebest_val;inti;doublesquare_sum;doublestddev;doublesum;doublesum_square;if(generation=0)coutn;coutGenerationBestAverageStandardn;coutnumbervaluefitnessdeviationn;coutn;sum=0.0;sum_square=0.0;for(i=0;iPOPSIZE;i+)sum=sum+populationi.fitness;sum_square=sum_square+populationi.fitness*populationi.fitness;avg=sum/(double)POPSIZE;square_sum=avg*avg*POPSIZE;stddev=sqrt(sum_square-square_sum)/(POPSIZE-1);best_val=populationPOPSIZE.fitness;coutsetw(8)generationsetw(14)best_valsetw(14)avgsetw(14)stddevn;return;第24页/共28页voidselector(int&seed)/选择运算constdoublea=0.0;constdoubleb=1.0;inti;intj;intmem;doublep;doublesum;sum=0.0;for(mem=0;memPOPSIZE;mem+)sum=sum+populationmem.fitness;for(mem=0;memPOPSIZE;mem+)populationmem.rfitness=populationmem.fitness/sum;population0.cfitness=population0.rfitness;for(mem=1;memPOPSIZE;mem+)populationmem.cfitness=populationmem-1.cfitness+populationmem.rfitness;for(i=0;iPOPSIZE;i+)p=Dou_uniform_ab(a,b);if(ppopulation0.cfitness)newpopulationi=population0;elsefor(j=0;jPOPSIZE;j+)if(populationj.cfitness=p&ppopulationj+1.cfitness)newpopulationi=populationj+1;for(i=0;iPOPSIZE;i+)populationi=newpopulationi;return;doubleround(doublenumber)returnnumber0.0?ceil(number-0.5):floor(number+0.5);voidtimestamp()#defineTIME_SIZE40staticchartime_bufferTIME_SIZE;conststructtm*tm;size_tlen;time_tnow;now=time(NULL);tm=localtime(&now);/将时间格式化len=strftime(time_buffer,TIME_SIZE,%d%B%Y%I:%M:%S%p,tm);couttime_buffern;return;#undefTIME_SIZE第25页/共28页voidXover(intone,inttwo,int&seed)inti;intpoint;doublet;point=Int_uniform_ab(0,NVARS-1);for(i=0;ipoint;i+)t=populationone.genei;populationone.genei=populationtwo.genei;populationtwo.genei=t;return;输出结果：第26页/共28页感 谢！Thangkyou第27页/共28页