遗传算法与优化问题(重要-有代码).pdf

实验十实验十遗传算法与优化问题遗传算法与优化问题一、问题背景与实验目的一、问题背景与实验目的遗传算法Genetic AlgorithmGA，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国 Michigan 大学的教授于 1975 年首先提出的遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为 21 世纪关键智能计算之一的地位本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算1遗传算法的基本原理遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程它把问题的参数用基因代表，把问题的解用染色体代表在电脑里用二进制码表示，从而得到一个由具有不同染色体的个体组成的群体 这个群体在问题特定的环境里生存竞争，适者有最好的时机生存和产生后代 后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解 值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用电脑解决复杂问题很有用，而它本身是否完全正确并不重要目前生物界对此学说尚有争议 1遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系这些概念如下：序号序号遗传学概念遗传学概念遗传算法概念遗传算法概念数学概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，可行解所对应的适应函数或在环境压力下的生存能力值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，保留或复制适应值大的可淘汰劣质个体的操作行解，去掉小的可行解9交叉一组染色体上对应基因段的根据交叉原则产生的一组交换新解10交叉概率染色体对应基因段交换的概闭区间0,1上的一个值率可能性大小11变异染色体水平上基因变化编码的某些元素被改变染色体上基 因变化的 概率开区间(0,1)内的一个值可能性大小13进化、个体进行优胜劣汰的进化，目标函数取到最大值，最适者生存一代又一代地优化优的可行解2遗传算法的步骤遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作 或称为算子：选择 Selection、交叉 Crossover、变异 Mutation 遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解下面给出遗传算法的具体步骤，流程图参见图 1：第一步：选择编码策略，把参数集合可行解集合转换染色体结构空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；第四步：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步产生初始群体12变异概率得到结果是是否满足终止条件否结束程序计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体图 1一个遗传算法的具体步骤遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止2遗传算法的实际应用例 1：设f(x)x22x0.5，求max f(x),x1,2注：这是一个非常简单的二次函数求极值的问题，相信大家都会做在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题在此将细化地给出遗传算法的整个过程1编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把1到 2 这个区间内的数用电脑语言表示出来编码就是表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点潜在解都能成为GA 编码空间中的点染色体位串的表现型；健全性：GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个0，1二进制串当然，串长取决于求解的精度如果要设定求解精度到六位小数，由于区间长度为由于区间长度为2(1)3，则必须将闭区间，则必须将闭区间1,2分为分为3106等分因为等分因为2097152 221 3106 222 4194304所以编码的二进制串至少需要所以编码的二进制串至少需要2222 位位将一个二进制串 b21b20b19b1b0 转化为区间1,2内对应的实数值很简单，只需采取以下两步Matlab 程序参见附录 4：1将一个二进制串b21b20b19b1b0代表的二进制数化为 10 进制数：(b21b20b19b1b0)2(bi2i)10 xi0212x对应的区间1,2内的实数：x 1 x2(1)2221x2=2288967x 1 2288967 3 0.6371972221利用这种方法我们就完成了遗传算法的第一步编码，这种二进制编码的方法完全符合上述的编码的三个原则首先我们来随机的产生一个个体数为 4 个的初始群体如下：pop(1)=，%a1，%a2，%a3%a4Matlab 程序参见附录 2化成十进制的数分别为：pop(1)=，0.574022，-0.697235，0.247238 接下来我们就要解决每个染色体个体的适应值问题了2定义适应函数和适应值由于给定的目标函数f(x)x22x0.5在1,2内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础对于此题中的最大化问题，定义适应函数g(x)，采用下述方法：f(x)Fmin,若 f(x)Fmin 0g(x)0,其他式中Fmin既可以是特定的输入值，也可以是当前所有代或最近 K 代中f(x)的最小值，这里为了便于计算，将采用了一个特定的输入值假设取Fmin 1，则当f(x)1时适应函数g(x)2；当f(x)1.1时适应函数g(x)0由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下Matlab 程序参见附录 3：f pop(1)=,-1.380607,0.933350 然后通过适应函数计算出适应值分别如下 Matlab 程序参见附录 5、附录 6：取Fmin 1，gpop(1)=2.226437,2.318543,0,1.933350 3确定选择标准这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率其计算公式如下：对于给定的规模为n的群体 pop=a1,a2,a3,则其入选概率为Ps(ai)g(ai)个体ai的适应值为g(ai)，,an，g(a)ii1n,i 1,2,3,n由上述给出的群体，我们可以计算出各个个体的入选概率首先可得g(a)6.478330，ii14i14然后分别用四个个体的适应值去除以g(ai)，得：P(a1)=2.226437/=%a1P(a2)=2.318543/=0.357892%a2P(a3)=0/=0%a3P(a4)=1.933350/=%a4Matlab 程序参见附录 74产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群 Matlab 程序参见附录 8、附录 11 要说明的是：附录 11 的算法与这里不完全相同为保证收敛性，附录 11 的算法作了修正，采用了最正确个体保存方法elitist model，具体内容将在后面给出介绍由初始群体的入选概率我们淘汰掉 a3，再加入 a2 补足成与群体同样大小的种群得到 newpop(1)如下：newpop(1)=，%a1，%a2，%a2%a45交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体Matlab 程序参见附录 9 我们把之前得到的 newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉 可以在任一位进行交叉，交叉得：，交叉得：，通过交叉得到了四个新个体，得到新的群体 jchpop(1)如下：jchpop(1)=，这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重介绍了6变异变异也就是通过一个小概率改变染色体位串上的某个基因 Matlab 程序参见附录 10 现把刚得到的 jchpop(1)中第 3 个个体中的第 9 位改变，就产生了变异，得到了新的群体 pop(2)如下：pop(2)=，然后重复上述的选择、交叉、变异直到满足终止条件为止7终止条件遗传算法的终止条件有两类常见条件：1采用设定最大遗传代数的方法，一般可设定为 50 代，此时就可能得出最优解此种方法简单易行，但可能不是很精确Matlab 程序参见附录 1；2根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制3遗传算法的收敛性前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下列图 2 所示图 2均衡搜索的具体实现图示应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决目前普遍认为，标准遗传算法并不保证全局最优收敛但是，在一定的约束条件下，遗传算法可以实现这一点下面我们不加证明地罗列几个定理或定义，供读者参考在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献 定理定理 1 1如果变异概率为如果变异概率为Pm(0,1)，交叉概率为，交叉概率为Pc0,1，同时采用比例选，同时采用比例选择法按个体适应度占群体适应度的比例进行复制择法按个体适应度占群体适应度的比例进行复制，则标准遗传算法的变换矩则标准遗传算法的变换矩阵阵 P P 是基本的是基本的定理定理 2 2标准遗传算法参数如定理标准遗传算法参数如定理 1 1不能收敛至全局最优解不能收敛至全局最优解由定理 2 可以知道，具有变异概率Pm(0,1)，交叉概率为Pc0,1以及按比例选择的标准遗传算法是不能收敛至全局最最优解我们在前面求解例1 时所用的方法就是满足定理 1 的条件的方法这无疑是一个令人沮丧的结论然而，庆幸的是，只要对标准遗传算法作一些改良，就能够保证其收敛性 具体如下：我们对标准遗传算法作一定改良，即不按比例进行选择，而是保留当前所得的最优解称作超个体 该超个体不参与遗传最正确个体保存方法elitist model的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中 此种选择操作又称复制 copy De Jong对此方法作了如下定义：定义定义设到时刻 t第 t 代时，群体中a*t为最正确个体又设At1为新一代群体，假设At1中不存在a*t，则把a*(t)作为 At1中的第n+1 个个体其中，n 为群体大小 Matlab 程序参见附录 11 采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索所以此方法一般都与其他选择方法结合使用定理定理 3 3具有定理 1 所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丧失但是定理3 至少说明了这种改良的遗传算法能够收敛至全局最优解有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理 4 描述了这种情况定理定理 4 4具有定理 1 参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解例 2：设f(x)3x2x，求max f(x),x0,2，编码长度为 5，采用上述定理 4 所述的“在选择前保留当前最优解的遗传算法”进行此略，留作练习二、相关函数命令及简介二、相关函数命令及简介本实验的程序中用到如下一些基本的 Matlab 函数：ones,zeros,sum,size,length,subs,double 等，以及 for,while 等基本程序结构语句，读者可参考前面专门关于 Matlab 的介绍，也可参考其他数学实验章节中的“相关函数命令及简介”内容，此略三、实验内容三、实验内容上述例 1 的求解过程为：群体中包含六个染色体，每个染色体用 22 位 01 码，变异概率为 0.01，变量区间为1,2，取Fmin=2，遗传代数为50 代，则运用第一种终止条件指定遗传代数的 Matlab 程序为：Count,Result,BestMember=Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50)执行结果为：Count=50Result=BestMember=图 2例 1 的计算结果注：上图为遗传进化过程中每一代的个体最大适应度；而下列图为目前为止的个体最大适应度单调递增我们通过 Matlab 软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当x取时，Max f(x)1.4990Max f(x)1.5000当然这个解和实际情况还有一点出入 应该是x取 1 时，但对于一个电脑算法来说已经很不错了我们也可以编制 Matlab 程序求在第二种终止条件下的最优解 此略，留作练习实践说明，此时的遗传算法只要经过 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=BestMember=可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小可见这两种终止算法都是可行的，而且可以知道对于例 1 的问题，遗传算法只要经过 10 代左右就可以完成收敛，到达一个最优解2按照例 2 的具体要求，用遗传算法求上述例 2 的最优解3附录9子程序 Crossing.m中的第3行到第7行为注解语句 假设去掉前面的%号，则程序的算法思想有什么变化？4附录 9 子程序 Crossing.m 中的第 8 行至第 13 行的程序说明，当 Dim(1)=3时，将交换数组 Population 的最后两行，即交换最后面的两个个体其目的是什么？5仿照附录 10 子程序 MutationGenetic2.m，以便代入交叉概率6设f(x)x24x1，求max f(x),x2,2，要设定求解精度到 15 位小数五、附录五、附录functionCount,Result,BestMember=Genetic1(MumberLength,MemberNumber,FunctionFitness,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,MemberNumber);global Count;global CurrentBest;Count=1;PopulationCode=Population;PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);Population,CurrentBest,EachGenMaxFitness=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.mfunctionPopulationFitness=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 个输入参数：PopulationCode 表示用 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+PopulationCode(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)PopulationFitness=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 PopulationFitnessF=FitnessF(PopulationFitness,Fmin)Dim=size(PopulationFitness);PopulationFitnessF=zeros(1,Dim(2);for i=1:Dim(2)if PopulationFitness(i)FminPopulationFitnessF(i)=PopulationFitness(i)-Fmin;endif PopulationFitness(i)CProbability(Index)Index=Index+1;endNewPopulation(i,:)=Population(Index,:);end【程序说明】子程序 Select.m 根据入选概率计算累计概率在群体中按比例选择部分染色体组成种群，该子程序的 3 个输入参数分别为：群体 Population，入选概率 PopulationProbability，群体中染色体的个数 MemberNumberfunction NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)%PopulationFitness=%Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);%PopulationProbability=Probability(PopulationFitness);%SortResult,SortSite=sort(PopulationProbability);%Population=Population(SortSite,:);Dim=size(Population);if Dim(1)=3Temp=Population(Dim(1),:);Population(Dim(1),:)=Population(Dim(1)-1,:);Population(Dim(1)-1,:)=Temp;endfor i=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，MinX，MaxX，MumberLength附录 10：子程序 Mutation.mfunction NewPopulation=Mutation(Population,MutationProbability)Dim=size(Population);for i=1:Dim(1)Probability=rand(1);Site=randperm(Dim(2);if ProbabilityMutationProbabilityif Population(i,Site(1)=1Population(i,Site(1)=0;endif Population(i,Site(1)=0Population(i,Site(1)=1;endendendNewPopulation=Population;【程序说明】子程序 Mutation.m 用于群体中少量个体变量并产生新的群体输入参数为：群体 Population 和变异概率 MutationProbability附录 11：子程序function NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness=Elitist(Population,PopulationFitness,MumberLength)global CountCurrentBest;MinFitness,MinSite=min(PopulationFitness);MaxFitness,MaxSite=max(PopulationFitness);EachGenMaxFitness=MaxFitness;if Count=1CurrentBest(1:MumberLength)=Population(MaxSite,:);CurrentBest(MumberLength+1)=PopulationFitness(MaxSite);elseif CurrentBest(MumberLength+1)PopulationFitness(MaxSite);CurrentBest(1:MumberLength)=Population(MaxSite,:);CurrentBest(MumberLength+1)=PopulationFitness(MaxSite);endPopulation(MinSite,:)=CurrentBest(1:MumberLength);endNewPopulationIncludeMax=Population;【程序说明】子程序用到最正确个体保存方法 “优胜劣汰”思想 输入参数为：群体 Population,目标函数值 PopulationFitness 和染色体个数 MumberLength