遗传算法及优化问题重要_有代码

1、word实验十遗传算法与优化问题一、问题背景与实验目的遗传算法Genetic Algorithm GA,是模拟达尔文的遗传选择和自然淘汰 的生物进化过程的计算模型，它是由美国Michigan大学的教授于1975年首先提 出的.遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适 于并行处理与应用X围广等显著特点，奠定了它作为21世纪关键智能计算之一 的地位.本实验将首先介绍一下遗传算法的根本理论，然后用其解决几个简单的函数 最值问题，使读者能够学会利用遗传算法进展初步的优化计算.1 .遗传算法的根本原理遗传算法的根本思想正是基于模仿生物界遗传学的遗传过程.它把问题的参数用基因代表，

2、把问题的解用染色体代表在计算机里用二进制码表示，从而得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生 存竞争，适者有最好的机会生存和产生后代. 后代随机化地继承了父代的最好特 征，并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体， 即得到问题最优的解.值 得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用， 而它本身是否完全正确并不重要目前生 物界对此学说尚有争议.1遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而

3、在这个算法中要用到各种进化和遗传学的概念.首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关 系.这些概念如下：厅P遗传学概念遗传算法概念数学概念1个体要处理的根本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数 值7种群被选定的一组染色体或个体根据入选概率定出的一组 可行解8选择从群体中选择优胜的个体， 淘汰劣质个体的操作保存或复制适应值大的可 行解，去掉小的可行解9交叉一组染

4、色体上对应基因段的 交换根据父叉原如此产生的一 组新解10父叉概率染色体对应基因段交换的概 率可能住大小闭区间0,1上的一个值11变异染色体水平上基因变化编码的某些元素被改变141 / 14word12变异概率染色体上基 因变化的 概率 可能住大小开区间(0,1)内的一个值13进化、适者生存个体进展优胜劣汰的进化， 一代又一代地优化目标函数取到最大值，最 优的可行解2遗传算法的步骤遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个根本操作或称为算子：选择Selection、交叉Crossover5、变异Mutation.遗传算法根本步骤主要是：先把问题的解表示成“染色体，在

5、算法中也就 是以二进制编码的申，在执行遗传算法之前，给出一群“染色体，也就是假设 的可行解.然后，把这些假设的可行解置于问题的“环境中，并按适者生存的 原如此，从中选择出较适应环境的“染色体进展复制，再通过交叉、变异过程 产生更适应环境的新一代“染色体群. 经过这样的一代一代地进化，最后就会 收敛到最适应环境的一个“染色体上，它就是问题的最优解.下面给出遗传算法的具体步骤，流程图参见图 1:第一步：选择编码策略，把参数集合可行解集合转换染色体结构空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以与确 定交叉概率、变异概率等遗传参数；第四步

6、：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一 代群体；第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数， 不满足如此返回第五步、或者修改遗传策略再返回第六步.图1 一个遗传算法的具体步骤142 / 14word遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要 步骤，此算法会一直运行直到找到满足条件的最优解为止.2 .遗传算法的实际应用例 1:设 f(x)x2 2x 0.5,求 max f(x), x 1,2.注：这是一个非常简单的二次函数求极值的问题，相信大家都会做.

7、在此我 们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题.在此将细化地给出遗传算法的整个过程.1编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把1到2这个区间内的数用计 算机语言表小出来.编码就是表现型到基因型的映射，编码时要注意以下三个原如此：完备性：问题空间中所有点潜在解都能成为 GA编码空间中的点染色 体位用的表现型；健全性：GA编码空间中的染色体位用必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应.这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个0, 1二进制用.当然，用长取决于求解的精度.如果要设定求解精

8、 度到六位小数， 由于区间长度为2 ( 1) 3,如此必须将闭区间 1,2分为 3 106等分.因为2097152 221 3 106 222 4194304所以编码的二进制用至 少需要22位.将一个二进制用b21b20b19b1bQ转化为区间1,2内对应的实数值很简单, 只需采取以下两步Matlab程序参见附录4：代表的二进制数化为10进制数:212x'对应的区间(b21b20bl9blb3)21,2内的实数:x2bi 2i)10x0(1)1将一个二进制用b21b20b19 b1b。x'2=22889673x 1 2288967 f 0.63719721利用这种方法我们就完成

