用于函数优化的遗传算法
一、遗传算法介绍1.综述遗传算法（Genetic Algorithm）是由美国Michigan 大学Holland 教授和他的学生发展建立起来的，其思想是起源于生物遗传学适者生存的自然规律，是一种新兴的自适应随机搜索方法，它对优化对象既不要求连续，也不要求可微，并具有极强的鲁棒性和内在的并行计算的机制，特别适合于非凸空间中复杂的多极值优化和组合优化问题。 2.基本原理传统的优化理论都是通过调整模型的参数来得到期望的结果，而遗传优化算法是根据生物界的遗传和自然选择的原理来实现的，它的学习过程是通过保持和修改群体解中的个体特性，并且保证这种修改能够使下一代的群体中的有利于与期望特性相近的个体在整个群体份额中占有的比例越来越多。与基于代数学的优化方法一样，遗传算法是通过连续不断地队群体进行改进来搜索函数的最大值。遗传算法的搜索结果会有很大的差异。遗传学习的基本机理是使那些优于群体中其他个体的个体具有生存、繁殖以及保持更多基因给下一代的机会。遗传算法实质上是在群体空间中寻求较优解。3.主要构成遗传算法主要由编码、适应度、遗传算子（选择算子、交叉算子、变异算子）构成，包含的主要进化参数有编码长度、种群规模、交叉概率、变异概率、终止进化代数。4.基本步骤（1）初始化：确定种群规模，交叉概率，变异概率和终止进化准则，随机生成初始种群；置;（2）个体评价：计算或估计中各个个体的适应度。（3）选择：从运用选择算子选择出一些母体。（4）交叉：对所选个体依概率执行交叉，形成新的种群。（5）变异：随所选个体依概率执行变异，形成新的种群。 反复执行步骤（2）-（4），直到满足终止进化准则为止。二、遗传算法的设计流程图运行参数：种群大小Popsize,a,b,pc,pm,迭代次数T,编码长度Length- 初始种群encoding 终止条件输出结果选择操作 selection交叉操作 crossover变异操作 mutation三、二进制遗传算法的设计与实现1、编码本次实验我们选择二进制编码方案，它是遗传算法中最常用的一种编码方法，以二进制字符0和1为等位基因的定长字符串编码。如果给定编码精度，取编码长度m为满足的最小整数。其中a,b是优化区间。在实验中,由于有两个自变量我们选定长度=2*Length，每个自变量编码长度为Length=10；其解码公式为 ，其中i=1，2是两个自变量的编号。2、适应度函数对优化的目标函数处理，使其转化为适应度函数。满足适应度大于0的条件，对于求函数的极大值，只须做非负化处理。对于求极小值的情况则在目标函数前加负号作为适应度函数转换为求极大值。3、选择算子 本次实验采用的是转盘式选择算子和最优保留策略相结合的方法来实现。计算种群中每个个体的适应度F，将适应度最大的五个个体保留下来不进行交叉变异而直接进入下一代，然后将每个个体的适应度求和得到ada_sum最为选择概率pi，选择时产生一个rand*ada_sum的随机数，如果则选择个体i。 我们采取的策略是最优个体保留和转盘式算子结合的方法，目的是在遗传操作中，不仅能不断提高群体的平均适应度，而且能保证最佳个体的适应值不减小。4、交叉算子 我们采用的是单点交叉的方法。它是等概率的随机指定一个基因位置作为交叉点，把母体对中两个个体从交叉点分为前后两段，确定一个交叉概率Pc=0.9，当产生的随机数小于交叉概率时将两个个体的后半部分交换，得到两个新的个体。5、变异算子 我们选择变异概率Pm=0.05对个体编码串每一位进行变异运算，采用单点变异作为变异算子，当某位基因处产生的随机数小于变异概率时实施变异操作。当该位基因是0时变异为1，基因是1时变异为0。6、终止条件我们以进化代数作为遗传算法的终止条件。对于不同的测试函数，我们选用了不同的迭代次数。四、运行结果及结果分析1、 运行结果我们选择了八个检测函数对程序进行了实验，每个函数运行10次取最优值和最差值，表1为函数优化结果函数最优值最差值平均值实际最优值f1(x)-1.2207e-0081.2207e-0056.6530e-0060f2(x)2.2631e-0061.9232e-0048.9500e-0050f3(x)33.000133f4(x)6.8081e-0082.2219e-0058.5730e-0060f5(x)-1.0316-1.0309-1.0143-1.f6(x)-0.1848-0.1848-0.1848-0.1848f7(x) -186.7308-186.7012-186.7291-186.73(x)-2.1188-2.1188-2.1188-2.118 检测函数1二维球形函数运行结果图一检测函数2De Jong函数运行结果见图二图二检测函数3Goldstein-price函数运行结果为图三检测函数4himmelbaut函数运行结果如图四图四 检测函数5Six-hump camelback函数运行结果如图五图五检测函数6Bohachevsky函数运行结果如图六图六 检测函数7Shubert函数运行结果如图七 检测函数8多峰函数运行结果如图八图八2、结果分析我们选用赌盘选择法和最优个体保留法相结合的选择方案，保证每次迭代的适应度较高的个体保存下来，直接遗传进入下一代。使得局部最优个体不被淘汰，从而使算法的全局搜索能力增强。从表一中可以看出运行10次的结果偏差较小，最优值接近实际最优值。从函数的运行结果曲线可以看出收敛特性较好，结果比较稳定。算法寻优能力较强，说明此方法较为可靠。五、总结 本次实习我们做的是最基本的遗传算法，首先，在这个过程中，发现要设计好这个算法，重点在于三个方面。一是编码的选择，遗传算法的编码有多种选择，而如何选择方便有效的编码是算法的前提；二是各算子的选择会影响算法的效果在设计过程中感受最大的就是选择算子的不同会对结果造成很大的影响；三是对于随机数的控制，如何能实现真正的随机，如何初始种群的随机而不是伪随机。matlab程序代码clear all;close all;clc;%遗传算法参数设定和初始化M=50; %种群大小20个T=1000; %遗传运算得终止进化代数120代Length=16; %二进制编码长度16位pc=0.9; %交叉概率F=0.7pm=0.04; %变异概率Bi=0.05Max=10; %输入值的取值上限Min=-10; %输入值的取值下限G=round(rand(M,Length*2); %初始化，使其成为布尔型数值NG=zeros(M,Length*2);for k=1:1:TT(k)=k;for s=1:1:M N=G(s,:); y1=0;y2=0;N1=N(1:Length); %对x1进行解码，for i=1:Length y1=y1+N1(i)*2(i-1);endx1=(Max-Min)*y1/(2Length-1)+Min; x1_G(k)=x1; %为了便于最后图形输出，而引进的类似指针型变量N2=N(Length+1:2*Length); %对x2进行解码for i=1:Length y2=y2+N2(i)*2(i-1);endx2=(Max-Min)*y2/(2Length-1)+Min; x2_G(k)=x2; %为了便于最后图形输出，而引进的类似指针型变量f1=0;f2=0;for i=1:5 f1=f1+i*(cos(i+1)*x1+i);% f2=f2+i*(cos(i+1)*x2+i); endF(s)=-f1*f2;%x1.2+2*x2.2-0.3*cos(3*pi.*x1)+0.3*cos(4*pi.*x2)+0.3;%4*x1.2-2.1*x1.4+1/3*x1.6+x1*x2-4*x2.2+4*x2.4;%(x1.2+x2-11).2+(x1+x2.2-7).2;%1+(1+x1+x2)2*(19-14*x1+3*x12-14*x2+6*x1*x2+3*x22)*30+(2*x1-3*x2)2*(18-32*x1+12*x12+48*x2-36*x1*x2+27*x22);%100*(x1.2-x2).2+(1-x1).2;%F(s)=f1*f2; %目标函数表达式endFit=F;%+max(F);Order,Index=sort(Fit); %将适应度从小到大进行排列BF=Index(M);%Order(M); %选出适应度最大得值BFI(k)=F(BF);%最小函数值BFM(k)=mean(BFI);%每次迭代函数值的平均值BG=G(Index(M),:); In=M; %保护5个最优个体for i=1:1:5 BGG(i,:)=G(Index(In),:); In=In-1;end%采用赌盘选择法ada_sum=0;for i=1:1:M %直到累加和>=fit_n，最后的累加就是复制个体 ada_sum=ada_sum+F(i);endfor i=1:(M-5) %选择39次，最后一个个体留给历代最优解 r=rand*ada_sum; %随机产生一个数 ada_temp=0; %初始化累加值为0 j=1; while(ada_temp<r&&j<20) ada_temp=ada_temp+F(j); j=j+1; end if j=1 j=1; else j=j-1; end NG(i,:)=G(j,:);end%Cn=ceil(2*Length*rand); %产生单点交叉起始位，%ceil(x)返回大于或等于x的最小整数值。X的绝对值一定要小于最大整数值for i=1:2:(M-5) Rn=rand; %Rn为0-1之间的随机数 if pc>Rn %交叉条件，pc=0.6，Rn<0.6时就进行交叉运算 Cn=ceil(2*Length*Rn); if or(Cn=0,Cn>=20) continue; end for j=Cn:1:2*Length %随机交换部分染色体的基因，交换的位从Cn到末位止 temp=NG(i,j);
