数学建模遗传算法及优化问题

.z.实验十遗传算法与优化问题一、问题背景与实验目的遗传算法〔GeneticAlgorithm—GA〕，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位．本实验将首先介绍一下遗传算法的根本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进展初步的优化计算．1．遗传算法的根本原理遗传算法的根本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表〔在计算机里用二进制码表示〕，从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的时机生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要〔目前生物界对此学说尚有争议〕．〔1〕遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念．首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下：序号遗传学概念遗传算法概念数学概念1个体要处理的根本对象、构造也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位*一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保存或复制适应值大的可行解，去掉小的可行解9穿插一组染色体上对应基因段的交换根据穿插原则产生的一组新解10穿插概率染色体对应基因段交换的概率〔可能性大小〕闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的*些元素被改变12变异概率染色体上基因变化的概率〔可能性大小〕开区间(0,1)的一个值,一般为0.001~0.0113进化、适者生存个体进展优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解〔2〕遗传算法的步骤遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个根本操作〔或称为算子〕：选择〔Selection〕、穿插〔Crossover〕、变异〔Mutation〕．遗传算法根本步骤主要是：先把问题的解表示成“染色体〞，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体〞，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境〞中，并按适者生存的原则，从中选择出较适应环境的“染色体〞进展复制，再通过穿插、变异过程产生更适应环境的新一代“染色体〞群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体〞上，它就是问题的最优解．下面给出遗传算法的具体步骤，流程图参见图1：第一步：选择编码策略，把参数集合〔可行解集合〕转换染色体构造空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、穿插、变异方法以及确定穿插概率、变异概率等遗传参数；第四步：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、穿插和变异算子作用于群体，形成下一代群体；第七步：判断群体性能是否满足*一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步．产生初始群体产生初始群体是否满足终止条件得到结果完毕程序是否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进展穿插插入到新群体选择一个个体进展变异插入到新群体得到新群体图1一个遗传算法的具体步骤遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止．2．遗传算法的实际应用例1：设，求．注：这是一个非常简单的二次函数求极值的问题，相信大家都会做．在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题．在此将细化地给出遗传算法的整个过程．〔1〕编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把到2这个区间的数用计算机语言表示出来．编码就是表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点〔潜在解〕都能成为GA编码空间中的点〔染色体位串〕的表现型；健全性：GA编码空间中的染色体位串必须对应问题空间中的*一潜在解；非冗余性：染色体和潜在解必须一一对应．这里我们通过采用二进制的形式来解决编码问题，将*个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为，则必须将闭区间分为等分．因为所以编码的二进制串至少需要22位．将一个二进制串〔b21b20b19…b1b0〕转化为区间对应的实数值很简单，只需采取以下两步〔Matlab程序参见附录4〕：1〕将一个二进制串〔b21b20b19…b1b0〕代表的二进制数化为10进制数：2〕对应的区间的实数：例如，一个二进制串a=<00111>表示实数0.637197．=(00111)2=2288967二进制串<00000>，<11111>，则分别表示区间的两个端点值-1和2．利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则．首先我们来随机的产生一个个体数为4个的初始群体如下：pop(1)={<11110>，%%a1<00010>，%%a2<00000>，%%a3<10101>}%%a4〔Matlab程序参见附录2〕化成十进制的数分别为：pop(1)={1.523032，0.574022，-0.697235，0.247238}接下来我们就要解决每个染色体个体的适应值问题了．〔2〕定义适应函数和适应值由于给定的目标函数在的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下根底．对于此题中的最大化问题，定义适应函数，采用下述方法：式中既可以是特定的输入值，也可以是当前所有代或最近K代中的最小值，这里为了便于计算，将采用了一个特定的输入值．假设取，则当时适应函数；当时适应函数．由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下〔Matlab程序参见附录3〕：f[pop(1)]={1.226437,1.318543,-1.380607,0.933350}然后通过适应函数计算出适应值分别如下〔Matlab程序参见附录5、附录6〕：取，g[pop(1)]={2.226437,2.318543,0,1.933350}〔3〕确定选择标准这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率．其计算公式如下：对于给定的规模为n的群体pop={}，个体的适应值为，则其入选概率为由上述给出的群体，我们可以计算出各个个体的入选概率．首先可得，然后分别用四个个体的适应值去除以，得：P(a1)=2.226437/6.478330=0.343675%%a1P(a2)=2.318543/6.478330=0.357892%%a2P(a3)=0/6.478330=0%%a3P(a4)=1.933350/6.478330=0.298433%%a4〔Matlab程序参见附录7〕〔4〕产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群〔Matlab程序参见附录8、附录11〕．要说明的是：附录11的算法与这里不完全一样．为保证收敛性，附录11的算法作了修正，采用了最正确个体保存方法〔elitistmodel〕，具体容将在后面给出介绍．由初始群体的入选概率我们淘汰掉a3，再参加a2补足成与群体同样大小的种群得到newpop(1)如下：newpop(1)={<11110>，%%a1<00010>，%%a2<00010>，%%a2<10101>}%%a4〔5〕穿插穿插也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体〔Matlab程序参见附录9〕．我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进展穿插．〔可以在任一位进展穿插〕<>，<00010>穿插得：<>，<11110><>，<10101>穿插得：<>，<00010>通过穿插得到了四个新个体，得到新的群体jchpop(1)如下：jchpop(1)={<00010>，<11110>，<10101>，<00010>}这里采用的是单点穿插的方法，当然还有多点穿插的方法，不过有些烦琐，这里就不着重介绍了．〔6〕变异变异也就是通过一个小概率改变染色体位串上的*个基因〔Matlab程序参见附录10〕．现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：pop(2)={<00010>，<11110>，<10101>，<00010>}然后重复上述的选择、穿插、变异直到满足终止条件为止．〔7〕终止条件遗传算法的终止条件有两类常见条件：〔1〕采用设定最大〔遗传〕代数的方法，一般可设定为50代，此时就可能得出最优解．此种方法简单易行，但可能不是很准确〔Matlab程序参见附录1〕；〔2〕根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进展控制．3．遗传算法的收敛性前面我们已经就遗传算法中的编码、适应度函数、选择、穿插和变异等主要操作的根本容及设计进展了详细的介绍．作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见以下图2所示．图2均衡搜索的具体实现图示应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决．目前普遍认为，标准遗传算法并不保证全局最优收敛．但是，在一定的约束条件下，遗传算法可以实现这一点．下面我们不加证明地罗列几个定理或定义，供读者参考〔在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献〕．定理1如果变异概率为，穿插概率为，同时采用比例选择法〔按个体适应度占群体适应度的比例进展复制〕，则标准遗传算法的变换矩阵P是根本的．定理2标准遗传算法〔参数如定理1〕不能收敛至全局最优解．由定理2可以知道，具有变异概率，穿插概率为以及按比例选择的标准遗传算法是不能收敛至全局最最优解．我们在前面求解例1时所用的方法就是满足定理1的条件的方法．这无疑是一个令人沮丧的结论．然而，庆幸的是，只要对标准遗传算法作一些改良，就能够保证其收敛性．具体如下：我们对标准遗传算法作一定改良，即不按比例进展选择，而是保存当前所得的最优解〔称作超个体〕．该超个体不参与遗传．最正确个体保存方法〔elitistmodel〕的思想是把群体中适应度最高的个体不进展配对穿插而直接复制到下一代中．此种选择操作又称复制〔copy〕．DeJong对此方法作了如下定义：定义设到时刻t〔第t代〕时，群体中a*〔t〕为最正确个体．又设A〔t＋1〕为新一代群体，假设A〔t＋1〕中不存在a*〔t〕，则把a*(t)作为A〔t＋1〕中的第n+1个个体〔其中，n为群体大小〕〔Matlab程序参见附录11〕．采用此选择方法的优点是，进化过程中*一代的最优解可不被穿插和变异操作所破坏．但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解．也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索．所以此方法一般都与其他选择方法结合使用．定理3具有定理1所示参数，且在选择后保存当前最优值的遗传算法最终能收敛到全局最优解．当然，在选择算子作用后保存当前最优解是一项比拟复杂的工作，因为该解在选择算子作用后可能丧失．但是定理3至少说明了这种改良的遗传算法能够收敛至全局最优解．有意思的是，实际上只要在选择前保存当前最优解，就可以保证收敛，定理4描述了这种情况．定理4具有定理1参数的，且在选择前保存当前最优解的遗传算法可收敛于全局最优解．例2：设，求，编码长度为5，采用上述定理4所述的“在选择前保存当前最优解的遗传算法〞进展．此略，留作练习．二、相关函数〔命令〕及简介本实验的程序中用到如下一些根本的Matlab函数：ones,zeros,sum,size,length,subs,double等，以及for,while等根本程序构造语句，读者可参考前面专门关于Matlab的介绍，也可参考其他数学实验章节中的“相关函数〔命令〕及简介〞容，此略．三、实验容上述例1的求解过程为：群体中包含六个染色体，每个染色体用22位0—1码，变异概率为0.01，变量区间为，取Fmin=，遗传代数为50代，则运用第一种终止条件〔指定遗传代数〕的Matlab程序为：[Count,Result,BestMember]=Genetic1(22,6,'-***+2**+0.5',-1,2,-2,0.01,50)执行结果为：Count=50Result=1.03161.03161.03161.03161.03161.03161.49901.49901.49901.49901.49901.4990BestMember=1.03161.4990图2例1的计算结果〔注：上图为遗传进化过程中每一代的个体最大适应度；而以下图为目前为止的个体最大适应度——单调递增〕我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当取1.0316时，．当然这个解和实际情况还有一点出入〔应该是取1时，〕，但对于一个计算机算法来说已经很不错了．我们也可以编制Matlab程序求在第二种终止条件下的最优解．此略，留作练习．实践说明，此时的遗传算法只要经过10代左右就可完成收敛，得到另一个“最优解〞，与前面的最优解相差无几．四、自己动手用Matlab编制另一个主程序Genetic2.m，求例1的在第二种终止条件下的最优解．提示：一个可能的函数调用形式以及相应的结果为：[Count,Result,BestMember]=Genetic2(22,6,'-***+2**+0.5',-1,2,-2,0.01,0.00001)Count=13Result=1.03921.03921.03921.03921.03921.03921.49851.49851.49851.49851.49851.4985BestMember=1.03921.4985可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小．可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只要经过10代左右就可以完成收敛，到达一个最优解．按照例2的具体要求，用遗传算法求上述例2的最优解．附录9子程序Crossing.m中的第3行到第7行为注解语句．假设去掉前面的%号，则程序的算法思想有什么变化？附录9子程序Crossing.m中的第8行至第13行的程序说明，当Dim(1)>=3时，将交换数组Population的最后两行，即交换最后面的两个个体．其目的是什么？仿照附录10子程序Mutation.m，修改附录9子程序Crossing.m，使得穿插过程也有一个概率值〔一般取0.65~0.90〕；同时适当修改主程序Genetic1.m或主程序Genetic2.m，以便代入穿插概率．设，求，要设定求解精度到15位小数．五、附录附录1：主程序Genetic1.mfunction[Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitness,Min*,Ma**,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,MemberNumber);globalCount;globalCurrentBest;Count=1;PopulationCode=Population;PopulationFitness=Fitness(PopulationCode,FunctionFitness,Min*,Ma**,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);[Population,CurrentBest,EachGenMa*Fitness]=Elitist(PopulationCode,PopulationFitness,MumberLength);EachMa*Fitness(Count)=EachGenMa*Fitness;Ma*Fitness(Count)=CurrentBest(length(CurrentBest));whileCount<GenNewPopulation=Select(Population,PopulationProbability,MemberNumber);Population=NewPopulation;NewPopulation=Crossing(Population,FunctionFitness,Min*,Ma**,MumberLength);Population=NewPopulation;NewPopulation=Mutation(Population,MutationProbability);Population=NewPopulation;PopulationFitness=Fitness(Population,FunctionFitness,Min*,Ma**,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);Count=Count+1;[NewPopulation,CurrentBest,EachGenMa*Fitness]=Elitist(Population,PopulationFitness,MumberLength);EachMa*Fitness(Count)=EachGenMa*Fitness;;Ma*Fitness(Count)=CurrentBest(length(CurrentBest));Population=NewPopulation;endDim=size(Population);Result=ones(2,Dim(1));fori=1:Dim(1)Result(1,i)=Translate(Population(i,:),Min*,Ma**,MumberLength);endResult(2,:)=PopulationFitness;BestMember(1,1)=Translate(CurrentBest(1:MumberLength),Min*,Ma**,MumberLength);BestMember(2,1)=CurrentBest(MumberLength+1);closeallsubplot(211)plot(EachMa*Fitness)subplot(212)plot(Ma*Fitness)【程序说明】主程序Genetic1.m包含了8个输入参数：(1)MumberLength：表示一个染色体位串的二进制长度．〔例1中取22〕(2)MemberNumber：表示群体中染色体的个数．〔例1中取6个〕(3)FunctionFitness：表示目标函数，是个字符串，因此用表达式时，用单引号括出．〔例1中是〕(4)Min*：变量区间的下限．〔例1中是中的〕(5)Ma**：变量区间的上限．〔例1中是中的2〕(6)Fmin：定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出．〔例1中取Fmin=〕(7)MutationProbability：表示变异的概率，一般都很小．〔例1中取0.01〕(8)Gen：表示遗传的代数，也就是终止程序时的代数．〔例1中取50〕另外，主程序Genetic1.m包含了3个输出值：Count表示遗传的代数；Result表示计算的结果，也就是最优解；BestMember表示最优个体及其适应值．附录2：子程序PopulationInitialize.mfunctionPopulation=PopulationInitialize(MumberLength,MemberNumber)Temporary=rand(MemberNumber,MumberLength);Population=(Temporary>=0.5*ones(size(Temporary)));【程序说明】子程序PopulationInitialize.m用于产生一个初始群体．这个初始群体含有MemberNumber个染色体，每个染色体有MumberLength个基因〔二进制码〕．附录3：子程序Fitness.mfunctionPopulationFitness=Fitness(PopulationCode,FunctionFitness,Min*,Ma**,MumberLength)Dim=size(PopulationCode);PopulationFitness=zeros(1,Dim(1));fori=1:Dim(1)PopulationFitness(i)=Transfer(PopulationCode(i,:),FunctionFitness,Min*,Ma**,MumberLength);end【程序说明】子程序Fitness.m用于计算群体中每一个染色体的目标函数值．子程序中含有5个输入参数：PopulationCode表示用0—1代码表示的群体，FunctionFitness表示目标函数，它是一个字符串，因此写入调用程序时，应该用单引号括出，MumberLength表示染色体位串的二进制长度．Min*和Ma**分别指变量区间的上下限．附录4：子程序Translate.mfunctionPopulationData=Translate(PopulationCode,Min*,Ma**,MumberLength)PopulationData=0;Dim=size(PopulationCode);fori=1:Dim(2)PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLength-i));endPopulationData=Min*+PopulationData*(Ma**-Min*)/(2^Dim(2)-1);【程序说明】子程序Translate.m把编成码的群体翻译成变量的数值．含有4个输入参数，PopulationCode,Min*,Ma**,MumberLength．附录5：子程序Transfer.mfunctionPopulationFitness=Transfer(PopulationCode,FunctionFitness,Min*,Ma**,MumberLength)PopulationFitness=0;PopulationData=Translate(PopulationCode,Min*,Ma**,MumberLength);PopulationFitness=double(subs(FunctionFitness,'*',sym(PopulationData)));【程序说明】子程序Transfer把群体中的染色体的目标函数值用数值表示出来，它是Fitness的重要子程序．其有5个输入参数分别为PopulationCode,FunctionFitness,Min*,Ma**，MumberLength．附录6：子程序FitnessF.mfunctionPopulationFitnessF=FitnessF(PopulationFitness,Fmin)Dim=size(PopulationFitness);PopulationFitnessF=zeros(1,Dim(2));fori=1:Dim(2)ifPopulationFitness(i)>FminPopulationFitnessF(i)=PopulationFitness(i)-Fmin;endifPopulationFitness(i)<=FminPopulationFitnessF(i)=0;endend【程序说明】子程序FitnessF.m是用于计算每个染色体的适应函数值的．其输入参数如下：PopulationFitness为群体中染色体的目标函数值，Fmin为定义适应函数过程中给出的一个目标函数的可能的最小值．附录7：子程序Probability.mfunctionPopulationProbability=Probability(PopulationFitness)SumPopulationFitness=sum(PopulationFitness);PopulationProbability=PopulationFitness/SumPopulationFitness;【程序说明】子程序Probability.m用于计算群体中每个染色体的入选概率，输入参数为群体中染色体的适应函数值PopulationFitness．附录8：子程序Select.mfunctionNewPopulation=Select(Population,PopulationProbability,MemberNumber)CProbability(1)=PopulationProbability(1);fori=2:MemberNumberCProbability(i)=CProbability(i-1)+PopulationProbability(i);endfori=1:MemberNumberr=rand(1);Inde*=1;whiler>CProbability(Inde*)Inde*=Inde*+1;endNewPopulation(i,:)=Population(Inde*,:);end【程序说明】子程序Select.m根据入选概率〔计算累计概率〕在群体中按比例选择局部染色体组成种群，该子程序的3个输入参数分别为：群体Population，入选概率PopulationProbability，群体中染色体的个数MemberNumber．附录9：子程序Crossing.mfunctionNewPopulation=Crossing(Population,FunctionFitness,Min*,Ma**,MumberLength)%%PopulationFitness=%%Fitness(Population,FunctionFitness,Min*,Ma**,MumberLength);%%PopulationProbability=Probability(PopulationFitness);%%[SortResult,SortSite]=sort(PopulationProbability);%%Population=Population(SortSite,:);Dim=size(Population);ifDim(1)>=3Temp=Population(Dim(1),:);Population(Dim(1),:)=Population(Dim(1)-1,:);Population(Dim(1)-1,:)=Temp;endfori=1:2:Dim(1)-1SiteArray=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，Min*，Ma**，MumberLength．附录10：子程序Mutation.mfunctionNewPopulation=Mutation(Population,MutationProbability)Dim=size(Population);fori=1:Dim(1)Probability=rand(1);Site=randperm(Dim(2));ifProbability<MutationProbabilityifPopulation(i,Site(1))==1Population(i,Site(1))=0;endifPopulation(i,Site(1))==0Population(i,Site(1))=1;endendendNewPopulation=Population;【程序说明】子程序Mutation.m用于群体中少量个体变量并产生新的群体．输入参数为：群体Population和变异概率MutationProbability．附录11：子程序Elitist.mfunction[NewPopulationIncludeMa*,CurrentBest,EachGenMa*Fitness]=Elitist(Population,PopulationFitness,MumberLength)globalCountCurrentBest;[MinFitness,MinSite]=min(PopulationFitness);[Ma*Fitness,Ma*Site]=ma*(PopulationFitness);EachGenMa*Fitness=Ma*Fitness;ifCount==1CurrentBest(1:MumberLength)=Population(Ma*Site,:);CurrentBest(MumberLength+1)=PopulationFitness(Ma*Site);elseifCurrentBest(MumberLength+1)<PopulationFitness(Ma*Site);CurrentBest(1:MumberLength)=Population(Ma*Site,:);CurrentBest(MumberLength+1)=PopulationFitness(Ma*Site);endPopulation(MinSite,:)=CurrentBest(1:MumberLength);endNewPopulationIncludeMa*=Population;【程序说明】子程序Elitist.m用到最正确个体保存方法〔“优胜劣汰〞思想〕．输入参数为：群体Population,目标函数值PopulationFitness和染色体个数MumberLength．“遗传算法〞专题一、遗传算法的主要特征： 我们的目的是获得“最好解〞，可以把这种任务看成是一个优化过程。对于小空间，经典的穷举法就足够了；而对大空间，则需要使用特殊的人工智能技术。遗传算法(GeneticAlgorithm)是这些技术中的一种，它是一类模拟生物进化过程而产生的由选择算子、杂交算子和变异算子三个根本算子组成的全局寻优算法。它从一个初始族出发，由选择算子选出性状好的父本，由杂交算子进展杂交运算，变异算子进展少许变异，在一定概率规则控制下随机搜索模型空间。一代代进化，直到最终解族对应的误差泛函值到达设定的要求。遗传算法的构造： ProcedureGeneticAlgorithm begininitializeevaluatewhile(nottermination-condition)dobeginselectfromalterevaluateendend 图1.遗传算法的构造 在第次迭代，遗传算法维持一个潜在解的群体。每个解用其“适应值〞评价。然后通过选择更适宜个体〔次迭代〕形成一个新的群体。新的群体的成员通过杂交和变异进展变换，形成新的解。杂交组合了两个亲体染色体〔即待求参数的二进制编码串〕的特征，通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为和，在第二个基因后杂交，产生的后代为和。杂交算子的目的是在不同潜在解之间进展信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因〔染色体中的一个二进制位〕。变异算子的意图是向群体引入一些额外的变化性。遗传算法的特点：(1).它不是直接作用于参变量集上，而是作用于参变量的*种编码形成的数字串上。(2).它不是从单个点，而是从一个解族开场搜索解空间，与传统的“点对点〞式的搜索方法不同。(3).它仅仅利用适应值信息评估个体的优劣，无须求导数或其它辅助信息。(4).它利用概率转移规则，而非确定性规则。优势：(1).不容易陷入局部极值，能以很大的概率找到全局最优解。(2).由于其固有的并行性，适合于大规模并行计算。二、遗传算法的运行步骤：1.一般性描述： 不失一般性，考虑求最大值的问题。问题：求一个有求一个有个变量的函数的的最大值。假设每个变量为域内的一个值，且对所有的，。假定以*个要求的精度优化函数：这里取自变量小数点后第6位。编码和解码：要到达要求的精度，每个域应该被分割为个等尺寸的区间。用表示使成立的最小整数。这样，对每个变量，由串长为的二进制编码表达可以满足精度要求。以下的公式对应于每个串的自变量的值：其中表示二进制串的十进制值。 代表一个潜在解的染色体被长度为的二进制串表达；前位对应区间[]里的一个值，随后的位对应区间[]里的一个值，等等；最后的位对应区间[]里的一个值。产生潜在解初始群体： 简单地以位的方式随机地设定个染色体。如果确实有一些关于最优分布的知识，可以使用这些信息来设定初始潜在解的集合。根据适应值评价解的适应程度并据此生成新群体： 通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构造轮盘〔假设这里的适应值时正值，否则可以使用一些比例机制调整〕：计算每个染色体的适应值；计算群体的总适应值：计算每个染色体的选择概率：计算每个染色体的累计概率： 对轮盘转动次，每次按照下面的方法为新群体选择一个单个的染色体：产生一个在区间[0，1]里的随机数；如果，则选择第一个染色体；否则选择使成立的第个染色体()。这样做的效果是：好的染色体得到多个拷贝，中等染色体保持平稳，最差染色体死亡。杂交(crossover)和变异(mutation)——决定新群体的性状：设杂交概率为，此概率给出预计要进展杂交的染色体个数。对于新群体中的每个染色体：产生一个在区间[0，1]里的随机数；如果，则选择给定的染色体进展杂交。随机地对被选择的染色体配对：对染色体中的每一个，产生一个在区间[1,]〔为总长，即染色体位数〕里的随机整数。表示杂交点的位置。两个染色体和被他们的子代和所替代。下一步的变异，是在一位一位(bit-by-bit)的根底上进展的。另一个遗传系统参数，变异率，给出了我们预计的变异位数：。整个群体中所有染色体的每一位都有均等的时机经历变异，即从0到1或者相反：产生一个在区间[0，1]里的随机数；如果，变异此位。随着选择、杂交和变异的进展，新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽距的轮盘。其它的局部只是上述步骤的循环重复，见图1。2.例子：问题：求以下函数的极大值：，其中及。假定对每个变量要求的精度是小数点后第4位。图2.函数的图按上面介绍的步骤求解此问题：解码和解码：变量的定义域长度为15.1，所要求的精度意味着区间[-3.0,12.1]至少要被分为15.1×10000个等距区间。由于，因此染色体的第一局部需要18位。变量的定义域长度为1.7，所要求的精度意味着区间[4.1,5.8]至少要被分为1.7×10000个等距区间。由于，因此染色体的第一局部需要15位。因此染色体的总长度为位，前18位为，后15位为。例如，染色体(00010)的前18位0表示；后15位0010表示；所以该染色体对应于，该染色体的适应值为。产生潜在解初始群体：设，随机产生一个初始化的20个染色体组成的群体，并计算相应的适应函数值：很明显，染色体是最好的，是最差的。根据适应值评价解的适应程度并据此生成新群体：现在系统为选择过程建立一个轮盘。群体的总适应值为对每个染色体，选择概率为：每个染色体的累计概率为：现在，准备转动轮盘20次，每次为新群体选择一个单个的染色体。假定在区间[0,1]里的20个数的一个随机序列是：0.5138700.1757410.3086520.5345340.9476280.1717360.7022310.2264310.4947730.4247200.7038990.3896470.2772260.3680710.9834370.0053980.7656820.6464730.7671390.780237第一个数大于而小于，意味着染色体被选择；第二个数大于而小于，意味着染色体被选择，等等。最后，新群体由以下染色体组成：杂交(crossover)和变异(mutation)——决定新群体的性状：设杂交概率，所以预计染色体中平均有25%〔即20个中的5个〕将经历杂交。杂交按照下面的方法进展：对新群体中的每个染色体，产生一个在区间[0,1]里的随机数，如果，则选择一个给定的染色体进展杂交。假定随机序列为：这说明染色体、、和被选择杂交。这里很幸运，给选择的染色体数是偶数，可以很容易地配对；如果选择的染色体数为奇数，可以参加一额外的染色体或者移走一被选择染色体，这种选择同样是随机的。对被选择染色体随机进展配对：设为前两个〔即和〕和后两个〔即和〕被配对。对这两对中的每一对，产生区间[1,32]〔33为染色体总长度〕里的一个随机整数。数字表示杂交点的位置。第一对染色体是：产生的数为。这对染色体在第9位后的局部互换，生成新的一对染色体：第二对染色体是：产生的数为。这对染色体在第20位后的局部互换，生成的新的染色体对为：群体的当前版本为：下一步操作——变异是在一位一位根底上进展的。变异概率，所以我们预计平均将有1%的位经历变异。整个群体共有位；可以预计平均每代有6.6次变异。因为每一位都有均等的时机被变异，所以对群体中的每一位可以产生区间[0,1]里的一个随机数，如果，则变异此位。这说明我们必须产生660个随机数。在运行的例子中，共产生5个小于0.01的数：变异位号和产生的随机数如表2.1所示：表2.2把染色体中的位号翻译成染色体中的位数：这就意味着有四个染色体通过变异而改变；其中一个染色体〔第13个〕有两位基因发生变化。变异位以黑体表示。对修正的染色体去掉撇号，最新的染色体群体如下：这里只完成了图1中的遗传过程while循环中的一次迭代〔即一代〕。检查一下新群体的评价过程，对每个染色体进展解码，并计算解码后的的适应函数值，得到： 注意新群体的总适应值为447.049688，高于先前群体的总适应值387.776822。同时，当前最好染色体的评价值(33.351874)要好于先前群体的最好染色体的评价值(30.060205)。 现在准备再运行以此选择过程：应用遗传算子及评价下一代等。经过1000代后，群体及其适应值为： 但是，仔细检查整个运行过程，可以发现早期代中的*些染色体的适应值要好于经过1000代后的最好染色体值35.47938。例如，第396代中的最好染色体的值为38.827553。这是由于取样的随机误差造成的。跟踪进化过程中的最好个体是容易的。在遗传算法的实现中，通常在一独立出来的位置保存“曾经最好〞的个体；用这种方法，算法将报告整个过程的最好值，而不只是最终群体的最好值。三、遗传算法的理论根底： 遗传算法的理论根底是遗传算法解的二进制表达式及模式的含义。模式是能对染色体之间相似性进展解释的模板。一个模式是通过引入通配符(*)到基因字母表中来建立的。一个模式代表所有的除“*〞外与所有位置都匹配的所有串〔搜索空间的子集〕。例如，考虑长度为10的串和模式。模式(*11100100)与两个串匹配：{(0111100100),(1111100100)}。而模式(*1*1100100)与四个串匹配：{(0101100100),(0111100100),(1101100100),(1111100100)}。显然，模式(1001110001)只代表一个串，而模式(**********)代表所有长度为10的串。很明显，每种模式准确地代表个串，这里为通配符(*)在模式模板中的个数。另一方面，每个长度为的串匹配个模式〔每位上可以为原数码和*两种可能〕。 不同的模式有不同的特性。注意到：在一个模式配符*的数目决定了匹配该模式的串数。有两个重要的模式性质：阶和定义长度。模式定理是在这些性质的根底上表达的。模式的阶〔由表示〕，为串中0和1的数目，即固定位而非通配位的数目。换句话说，它是模板长度减去通配符(*)的数目。一个模式的阶定义了模式的特殊性。如下面三个长度为10的模式：，，的阶为：，及。其中模式是最特殊的一个。模式的阶对计算变异操作种模式的存活概率时很有用的，随后将讨论。模式的定义长度〔由表示〕，为第一个和最后一个固定串位之间的距离。它定义了包含在模式中的信息的致密度。如，，和。注意，只有单个固定点的模式的定义长度为零。模式的定义长度在计算模式杂交的存活概率时很有用，随后讨论。 遗传算法模拟进化过程包括四个不断重复的步骤：selectfromrebineevaluate 第一步〔〕简单地将演化时钟向前移动一个单位；最后一步〔evaluate〕只是对当前群体进展评价。发生在进化周期其余两个阶段的主要现象是选择和重组。这里将讨论这两步作用在群体中预定数目的模式上的效果。首先从运行一个例子开场来说明所有的定理。1． 选择： 仍然采用上一节的例子，群体规模，模式模板的长度。假定在时刻，群体为原先初始化的结果〔见P4的〕。表示时刻时群体中匹配模式的串数，如对于一个给定模式：，，因为有3个串，和匹配模式。注意模式的阶，其定义长度。 模式在时刻的适应值定义为群体中和模式匹配的所有串的平均适应值。假定在时刻，群体中匹配模式的串有个{}，则在选择过程中，中间群体是这样产生的：对个单个串进展选择。每个串根据其适应值被拷贝零次、一次或屡次。如在先前的例子中看到的那样，在一个单个串的选择中，串被选择的概率，其中为整个群体在时刻的总适应值。设经过选择步骤，有个串被模式匹配。因为：(1)对一个被模式匹配的一般串，在一个单个串的选择中，其选择概率约等于；(2)被模式匹配的串数为；(3)单个串的选择数目为，很明显，因为群体的平均适应值，所以上式可写为(1)这就意味着一个适应值在平均值之上的模式在下一代中的串数会增加，一个适应值低于平均的模式在下一代中的串数会减小，而一个中庸的模式将保持不变的水平。 上述规则的长期效果是明显的。如果假定模式高出平均，即，则，且，其中，相应于平均值之上的模式；相应于平均值之下的模式。 这是一个几何级数方程：一个平均值之上的模式不仅在下一代中串数增长，而且是几何增长。把方程〔1〕称为复制模式增长方程。 回到模式，因为在时刻有3个串，和匹配模式，模式的适应值为：同时，整个群体的平均适应值为：模式的适应值与群体平均适应值的比例为： 这就意味着如果模式保持在平均之上，则它将在下一代中保持串数的几何增长。特别地，如果模式保持在平均值之上的因子为1.396751，在时刻，预计可以得到3*1.396751=4.19个串〔可能有4个或5个〕被模式匹配；在时刻，有3*1.3967512=5.85个串，即可能有6个串，等等。根据直觉，的模式定义了搜索空间中极有希望的一局部，并且它以几何增长的方式被复制。可以用以前的实例检验对的预测。在时刻，新的群体见P5下方的。可见，模式在时刻匹配5个串：、、、和。 然而，选择本身不能产生新的潜在解，只能从中间群体中复制一些串。所以在进化周期的第二步〔重组〕中向群体中引入了新个体。这是通过杂交和变异两个算子完成的。以下依次讨论两个算子作用于群体中模式的效果。杂交：考虑下面的例子：如在前面讨论的，群体中一个单独个体的串，设为：被233种模式匹配；该串同时被下面两个模式匹配： 进一步假定上述串被选择用来杂交。根据上一节的例子〔个体和被选择进展杂交〕，假定杂交位置为。很明显，模式生存下来，即有一个后代仍然匹配。因为杂交在一个后代串上保存了第5，6，7位上的序列“111”。杂交前杂交后 另一方面，模式遭破坏：子代不与它匹配。因为在模板开场的固定位“111”和结尾的固定位“10” 很明显，模式的定义长度对其生存和损坏的概率起着很重要的作用。注意模式的定义长度为，而模式的定义长度为。 通常，杂交位是在中可能的位置上被唯一地选择的。这就意味着模式的最大消亡概率为因此，该模式的最小存活概率为实际上，我们的例子中的模式和的存活概率和消亡概率分别为：，，所以结果是可以预测的。注意实际上只有一些染色体经历杂交，并且杂交的选择性概率为。这说明一个模式的最小存活概率实际上为：再一次参考前面例子中的模式()： 注意，尽管杂交位置是在一个模式的固定位置之间选择的，该模式仍然有时机存活。例如，如果串和都是以“111”开场，“10”结尾，模式将杂交存活，当然，这种可能性非常小。因此，模式的存活概率为 所以，选择和杂交的结合给出了一个新的形式的复制模式生长公式：(2)公式(2)告诉我们在下一代中匹配模式的预测串数是实际匹配模式串数、模式的相对适应值及模式的定义长度的函数。显然，在平均之上，短的定义长度的模式将按照几何增长的速率被复制。对模式：这说明短的、平均值之上的模式将在下一代中出现几何增长的串数：在时刻，预测有3*1.374927=4.12个串被模式匹配；在时刻，将有3*1.3749272=5.67个串被模式匹配。变异：变异算子以概率随机地改变一个染色体中的*一位。其变化为从0到1或者相反。很明显，如果模式经过变异还存活，该模式上的所有固定位应保持不变。再一次考虑群体中的一个串，设为：()和模式。进一步假定串经历变异，即至少有一位发生变异。根据前一节的结果，在第9位变异，其子代为仍然被模式匹配。如果被选择变异的位置是从1到4，或者8到33，则所生成的子代仍然被模式匹配。这里只有3位〔第5，6和7位，即模式的固定位〕是很重要的：变异其中之一将破坏模式。很明显，这些重要位的数目等于模式的阶，即固定位的数目。 因为单个位变异的概率为，所以单个位存活的概率为。单个变异是和其它变异相互独立的，所以模式经过单点变异后的存活概率为由于，所以此概率可以被近似为再一次参考例子中的模式():选择、杂交和变异的组合给出了复制生长公式的新形式：(3) 正如简单公式(1)和(2)，公式(3)告诉我们在下一代中，预测匹配模式的串数是匹配模式的实际串数、模式的相对适应值和定义长度以及阶的函数。很明显，在平均值之上的、短的定义长度和低阶的模式将按照几何增长的速率被复制。 对模式：这就意味着短的、低阶、平均之上的模式将在下一代中产生几何增长的串数：在时刻预计有3*1.333024=4.00个串被模式匹配〔稍小于4.19——只考虑选择的结果，或4.12——值考虑选择和杂交的结果〕，在时刻，有3*1.3330242=5.33个这样的串〔仍小于5.85或5.67〕。 注意，公式(3.3)是基于适应值函数返回正值的假定：当用遗传算法优化可能返回负值的优化函数时，需要附加一些适应值函数和优化函数之间的映射。 概括起来，生长公式(1)显示：选择增加了平均之上的模式的复制率，并且这种变化是指数型的。复制本身并不能增加新的模式〔初始时刻的复制除外〕。这就是为什么要引入杂交算子的原因——能以构造化的方式随机地交换信息。另外，变异算子向群体引入了较大的变化性。如果一个模式是短的且低阶的，这些算子作用在该模式上的组合分裂效果是不大的。生长公式(3)的最终结果可以用下面的定理和假设表示：定理1模式定理(SchemaTheorem)：短的、低阶、平均之上的模式在遗传算子的后续代中将按几何级数增长。定理1模式定理(SchemaTheorem)：短的、低阶、平均之上的模式在遗传算子的后续代中将按几何级数增长。这一定理的直接结果是：遗传算法通过短的、低阶模式的杂交信息交换过程探求了搜索空间。假设1基因块假设(BuildingBlockHypothesis)：遗传算法是通过并列短的、低阶、高效模式〔称之为基因块〕来寻求接近最优的执行效果。假设1基因块假设(BuildingBlockHypothesis)：遗传算法是通过并列短的、低阶、高效模式〔称之为基因块〕来寻求接近最优的执行效果。虽然已有一些研究来证明此假设，但是多数重要的应用还是依赖于实验结果。遗传算法在众多问题领域中的应用支持基因块假设。毫无疑问，基因块假设说明遗传算法的编码问题对其执行效果来说是至关重要的，并且这种编码应该符合短基因块的思想。四、遗传算法实现中的假设干问题和讨论：前面已给出了遗传算法运行步骤的一般描述，通过一个实例具体地考察了它的运行步骤，并给出了遗传算法的理论根底。在具体实现过程中，仍有一些问题值得