遗传算法及其应用实例

Page1of20遗传算法及其应用实例遗传算法（GeneticAlgorithm）是由美国Michigan大学的Holland教授（1969）提出，后经由DeJong（1975），Goldberg（1989）等归纳总结所形成的一类模拟进化算法。遗传算法搜索最优解的方法是模仿生物的进化过程，即通过选择与染色体之间的交叉和变异来完成的。遗传算法主要使用选择算子、交叉算子与变异算子来模拟生物进化，从而产生一代又一代的种群()Xt。（1）选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。它根据每一个个体的适应度，按照一定规则或方法，从t代种群()Xt中选择出一些优良的个体（或作为母体，或让其遗传到下一代种群(1)Xt）。（2）交叉算子：是模拟有性繁殖的基因重组操作，它将从种群()Xt所选择的每一对母体，以一定的交叉概率交换它们之间的部分基因。（3）变异算子：是模拟基因突变的遗传操作，它对种群()Xt中的每一个个体，以一定的变异概率改变某一个或某一些基因座上的基因值为其他的等位基因。交叉算子与变异算子的作用都在于重组染色体基因，以生成新的个体。Page2of20遗传算法的运算过程如下：步1（初始化）确定种群规模N，交叉概率cP，变异概率mP和终止进化准则；随机生成N个个体作为初始种群(0)X；置0t。步2（个体评价）计算评估()Xt中各个体的适应度。步3（种群进化）3.1.选择（母体）从()Xt中运用选择算子选择出/2M对母体（MN）。3.2.交叉对所选择的/2M对母体，以概率cP执行交叉，形成M个中间个体。3.3.变异对M个中间个体分别独立以概率mP执行变异，形成M个候选个体。3.4.选择（子代）从上述所形成的M个候选个体中依据适应度选择出N个个体组成新一代种群(1)Xt。步4（终止检验）如已满足终止准则，则输出(1)Xt中具有最大适应度的个体作为最优解，终止计算，否则置1tt并转步2。以上运算过程只是遗传算法的多种实现方式中的一种，根据实际问题的不同，遗传算法的实现也是多种多样的。Page3of20遗传算法具有通用、并行、稳健、简单与全局优化能力强等突出优点，适用于解决复杂、困难的全局优化问题。一个优化问题被称为是复杂的，通常指它具有下述特征之一：（1）目标函数没有明确解析表达（如非数值优化问题）。（2）目标函数虽有明确表达，但不可能恰好估值（如大部分最优控制问题、金融优化问题）。（3）目标函数有极多的峰值（如DNA计算、组合优化问题）。（4）多目标优化，即目标函数是向量值。一个优化问题被称为是困难的，则通常是指：或者目标函数f不连续、不可微、高度非线性，或者优化问题是困难的组合问题。对于这些复杂、困难的优化问题，已知的优化方法或者根本不可用，或者可用但不有效。相比之下，遗传算法不但保证可用，而且常常显得更为有效。但是，我们必须注意到，一个通用而又较少依赖于目标函数值与其他辅助信息的算法不可能比专用且充分利用目标函数值与相关辅助信息的算法更为有效，而当一个问题有某些辅助信息可供使用时，舍弃应用本来可供应用的信息而去应用于这些信息无关的算法也不是一个聪明的选择。所以，遗传算法一般来说并不适宜应用于通常的数值优化问题（例如连续可微的数学规划问题），或者说，当应用于这样的问题时，遗传算法并不总能显示其优越性。Page4of20接下来，我们通过一个求解简单函数的最小值点的问题来初步展示遗传算法的具体实现方法：问题1：求函数()11sin(6)7cos(5)fxxx在[0,2]x区间上的最小值点。上图为函数()11sin(6)7cos(5)fxxx在[0,2]x区间上的曲线图像，可以看出，该函数有多个极值点，如果使用其他的搜寻方法，很容易陷入局部最小点，而不能搜寻到真正的全局最小点，但遗传算法可以较好地弥补这个缺陷。遗传算法的具体实现如下：1.问题分析。对于本问题，自变量x可以抽象为个体的基因组，即用二进制编码表示x；函数值()fx可以抽象为个体的适应度，函数值越小，适应度越高。关于二进制编码方式，在精度允许的范围下，可以将区间内的无01234567-20-15-10-505101520Page5of20穷多点用间隔足够小的有限点来代替，以降低计算量同时保证精度损失不大。如用16位二进制数来表示该区间的点，相邻点的间隔仅为516209.58751021，相邻点的函数值的变化幅度已经很小，由此带来的精度损失完全可以接受。另一个问题是普通的二进制编码方式可能具有较大的汉明（Hamming）距离，例如15和16的二进制表示为01111和10000，从15到16必须改变所有位，这种缺陷将降低遗传算法的搜索效率。采用格雷编码（GrayEncoding）可以避免这一缺陷。格雷码的特点是任意两个连续的两个整数的编码值之间只有一个位是不同的，其他位都完全相同。格雷编码的原理如下：设有二进制串12nbbb，对应的格雷串12naaa，则从二进制编码到格雷编码的变换为11,1,1iiibiabbi。从格雷编码到二进制编码的变换为1()mod2iijjba。例如，0-15的格雷码如下表所示：012345670000000100110010011001110101010089101112131415110011011111111010101011100110002.根据遗传算法的运算过程编写程序。%f(x)=11sin(6x)+7cos(5x),0=x=2*piL=16;N=32;M=48;Page6of20T=100;Pc=0.8;Pm=0.03;fori=1:1:Nx1(1,i)=rand()*2*pi;x2(1,i)=uint16(x1(1,i)/(2*pi)*65535);grayCode(i,:)=num2gray(x2(1,i),L);endfort=1:1:Ty1=11*sin(6*x1)+7*cos(5*x1);fori=1:1:M/2[a,b]=min(y1);grayCodeNew(i,:)=grayCode(b,:);grayCodeNew(i+M/2,:)=grayCode(b,:);y1(1,b)=inf;endfori=1:1:M/2p=unidrnd(L);ifrand()Pcforj=p:1:Ltemp=grayCodeNew(i,j);grayCodeNew(i,j)=grayCodeNew(M-i+1,j);grayCodeNew(M-i+1,j)=temp;endendendfori=1:1:Mforj=1:1:Lifrand()PmgrayCodeNew(i,j)=1-grayCodeNew(i,j);endendendfori=1:1:Mx4(1,i)=gray2num(grayCodeNew(i,:));endx3=double(x4)*2*pi/65535;y3=11*sin(6*x3)+7*cos(5*x3);fori=1:1:N[a,b]=min(y3);x1(1,i)=x3(1,b);grayCode(i,:)=grayCodeNew(b,:);y3(1,b)=inf;endPage7of20endx1y1=11*sin(6*x1)+7*cos(5*x1)3.结论分析。程序运行结果为：最小值点为1.8486,()17.8340xfx。下面针对上面的问题，讨论遗传算法中一些初始化参数的设定方法及其影响。（1）编码长度L。使用二进制编码时，L通常由对问题的求解精度决定，编码长度L越长，可期望的最优解的精度也就越高，但应注意过大的L会增大运算量。（2）种群规模N。种群规模N表示每一代种群中所含个体数目。当N取值较小时，可提高遗传算法的运算速度，但却降低种群的多样性，容易引起遗传算法早熟，出现假收敛；而当N取值较大时，又会使得遗传算法效率降低。一般建议的取值范围是20~100。（3）交叉概率cP。在遗传算法中交叉算子被认为是主要搜索算子，因而一般取较大值。一般说，较大的cP容易破坏群体中已形成的优良模式，是搜索的随机性太大，而较小的cP使发现新个体（特别是优良新个体）的速度太慢。一般建议的取值范围是0.4~0.99。另外，比较理想的的方式是非一致地使用交叉概率，例如在遗传算法的前期使用较大的cP，后期降低cP以保留优良个体。（4）变异概率mP。较大的变异概率mP使遗传算法在整个搜索空间中大步跳跃，而小的变异概率使遗传算法聚焦于特别区域作局部搜Page8of20索。一般在不使用交叉算子的情形（演化策略（EvolutionStrategy）算法，进化程序（EvolutionProgramming）算法），变异算子作主要搜索算子，mP取较大值（0.4~1）；而在与交叉算子联合使用的情形（遗传算法），mP通常取较小值（0.0001~0.5）。（5）终止进化代数T。遗传算法不同于传统优化算法，它很难有明确的搜索终止准则（特别是对于非数值优化问题），于是通常需指定一个终止进化代数来终止算法，一般设[100,1000]T。一般来说，事先指定T通常只能找到给定问题的在给定时限内所能寻求的相对满意解，但不一定是问题的最优解或较高精度的近似解。为了获得较高精度解，通常可依据种群适应度的稳定情况来实时调整T的设置。总体来说，以上参数的确定并没有明确的准则可依据，需要根据实际问题的特点以及算法的运行情况进行实时的调整，以搜索获得更为满意的最优解。Page9of20接下来，我们用遗传算法来求解一个更为复杂的函数最值问题。问题2：求Schaffer函数的最大值点：222121222212sin0.5(,)0.5,55,1,2[10.001()]ixxfxxxixx根据遗传算法的一般运算过程编写MATLAB程序如下：L=32;N=60;M=80;T=100;Pc=0.6;Pm=0.02;fori=1:1:Nx10(1,i)=unidrnd(2^L-1);x10(2,i)=unidrnd(2^L-1);x11(1,i)=double(x10(1,i))/(2^L-1)*10-5;x11(2,i)=double(x10(2,i))/(2^L-1)*10-5;endfort=1:1:T-505-50500.20.40.60.81Page10of20fori=1:1:Ntemp1(1,i)=x11(1,i)^2+x11(2,i)^2;y1(1,i)=0.5-(sin(sqrt(temp1(1,i)))^2-0.5)/(1+0.001*temp1(1,i));grayCode1(1,i,:)=num2gray(x10(1,i),L);grayCode1(2,i,:)=num2gray(x10(2,i),L);endfori=1:1:M[a,b]=max(y1);grayCode2(1,i,:)=grayCode1(1,b,:);grayCode2(2,i,:)=grayCode1(2,b,:);y1(1,b)=-inf;endfori=1:1:M/2p=unidrnd(L);ifrand()Pcforj=p:1:Ltemp=grayCode2(1,i,j);grayCode2(1,i,j)=grayCode2(1,M-i+1,j);grayCode2(1,M-i+1,j)=temp;temp=grayCode2(2,i,j);grayCode2(2,i,j)=grayCode2(2,M-i+1,j);grayCode2(2,M-i+1,j)=temp;endendendfori=1:1:Mforj=1:1:Lfork=1:1:2ifrand()PmgrayCode2(k,i,j)=1-grayCode2(k,i,j);endendendendfori=1:1:Mx20(1,i)=gray2num(grayCode2(1,i,:));x20(2,i)=gray2num(grayCode2(2,i,:));x21(1,i)=double(x20