用于函数优化的遗传算法

1、用于函数优化的遗传算法一、遗传算法介绍1 .综述遗传算法 （ Genetic Algorithm ） 是由美国Michigan 大学 Holland 教授和他的学生发展建立起来的，其思想是起源于生物遗传学适者生存的自然规律，是一种新兴的自适应随机搜索方法，它对优化对象既不要求连续，也不要求可微，并具有极强的鲁棒性和内在的并行计算的机制，特别适合于非凸空间中复杂的多极值优化和组合优化问题。2 .基本原理传统的优化理论都是通过调整模型的参数来得到期望的结果，而遗传优化算法是根据生物界的遗传和自然选择的原理来实现的，它的学习过程是通过保持和修改群体解中的个体特性，并且保证这种修改能够使下一代的群体中

2、的有利于与期望特性相近的个体在整个群体份额中占有的比例越来越多。与基于代数学的优化方法一样，遗传算法是通过连续不断地队群体进行改进来搜索函数的最大值。遗传算法的搜索结果会有很大的差异。遗传学习的基本机理是使那些优于群体中其他个体的个体具有生存、繁殖以及保持更多基因给下一代的机会。遗传算法实质上是在群体空间中寻求较优解。3 .主要构成遗传算法主要由编码、适应度、遗传算子（选择算子、交叉算子、变异算子）构成，包含的主要进化参数有编码长度、种群规模、交叉概率、变异概率、终止进化代数。4 .基本步骤（ 1）初始化：确定种群规模，交叉概率Pc ， 变异概率Pm 和终止进化准则，随机生成初始种群X（t）；

3、置 t 0 ;个体评价:计算或估计X（t）中各个个体的适应度。（3）选择：从X（t）运用选择算子选择出一些母体。（ 4）交叉：对所选个体依概率Pc 执行交叉，形成新的种群。（ 5）变异：随所选个体依概率Pm 执行变异，形成新的种群。反复执行步骤（2） -（ 4） ，直到满足终止进化准则为止。、遗传算法的设计流程图运行参数：种群大小初始种群三、二进制遗传算法的设计与实现1、编码本次实验我们选择二进制编码方案，它是遗传算法中最常用的一种编码方 法，以二进制字符0和1为等位基因的定长字符串编码。如果给定编码精度e , 取编码长度m为满足的最小整数。其中a,b是优化区间。2m 1在实验中,由于有两个自

4、变量我们选定长度=2*Length ,每个自变量编码长度mx a ( bJ2j1)为为Length=10 ；其解码公式为j 1,其中i=1 , 2是两个自变量的编号。2、适应度函数对优化的目标函数处理，使其转化为适应度函数。满足适应度大于0的条件，对于求函数的极大值，只须做非负化处理。对于求极小值的情况则在目标 函数前加负号作为适应度函数转换为求极大值。3、选择算子本次实验采用的是转盘式选择算子和最优保留策略相结合的方法来 实现。计算种群中每个个体的适应度 F,将适应度最大的五个个体保留下来不进 行交叉变异而直接进入下一代，然后将每个个体的适应度求和得到ada_sum最为选择概率pi ,选择时

5、产生一个rand*ada_sum 的随机数，如果 F F(2) F(i 1) ada_sum * rand F(1) F(2)F 则选择个体 i。我们采取的策略是最优个体保留和转盘式算子结合的方法，目的是在遗 传操作中，不仅能不断提高群体的平均适应度，而且能保证最佳个体的适应值 不减小。4、交叉算子我们采用的是单点交叉的方法。它是等概率的随机指定一个基因位置 作为交叉点，把母体对中两个个体从交叉点分为前后两段，确定一个交叉概率 Pc=0.9,当产生的随机数小于交叉概率时将两个个体的后半部分交换，得到两个新的个体。5、变异算子我们选择变异概率Pm=0.05对个体编码用每一位进行变异运算，采用 单

6、点变异作为变异算子，当某位基因处产生的随机数小于变异概率时实施变异 操作。当该位基因是0时变异为1,基因是1时变异为006、终止条件我们以进化代数作为遗传算法的终止条件。对于不同的测试函数，我们选 用了不同的迭代次数。四、运行结果及结果分析1、运行结果我们选择了八个检测函数对程序进行了实验，每个函数运行10次取最优值和最差值，表1为函数优化结果函数最优值最差值平均值实际 最优 值f1(x)-1.2207 e-0081.2207e-0056.6530 e-0060f2（X）2.2631e-0061.9232e-0048.9500 e-0050f3(x)33.000133f4（X）6.8081e-

7、0082.2219e-0058.5730 e-0060f5（X）-1.0316-1.0309-1.0143-1.031628f6（X）-0.1848-0.1848-0.1848-0.1848f7（X）-186.73 08-186.7012-186.7291-186.73L(X)-2.1188-2.1188-2.1188-2.118检测函数1二维球形函数运行结果19次薮图一检测函数2De Jong函数运行结果见图二量优值平均值一图二检测函数3Goldstein-price函数运行结果为图三检测函数4himmelbaut函数运行结果如图四图四检测函 娄攵5Six-hump camelback函数运

8、行结果如图五6 7 8 9-1 一 . - 图五检测函数6Bohachevsky函数运行结果如图六次数o图六检测函数7Shubert函数运行结果如图七量优值平场点-l I-I l口III,IIII-n10020ason400eoneno7m eno sonimo5000OO检测函数8多峰函数运行结果如图八1050由5-15001COO2 C42.161500次数乎均值-1QOO13QC次数图八2、结果分析我们选用赌盘选择法和最优个体保留法相结合的选择方案，保证每次迭代的适 应度较高的个体保存下来，直接遗传进入下一代。使得局部最优个体不被淘汰， 从而使算法的全局搜索能力增强。从表一中可以看出运行

