1、遗传算法求解函数优化问题的比较遗传算法求解函数优化问题的比较多极值点函数具有多个极值，对此问题，传统的优化技术很容易陷入局部最优解，求得全局优化解的概率不高，可靠性低；为此，建立尽可能大概率的求解全局优化解算法是求解函数优化的一个重要问题。遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传制）演化而来的随机搜索和优化方法，是当今影响最广泛的进化计算方法之一，是进化计算理论体系的中心。遗传算法借鉴了物种进化的思想，将欲求解问题编码，把可行解表示成字符串形式。初始化随机产生一个种群，用合理的评价函数对种群进行评估，在此基础上进行选择、交叉及变异等遗传操作。选择算子根据父代中个体适值大小进行
2、选择或淘汰，它保证了算法的最优搜索方向。交叉算子模拟基因重组及随机信息交换，产生更好个体，使其在可行域内有效搜索。变异算子模拟基因突变，保证了遗传算法的全局搜索能力。遗传算法的搜索能力主要由选择算子及交叉算子赋存，变异算子尽可能保证算法达到全局最优，避免陷入局部最优。遗传算法中的各个模块如下所示1、编码将数据进行二进制编码，其规则如下：设某一参数的取值范围为（L,U），使用长度为k的二进制编码表示该参数，则它共有2k种不同的编码。该参数编码时代对应关系为00000000000000=0-L00000000000001=1-L+00000000000010=2-L+200000000000011
3、=3-L+311111111111111=2k-1-U2、解码解码的目的是为了将不直观的二进制数据串还成十进制。是编码过程的逆过程。3、初始种群随机产生k位的0、1排列，将该排列数来表示一个染色体，每个染色体代表一个初始值。初始种群就是随机产生数量为群体规模的染色体。4、选择这里选择轮盘赌方法，轮盘赌选择又称适应度比例选择方法，是最常见也是最为著名的选择方法，由Holland 教授提出。基本原理是根据个体适应值的比例来确定个体的选择概率，是一个随机采样的过程。为了防止当前群体的最优个体在下一代发生丢失，导致遗传算法不能收敛到全局最优解，引入了精英选择策略。5、杂交假设个体A和B被选择进行杂交。
4、首先在个体中随机选择一个交配区域，如随机产生一个1到k的数，在个体A、B在该随机数后的染色体进行交换。如交换前A：00000111|110000B：01100000|001111交换后A：00000111|001111B：01100000|1100006、变异为了避免在算法迭代后期出现种群过早收敛，对于二进制的基因码组成的个体种群，实行基因码的小概率翻转，对于二进制编码即0变成1，而1变成0。例如个体01100000001111的第2个位发生变异，则个体变为00100000001111.7、个体适应度评估遗传算法利用个体的适应度函数搜索基本不利于外部信息的因素，在算法设计时，适应度函数决定系统
5、是否能寻找到系统最优解。由目标函数变换而成的适应度函数在设计时应考虑一下几个因素：适应度函数是否能反映解的优劣，该函数是否是单值的和非负的，只有满足以上因素才能设计出合理的算法。对于函数优化问题，适应度可取为函数值。8、复制将子代复制为父代。遗传算法的步骤如下所示：begint-0 初始化P(t)评价P(t)while(终止条件不满足) dobegin杂交P(t)以产生C(t)变异C(t)评价C(t)从P(t)和C(t)中选择P(t+1)t-t+1endend函数y=x.*sin(10*pi*x)+2的图像如下图所示：从上图可以看出，该函数在区间-1 2上有很多个极大值。用遗传算法计算函数y=
6、x.*sin(10*pi*x)+2在区间-1 2上的最大值，得到如下图像：从上图看出，在17代时，种群中出现了最大值，该种群几乎收敛于最优值。此时函数自变量x的取值为1.853511，函数值y的值为3.842246。用遗传算法计算10次求得函数的最大值如下表所示：第1次3.8484第2次3.65928第3次3.85022第4次3.82508第5次3.84111第6次3.8489第7次3.7734第8次3.84869第9次3.65031第10次3.64293平均值3.73883从上表看出，遗传算法每次得到的结果基本相同（除3.642933数据较小外），可见遗传算法具有较强的适应性。附录：%主程序
7、：用遗传算法求解y=x.*sin(10*pi*x)+2在-2 2区间上的最大值clc;clear all;close all;global BitLength %全局变量，计算如果满足求解精度至少需要编码的长度global boundsbegin %全局变量，自变量的起始点global boundsend %全局变量，自变量的终止点bounds=-2 2;%一维自变量的取值范围precision=0.0001; %运算精度boundsbegin=bounds(:,1);boundsend=bounds(:,2);%计算如果满足求解精度至少需要多长的染色体BitLength=ceil(log2(
8、boundsend-boundsbegin) ./ precision);popsize=50; %初始种群大小Generationnmax=20; %最大代数pcrossover=0.90; %交配概率pmutation=0.09; %变异概率%产生初始种群population=round(rand(popsize,BitLength); %初始种群，行代表一个个体，列代表不同个体%计算适应度,返回适应度Fitvalue和累积概率cumsumpFitvalue,cumsump=fitnessfun(population); %输入为群体population，返回适应度Fitvalue和累积概
9、率cumsumpGeneration=1;while GenerationGenerationnmax+1 for j=1:2:popsize %1对1对的群体进行如下操作（交叉，变异） %选择操作 seln=selection(population,cumsump); %选择两个个体，返回个体的序号，有可能两个序号相同 %交叉操作 scro=crossover(population,seln,pcrossover); scnew(j,:)=scro(1,:); %先两个个体交叉，再分别对两个个体进行变异 scnew(j+1,:)=scro(2,:); %变异操作 smnew(j,:)=mut
10、ation(scnew(j,:),pmutation); smnew(j+1,:)=mutation(scnew(j+1,:),pmutation); end population=smnew; %产生了新的种群 %计算新种群的适应度 Fitvalue,cumsump=fitnessfun(population); %记录当前代最好的适应度和平均适应度 fmax,nmax=max(Fitvalue); %最好的适应度为fmax（即函数值最大），其对应的个体为nmax fmean=mean(Fitvalue); %平均适应度为fmean ymax(Generation)=fmax; %每代中最好
11、的适应度 ymean(Generation)=fmean; %每代中的平均适应度 %记录当前代的最佳染色体个体 x=transform2to10(population(nmax,:);%population(nmax,:)为最佳染色体个体，x返回的是其对应的十进制数 %自变量取值范围是-2 2,需要把经过遗传运算的最佳染色体整合到-2 2区间 xx=boundsbegin+x*(boundsend-boundsbegin)/(power(2,BitLength)-1);%译码，boundsend为2 xmax(Generation)=xx; Generation=Generation+1end
12、Generation=Generation-1;%Generation加1、减1的操作是为了能记录各代中的最佳函数值xmax(Generation)%Bestpopulation=xx %把最后1代中最优的当成全局最优的，欠妥%Besttargetfunvalue=targetfun(xx)targetfunvalue=targetfun(xmax)Besttargetfunvalue,nmax=max(targetfunvalue)Bestpopulation=xmax(nmax)%绘制经过遗传运算后的适应度曲线。一般地，如果进化过程中种群的平均适应度与最大适%应度在曲线上有相互趋同的形态，
13、表示算法收敛进行得很顺利，没有出现震荡；在这种前%提下，最大适应度个体连续若干代都没有发生进化表明种群已经成熟。figure(1);hand1=plot(1:Generation,ymax);set(hand1,linestyle,-,linewidth,1.8,marker,*,markersize,6)hold on;hand2=plot(1:Generation,ymean);set(hand2,color,r,linestyle,-,linewidth,1.8,.marker,h,markersize,6)xlabel(进化代数);ylabel(最大/平均适应度);xlim(1 Gen
14、erationnmax);legend(最大适应度,平均适应度);box off;hold off;%子程序：计算适应度函数, 函数名称存储为fitnessfunfunction Fitvalue,cumsump=fitnessfun(population);global BitLengthglobal boundsbeginglobal boundsendpopsize=size(population,1); %，计算个体个数，有popsize个个体for i=1:popsize x=transform2to10(population(i,:); %将二进制转换为十进制 %转化为-2,2区间
15、的实数 xx=boundsbegin+x*(boundsend-boundsbegin)/(power(2,BitLength)-1); %恢复原来的数据，即译码 Fitvalue(i)=targetfun(xx); %计算函数值，即适应度end%给适应度函数加上一个大小合理的数以便保证种群适应值为正数Fitvalue=Fitvalue+230 %该处还有一个作用就是决定适应度是有利于选取几个有利个体（加强竞争），海深减弱竞争%计算选择概率fsum=sum(Fitvalue)Pperpopulation=Fitvalue/fsum %适应度归一化，及被复制的概率%计算累积概率cumsump(1
16、)=Pperpopulation(1)for i=2:popsize cumsump(i)=cumsump(i-1)+Pperpopulation(i) %求累计概率endcumsump=cumsump %累计概率%子程序：对于优化最大值或极大值函数问题，目标函数可以作为适应度函数%函数名称存储为targetfun.mfunction y=targetfun(x); %目标函数y=x.*sin(10*pi*x)+2;%子程序：新种群交叉操作,函数名称存储为crossover.m%输入population为种群，seln为选择的两个个体，pc为交配的概率function scro=crossov
17、er(population,seln,pc);BitLength=size(population,2);%二进制数的个数pcc=IfCroIfMut(pc); %根据交叉概率决定是否进行交叉操作，1则是，0则否if pcc=1 %进行交叉操作 chb=round(rand*(BitLength-2)+1; %在1,BitLength-1范围内随机产生一个交叉位 scro(1,:)=population(seln(1),1:chb) population(seln(2),chb+1:BitLength); %序号为seln(1)的个体在交叉位chb前面的信息与序号为seln(2)的个体在交叉位c
18、hb+1后面的信息重新组合 scro(2,:)=population(seln(2),1:chb) population(seln(1),chb+1:BitLength); %序号为seln(2)的个体在交叉位chb前面的信息与序号为seln(1)的个体在交叉位chb+1后面的信息重新组合else %不进行交叉操作 scro(1,:)=population(seln(1),:); scro(2,:)=population(seln(2),:);end %子程序：判断遗传运算是否需要进行交叉或变异, 函数名称存储为IfCroIfMut.m%mutORcro为动作（交叉、变异）发生的概率%根据概率
19、mutORcro决定是否进行操作，产生1的概率是mutORcro，产生0的概率为1-mutORcrofunction pcc=IfCroIfMut(mutORcro); test(1:100)=0; %1x100的行向量l=round(100*mutORcro); %产生一个数为100*mutORcro，round为取靠近的整数test(1:l)=1;n=round(rand*99)+1;pcc=test(n); %子程序：新种群变异操作，函数名称存储为mutation.m%snew为一个个体function snnew=mutation(snew,pmutation);BitLength=s
20、ize(snew,2);snnew=snew;pmm=IfCroIfMut(pmutation); %根据变异概率决定是否进行变异操作，1则是，0则否if pmm=1 chb=round(rand*(BitLength-1)+1; %在1,BitLength范围内随机产生一个变异位 snnew(chb)=abs(snew(chb)-1); %0变成1，1变成0end %子程序：新种群选择操作, 函数名称存储为selection.m%选择两个个体，返回个体的序号，有可能两个序号相同function seln=selection(population,cumsump);%从种群中选择两个个体for
21、 i=1:2 r=rand; %产生一个随机数 prand=cumsump-r; %都减去r，求出cumsump中第一个比r大的元素 j=1; while prand(j)0 j=j+1; end seln(i)=j; %选中个体的序号end%子程序：将2进制数转换为10进制数,函数名称存储为transform2to10.mfunction x=transform2to10(Population);BitLength=size(Population,2); %Population的列，即2进制的长度x=Population(BitLength); %x=末位for i=1:BitLength-1 x=x+Population(BitLength-i)*power(2,i);%从末位加到首位end
