《智能控制和智能系统作业一：遗传算法.doc》由会员分享，可在线阅读，更多相关《智能控制和智能系统作业一：遗传算法.doc（6页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上遗传算法求解函数最值by 孤鸿原野摘要：遗传算法是一种十分常见的智能算法，它通过模拟生物进化过程，来求解最优化问题。本文主要介绍如何利用遗传算法求解函数的极值问题，并通过MATLAB编程，实现了对两个二元函数的最值的求解。关键字：遗传算法 MATLAB编程 函数最值专心-专注-专业1 引言遗传算法（Genetic Algorith，GA）最先是由美国Michgan大学的John Holland于1975年提出的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的一种计算模型，常被用来求解最优化问题。遗传算法从一组随机产生的称之为“种群（Population）”的
2、初始解开始搜索过程。根据问题的性质，对种群的每个个体进行适应性评价，得到适应值（fitness），适应值代表着该个体是问题解的适合程度。同时对该种群中好的个体进行复制和选择，并随机交叉（crossover）和变异（mutation），从而得到下一代种群。如此往复，经过一代代的选择和淘汰，最终得到问题的最优解或次优解。2 遗传算法操作步骤遗传算法主要实现步骤如下：（1）编码：通过选择一定的编码方式，将解空间的数据表示成遗传空间的基因串，一般采用二进制编码方式。 （2）产生初始种群：随机产生一定数量的个体作为初始种群，作为迭代的开始。 （3）评价个体适应度：根据实际问题设计一个评价函数，评价每个个
3、体的适应度，即个体作为问题解的优劣性。 （4）选择：根据个体的适应度，选择优秀的个体，作为下一代种群，适应度越强的个体被选择并保留下来的概率越大。 （5）交叉：为了使个体能够优势互补，以一定的概率对两个个体的某些位进行交叉互换。（6）变异：以一定的概率对种群中某些个体的某些位进行变异，从而为新个体的产生创造机会。3 遗传算法MATLAB程序实现根据遗传算法的操作步骤，得到MATLAB实现遗传算法的程序流程图，如图1所示。图1 遗传算法程序流程图图中的“退出条件”可以根据种群中个体的最大适应度来选择，当种群已经进化到适应度不变时，可以退出迭代过程，或者设置最大迭代次数，到指定迭代次数后退出循环。
4、后一种方法可以避免始终没有找到最优解的情况下无限次迭代过程。4 利用遗传算法求解函数极值下面通过两个具体的实例，利用MATLAB编程实现遗传算法，来求解两个二元函数指定区域内的最值。1.求函数的最大值。函数三维曲线如图2所示，直观上可以看出函数在指定区间内存在一个最大值。通过求偏导数法，可以得到函数在点0,0处取得极大值1。图2 函数三维图形图3 Nc=36，Nm=5时，遗传算法的输出曲线运行遗传算法程序（见附录），初始种群N取50，交叉个体数Nm分别取20，28，36，44，变异个体数Nc分别取1，5，10，15，个体位数取16位，交叉位数取8，变异位数取4，得到各组Nm和Nc下最大适应值和
5、相应的位置如表1所示。选取Nc=36，Nm=5时的结果如图3所示。从图中可以看出，经过若干次次遗传操作，算法几乎可以达到函数极值位置。表1 程序一次运行得到的结果NcNm最大适应值最大适应值时x值最大适应值时y值2010.9987-0.08194-0.035862050.9996-0.01541-0.20100.99980.0.20150.98750.18970.19822810.9996-0.0.047762850.9999-0.-0.0227328100.99230.0.0676028151.0000.0.3610.99910.07065-0.016943651.000-0.01450-0
6、.36101.000-0.-0.0144436151.0000.-0.4410.99990.01480-0.4450.9823-0.3041-0.121044101.0000.-0.44151.0000.-0.2求Rastrigin函数的最小值函数的三维图形如图4所示。利用偏导数确定函数的最小值在点0,0处取得，且最小值为0。图4 三维曲线图图5 对Rastrigin函数进行一次遗传算法运行得到的曲线选取初始种群数为50，个体位数为32，变异位数取2，交叉位数取16，交叉个体数取20，变异个体数取5，运行遗传算法程序，得到一次迭代结果如图4所示。从图中可以看出，经过若干次迭代后，算法基本可以找
7、到函数最值点。5 遗传算法的影响因素遗传算法寻求到最优解的准确性和速度，与很多因素有关，如变异的概率、交叉的概率和位数、适应度函数的选取等等。变异的概率越大，产生新个体的机会越大，但是优秀基因被丢失的概率也越大，故求解过程波动性越大。适应度函数的选取不当，会导致区分个体优劣性质不明显，从而减缓搜索过程。下面取一次运行结果中的两个输出结果进行比较，如图6所示，来分析变异个体数对搜索过程的影响。图（a）是在Nc=44，Nm=1时的输出结果，图（b）是在Nc=44，Nm=15时的输出结果。从两图的比较中可以看出，交叉个体数相同时，变异个体数越大（即变异的概率越大），搜索过程波动性越大。（a）Nc=4
8、4,Nm=1输出结果（b）Nc=44,Nm=15输出结果图6 不同变异概率对搜索结果的影响附录：遗传算法源程序（目标函数为1中讨论的函数）% 智能控制和智能系统作业：遗传算法求解函数极值% By:孤鸿原野% Time: 2011-10-10function y=GA()clear allclose allN=50; %种群个数Nc=20,28,36,44; %交换个体数Nm=1,5,10,15;%变异个体数generation=;%遗传代数maxgeneration=100; %最大遗传代数maxfitness=;%最大适应度数组max_X=;%最大适应值对应的 x 值max_Y=;%最大适应
9、值对应的 y 值%循环操作for i=1:numel(Nc)Nc_i=Nc(i);for j=1:numel(Nm)Nm_i=Nm(j);%产生初始种群population=randint(N,32);%开始进行遗传操作for k=1:maxgeneration generation(k)=k; nextgen,max_x,max_y,maxfit=selection(population);maxfitness(k)=maxfit;max_X(k)=max_x;max_Y(k)=max_y;population=nextgen;population=crossover(population,
10、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(最大适应值： %dn,max(maxfitness);fprintf(位置：x=%d,y=%dn,Max_X,Max_Y);%绘制最大
11、适应值曲线figure(i-1)*4+j);subplot(2,2,1:2);plot(generation,maxfitness);title(sprintf(最大适应值f(x,y)=sin(x)/x*sin(y)/y Nc=%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:每个参数采用的二进制位数% l
12、ow:参数范围下限值 % high:参数范围上限值function x1,x2=codemap(code,N,low,high)x1=0;x2=0;for i=1:N x1=x1+code(i)*2(N-i); x2=x2+code(i+N)*2(N-i); end x1=x1*(high-low)/(2N-1)+low; x2=x2*(high-low)/(2N-1)+low;end%目标函数，由自变量的值返回二元函数值function y=destfun(x1,x2)if (x1=0)&(x2=0) y=sin(x2)/x2;endif (x1=0)&(x2=0) y=sin(x1)/x1
13、;endif(x1=0)&(x2=0) y=1;else y=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(The size of parameters doesnot
14、matchn); end %交换位数大于个体位数，输出错误信息 if(Nbitnum)fprintf(crossover error! Parameter bitnum is too large.n); end mask=randperm(N); for i=1:N if(mask(i)=bitnum) t=unit1(i); unit1(i)=unit2(i); unit2(i)=t; end endend%交叉操作% pregen:交叉操作前种群% unitnum:进行交叉操作的个体数% bitnum:交叉的位数% nextgen:交叉操作后的种群function nextgen=cros
15、sover(pregen,unitnum,bitnum) %种群个体数目 row=size(pregen,1); cross=randperm(row); i=1; %交叉操作 while i*2=unitnum row1=find(cross=i); unit1=pregen(row1,:); row2=find(cross=(row-i);unit2=pregen(row2,:); if(numel(unit1)*numel(unit2)=0) unit1,unit2=crossoverunit(unit1,unit2,bitnum);endpregen(row1,:)=unit1;pre
16、gen(row2,:)=unit2;i=i+1; end%更新种群nextgen=pregen;end%变异操作% pregen:进行变异操作前种群% unitnum:进行变异的个体数% bitnum:变异的位数% nextgen:进行变异操作后的种群function nextgen=mutation(pregen,unitnum,bitnum)% row:种群个体数 column:个体的位数 row,column=size(pregen); needmutation=randperm(row); for i=1:row %判断该个体是否需要变异 if needmutation(i)=unit
17、num %取出该个体进行变异操作 unit=pregen(i,:); %随机生成一个 1xN 的0-1数组bitseq，其中1的个数为 bitnum bitseq=randperm(column); for j=1:column if(bitseq(j)=bitnum) bitseq(j)=0; else bitseq(j)=1; end end%对 bitseq中的0对应的unit位进行变异操作 for k=1:column if(bitseq(k)=0) %变异：0变1，1变0 unit(k)=1-unit(k); end end pregen(i,:)=unit; end end %更新
18、种群 nextgen=pregen;end%计算适应值数组function fitness=computefitness(population) fitness=; count=size(population,1); for i=1:count x1,x2=codemap(population(i,:),16,-10,10); fitness(i)=destfun(x1,x2); endend%计算实际复制数function virtualcopy=computecopy(fitness) copy=; count=numel(fitness); meanvalue=mean(fitness)
19、; for i=1:count copy(i)=fitness(i)/meanvalue; if(copy(i)0) copy(i)=0; end end virtualcopy=round(copy); end%选择和复制操作% pregen:复制前种群 nextgen:复制后种群% maxfitness:最大适应度function nextgen,max_x,max_y,maxfitness=selection(pregen) nextgen=;fitness=computefitness(pregen); %适应值函数maxposition=find(fitness=max(fitnes
20、s); max_x,max_y=codemap(pregen(maxposition(1),:),16,-10,10); maxfitness=max(fitness);virtualcopy=computecopy(fitness);%个体期望的复制数 count=numel(fitness);%如果 virtualcopy 总和个数小于原种群个体数，全部复制 if(sum(virtualcopy)count)%还可以复制的个体数目rest=count; while rest0 maxnum=max(virtualcopy); %最大适应值个体应该复制的个数 maxindex=find(virtualcopy=maxnum);%最大适应值个体的位置if maxnum0for l=1:virtualcopy(k) nextgen=nextgen;pregen(k,:);endendend endend
