matlab遗传算法工具箱函数及实例讲解.doc

核心函数： (1)functionpop=initializega(num,bounds,eevalFN,eevalOps,options)-初始种群的生成函数 【输出参数】 pop-生成的初始种群 【输入参数】 num-种群中的个体数目 bounds-代表变量的上下界的矩阵 eevalFN-适应度函数 eevalOps-传递给适应度函数的参数 options-选择编码形式(浮点编码或是二进制编码)precisionF_or_B,如 precision-变量进行二进制编码时指定的精度 F_or_B-为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)functionx,endPop,bPop,traceInfo=ga(bounds,evalFN,evalOps,startPop,opts,. termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)-遗传算法函数 【输出参数】 x-求得的最优解 endPop-最终得到的种群 bPop-最优种群的一个搜索轨迹 【输入参数】 bounds-代表变量上下界的矩阵 evalFN-适应度函数 evalOps-传递给适应度函数的参数 startPop-初始种群 optsepsilonprob_opsdisplay-opts(1:2)等同于initializega的options参数，第三个参数控制是否输出，一般为0。如1e-610 termFN-终止函数的名称,如maxGenTerm termOps-传递个终止函数的参数,如100 selectFN-选择函数的名称,如normGeomSelect selectOps-传递个选择函数的参数,如0.08 xOverFNs-交叉函数名称表，以空格分开，如arithXoverheuristicXoversimpleXover xOverOps-传递给交叉函数的参数表，如20;23;20 mutFNs-变异函数表，如boundaryMutationmultiNonUnifMutationnonUnifMutationunifMutation mutOps-传递给交叉函数的参数表,如400;61003;41003;400 【注意】matlab工具箱函数必须放在工作目录下 【问题】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0=x=9 【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08 【程序清单】 %编写目标函数 functionsol,eval=fitness(sol,options) x=sol(1); eval=x+10*sin(5*x)+7*cos(4*x); %把上述函数存储为fitness.m文件并放在工作目录下 initPop=initializega(10,09,fitness);%生成初始种群，大小为10 xendPop,bPop,trace=ga(09,fitness,initPop,1e-611,maxGenTerm,25,normGeomSelect,. 0.08,arithXover,2,nonUnifMutation,2253)%25次遗传迭代 运算借过为：x= 7.856224.8553(当x为7.8562时，f（x）取最大值24.8553) 注：遗传算法一般用来取得近似最优解，而不是最优解。另外遗传算法的收敛性跟其初始值有关，大家运行上面的命令所得到的借过可能跟我的借过不同或是差别很大。但多执行几次上面的命令（随即取不同的初始群体）一定可以得到近似最优解。 遗传算法实例2 【问题】在5=Xi=5,i=1,2区间内，求解 f(x1,x2)=-20*exp(-0.2*sqrt(0.5*(x1.2+x2.2)-exp(0.5*(cos(2*pi*x1)+cos(2*pi*x2)+22.71282的最小值。 【分析】种群大小10，最大代数1000，变异率0.1,交叉率0.3 【程序清单】 源函数的matlab代码 functioneval=f(sol) numv=size(sol,2); x=sol(1:numv); eval=-20*exp(-0.2*sqrt(sum(x.2)/numv)-exp(sum(cos(2*pi*x)/numv)+22.71282; %适应度函数的matlab代码 functionsol,eval=fitness(sol,options) numv=size(sol,2)-1; x=sol(1:numv); eval=f(x); eval=-eval; %遗传算法的matlab代码 bounds=ones(2,1)*-55; p,endPop,bestSols,trace=ga(bounds,fitness) 注：前两个文件存储为m文件并放在工作目录下，运行结果为 p= 0.0000-0.00000.0055旅行商问题(travelingsalemanproblem,简称tsp)： 已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？ 用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。 这个问题可分为对称旅行商问题(dij=dji,任意i,j=1,2,3，,n)和非对称旅行商问题(dijdji,任意i,j=1,2,3，,n)。 若对于城市v=v1,v2,v3,vn的一个访问顺序为t=(t1,t2,t3,ti,tn),其中tiv(i=1,2,3,n)，且记tn+1=t1，则旅行商问题的数学模型为： minl=d(t(i),t(i+1)（i=1,n） 旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。 遗传算法： 初始化过程：用v1,v2,v3,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。 适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=d(t(i),t(i+1). 评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).(i-1)。随机规划与模糊规划 选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。 step1、对每个染色体vi,计算累计概率qi，q0=0;qi=eval(vj)j=1,i;i=1,pop-size. step2、从区间(0,pop-size)中产生一个随机数r； step3、若qi-1rqi,则选择第i个染色体； step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。 grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码遗传算法原理及应用可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如： 815216107431114612951813171 对应： 81421386325734324221。 交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复以下过程：从0，1中产生一个随机数r，如果rpc，则选择vi作为一个父代。 将所选的父代两两组队，随机产生一个位置进行交叉，如： 81421386325734324221 6123568563185633211 交叉后为： 81421386325185633211 6123568563734324221 变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在rpm的标准下选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异（该变异点xk的取值范围为ukmin,ukmax,产生一个0，1中随机数r，该点变异为xk=ukmin+r(ukmax-ukmin)）操作。如： 81421386325734324221 变异后： 814213106322734524121 反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。 循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。 functionbestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha) % % %bestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha) %d:距离矩阵 %termops:种群带数 %num:每带染色体的个数 %pc:交叉概率 %cxops:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxops，可以随机产生。 %pm:变异概率 %alpha:评价函数eval(vi)=alpha*(1-alpha).(i-1). %bestpop:返回的最优种群 %trace:进化轨迹 %- %#版权所有！欢迎广大网友改正，改进！# %e-mail: %# % citynum=size(d,2); n=nargin; ifn2 disp(缺少变量！) disp(_开个玩笑_) end ifn2 termops=500; num=50; pc=0.25; cxops=3; pm=0.30; alpha=0.10; end ifn3 num=50; pc=0.25; cxops=3; pm=0.30; alpha=0.10; end ifn4 pc=0.25; cxops=3; pm=0.30; alpha=0.10; end ifn5 cxops=3; pm=0.30; alpha=0.10; end ifn6 pm=0.30; alpha=0.10; end ifn7 alpha=0.10; end ifisempty(cxops) cxops=3; end t=initializega(num,citynum); fori=1:termops l=f(d,t); x,y=find(l=max(l); trace(i)=-l(y(1); bestpop=t(y(1),:); t=select(t,l,alpha); g=grefenstette(t); g1=crossover(g,pc,cxops); g=mutation(g1,pm);%均匀变异 t=congrefenstette(g); end - functiont=initializega(num,citynum) fori=1:num t(i,:)=randperm(citynum); end - functionl=f(d,t) m,n=size(t); fork=1:m fori=1:n-1 l(k,i)=d(t(k,i),t(k,i+1); end l(k,n)=d(t(k,n),t(k,1); l(k)=-sum(l(k,:); end - functiont=select(t,l,alpha) m,n=size(l); t1=t; beforesort,aftersort1=sort(l,2);%fsortfromltou fori=1:n aftersort(i)=aftersort1(n+1-i);%change end fork=1:n; t(k,:)=t1(aftersort(k),:); l1(k)=l(aftersort(k); end t1=t; l=l1; fori=1:size(aftersort,2) evalv(i)=alpha*(1-alpha).(i-1); end m=size(t,1); q=cumsum(evalv); qmax=max(q); fork=1:m r=qmax*rand(1); forj=1:m ifj=1&rq(j-1)&r=q(j) t(k,:)=t1(j,:); end end end - functiong=grefenstette(t) m,n=size(t); fork=1:m t0=1:n; fori=1:n forj=1:length(t0) ift(k,i)=t0(j) g(k,i)=j; t0(j)=; break end end end end - functiong=crossover(g,pc,cxops) m,n=size(g); ran=rand(1,m); r=cxops; x,ru=find(ran=2 fork=1:2:length(ru)-1 g1(ru(k),:)=g(ru(k),1:r),g(ru(k+1),(r+1):n); g(ru(k+1),:)=g(ru(k+1),1:r),g(ru(k),(r+1):n); g(ru(k),:)=g1(ru(k),:); end end - functiong=mutation(g,pm)%均匀变异 m,n=size(g); ran=rand(1,m); r=rand(1,3);%daigaijin rr=floor(n*rand(1,3)+1); x,mu=find(ranpm); fork=1:length(mu) fori=1:length(r) umax(i)=n+1-rr(i); umin(i)=1; g(mu(k),rr(i)=umin(i)+floor(umax(i)-umin(i)*r(i); end end - functiont=congrefenstette(g) m,n=size(g); fork=1:m t0=1:n; fori=1:n t(k,i)=t0(g(k,i); t0(g(k,i)=; end end%/blog/more.asp?name=hitjzm&id=170一、GA的Matlab程序原理z=f(x,y)1、编码（解决初始化种群），先创建一个数组pop（popsizestringlenth）有popsize表示染色体个数列stringlenth的前一部分代表x的染色体，后一部分代表y的染色体。计算x，y染色体对所对应的十进制数值并记数组pop的第stringlenth+1，stringlenth+2列，计算f（x，y）的值并计为数组pop的第stringlenth+3列，计算每个染色体的复制概率并计为数组pop的第stringlenth+4列functionpop1fdpestringlenth=initialize(popsizestringlenthpop),pop=round(rand(popsizestringlenth),pop(.stringlenth+1=(2.(size(pop(.1.stringlenth1).2)-1.-1.0)*pop(.1.stringlenth).*()/(2.stringlenth1-1)+),pop(.stringlenth+3)=fun(pop(.stringlenth+1)pop(.stringlenth+2),pop(.stringlenth+4)=pop(.stringlenth+4)=pop(.stringlenth+3)./sum(pop(.stringlenth+3),其中fun(x)为目标函数的matlab.m文件2、确保复制过程中染色体个数保持不变的情况下确定每个染色体复制数，如果是某一染色体的复制数为负数，则令此染色体的复制数为0，复制概率为止的染色体的复制数根据其占正值总体的比率来确定，复制数=比率popsizepop(.stringlenth+5)=round(pop.Stringlenth+4).*popsize),A=sort(pop(.stringlenth+5),b=sum(A(11-a).10),(其中a为复制概率为正值的染色体个数)pop(.stringlenth+6)=round(pop(.stringlenth+5)./b).*popsize).pop(.stringlenth+6)表示每个染色体复制数3、染色体复制数，根据每个染色体的复制数重新创建新的染色体数组pop1functionparent1parent2stringlenth=parent(fdpopstringlenth),Ci=repmat(pop(i1.stringlenth)pop(istringlenth+6)11).(i=12popsize)pop1=C1C2Cpopsize,pop1=round(C1C2Cpopsize).每个初始染色体按其复制数进行复制4、选择父代进行父叉，在数组pop1中随机地使各染色体两两配对，作为父代进行父叉，创建新的数组child1和child2父叉点cpoint随机选取父叉概率pc根据实际情况人为选取functionchild1child2pmparentstringlenth=crossover(parent1parent2pcstringlenth),f=round(9*rand(1.10)+1,d=12345678910,parent1=pop1(f.),parent2=pop1(d.),if(randpc)cpoint=round(rand*(stringlenth-2)+1,child1=parent1(.1.cpoint)parent2(.cpoint+1.stringlenth),child2=parent2(.1.cpoint)parent1(.cpoint+1.stringlenth),elsechild1=parent1,child2=parent2.5、染色体变异随机选取染色体中某一个或几个基因进行变异创建新的数组child作为父代functionchild=mutation(parentpm),parent=child,if(rand(max(Q1)-0.0001)q1=i,endendW=round(9.*rand(14)+1,pop2(W1.stringlenth+3)=child(q1.)child(q2.).child2(q3.).pop(q41.stringlenth+3),m=max(max(Q1)max(Q2)max(Q3)max(Q4),end其中m为最好染色体值，循环执行上述程序即可关于2元约束问题先根据约束力方程求解2元函数fun1（x）再只需要将单约束程序中的y的下限b2换成fun1（x）即可，因为这样能限制当x取值后y的取值。多元多约束程序和2元多约束程序一样，只不过多开辟空间而已。%遗传算法(GeneticAlgorithm,GA)是近几年发展起来的一种崭新的全局优化算法， 它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个 个体的适应性的提高。这一点体现了自然界中物竞天择、适者生存进化过程。 1962年Holland教授首次提出了GA算法的思想，从而吸引了大批的研究者，迅速 推广到优化、搜索、机器学习等方面，并奠定了坚实的理论基础。 用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般 用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空 间定义的GA(GeneticAlgorithminContinuousSpace,GACS)，暂不讨论。 一个串行运算的遗传算法(SeguentialGeneticAlgoritm,SGA)按如下过程进行： (1)对待解决问题进行编码； (2)随机初始化群体X(0):=(x1,x2,xn)； (3)对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性 能好坏； (4)应用选择算子产生中间代Xr(t)； (5)对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展 有限个体的覆盖面，体现全局搜索的思想； (6)t:=t+1；如果不满足终止条件继续(3)。 GA中最常用的算子有如下几种： (1)选择算子(selection/reproduction):选择算子从群体中按某一概率成对 选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现 方法是轮盘赌(roulettewheel)模型。 (2)交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率pc进 行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 (3)变异算子(Mutation):变异算子将新个体的基因链的各位按概率pm进行变异， 对二值基因链(0,1编码)来说即是取反。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改 进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对 算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。 GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的 类的继承为我们提供了这一可能。 (2)随机初始化群体X(0):=(x1,x2,xn)； (3)对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性 能好坏； (4)应用选择算子产生中间代Xr(t)； (5)对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展 有限个体的覆盖面，体现全局搜索的思想； (6)t:=t+1；如果不满足终止条件继续(3)。 GA中最常用的算子有如下几种： (1)选择算子(selection/reproduction):选择算子从群体中按某一概率成对 选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现 方法是轮盘赌(roulettewheel)模型。 (2)交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率pc进 行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 (3)变异算子(Mutation):变异算子将新个体的基因链的各位按概率pm进行变异， 对二值基因链(0,1编码)来说即是取反。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改 进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对 算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。 GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的 类的继承为我们提供了这一可能。 定义两个基本结构：基因(ALLELE)和个体(INDIVIDUAL)，以个体的集合作为群体 类TPopulation的数据成员，而TSGA类则由群体派生出来，定义GA的基本操作。 对任一个应用实例，可以在TSGA类上派生，并定义新的操作。 TPopulation类包含两个重要过程： FillFitness:评价函数，对每个个体进行解码(decode)并计算出其适应度值， 具体操作在用户类中实现。 Statistic:对当前群体进行统计，如求总适应度sumfitness、平均适应度 average、最好个体fmax、最坏个体fmin等。 TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数， 它有4个重要的成员函数： Select:选择算子，基本的选择策略采用轮盘赌模型（如图2）。轮盘经任意 旋转停止后指针所指向区域被选中，所以fi值大的被选中的概率就大。 Crossover:交叉算子，以概率Pc在两基因链上的随机位置交换子串。 Mutation:变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。 Generate:产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每 运行一次，产生新的一代。SGA的结构及类定义如下(用C+编写)： typedefcharALLELE;/基因类型 typedefstruct ALLELE*chrom; floatfitness;/fitnessofChromosome INDIVIDUAL;/个体定义 classTPopulation/群体类定义 定义两个基本结构：基因(ALLELE)和个体(INDIVIDUAL)，以个体的集合作为群体 类TPopulation的数据成员，而TSGA类则由群体派生出来，定义GA的基本操作。 对任一个应用实例，可以在TSGA类上派生，并定义新的操作。 TPopulation类包含两个重要过程： FillFitness:评价函数，对每个个体进行解码(decode)并计算出其适应度值， 具体操作在用户类中实现。 Statistic:对当前群体进行统计，如求总适应度sumfitness、平均适应度 average、最好个体fmax、最坏个体fmin等。 TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数， 它有4个重要的成员函数： Select:选择算子，基本的选择策略采用轮盘赌模型（如图2）。轮盘经任意 旋转停止后指针所指向区域被选中，所以fi值大的被选中的概率就大。 Crossover:交叉算子，以概率Pc在两基因链上的随机位置交换子串。 Mutation:变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。 Generate:产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每 运行一次，产生新的一代。SGA的结构及类定义如下(用C+编写)： typedefcharALLELE;/基因类型 typedefstruct ALLELE*chrom; floatfitness;/fitnessofChromosome INDIVIDUAL;/个体定义 classTPopulation/群体类定义 public: intsize;/Sizeofpopulation:n intlchrom;/Lengthofchromosome:l floatsumfitness,average; INDIVIDUAL*fmin,*fmax; INDIVIDUAL*pop; TPopulation(intpopsize,intstrlength); TPopulation(); inlineINDIVIDUAL&Individual(inti)returnpopi; voidFillFitness();/评价函数 virtualvoidStatistics();/统计函数 ; classTSGA:publicTPopulation/TSGA类派生于群体类 public: floatpcross;/ProbabilityofCrossover floatpmutation;/ProbabilityofMutation intgen;/Counterofgeneration TSGA(intsize,intstrlength,floatpm=0.03,floatpc=0.6): TPopulation(size,strlength) gen=0;pcross=pc;pmutation=pm; virtualINDIVIDUAL&Select(); virtualvoidCrossover(INDIVIDUAL&parent1,INDIVIDUAL&parent2, public: intsize;/Sizeofpopulation:n intlchrom;/Lengthofchromosome:l floatsumfitness,average; INDIVIDUAL*fmin,*fmax; INDIVIDUAL*pop; TPopulation(intpopsize,intstrlength); TPopulation(); inlineINDIVIDUAL&Individual(inti)returnpopi; voidFillFitness();/评价函数 virtualvoidStatistics();/统计函数 ; classTSGA:publicTPopulation/TSGA类派生于群体类 public: floatpcross;/ProbabilityofCrossover floatpmutation;/ProbabilityofMutation intgen;/Counterofgeneration TSGA(intsize,intstrlength,floatpm=0.03,floatpc=0.6): TPopulation(size,strlength) gen=0;pcross=pc;pmutation=pm; virtualINDIVIDUAL&Select(); virtualvoidCrossover(INDIVIDUAL&parent1,INDIVIDUAL&parent2, DistributionoftheNeuralNetworks,IEEE,Trans.onNeural Networks,Vol.5,NO.1,1994,PP39-53 XiaofengQi,FrancescoPalmieri,TheoreticalAnalysisofEvolutionary AlgorithmswithanInfinitePopulationSizeinContinuousSpace.Part: BasicPropertiesofSelectionandMutation,IEEE,Trans.onNeural Networks,Vol.5,NO.1,1994,PP102-119 XiaofengQi,FrancescoPalmieri,TheoreticalAnalysisofEvolutionary AlgorithmswithanInfinitePopulationSizeinContinuousSpace.Part: AnalysisoftheDiversificationRoleofCrossover,IEEE,Trans.on NeuralNetworks,Vol.5,NO.1,1994,PP102-119 GunterRudolph,ConvergenceAnalysisofCanonicalGeneticAlgorithms, IEEE,Trans.onNeuralNetworks,Vol.5,NO.1,1994,PP96-101 AEEiben,EHLAarts,KMVanHee.Gloableconvergenceofgenetic algorithms:AMarkovchainanalysis.inParallelProblemSolvingfrom Nature.H.-P.Schwefel,R.Manner,Eds.BerlinandHeidelberg:Springer, 1991,PP4-12 WirtAtmar,NotesontheSimulationofEvolution,IEEE,Trans.on NeuralNetworks,Vol.5,NO.1,1994,PP130-147 AnthonyV.Sebald,JenniferSchlenzig,MinimaxDesignofNeuralNet ControllersforHighlyUncertainPlants,IEEE,Trans.onNeuralNetworks, Vol.5,NO.1,1994,PP73-81 方建安、邵世煌，“采用遗传算法自学习模型控制规则”，自动化理论、技 Distributi