9、了遗传算法的第一步一一编码，这种二进制编码的方法完全符合上述的编码的三个原如此.首先我们来随机的产生一个个体数为 4个的初始群体如下：pop(1)=< >,% a1< >,% a2< >,% a3< >% a4 Matlab程序参见附录2化成十进制的数分别为：pop(1)= , 0.574022 , -0.697235 , 0.247238 143 / 14word接下来我们就要解决每个染色体个体的适应值问题了. 2定义适应函数和适应值由于给定的目标函数f(x)x2 2x 0.5在1,2内的值有正有负，所以必保证映射后的适应值非负，而且目也为以后

10、计算各个体的入选概率g(x),采用下述方法:若 f(x) Fmin 0其他须通过建立适应函数与目标函数的映射关系， 标函数的优化方向应对应于适应值增大的方向, 打下根底.对于此题中的最大化问题，定义适应函数/、 f(x) Fmin.g(x) 0,式中Fmin既可以是特定的输入值，也可以是当前所有代或最近K代中f(x)的最小值，这里为了便于计算，将采用了一个特定的输入值.假如取Fmin1,如此当f (x) 1时适应函数g(x) 2;当f (x)1.1时适应函数g(x) 0 .由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下 Matlab程序参见附录3：f pop(1)= , -1.

11、380607 ,0.933350 然后通过适应函数计算出适应值分别如下取 Fmin 1 ,Matlab程序参见附录5、附录6:gpop(1)= 2.226437,2.318543 ,0 ,1.933350 3确定选择标准这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值 比例叫作入选概率.其计算公式如下：对于给定的规模为n的群体pop= a1 ,a2,a3,|,an，个体ai的适应值为g(ai),如此其入选概率为 g(ai) Ps(ai) -, i 1,2,3, ,ng(aj i 1由上述给出的群体，我们可以计算出各个个体的入选概率. 4首先可得g(a) 6.478330,i

12、1 4然后分别用四个个体的适应值去除以g(ai),得：i 1P(a1)=2.226437 / =% a1P(a2)=2.318543 / = 0.357892 % a2 P(a3)=0 / =0% a3P(a4)=1.933350 / =% a4Matlab 程序参见附录 74产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体， 并用入选概率最大的个体补入种群，得到与原群体大小同样的种群Matlab程序参见附录8、附录11.要说明的是：附录11的算法与这里不完全一样.为保证收敛性，附录 11的14 4 / 14word算法作了修正，采用了最优个体保存方法elitist

13、model，具体内容将在后面给 出介绍.由初始群体的入选概率我们淘汰掉 a3,再参加a2补足成与群体同样大小的种群得到newpop(1)如下：newpop(1)=<110101110,% al<10000110A,% a2<>,% a2<>% a45交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体Matlab程序参见附录9.我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进展交叉.可以在任一位进展交叉交叉得:交叉得:通过交叉得到了四个新个体，得到新的群体jchpop (1)如下：jchpo

14、p(1)=<110101110><>,<100001100>,<>这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐， 这里就不着重介绍了.6变异变异也就是通过一个小概率改变染色体位用上的某个基因Matlab程序参见附录10.现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到 了新的群体pop(2)而下：pop(2)= <>,<>,<100001101>,<> 然后重复上述的选择、交叉、变异直到满足终止条件为止.7终止条件遗传算法的终止条件有两类常见条件：1采

15、用设定最大遗传代数的方145 / 14word法，一般可设定为50代，此时就可能得出最优解.此种方法简单易行，但可能 不是很准确Matlab程序参见附录1；2根据个体的差异来判断，通过计算 种群中基因多样性测度，即所有基因位相似程度来进展控制.3.遗传算法的收敛性前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要 操作的根本内容与设计进展了详细的介绍.作为一种搜索算法，遗传算法通过对 这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜 索，具体实现见如下图2所示.图2均衡搜索的具体实现图示应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的 求解

16、中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解 决.目前普遍认为，标准遗传算法并不保证全局最优收敛.但是，在一定的约束 条件下，遗传算法可以实现这一点.下面我们不加证明地罗列几个定理或定义，供读者参考在这些定理的证明 中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文 献.定理1如果变异概率为Pm(0,1),交叉概率为Pc 0,1,同时采用比例选择法按个体适应度占群体适应度的比例进展复制，如此标准遗传算法的变换 矩阵P是根本的.定理2标准遗传算法参数如定理1不能收敛至全局最优解.由定理2可以知道，具有变异概率Pm (0,1),交叉概率为Pc 0,1以与按

17、比例选择的标准遗传算法是不能收敛至全局最最优解.我们在前面求解例1时所用的方法就是满足定理1的条件的方法.这无疑是一个令人沮丧的结论.然而，庆幸的是，只要对标准遗传算法作一些改良，就能够保证其收敛性.具 体如下：我们对标准遗传算法作一定改良，即不按比例进展选择，而是保存当前 所得的最优解称作 超个体.该超个体不参与遗传.最优个体保存方法elitistmodel的思想是把群体中适应度最高的个体不进展配对交叉而直接复制到下一代中.此种选择操作又称复制 copy. DeJong 对此方法作了如下定义：定义 设到时刻t第t代时，群体中at为最优个体.又设At+1146 / 14word为新一代群体，假

18、如At+1中不存在a*t，如此把a*(t)作为At+1中的 第n+1个个体其中，n为群体大小Matlab程序参见附录11.采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操 作所破坏.但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加 而使进化有可能限于局部解.也就是说，该方法的全局搜索能力差，它更适合单 峰性质的搜索空间搜索，而不是多峰性质的空间搜索.所以此方法一般都与其他 选择方法结合使用.定理3具有定理1所示参数，且在选择后保存当前最优值的遗传算法最终能 收敛到全局最优解.当然，在选择算子作用后保存当前最优解是一项比拟复杂的工作，因为该解 在选择算子作用后可能丢

19、失.但是定理 3至少明确了这种改良的遗传算法能够收 敛至全局最优解.有意思的是，实际上只要在选择前保存当前最优解，就可以保 证收敛，定理4描述了这种情况.定理4具有定理1参数的，且在选择前保存当前最优解的遗传算法可收敛 于全局最优解.例2:设f(x) 3 x2 x,求max f (x), x 0,2,编码长度为5,采用上述定理4所述的“在选择前保存当前最优解的遗传算法进展.此略，留作练习.二、相关函数命令与简介本实验的程序中用到如下一些根本的Matlab函数：ones, zeros, sum, size,length, subs, double等，以与for, while等根本程序结构语句，读

20、者可参考前面 专门关于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 =147 / 14word般 1 1111r1111

21、.4D9 -/1田虹 /-1.4SSS - -I-1 JQR7iI|1|I口 片 1。 伯 如 乂 加 王 上口 延 效图2例1的计算结果注：上图为遗传进化过程中每一代的个体最大适应度；而如下图为目前为止的个体最大适应度一一单调递增我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最 优解：当 x取时，Max f(x) 1.4990 .当然这个解和实际情况还有一点出入应该是x取1时，Max f(x) 1.5000, 但对于一个计算机算法来说已经很不错了.我们也可以编制Matlab程序求在第二种终止条件下的最优解.此略，留作练 习.实践明确，此时的遗传算法只要经过10代左右就

22、可完成收敛，得到另一个“最优解，与前面的最优解相差无几.四、自己动手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 =148 / 14word可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小.可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只

23、要经过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) x2 4x 1,求max f (x), x 2,2,要设定求解精度到15位小数.五、附录f

