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

《遗传算法讲义(数模培训)》由会员分享，可在线阅读，更多相关《遗传算法讲义(数模培训)（9页珍藏版）》请在装配图网上搜索。

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

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

3、平性。 适应度评估检测:生物的进化服从适者生存，优胜劣汰的进化规则，因此， 我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称 为适应度。显然，由于我们要求的最大值，因此，能使函数值较大的基因是优的， 使函数值较小的基因是劣的，因此，我们可以将原函数f (x) = x2定义为适应度函 数，用来衡量某一生物体的适应程度。 选择:接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫 做选择。注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰， 只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以 采取赌轮的方式来进行选择。 交叉操作:接下

4、来进行交叉繁殖，随机选出两个生物体，让其交换一部分基 因，这样便形成了两个新的生物体，为第二代。 .变异:生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变 异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动， 能避免局部极值的问题。以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便 逐渐地趋向最优，最后便能得到我们想要的结果。2 遗传算法的步骤从上面的例子中，我们便能得到遗传算法的一般步骤，如下图所示：遗传算法主要是用来寻优，它具有很多优点：它能有效地避免局部最优现象，有及其顽强的鲁棒性，并且在寻优过程中，基本不需要任何搜 索空间的知识和其他辅

5、助信息等等。为了介绍遗传算法的应用，我们将前面 的例子进行完，整个过程如下：初始群体01101 11000 01000 10011x的值1324819适应度 f ( x)16957664361选择概率0.140.490.060.31选择上的计数(来自赌轮)1201交叉处0110|11100|011|00010|011下一代群体01100110011101110000X的值12252716适应度144625729256求解过程：将自变量在给定的范围内进行编码，得到种群编码，按照所选择的 适应度函数并通过选择复制，交叉重组与变异对个体进行筛选与进化，使适应 度值大的个体被保留，适应度小的个体被淘汰

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

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

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

9、用函数bs2rv二进制串到实值的转换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. 交叉算子recombin

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

11、i*X)/X,lb,ub); %画出函数曲线xlabel(自变量 /X)ylabel(函数值/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); %计算初始种群的十进制转

12、换ObjV=sin(10*pi*X)./X; %计算目标函数值while genMAXGENFitnV=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); %重插入子代到父代，

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

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

15、uby=2; %函数自变量y范围-2,2 ezmesh(y*sin(2*pi*x)+x*cos(2*pi*y),lbx,ubx,lby,uby,50); %画出函数曲线 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(

16、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 genMAXGENFitnV=ranking(-ObjV); %分配适应度值SelCh=select(sus,Chrom,FitnV,GGAP); %选择 SelCh=recombin(xovsp,SelCh,px); %重组SelCh=mut(SelCh,pm); %变异XY=bs2rv(SelCh,Fie

17、ldD); %子代个体的十进制转换 X=XY(:,1);Y=XY(:,2);ObjVSel=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %计算子代的目标函数值Chrom,ObjV=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群 XY=bs2rv(Chrom,FieldD);gen=gen+1; %代计数器增加%获取每代的最优解及其序号，Y为最优解,1为个体的序号 Y,I=max(ObjV);trace(1:2,gen)=XY(I,:); %记下每代的最优值 trace(3,gen)=Y; %记下每代的最优值end pl

18、ot3(trace(1,:),trace(2,:),trace(3,:),bo); %画出每代的最优点 grid on;plot3(XY(:,1),XY(:,2),ObjV,bo); %画出最后一代的种群 hold off% 画进化图 figure(2);plot(1:MAXGEN,trace(3,:);grid onxlabel(遗传代数)ylabel(解的变化) titleC进化过程) bestZ=trace(3,end); bestX=trace(1,end); bestY=trace(2,end);fprintf(最优解:nX=,num2str(bestX),nY=,num2str(b

19、estY),nZ=,num2str(bestZ),n)作业：用遗传算法求函数f (x)二-20exp( 0.2cos 2k x + cos2兀 x)+ 20 + 2.71289的最小值。clcclear allclose all% 画出函数图figure(1);lbxl=-2;ubxl=2; % 函数自变量 xl 范围-2,2Ibx2=-2;ubx2=2; %函数自变量 x2 范围-2,2ezmesh(-20*exp(-0.2*sqrt(x1人2+x2人2)/2)-exp(cos(2*pi*x1)+cos(2*pi*x2)/2)+20+2.7128 9,lbxl,ubxl,lbx2,ubx2,

20、50); %画出函数曲线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=

21、XY(:,1);Y=XY(:,2); ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %计算目标函数值while genMAXGENFitnV=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);

22、%计算子代的目标函数值 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; %记下每代的最优值end plot3(trace(1,:),trace(2,:),trace(3,:),bo); %画出每代的最优点 grid on;plot3(XY(:,1),XY(:,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)