遗传算法讲义(2013数模培训

1、遗传算法1. 遗传算法的简单原理 遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。我们先通过一个例子来了解遗

2、传算法的原理： 假定我们要求函数的极大值，其中为自然数，。现在，我们将每一个数看成一个生命体，通过进化，我们看谁能最后生存下来，谁就是我们所寻找的数。编码:我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程叫做编码。我们可以把变量编码成5位长的二进制无符号整数表示形式，比如可表示为01101的形式，也就是说，数13的基因为01101。初始群体的生成: 由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便可以保证生物的多样性和竞争的公平性。适应度评估检测: 生物的进化服从适者生存，优胜劣汰的进化规

3、则，因此，我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称为适应度。显然，由于我们要求的最大值，因此，能使函数值较大的基因是优的，使函数值较小的基因是劣的，因此，我们可以将原函数定义为适应度函数，用来衡量某一生物体的适应程度。选择：接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰，只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌轮的方式来进行选择。交叉操作：接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便形成了两个新的生物体，为第二代。变异：生

4、物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免局部极值的问题。以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便逐渐地趋向最优，最后便能得到我们想要的结果。2 遗传算法的步骤 从上面的例子中，我们便能得到遗传算法的一般步骤，如下图所示： 3 遗传算法的应用 遗传算法主要是用来寻优，它具有很多优点：它能有效地避免局部最优现象，有及其顽强的鲁棒性，并且在寻优过程中，基本不需要任何搜索空间的知识和其他辅助信息等等。为了介绍遗传算法的应用，我们将前面的例子进行完，整个过程如下： 初始群体 011

5、01 11000 01000 10011 x的值 13 24 8 19 适应度 169 576 64 361选择概率 0.14 0.49 0.06 0.31 选择上的计数（来自赌轮） 1 2 0 1 交叉处 0110|1 1100|0 11|000 10|011 下一代群体 01100 11001 11011 10000 x的值 12 25 27 16 适应度 144 625 729 256 求解过程：将自变量在给定的范围内进行编码，得到种群编码，按照所选择的适应度函数并通过选择复制，交叉重组与变异对个体进行筛选与进化，使适应度值大的个体被保留，适应度小的个体被淘汰，新的群体继承了上一代的信息

6、，同时又优于上一代，这样反复循环，直到满足条件，最后留下来的个体集中分布在最优解周围，筛选出其中的个体作为问题的解。4遗传算法的程序设计 （1）谢尔菲德遗传算法工具箱-英国谢尔菲德大学开发 特点：1）使用MATLAB高级语言编写； 2）对问题使用M文件编写，可以看见源代码； 3）为用户提供了广泛多样的实用函数。 安装：1）解压谢尔菲德遗传算法工具箱，得到谢尔菲德遗传算法工具箱文件夹，内含DOC文件夹与gatbx文件夹； 2）将谢尔菲德遗传算法工具箱文件夹拷贝到MATLABbin目录下； 3）为谢尔菲德遗传算法工具箱文件设置工作路径：双击MATLAB，运行MATLAB，在MATLAB窗口中选择路

7、径设置窗口：Set path； 4)在Set path中选择 Add folder项； 5）设置如下：谢尔菲德遗传算法工具箱文件；谢尔菲德遗传算法工具箱文件DOC；谢尔菲德遗传算法工具箱文件gatbx；谢尔菲德遗传算法工具箱文件gatbxtest_fns。点击SAVE保存，再点击CLOSE关闭Set path窗口。 6）将文件夹的所有字母改为小写字母。 7）测试：在Command Window窗口键入：help crtbp。 谢尔菲德遗传算法工具箱中主要函数函数分类 函数 功能 创建 种群crtbase 创建基向量crtbp 创建离散的随机种群 crtrp 创建实数随机种群适应度计算ranki

8、ng 基于排序的适应度分配scaling 比率适应度计算选择函数reins一致随机和基于适应度的重插入rws轮盘选择select高级选择例程sus随即便利采样交叉算子recdis高级重组recint中间重组recline线性重组recmut具有变异特征的线性重组recombin高级重组算子xovdp两点交叉算子xovdprs减少代理的两点交叉xovmp通常多点交叉xovsh洗牌交叉xovshrs减少代理的洗牌交叉xovsp单点交叉xovsprs减少代理的单点交叉变异算子mut离散变异mutate高级变异函数mutbga实值变异子种群的支持migrate在子种群间交换个体实用函数bs2rv二进制

9、串到实值的转换rep矩阵的复制常用函数1创建离散的随机种群Chrom, Lind,BaseV=crtbp(Nind,Lind)Chrom, Lind,BaseV=crtbp(Nind,Base)Chrom, Lind,BaseV=crtbp(Nind,Lind,Base)（注意：Base 的列数就是Lind,即染色体的长度）Chrom, Lind,BaseV=crtbp(5，10)Chrom, Lind,BaseV=crtbp(5，2 3 4 5 6 7 8 9)2适应度计算函数FitnV=ranking(ObjV)3.选择算子select4.交叉算子recombin5.变异算子mut6.重插

10、入函数reins7.实用函数bs2rvPhen=bs2rv(Chrom,FieldD),其中FieldD=len;lb;ub;code;scale;lbin;ubin8.实用函数rep谢尔菲德遗传算法工具箱应用举例例1. 用遗传算法求的最小值。遗传算法参数设置种群规模最大遗传代数个体长度代沟交叉概率变异概率4020200.950.70.01程序清单如下：clcclear allclose all% 画出函数图figure(1);hold on;lb=1;ub=2; %函数自变量范围1,2ezplot(sin(10*pi*X)/X,lb,ub); %画出函数曲线xlabel(自变量/X)ylab