9、10次的结果偏差较小, 最优值接近实际最优值。从函数的运行结果曲线可以看出收敛特性较好，结果 比较稳定。算法寻优能力较强，说明此方法较为可靠。五、总结本次实习我们做的是最基本的遗传算法，首先，在这个过程中，发现要设 计好这个算法，重点在于三个方面。一是编码的选择，遗传算法的编码有多种 选择，而如何选择方便有效的编码是算法的前提；二是各算子的选择会影响算 法的效果在设计过程中感受最大的就是选择算子的不同会对结果造成很大的影 响；三是对于随机数的控制，如何能实现真正的随机，如何初始种群的随机而 不是伪随机。matlab 程序代码clear all;close all;clc;% 遗传算法参数设定和

10、初始化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:MN=G(s,:);y1=0;y2=0;N1=N(1:Length);% 对 x1 进行解码，for i=1:Lengthy1=y1+

11、N1(i)*2A(i-1);endx1=(Max-Min)*y1/(2ALength-1)+Min;x1_G(k)=x1;% 为了便于最后图形输出，而引进的类似指针型变N2=N(Length+1:2*Length);% 对 x2 进行解码for i=1:Lengthy2=y2+N2(i)*2A(i-1);endx2=(Max-Min)*y2/(2ALength-1)+Min;x2_G(k)=x2;% 为了便于最后图形输出，而引进的类似指针型变f1=0;f2=0;for i=1:5f1=f1+i*(cos(i+1)*x1+i);%f2=f2+i*(cos(i+1)*x2+i); endF(s尸-

12、f1*f2;%x1A2+2*x2A2-0.3*cos(3*pi.*x1)+0.3*cos(4*pi.*x2)+0.3;%4*x 1A2-2.1*x1A4+1/3*x1A6+x1*x2-4*x2A2+4*x2A4;%(x1A2+x2-11)A2+(x1+x2 A 2-7)A2;%1+(1+x1+x2)A2*(19-14*x1+3*x1A2-14*x2+6*x1*x2+3*x2A2)*30+(2*x1- 3*x2)A2*(18-32*x1+12*x1A2+48*x2-36*x1*x2+27*x2A2);%100*(x1.A2-x2).A2+(1-x1).A2;%F(s)=f1*f2; % 目标函数

13、表达式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:5BGG(i,:)=G(Index(In),:);In=In-1;end% 采用赌盘选择法ada_sum=0;for i=1:1:M% 直到累加和>=fit_n ，最后的累加就是复制个体ada_sum=ada_sum+F(i)

14、;endfor i=1:(M-5)%选择 39 次，最后一个个体留给历代最优解r=rand*ada_sum; % 随机产生一个数ada_temp=0; % 初始化累加值为0j=1;while(ada_temp<r&&j<20)ada_temp=ada_temp+F(j);j=j+1;endif j=1j=1;elsej=j-1;endNG(i,:)=G(j,:);end%Cn=ceil(2*Length*rand);% 产生单点交叉起始位，%ceil(x)返回大于或等于x的最小整数值。X的绝对值一定要小于最大整数 值for i=1:2:(M-5)Rn=rand;%R

15、n 为 0-1 之间的随机数if pc>Rn % 交叉条件，pc=0.6， Rn<0.6 时就进行交叉运算Cn=ceil(2*Length*Rn);if or(Cn=0,Cn>=20)continue;endfor j=Cn:1:2*Length %随机交换部分染色体的基因，交换的位从Cn 到末位止temp=NG(i,j);NG(i,j)=NG(i+1,j);NG(i+1,j)=temp;endend end %Rs=4;% 对第76位到第80位(即后五位)进行保优for i=1:1:(M-5)%变异运算for j=1:1:2*LengthMr=rand;% 产生基本位变异位

16、，同样Mr 是 0-1 之间的数if pm>Mr% 变异条件，只有当Mr<0.001 时才会进行变异运算，保证if NG(i,j)=0NG(i,j)=1;elseNG(i,j)=0;endendend end Rs=4;% 对第76位到第80位(即后五位)进行保优for i=1:1:5NG(M-Rs,:)=BGG(i,:);Rs=Rs-1; endG=NG; endMin,index=max(BFI);Min=-Min%BFI 每次迭代最优值，Max 最优值%Max=max(BFI)% 历代最优值中的最差最优值mean=mean(BFM)% 平均值x1=x1_G(index)% 最

17、优值处横坐标x1 的值x2=x2_G(index)% 最优值处横坐标x2 的值% 画图部分%figure(1)subplot(2,1,1);plot(T,BFI,'b',T,BFM,'r');legend('it 最优值 ','it 平均值');xlabel(' 次数');ylabel(' 函数值');%hold on%plot(T,BFM,'r'); xlabel(' 次数 ');ylabel(' 平均值 ');%hold off%subplot(2

18、,2,1);plot(T,x1_G); xlabel(' 次数');ylabel('X1');%subplot(2,2,2);plot(T,x2_G); xlabel(' 次数');ylabel('X2');X1_G,X2_G=meshgrid(-10:.05:10,-10:.05:10);f1=0;f2=0;for i=1:5f1=f1+i.*(cos(i+1).*X1_G)+i);f2=f1+i.*(cos(i+1).*X2_G)+i);endH=f1.*f2;%X1_G A2+X2_G A2-0.3*cos(3*pi.*X1_G)+0.3*cos(4*pi.*X2_G)+