智能控制和智能系统作业一：遗传算法

-1-遗传算法求解函数最值——by孤鸿原野摘要：遗传算法是一种十分常见的智能算法，它通过模拟生物进化过程，来求解最优化问题。本文主要介绍如何利用遗传算法求解函数的极值问题，并通过MATLAB编程，实现了对两个二元函数的最值的求解。关键字：遗传算法MATLAB编程函数最值1引言遗传算法（GeneticAlgorith，GA）最先是由美国Michgan大学的JohnHolland于1975年提出的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的一种计算模型，常被用来求解最优化问题。遗传算法从一组随机产生的称之为“种群（Population）”的初始解开始搜索过程。根据问题的性质，对种群的每个个体进行适应性评价，得到适应值（fitness），适应值代表着该个体是问题解的适合程度。同时对该种群中好的个体进行复制和选择，并随机交叉（crossover）和变异（mutation），从而得到下一代种群。如此往复，经过一代代的选择和淘汰，最终得到问题的最优解或次优解。2遗传算法操作步骤遗传算法主要实现步骤如下：（1）编码：通过选择一定的编码方式，将解空间的数据表示成遗传空间的基因串，一般采用二进制编码方式。（2）产生初始种群：随机产生一定数量的个体作为初始种群，作为迭代的开始。（3）评价个体适应度：根据实际问题设计一个评价函数，评价每个个体的适应度，即个体作为问题解的优劣性。（4）选择：根据个体的适应度，选择优秀的个体，作为下一代种群，适应度越强的个体被选择并保留下来的概率越大。（5）交叉：为了使个体能够优势互补，以一定的概率对两个个体的某些位进行交叉互换。（6）变异：以一定的概率对种群中某些个体的某些位进行变异，从而为新个体的产生创造机会。3遗传算法MATLAB程序实现根据遗传算法的操作步骤，得到MATLAB实现遗传算法的程序流程图，如图1所示。初始化产生种群评价个体适应度选择（复制）、交叉、变异结束满足退出条件？NY图1遗传算法程序流程图图中的“退出条件”可以根据种群中个体的最大适应度来选择，当种群已经进化到适应度不变时，可以退出迭代过程，或者设置最大迭代次数，到指定迭代次数后退出循环。后一种方法可以避免始终没有找到最优解的情况下无限次迭代过程。4利用遗传算法求解函数极值下面通过两个具体的实例，利用MATLAB编程实现遗传算法，来求解两个二元函数指定区域内的最值。1.求函数sinsin(,),10,10xyfxyxyxy的最大值。函数三维曲线如图2所示，直观上可以-2-看出函数在指定区间内存在一个最大值。通过求偏导数法，可以得到函数在点[0,0]处取得极大值1。图2函数sinsin(,),(10,10)xyfxyxyxy三维图形01020304050607080901000.40.60.81maxf(x,y)=sin(x)/x*sin(y)/yNc=36,Nm=5050100-2-1.5-1-0.50x050100-1.5-1-0.50y图3Nc=36，Nm=5时，遗传算法的输出曲线运行遗传算法程序（见附录），初始种群N取50，交叉个体数Nm分别取20，28，36，44，变异个体数Nc分别取1，5，10，15，个体位数取16位，交叉位数取8，变异位数取4，得到各组Nm和Nc下最大适应值和相应的位置如表1所示。选取Nc=36，Nm=5时的结果如图3所示。从图中可以看出，经过若干次次遗传操作，算法几乎可以达到函数极值位置。表1程序一次运行得到的结果NcNm最大适应值最大适应值时x值最大适应值时y值2010.9987-0.08194-0.035862050.9996-0.01541-0.00167820100.99980.0038150.00961320150.98750.18970.19822810.9996-0.0025940.047762850.9999-0.008698-0.0227328100.99230.0071710.0676028151.0000.0093080.00076303610.99910.07065-0.016943651.000-0.01450-0.00839236101.000-0.003815-0.0144436151.0000.001373-0.0038154410.99990.01480-0.0093084450.9823-0.3041-0.121044101.0000.002594-0.000152644151.0000.002899-0.0028992．求Rastrigin函数的最小值222010(cos2cos2)5,5121212fxxxxxx，函数的三维图形如图4所示。利用偏导数确定函数的最小值在点[0,0]处取得，且最小值为0。图4222010(cos2cos2)1211fxxxx三维曲线图0102030405060708090100051015minf(x1,x2)=20+x12+x22-10(cos(2*pi*x1)+cos(2*pi*x2))Nc=20,Nm=505010000.511.5x1050100-2-1012x2图5对Rastrigin函数进行一次遗传算法运行得到的曲线-3-选取初始种群数为50，个体位数为32，变异位数取2，交叉位数取16，交叉个体数取20，变异个体数取5，运行遗传算法程序，得到一次迭代结果如图4所示。从图中可以看出，经过若干次迭代后，算法基本可以找到函数最值点。5遗传算法的影响因素遗传算法寻求到最优解的准确性和速度，与很多因素有关，如变异的概率、交叉的概率和位数、适应度函数的选取等等。变异的概率越大，产生新个体的机会越大，但是优秀基因被丢失的概率也越大，故求解过程波动性越大。适应度函数的选取不当，会导致区分个体优劣性质不明显，从而减缓搜索过程。下面取一次运行结果中的两个输出结果进行比较，如图6所示，来分析变异个体数对搜索过程的影响。图（a）是在Nc=44，Nm=1时的输出结果，图（b）是在Nc=44，Nm=15时的输出结果。从两图的比较中可以看出，交叉个体数相同时，变异个体数越大（即变异的概率越大），搜索过程波动性越大。01020304050607080901000.20.40.60.81maxf(x,y)=sin(x)/x*sin(y)/yNc=44,Nm=1050100-2-1.5-1-0.50x0501000123y（a）Nc=44,Nm=1输出结果01020304050607080901000.950.960.970.980.991maxf(x,y)=sin(x)/x*sin(y)/yNc=44,Nm=1505010000.050.10.150.2x050100-0.8-0.6-0.4-0.20y（b）Nc=44,Nm=15输出结果图6不同变异概率对搜索结果的影响附录：遗传算法源程序（目标函数为1中讨论的函数）%智能控制和智能系统作业：遗传算法求解函数极值%By:孤鸿原野%Time:2011-10-10functiony=GA()clearallcloseallN=50;%种群个数Nc=[20,28,36,44];%交换个体数Nm=[1,5,10,15];%变异个体数generation=[];%遗传代数maxgeneration=100;%最大遗传代数maxfitness=[];%最大适应度数组max_X=[];%最大适应值对应的x值max_Y=[];%最大适应值对应的y值%循环操作fori=1:numel(Nc)Nc_i=Nc(i);forj=1:numel(Nm)Nm_i=Nm(j);%产生初始种群population=randint(N,32);%开始进行遗传操作fork=1:maxgenerationgeneration(k)=k;[nextgen,max_x,max_y,maxfit]=selection(population);maxfitness(k)=maxfit;max_X(k)=max_x;-4-max_Y(k)=max_y;population=nextgen;population=crossover(population,Nc_i,16);population=mutation(population,Nm_i,4);end%最大适应性MaxFitness=max(maxfitness);MaxFitnessIndex=find(maxfitness==MaxFitness);%最大适应性对应的位置：x值Max_X=max_X(MaxFitnessIndex(1));%最大适应性对应的位置：y值Max_Y=max_Y(MaxFitnessIndex(1));fprintf('最大适应值：%d\n',max(maxfitness));fprintf('位置：x=%d,y=%d\n',Max_X,Max_Y);%绘制最大适应值曲线figure((i-1)*4+j);subplot(2,2,1:2);plot(generation,maxfitness);title(sprintf('最大适应值f(x,y)=sin(x)/x*sin(y)/yNc=%d,Nm=%d',Nc_i,Nm_i));subplot(2,2,3);plot(generation,max_X);title('x');subplot(2,2,4);plot(generation,max_Y);title('y');endendend%根据个体的编码（二进制），获得个体所代表的真实值%code:个体二进制编码数组，%N:每个参数采用的二进制位数%low:参数范围下限值%high:参数范围上限值function[x1,x2]=codemap(code,N,low,high)x1=0;x2=0;fori=1:Nx1=x1+code(i)*2^(N-i);x2=x2+code(i+N)*2^(N-i);endx1=x1*(high-low)/(2^N-1)+low;x2=x2*(high-low)/(2^N-1)+low;end%目标函数，由自变量的值返回二元函数值functiony=destfun(x1,x2)if(x1==0)&&(x2~=0)y=sin(x2)/x2;endif(x1~=0)&&(x2==0)y=sin(x1)/x1;endif(x1==0)&&(x2==0)y=1;elsey=sin(x1)./x1*sin(x2)./x2;endend%利用掩码对两个个体进行交叉操作%unit1,unit2:两个待交叉的个体，均为1xN的向量，N为个体位数%bitnum:交叉位数function[unit1,unit2]=crossoverunit(unit1,unit2,bitnum)N=numel(unit1);%个体的位数%如果unit1和unit2的维数不匹配，输出错误信息if(numel(unit1)~=numel(unit2))fprintf('Thesizeofparametersdoesnotmatch\n');end%交换位数大于个体位数，输出错误信息if(Nbitnum)fprintf('crossovererror!Parameterbitnumistoolarge.\n');endmask=randperm(N);-5-fori=1:Nif(mask(i)=bitnum)t=unit1(i);unit1(i)=unit2(i);unit2(i)=t;endendend%交叉操作%pregen:交叉操作前种群%unitnum:进行交叉操作的个体数%bitnum:交叉的位数%nextgen:交叉操作后的种群functionnextgen=crossover(pregen,unitnum,bitnum)%种群个体数目row=size(pregen,1);cross=randperm(row);i=1;%交叉操作whilei*2=unitnumrow1=find(c