11、el(函数值/Y)% 定义遗传算法参数NIND=40; %个体数目MAXGEN=20; %最大遗传代数PRECI=20; %变量的二进制位数GGAP=0.95; %代沟px=0.7; %交叉概率pm=0.01; %变异概率trace=zeros(2,MAXGEN); %寻优结果的初始值FieldD=PRECI;lb;ub;1;0;1;1; %区域描述器Chrom=crtbp(NIND,PRECI); %产生初始种群% 优化gen=0; %代计数器X=bs2rv(Chrom,FieldD); %计算初始种群的十进制转换ObjV=sin(10*pi*X)./X; %计算目标函数值while gen

12、MAXGEN FitnV=ranking(ObjV); %分配适应度值 SelCh=select(sus,Chrom,FitnV,GGAP); %选择 SelCh=recombin(xovsp,SelCh,px); %重组 SelCh=mut(SelCh,pm); %变异 X=bs2rv(SelCh,FieldD); %子代个体的十进制转换 ObjVSel=sin(10*pi*X)./X; %计算子代的目标函数值 Chrom,ObjV=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群 X=bs2rv(Chrom,FieldD); gen=

13、gen+1; %代计数器增加 %获取每代的最优解及其序号，Y为最优解,I为个体的序号 Y,I=min(ObjV); trace(1,gen)=X(I); %记下每代的最优值 trace(2,gen)=Y; %记下每代的最优值endplot(trace(1,:),trace(2,:),bo); %画出每代的最优点grid on;plot(X,ObjV,b*); %画出最后一代的种群hold off% 画进化图figure(2);plot(1:MAXGEN,trace(2,:);grid onxlabel(遗传代数)ylabel(解的变化)title(进化过程)bestY=trace(2,end)

14、;bestX=trace(1,end);fprintf(最优解:nX=,num2str(bestX),nY=,num2str(bestY),n)例2. 用遗传算法求的最大值。遗传算法参数设置种群规模最大遗传代数个体长度代沟交叉概率变异概率405040（2个，每个长20）0.950.70.01程序清单如下：clcclear allclose all% 画出函数图figure(1);lbx=-2;ubx=2; %函数自变量x范围-2,2lby=-2;uby=2; %函数自变量y范围-2,2ezmesh(y*sin(2*pi*x)+x*cos(2*pi*y),lbx,ubx,lby,uby,50);

15、 %画出函数曲线hold on;% 定义遗传算法参数NIND=40; %个体数目MAXGEN=50; %最大遗传代数PRECI=20; %变量的二进制位数GGAP=0.95; %代沟px=0.7; %交叉概率pm=0.01; %变异概率trace=zeros(3,MAXGEN); %寻优结果的初始值FieldD=PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1; %区域描述器Chrom=crtbp(NIND,PRECI*2); %初始种群% 优化gen=0; %代计数器XY=bs2rv(Chrom,FieldD); %计算初始种群的十进制转换X=XY(:,

16、1);Y=XY(:,2);ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %计算目标函数值while genMAXGEN FitnV=ranking(-ObjV); %分配适应度值 SelCh=select(sus,Chrom,FitnV,GGAP); %选择 SelCh=recombin(xovsp,SelCh,px); %重组 SelCh=mut(SelCh,pm); %变异 XY=bs2rv(SelCh,FieldD); %子代个体的十进制转换 X=XY(:,1);Y=XY(:,2); ObjVSel=Y.*sin(2*pi*X)+X.*cos(2*pi*Y);

17、%计算子代的目标函数值 Chrom,ObjV=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群 XY=bs2rv(Chrom,FieldD); gen=gen+1; %代计数器增加 %获取每代的最优解及其序号，Y为最优解,I为个体的序号 Y,I=max(ObjV); trace(1:2,gen)=XY(I,:); %记下每代的最优值 trace(3,gen)=Y; %记下每代的最优值endplot3(trace(1,:),trace(2,:),trace(3,:),bo); %画出每代的最优点grid on;plot3(XY(:,1),X

18、Y(:,2),ObjV,bo); %画出最后一代的种群hold off% 画进化图figure(2);plot(1:MAXGEN,trace(3,:);grid onxlabel(遗传代数)ylabel(解的变化)title(进化过程)bestZ=trace(3,end);bestX=trace(1,end);bestY=trace(2,end);fprintf(最优解:nX=,num2str(bestX),nY=,num2str(bestY),nZ=,num2str(bestZ),n)作业：用遗传算法求函数的最小值。clcclear allclose all% 画出函数图figure(1);

19、lbx1=-2;ubx1=2; %函数自变量x1范围-2,2lbx2=-2;ubx2=2; %函数自变量x2范围-2,2ezmesh(-20*exp(-0.2*sqrt(x12+x22)/2)-exp(cos(2*pi*x1)+cos(2*pi*x2)/2)+20+2.71289,lbx1,ubx1,lbx2,ubx2,50); %画出函数曲线hold on;% 定义遗传算法参数NIND=40; %个体数目MAXGEN=50; %最大遗传代数PRECI=20; %变量的二进制位数GGAP=0.95; %代沟px=0.7; %交叉概率pm=0.01; %变异概率trace=zeros(3,MAX

20、GEN); %寻优结果的初始值FieldD=PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1; %区域描述器Chrom=crtbp(NIND,PRECI*2); %初始种群% 优化gen=0; %代计数器XY=bs2rv(Chrom,FieldD); %计算初始种群的十进制转换X=XY(:,1);Y=XY(:,2);ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %计算目标函数值while genMAXGEN FitnV=ranking(-ObjV); %分配适应度值 SelCh=select(sus,Chrom,FitnV,GGAP); %选择 SelCh=recombin(xovsp,SelCh,px);