




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、精选优质文档-倾情为你奉上实验十 遗传算法与优化问题一、问题背景与实验目的遗传算法(Genetic AlgorithmGA),是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它是由美国Michigan大学的J.Holland教授于1975年首先提出的遗传算法作为一种新的全局优化搜索算法,以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点,奠定了它作为21世纪关键智能计算之一的地位本实验将首先介绍一下遗传算法的基本理论,然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算1遗传算法的基本原理遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程它把问题
2、的参数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体这个群体在问题特定的环境里生存竞争,适者有最好的机会生存和产生后代后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过程群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解值得注意的一点是,现在的遗传算法是受生物进化论学说的启发提出的,这种学说对我们用计算机解决复杂问题很有用,而它本身是否完全正确并不重要(目前生物界对此学说尚有争议)(1)遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法
3、;故而在这个算法中要用到各种进化和遗传学的概念首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系这些概念如下:序号遗传学概念遗传算法概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度,或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体,淘汰劣质个体的操作保留或复制适应值大的可行解,去掉小的可行解9交叉一组染色体上对应
4、基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率(可能性大小)闭区间0,1上的一个值,一般为0.650.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率(可能性大小)开区间(0,1)内的一个值, 一般为0.0010.0113进化、适者生存个体进行优胜劣汰的进化,一代又一代地优化目标函数取到最大值,最优的可行解(2)遗传算法的步骤遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程,主要有三个基本操作(或称为算子):选择(Selection)、交叉(Crossover)、变异(Mutation)遗传算法基本步骤主要是:先把问
5、题的解表示成“染色体”,在算法中也就是以二进制编码的串,在执行遗传算法之前,给出一群“染色体”,也就是假设的可行解然后,把这些假设的可行解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉、变异过程产生更适应环境的新一代“染色体”群经过这样的一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解下面给出遗传算法的具体步骤,流程图参见图1:第一步:选择编码策略,把参数集合(可行解集合)转换染色体结构空间;第二步:定义适应函数,便于计算适应值;第三步:确定遗传策略,包括选择群体大小,选择、交叉、变异方法以及确定交叉概率、变异概率等
6、遗传参数;第四步:随机产生初始化群体;第五步:计算群体中的个体或染色体解码后的适应值;第六步:按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体;第七步:判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步产生初始群体是否满足终止条件得到结果结束程序是否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体图1 一个遗传算法的具体步骤遗传算法有很多种具体的不同实现过程,以上介绍的是标准遗传算法的主要步骤,此算法会一直运行直到找到满足条件的最优解
7、为止2遗传算法的实际应用例1:设,求 注:这是一个非常简单的二次函数求极值的问题,相信大家都会做在此我们要研究的不是问题本身,而是借此来说明如何通过遗传算法分析和解决问题在此将细化地给出遗传算法的整个过程(1)编码和产生初始群体首先第一步要确定编码的策略,也就是说如何把到2这个区间内的数用计算机语言表示出来编码就是表现型到基因型的映射,编码时要注意以下三个原则:完备性:问题空间中所有点(潜在解)都能成为GA编码空间中的点(染色体位串)的表现型;健全性:GA编码空间中的染色体位串必须对应问题空间中的某一潜在解;非冗余性:染色体和潜在解必须一一对应这里我们通过采用二进制的形式来解决编码问题,将某个
8、变量值代表的个体表示为一个0,1二进制串当然,串长取决于求解的精度如果要设定求解精度到六位小数,由于区间长度为,则必须将闭区间 分为等分因为 所以编码的二进制串至少需要22位将一个二进制串(b21b20b19b1b0)转化为区间内对应的实数值很简单,只需采取以下两步(Matlab程序参见附录4):1)将一个二进制串(b21b20b19b1b0)代表的二进制数化为10进制数:2) 对应的区间内的实数:例如,一个二进制串a=表示实数0.=()2=二进制串,则分别表示区间的两个端点值-1和2利用这种方法我们就完成了遗传算法的第一步编码,这种二进制编码的方法完全符合上述的编码的三个原则首先我们来随机的
9、产生一个个体数为4个的初始群体如下:pop(1)=, % a1, % a2, % a3 % a4(Matlab程序参见附录2)化成十进制的数分别为:pop(1)= 1.,0. ,-0. ,0. 接下来我们就要解决每个染色体个体的适应值问题了(2)定义适应函数和适应值由于给定的目标函数在内的值有正有负,所以必须通过建立适应函数与目标函数的映射关系,保证映射后的适应值非负,而且目标函数的优化方向应对应于适应值增大的方向,也为以后计算各个体的入选概率打下基础对于本题中的最大化问题,定义适应函数,采用下述方法:式中既可以是特定的输入值,也可以是当前所有代或最近K代中的最小值,这里为了便于计算,将采用了
10、一个特定的输入值若取,则当时适应函数;当时适应函数由上述所随机产生的初始群体,我们可以先计算出目标函数值分别如下(Matlab程序参见附录3):f pop(1)= 1. , 1. , -1. , 0. 然后通过适应函数计算出适应值分别如下(Matlab程序参见附录5、附录6):取,gpop(1)= 2. , 2. , 0 , 1. (3)确定选择标准这里我们用到了适应值的比例来作为选择的标准,得到的每个个体的适应值比例叫作入选概率其计算公式如下:对于给定的规模为n的群体pop=,个体的适应值为,则其入选概率为由上述给出的群体,我们可以计算出各个个体的入选概率首先可得 ,然后分别用四个个体的适应
11、值去除以,得:P(a1)=2. / 6. = 0. % a1P(a2)=2. / 6. = 0. % a2P(a3)= 0 / 6. = 0 % a3P(a4)=1. / 6. = 0. % a4(Matlab程序参见附录7)(4)产生种群计算完了入选概率后,就将入选概率大的个体选入种群,淘汰概率小的个体,并用入选概率最大的个体补入种群,得到与原群体大小同样的种群(Matlab程序参见附录8、附录11)要说明的是:附录11的算法与这里不完全相同为保证收敛性,附录11的算法作了修正,采用了最佳个体保存方法(elitist model),具体内容将在后面给出介绍由初始群体的入选概率我们淘汰掉a3,
12、再加入a2补足成与群体同样大小的种群得到newpop(1)如下:newpop(1)=, % a1, % a2, % a2 % a4(5)交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体,然后得到新的染色体组,组成新的群体(Matlab程序参见附录9)我们把之前得到的newpop(1)的四个个体两两组成一对,重复的不配对,进行交叉(可以在任一位进行交叉), 交叉得:, , 交叉得:, 通过交叉得到了四个新个体,得到新的群体jchpop (1)如下:jchpop(1)=,这里采用的是单点交叉的方法,当然还有多点交叉的方法,不过有些烦琐,这里就不着重介绍了(6)变异变异也就是通过一个小概率
13、改变染色体位串上的某个基因(Matlab程序参见附录10)现把刚得到的jchpop(1)中第3个个体中的第9位改变,就产生了变异,得到了新的群体pop(2)如下:pop(2)= , 然后重复上述的选择、交叉、变异直到满足终止条件为止(7)终止条件遗传算法的终止条件有两类常见条件:(1)采用设定最大(遗传)代数的方法,一般可设定为50代,此时就可能得出最优解此种方法简单易行,但可能不是很精确(Matlab程序参见附录1);(2)根据个体的差异来判断,通过计算种群中基因多样性测度,即所有基因位相似程度来进行控制3遗传算法的收敛性前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作
14、的基本内容及设计进行了详细的介绍作为一种搜索算法,遗传算法通过对这些操作的适当设计和运行,可以实现兼顾全局搜索和局部搜索的所谓均衡搜索,具体实现见下图2所示图2 均衡搜索的具体实现图示应该指出的是,遗传算法虽然可以实现均衡的搜索,并且在许多复杂问题的求解中往往能得到满意的结果,但是该算法的全局优化收敛性的理论分析尚待解决目前普遍认为,标准遗传算法并不保证全局最优收敛但是,在一定的约束条件下,遗传算法可以实现这一点下面我们不加证明地罗列几个定理或定义,供读者参考(在这些定理的证明中,要用到许多概率论知识,特别是有关马尔可夫链的理论,读者可参阅有关文献)定理1 如果变异概率为,交叉概率为,同时采用
15、比例选择法(按个体适应度占群体适应度的比例进行复制),则标准遗传算法的变换矩阵P是基本的定理2 标准遗传算法(参数如定理1)不能收敛至全局最优解由定理2可以知道,具有变异概率,交叉概率为以及按比例选择的标准遗传算法是不能收敛至全局最最优解我们在前面求解例1时所用的方法就是满足定理1的条件的方法这无疑是一个令人沮丧的结论然而,庆幸的是,只要对标准遗传算法作一些改进,就能够保证其收敛性具体如下:我们对标准遗传算法作一定改进,即不按比例进行选择,而是保留当前所得的最优解(称作超个体)该超个体不参与遗传最佳个体保存方法(elitist model)的思想是把群体中适应度最高的个体不进行配对交叉而直接复
16、制到下一代中此种选择操作又称复制(copy)De Jong对此方法作了如下定义:定义 设到时刻t(第t代)时,群体中a*(t)为最佳个体又设A(t1)为新一代群体,若A(t1)中不存在a*(t),则把a*(t)作为A(t1)中的第n+1个个体(其中,n为群体大小)(Matlab程序参见附录11)采用此选择方法的优点是,进化过程中某一代的最优解可不被交叉和变异操作所破坏但是,这也隐含了一种危机,即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解也就是说,该方法的全局搜索能力差,它更适合单峰性质的搜索空间搜索,而不是多峰性质的空间搜索所以此方法一般都与其他选择方法结合使用定理3 具有定理1
17、所示参数,且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解当然,在选择算子作用后保留当前最优解是一项比较复杂的工作,因为该解在选择算子作用后可能丢失但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解有意思的是,实际上只要在选择前保留当前最优解,就可以保证收敛,定理4描述了这种情况定理4 具有定理1参数的,且在选择前保留当前最优解的遗传算法可收敛于全局最优解例2:设,求 ,编码长度为5,采用上述定理4所述的“在选择前保留当前最优解的遗传算法”进行此略,留作练习二、相关函数(命令)及简介本实验的程序中用到如下一些基本的Matlab函数:ones, zeros, sum, size,
18、 length, subs, double 等,以及 for, while 等基本程序结构语句,读者可参考前面专门关于Matlab的介绍,也可参考其他数学实验章节中的“相关函数(命令)及简介”内容,此略三、实验内容上述例1的求解过程为:群体中包含六个染色体,每个染色体用22位01码,变异概率为0.01,变量区间为 ,取Fmin=,遗传代数为50代,则运用第一种终止条件(指定遗传代数)的Matlab程序为:Count,Result,BestMember=Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50)执行结果为:Count = 50Result = 1.03
19、16 1.0316 1.0316 1.0316 1.0316 1.0316 1.4990 1.4990 1.4990 1.4990 1.4990 1.4990BestMember = 1.0316 1.4990图2 例1的计算结果(注:上图为遗传进化过程中每一代的个体最大适应度;而下图为目前为止的个体最大适应度单调递增)我们通过Matlab软件实现了遗传算法,得到了这题在第一种终止条件下的最优解:当取1.0316时,当然这个解和实际情况还有一点出入(应该是取1时,),但对于一个计算机算法来说已经很不错了我们也可以编制Matlab程序求在第二种终止条件下的最优解此略,留作练习实践表明,此时的遗传
20、算法只要经过10代左右就可完成收敛,得到另一个“最优解”,与前面的最优解相差无几四、自己动手1 用Matlab编制另一个主程序Genetic2.m,求例1的在第二种终止条件下的最优解提示:一个可能的函数调用形式以及相应的结果为:Count,Result,BestMember=Genetic2(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,0.00001)Count = 13Result = 1.0392 1.0392 1.0392 1.0392 1.0392 1.0392 1.4985 1.4985 1.4985 1.4985 1.4985 1.4985BestMember =
21、 1.0392 1.4985可以看到:两组解都已经很接近实际结果,对于两种方法所产生的最优解差异很小可见这两种终止算法都是可行的,而且可以知道对于例1的问题,遗传算法只要经过10代左右就可以完成收敛,达到一个最优解2 按照例2的具体要求,用遗传算法求上述例2的最优解3 附录9子程序 Crossing.m中的第3行到第7行为注解语句若去掉前面的%号,则程序的算法思想有什么变化?4 附录9子程序 Crossing.m中的第8行至第13行的程序表明,当Dim(1)=3时,将交换数组Population的最后两行,即交换最后面的两个个体其目的是什么?5 仿照附录10子程序Mutation.m,修改附录
22、9子程序 Crossing.m,使得交叉过程也有一个概率值(一般取0.650.90);同时适当修改主程序Genetic1.m或主程序Genetic2.m,以便代入交叉概率6 设,求 ,要设定求解精度到15位小数五、附录附录1:主程序Genetic1.mfunction Count,Result,BestMember=Genetic1(MumberLength,MemberNumber,FunctionFitness,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,Member
23、Number);global Count;global CurrentBest;Count=1;PopulationCode=Population;PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);Population,CurrentBest,EachGenMaxFitnes
24、s=Elitist(PopulationCode,PopulationFitness,MumberLength);EachMaxFitness(Count)=EachGenMaxFitness;MaxFitness(Count)=CurrentBest(length(CurrentBest);while Count=0.5*ones(size(Temporary);【程序说明】子程序 PopulationInitialize.m用于产生一个初始群体这个初始群体含有MemberNumber个染色体,每个染色体有MumberLength个基因(二进制码)附录3:子程序Fitness.mfuncti
25、on PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)Dim=size(PopulationCode);PopulationFitness=zeros(1,Dim(1);for i=1:Dim(1)PopulationFitness(i)=Transfer(PopulationCode(i,:),FunctionFitness,MinX,MaxX,MumberLength);end【程序说明】子程序Fitness.m用于计算群体中每一个染色体的目标函数值子程序中含有5个输入参数:Po
26、pulationCode表示用01代码表示的群体,FunctionFitness 表示目标函数,它是一个字符串,因此写入调用程序时,应该用单引号括出,MumberLength表示染色体位串的二进制长度MinX和MaxX 分别指变量区间的上下限附录4:子程序 Translate.mfunction PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)PopulationData=0;Dim=size(PopulationCode);for i=1:Dim(2) PopulationData=PopulationData+P
27、opulationCode(i)*(2(MumberLength-i);endPopulationData=MinX+PopulationData*(MaxX-MinX)/(2Dim(2)-1);【程序说明】子程序 Translate.m把编成码的群体翻译成变量的数值含有4个输入参数,PopulationCode, MinX, MaxX, MumberLength附录5:子程序Transfer.mfunction PopulationFitness=Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)Population
28、Fitness=0;PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength);PopulationFitness=double(subs(FunctionFitness,x,sym(PopulationData); 【程序说明】子程序 Transfer 把群体中的染色体的目标函数值用数值表示出来,它是Fitness的重要子程序其有5个输入参数分别为PopulationCode, FunctionFitness, MinX, MaxX,MumberLength附录6:子程序FitnessF.mfunction Populati
29、onFitnessF=FitnessF(PopulationFitness,Fmin)Dim=size(PopulationFitness);PopulationFitnessF=zeros(1,Dim(2);for i=1:Dim(2)if PopulationFitness(i)Fmin PopulationFitnessF(i)=PopulationFitness(i)-Fmin;endif PopulationFitness(i)CProbability(Index) Index=Index+1; end NewPopulation(i,:)=Population(Index,:);e
30、nd【程序说明】子程序 Select.m 根据入选概率(计算累计概率)在群体中按比例选择部分染色体组成种群,该子程序的3个输入参数分别为:群体Population,入选概率PopulationProbability,群体中染色体的个数MemberNumber附录9:子程序 Crossing.mfunction NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)%PopulationFitness=% Fitness(Population,FunctionFitness,MinX,MaxX,Mumbe
31、rLength);%PopulationProbability=Probability(PopulationFitness);%SortResult,SortSite=sort(PopulationProbability);%Population=Population(SortSite,:);Dim=size(Population);if Dim(1)=3 Temp=Population(Dim(1),:); Population(Dim(1),:)=Population(Dim(1)-1,:); Population(Dim(1)-1,:)=Temp;endfor i=1:2:Dim(1)-
32、1 SiteArray=randperm(Dim(2); Site=SiteArray(1); Temp=Population(i,1:Site); Population(i,1:Site)=Population(i+1,1:Site); Population(i+1,1:Site)=Temp;endNewPopulation=Population;【程序说明】子程序 Crossing.m 用于群体中的交叉并产生新群体其输入参数为:Population, FunctionFitness,MinX,MaxX,MumberLength附录10:子程序Mutation.mfunction NewPo
33、pulation=Mutation(Population,MutationProbability)Dim=size(Population);for i=1:Dim(1) Probability=rand(1); Site=randperm(Dim(2); if ProbabilityMutationProbability if Population(i,Site(1)=1 Population(i,Site(1)=0; end if Population(i,Site(1)=0 Population(i,Site(1)=1; end endendNewPopulation=Population
34、;【程序说明】子程序Mutation.m用于群体中少量个体变量并产生新的群体输入参数为:群体Population和变异概率MutationProbability附录11:子程序Elitist.mfunction NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness=Elitist(Population,PopulationFitness,MumberLength)global Count CurrentBest;MinFitness,MinSite=min(PopulationFitness);MaxFitness,MaxSite=max(
35、PopulationFitness);EachGenMaxFitness=MaxFitness;if Count=1 CurrentBest(1:MumberLength)=Population(MaxSite,:); CurrentBest(MumberLength+1)=PopulationFitness(MaxSite);else if CurrentBest(MumberLength+1)PopulationFitness(MaxSite); CurrentBest(1:MumberLength)=Population(MaxSite,:); CurrentBest(MumberLen
36、gth+1)=PopulationFitness(MaxSite); endPopulation(MinSite,:)=CurrentBest(1:MumberLength);endNewPopulationIncludeMax=Population;【程序说明】子程序Elitist.m用到最佳个体保存方法(“优胜劣汰”思想)输入参数为:群体Population, 目标函数值PopulationFitness和染色体个数MumberLength“遗传算法”专题一、遗传算法的主要特征:我们的目的是获得“最好解”,可以把这种任务看成是一个优化过程。对于小空间,经典的穷举法就足够了;而对大空间,则需
37、要使用特殊的人工智能技术。遗传算法(Genetic Algorithm)是这些技术中的一种,它是一类模拟生物进化过程而产生的由选择算子、杂交算子和变异算子三个基本算子组成的全局寻优算法。它从一个初始族出发,由选择算子选出性状好的父本,由杂交算子进行杂交运算,变异算子进行少许变异,在一定概率规则控制下随机搜索模型空间。一代代进化,直到最终解族对应的误差泛函值达到设定的要求。遗传算法的结构:Procedure Genetic Algorithmbegin initialize evaluate while (not termination-condition) do beginselect fro
38、m alter evaluate end end 图1. 遗传算法的结构在第次迭代,遗传算法维持一个潜在解的群体。每个解用其“适应值”评价。然后通过选择更合适个体(次迭代)形成一个新的群体。新的群体的成员通过杂交和变异进行变换,形成新的解。杂交组合了两个亲体染色体(即待求参数的二进制编码串)的特征,通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为和,在第二个基因后杂交,产生的后代为和。杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因(染色体中的一个二进制位)。变异算子的意图是向群体引入一些额外的变化性。遗传算法的
39、特点:(1). 它不是直接作用于参变量集上,而是作用于参变量的某种编码形成的数字串上。(2). 它不是从单个点,而是从一个解族开始搜索解空间,与传统的“点对点”式的搜索方法不同。(3). 它仅仅利用适应值信息评估个体的优劣,无须求导数或其它辅助信息。(4). 它利用概率转移规则,而非确定性规则。优势:(1). 不容易陷入局部极值,能以很大的概率找到全局最优解。(2). 由于其固有的并行性,适合于大规模并行计算。二、遗传算法的运行步骤:1. 一般性描述:不失一般性,考虑求最大值的问题。问题:求一个有个变量的函数的的最大值。假设每个变量为域内的一个值,且对所有的,。假定以某个要求的精度优化函数:这
40、里取自变量小数点后第6位。1) 编码和解码:要达到要求的精度,每个域应该被分割为个等尺寸的区间。用表示使成立的最小整数。这样,对每个变量,由串长为的二进制编码表达可以满足精度要求。以下的公式对应于每个串的自变量的值:其中表示二进制串的十进制值。代表一个潜在解的染色体被长度为的二进制串表达;前位对应区间里的一个值,随后的位对应区间里的一个值,等等;最后的位对应区间里的一个值。2) 产生潜在解初始群体:简单地以位的方式随机地设定个染色体。如果确实有一些关于最优分布的知识,可以使用这些信息来设定初始潜在解的集合。3) 根据适应值评价解的适应程度并据此生成新群体:通常使用一个根据适应值调节刻度宽度的轮
41、盘。按照如下方法构造轮盘(假设这里的适应值时正值,否则可以使用一些比例机制调整): 计算每个染色体的适应值; 计算群体的总适应值: 计算每个染色体的选择概率: 计算每个染色体的累计概率: 对轮盘转动次,每次按照下面的方法为新群体选择一个单个的染色体: 产生一个在区间0,1里的随机数; 如果,则选择第一个染色体;否则选择使成立的第个染色体()。这样做的效果是:好的染色体得到多个拷贝,中等染色体保持平稳,最差染色体死亡。4) 杂交(crossover)和变异(mutation)决定新群体的性状:设杂交概率为,此概率给出预计要进行杂交的染色体个数。对于新群体中的每个染色体: 产生一个在区间0,1里的
42、随机数; 如果,则选择给定的染色体进行杂交。随机地对被选择的染色体配对:对染色体中的每一个,产生一个在区间1, (为总长,即染色体位数)里的随机整数。表示杂交点的位置。两个染色体 和 被他们的子代 和 所替代。 下一步的变异,是在一位一位(bit-by-bit)的基础上进行的。另一个遗传系统参数,变异率,给出了我们预计的变异位数:。整个群体中所有染色体的每一位都有均等的机会经历变异,即从0到1或者相反: 产生一个在区间0,1里的随机数; 如果,变异此位。随着选择、杂交和变异的进行,新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的,即建立一个根据当前适应值构造宽距的轮
43、盘。其它的部分只是上述步骤的循环重复,见图1。2. 例子:问题:求下列函数的极大值:,其中及。假定对每个变量要求的精度是小数点后第4位。图2. 函数的图按上面介绍的步骤求解此问题:1) 解码和解码:变量的定义域长度为15.1,所要求的精度意味着区间-3.0, 12.1至少要被分为15.110000个等距区间。由于,因此染色体的第一部分需要18位。变量的定义域长度为1.7,所要求的精度意味着区间4.1, 5.8至少要被分为1.710000个等距区间。由于,因此染色体的第一部分需要15位。因此染色体的总长度为位,前18位为,后15位为。例如,染色体 ()的前18位表示;后15位0010表示 ;所以
44、该染色体对应于,该染色体的适应值为。2) 产生潜在解初始群体:设,随机产生一个初始化的20个染色体组成的群体,并计算相应的适应函数值: 很明显,染色体是最好的,是最差的。3) 根据适应值评价解的适应程度并据此生成新群体:现在系统为选择过程建立一个轮盘。群体的总适应值为对每个染色体,选择概率为:每个染色体的累计概率为: 现在,准备转动轮盘20次,每次为新群体选择一个单个的染色体。假定在区间0, 1里的20个数的一个随机序列是: 0. 0. 0. 0. 0.0. 0. 0. 0. 0.0. 0. 0. 0. 0.0. 0. 0. 0. 0.第一个数大于而小于,意味着染色体被选择;第二个数大于而小于,意味着染色体被选择,等等。最后,新群体由以下染色体组成:4) 杂交(crossover)和变异(mutation)决定新群体的性状:设杂交概率,所以预计染色体中平均有25%(即20个中的5个)将经历杂交。杂交按照下面的方法进行:对新群体中的每个染色体,产生一个在区间0, 1里的随机数,如果,则选择一个给定的染色体进行杂交。假定随机序列为:这说明染色体、和被选择杂交。这里很幸运,给选择的染色体数是偶数,可以很容易地配对;如果选择的染色体数为奇数,可以加入一额外的染色体或者移走一被选择染色
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 南通大学杏林学院《中学美术课程标准与教材研究》2023-2024学年第二学期期末试卷
- 辽宁师范大学《急诊医学Ⅰ》2023-2024学年第二学期期末试卷
- 漳州职业技术学院《化学课堂教学技能训练》2023-2024学年第二学期期末试卷
- 江西冶金职业技术学院《建筑快题设计》2023-2024学年第二学期期末试卷
- 沈阳理工大学《固体废物处理与处置工程》2023-2024学年第二学期期末试卷
- 长春光华学院《人工智能程序设计实验》2023-2024学年第二学期期末试卷
- 茂名职业技术学院《临床流行病学》2023-2024学年第二学期期末试卷
- 昌吉学院《武术》2023-2024学年第二学期期末试卷
- 天津外国语大学《机械制图(二)》2023-2024学年第二学期期末试卷
- 浙大宁波理工学院《数字电视中心技术》2023-2024学年第二学期期末试卷
- 【MOOC】大学英语视听导学-湖南大学 中国大学慕课MOOC答案
- 2024年高考真题-化学(天津卷) 含解析
- 2024年可行性研究报告投资估算及财务分析全套计算表格(含附表-带只更改标红部分-操作简单)
- 国开2024年《机械设计基础》形考任务1-4答案
- Creo-7.0基础教程-配套课件
- 中国民主同盟入盟申请表(样表)
- 毕业设计(论文)-轴向柱塞泵设计(含全套CAD图纸)
- 公安机关通用告知书模板
- 山东省初中学业水平考试信息技术学科命题要求
- 年贴现值系数表
- 《呼吸机的使用管理》PPT课件.ppt
评论
0/150
提交评论