24、unctionCount,Result,BestMember=Genetic1(MumberLength,MemberNumber,FunctionFitn ess,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,MemberNumber);global Count;global CurrentBest;Count=1;PopulationCode=Population;PopulationFitness=Fitness(PopulationCode,FunctionFitn

25、ess,MinX,MaxX,Mumbe rLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);149 / 14wordPopulation,CurrentBest,EachGenMaxFitness=Elitist(PopulationCode,Populatio nFitness,MumberLength);EachMaxFitness(Count)=EachGenMaxFitness;MaxFitness(Count

26、)=CurrentBest(length(CurrentBest);while Count<GenNewPopulation=Select(Population,PopulationProbability,MemberNumber);Population=NewPopulation;NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength);Population=NewPopulation;NewPopulation=Mutation(Population,MutationProbability);P

27、opulation=NewPopulation;PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin); PopulationProbability=Probability(PopulationFitnessF);Count=Count+1;NewPopulation,CurrentBest,EachGenMaxFitness=Elitist(Population,PopulationFitn

28、ess,MumberLength);EachMaxFitness(Count)=EachGenMaxFitness;MaxFitness(Count)=CurrentBest(length(CurrentBest);Population=NewPopulation;endDim=size(Population);Result=ones(2,Dim(1);for i=1:Dim(1)Result(1,i)=Translate(Population(i,:),MinX,MaxX,MumberLength);endResult(2,:)=PopulationFitness;BestMember(1,

29、1)=Translate(CurrentBest(1:MumberLength),MinX,MaxX,Mumb erLength);BestMember(2,1)=CurrentBest(MumberLength+1);close allsubplot(211)plot(EachMaxFitness)subplot(212)plot(MaxFitness)【程序说明】主程序 Genetic1.m包含了 8个输入参数：(1) MumberLength：表示一个染色体位用的二进制长度.例1中取22(2) MemberNumber：表示群体中染色体的个数.例1中取6个(3) FunctionFitn

30、ess：表示目标函数，是个字符串，因此用表达式时，用单150 / 14word引号括出.例1中是f (x)x2 2x 0.5(4) MinX :变量区间的下限.例1中是1,2中的(5) MaxX:变量区间的上限.例1中是1,2中的2(6) Fmin：定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出.例1中取Fmin= 2(7) MutationProbability :表示变异的概率，一般都很小.例1中取0.01(8) Gen：表示遗传的代数，也就是终止程序时的代数.例1中取50另外，主程序Genetic1.m包含了 3个输出值：Count表示遗传的代数；Result 表示

31、计算的结果，也就是最优解；BestMember表示最优个体与其适应值.附录 2：子程序 PopulationInitialize.mfunction Population=PopulationInitialize(MumberLength,MemberNumber)Temporary=rand(MemberNumber,MumberLength);Population=(Temporary>=0.5*ones(size(Temporary);【程序说明】子程序 PopulationInitialize.m用于产生一个初始群体.这个初始群 体含有MemberNumber个染色体，每个染色体

32、有 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【程序说明】子

33、程序Fitness.m用于计算群体中每一个染色体的目标函数值.子 程序中含有 5个输入参数：PopulationCode表示用01代码表示的群体， FunctionFitness表示目标函数，它是一个字符串，因此写入调用程序时，应该用 单引号括出，MumberLength表示染色体位用的二进制长度.MinX和MaxX分别指变量区间的上下限.附录4：子程序Translate.mfunction PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)PopulationData=0;Dim=size(PopulationCod

34、e);for i=1:Dim(2)PopulationData=PopulationData+PopulationCode(i)*(2A(MumberLength-i); end151 / 14wordPopulationData=MinX+PopulationData*(MaxX-MinX)/(2ADim(2)-1);【程序说明】子程序Translate.m把编成码的群体翻译成变量的数值.含有 4个 输入参数，PopulationCode,MinX,MaxX, MumberLength .附录 5:子程序 Transfer.mfunctionPopulationFitness=Transfe

35、r(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength) PopulationFitness=0;PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength);PopulationFitness=double(subs(FunctionFitness,'x',sym(PopulationData);【程序说明】子程序Transfer把群体中的染色体的目标函数值用数值表示出来， 它是Fitness的重要子程序.其有5个输入参数分别为PopulationCode

36、, 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

37、(i)<=FminPopulationFitnessF(i)=0;end end【程序说明】子程序FitnessF.m是用于计算每个染色体的适应函数值的.其输入 参数如下：PopulationFitness为群体中染色体的目标函数值，Fmin为定义适应函 数过程中给出的一个目标函数的可能的最小值.附录7：子程序Probability.mfunction PopulationProbability=Probability(PopulationFitness) SumPopulationFitness=sum(PopulationFitness);PopulationProbability=

38、PopulationFitness/SumPopulationFitness;【程序说明】子程序 Probability.m用于计算群体中每个染色体的入选概率，输 入参数为群体中染色体的适应函数值PopulationFitness附录8:子程序Select.mfunction NewPopulation=Select(Population,PopulationProbability,MemberNumber)152 / 14wordCProbability(1)=PopulationProbability(1); for i=2:MemberNumberCProbability(i)=CPro

39、bability(i-1)+PopulationProbability(i); end for i=1:MemberNumber r=rand(1);Index=1;while r>CProbability(Index) Index=Index+1;endNewPopulation(i,:)=Population(Index,:); end【程序说明】子程序 Select.m根据入选概率计算累计概率在群体中按比例 选择局部染色体组成种群，该子程序的3个输入参数分别为：群体 Population,入选才既率PopulationProbability,群体中染色体的个数 MemberNumb

40、er.functionNewPopulation=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);Populat