南京航空航天大学遗传算法大作业

1、南 京 航 空 航 天 大 学研究生课程考试答题纸 共 页 第 1 页2013 -2014 学年第 1 学期计算智能技术的MATLAB实现课程学院 航空宇航学院 姓名 成绩 1. 最好结合自己的课题，提取其科学问题并建立其数学模型或选择一数学问题，任意选择一种智能算法进行求解。要求论述清楚你所选择的科学问题（或数学问题）及所选择的智能算法的控制参数（若选择遗传算法求解，控制参数包括适应度函数形式、最大遗传代数参考值、交叉率、变异率、代沟、插入概率、子种群个数、迁移率等；若选择二进制编码，要说明自变量取值范围及取值要求精确到小数点后几位，如何确定二进制编码位数；要求必须使用适应度排序和子代插入命

2、令；要求绘出所建数学模型的最佳解及种群均值随迭代次数的变化曲线；输出函数的极值及对应的自变量取值；）若所建的数学模型有显函数形式，需绘出该函数图像；要求尽可能发挥自己的想像力和创造力，提出新问题、新解法，若问题过于复杂，无法写出目标函数求解过程中的一些中间量，可略去其过程，论述清楚你所选择的其它辅助软件或工具的功能及其与智能算法程序的连接思想或方法即可；具体要求在大作业中有问题描述和理论分析、图像或曲线、结果输出、程序源代码等，并提交电子版，任何人的程序不得重复，否则按不及格论处！商旅问题的MATLAB实现商旅问题可描述为：一位销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回

3、到原出发点，在所有可能路径中求出路径长度最短的一条。遗传算法求解商旅问题的控制参数1.种群初始化。个体编码方法有二进制编码和实数编码，在解决商旅问题过程中个体编码方法为实数编码。对于商旅问题，实数编码为1-n的实数的随机排列，初始化的参数有种群个数M、染色体基因个数N（即城市的个数）、最大遗传代数参考值C=100、交叉概率Pc=0.4、变异概率Pmutation=0.2。2.适应度函数。在商旅问题中，对于任意两个城市之间的距离D(i,j)已知，每个染色体（即n个城市的随机排列）可计算出总距离，因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足商旅问题要求。fi

4、tness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001).m3.选择操作。遗传算法选择操作有轮盘赌法、锦标赛法等多种方法，本程序采用基于适应度比例的选择，即适应度越好的个体被选择的概率越大，同时在选择中保存适应度最高的个体。4.交叉操作。遗传算法中交叉操作有多种方法。本程序中对于个体，随机选择两个个体，在对应位置交换若干个基因片段，同时保证每个个体依然是1-n的随机排列，防止进入局部收敛。5.变异操作。本程序中对于变异操作，随机选取个体，同时随机选取个体的两个基因进行交换以实现变异操作。图1 初始种群分布图2 未进行遗传迭代的结果图3 进行了

5、迭代优化后的结果图4 优化后的最优解的变化和种群均值的变化源程序主函数clear;clc;N=50;M=100;C=100;C_old=C;m=2;Pc=0.4; Pmutation=0.2; pos=randn(N,2);D=zeros(N,N);for i=1:N    for j=i+1:N        dis=(pos(i,1)-pos(j,1).2+(pos(i,2)-pos(j,2).2;        D(i,

6、j)=dis(0.5);        D(j,i)=D(i,j);    endendpopm=zeros(M,N);for i=1:M    popm(i,:)=randperm(N);endR=popm(1,:); figure(1);scatter(pos(:,1),pos(:,2),'rx');axis(-3 3 -3 3);figure(2);plot_route(pos,R); axis(-3 3 -3 3);fitness=

7、zeros(M,1);len=zeros(M,1);for i=1:M    len(i,1)=myLength(D,popm(i,:);endmaxlen=max(len);minlen=min(len);fitness=fit(len,m,maxlen,minlen);rr=find(len=minlen);R=popm(rr(1,1),:);for i=1:Nfprintf('%d ',R(i);endfprintf('n');fitness=fitness/sum(fitness);distance_min=zeros(C+

8、1,1); while C>=0fprintf('迭代第%d次n',C);nn=0;for i=1:size(popm,1)    len_1(i,1)=myLength(D,popm(i,:);    jc=rand*0.3;    for j=1:size(popm,1)        if fitness(j,1)>=jc       

9、; nn=nn+1;        popm_sel(nn,:)=popm(j,:);        break;        end    endendpopm_sel=popm_sel(1:nn,:);len_m len_index=min(len_1);popm_sel=popm_sel;popm(len_index,:); nnper=r

10、andperm(nn);A=popm_sel(nnper(1),:);B=popm_sel(nnper(2),:);for i=1:nn*PcA,B=cross(A,B);popm_sel(nnper(1),:)=A;popm_sel(nnper(2),:)=B;endfor i=1:nn    pick=rand;    while pick=0         pick=rand;    end  &#

11、160; if pick<=Pmutation       popm_sel(i,:)=Mutation(popm_sel(i,:);    endendNN=size(popm_sel,1);len=zeros(NN,1);for i=1:NN    len(i,1)=myLength(D,popm_sel(i,:);endmaxlen=max(len);minlen=min(len);distance_min(C+1,1)=minlen;fitness=fit(le

12、n,m,maxlen,minlen);rr=find(len=minlen);fprintf('minlen=%dn',minlen);R=popm_sel(rr(1,1),:);for i=1:Nfprintf('%d ',R(i);endfprintf('n');popm=;popm=popm_sel;C=C+1;trace(1,C)=min(len);trace(2,C)=sum(len)/length(len);endfigure(3)plot_route(pos,R);axis(-3 3 -3 3);figure(4)plot(trac

13、e(1,:)');hold on;plot(trace(2,:)','-.');grid;legend('解的变化','种群均值的变化');个体距离mylength.mfunction len=myLength(D,p)N,NN=size(D);len=D(p(1,N),p(1,1);for i=1:(N-1)  len=len+D(p(1,i),p(1,i+1);endend交叉cross.mfunction A,B=cross(A,B)L=length(A);if L<10  &#

14、160; W=L;elseif (L/10)-floor(L/10)>=rand&&L>10    W=ceil(L/10)+8;else    W=floor(L/10)+8;endp=unidrnd(L-W+1);fprintf('p=%d ',p);for i=1:W    x=find(A=B(1,p+i-1);    y=find(B=A(1,p+i-1);    A(1,p+i-1),B(1

15、,p+i-1)=exchange(A(1,p+i-1),B(1,p+i-1);    A(1,x),B(1,y)=exchange(A(1,x),B(1,y);endend对调 exchange.mfunction x,y=exchange(x,y)temp=x;x=y;y=temp;end变异 Mutation.mfunction a=Mutation(A)index1=0;index2=0;nnper=randperm(size(A,2);index1=nnper(1);index2=nnper(2);temp=0;temp=A(index1);A(index

16、1)=A(index2);A(index2)=temp;a=A;end适应度fit.mfunction fitness=fit(len,m,maxlen,minlen)fitness=len;for i=1:length(len)  fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001).m;end连点画图 plot_route.mfunction plot_route(a,R)scatter(a(:,1),a(:,2),'rx');hold on;plot(a(R(1),1),a(R(length(

17、R),1),a(R(1),2),a(R(length(R),2);hold on;end主函数clear;clc;N=50;M=100;C=100;C_old=C;m=2;Pc=0.4; Pmutation=0.2; pos=randn(N,2);D=zeros(N,N);for i=1:N    for j=i+1:N        dis=(pos(i,1)-pos(j,1).2+(pos(i,2)-pos(j,2).2;      

18、;  D(i,j)=dis(0.5);        D(j,i)=D(i,j);    endendpopm=zeros(M,N);for i=1:M    popm(i,:)=randperm(N);endR=popm(1,:); figure(1);scatter(pos(:,1),pos(:,2),'rx');axis(-3 3 -3 3);figure(2);plot_route(pos,R); axis(-3 3 -3

19、 3);fitness=zeros(M,1);len=zeros(M,1);for i=1:M    len(i,1)=myLength(D,popm(i,:);endmaxlen=max(len);minlen=min(len);fitness=fit(len,m,maxlen,minlen);rr=find(len=minlen);R=popm(rr(1,1),:);for i=1:Nfprintf('%d ',R(i);endfprintf('n');fitness=fitness/sum(fitness);distance_

20、min=zeros(C+1,1); while C>=0fprintf('迭代第%d次n',C);nn=0;for i=1:size(popm,1)    len_1(i,1)=myLength(D,popm(i,:);    jc=rand*0.3;    for j=1:size(popm,1)        if fitness(j,1)>=jc     

21、;   nn=nn+1;        popm_sel(nn,:)=popm(j,:);        break;        end    endendpopm_sel=popm_sel(1:nn,:);len_m len_index=min(len_1);popm_sel=popm_sel;popm(len_index,:); nnper=randperm(nn);A=popm_sel(nnper(1),:);B=popm_sel(nnper(2),:);for i=1:nn*PcA,B=cross(A,B);popm_sel(nnper(1),:)=A;popm_sel(nnper(2),:)=B;endfor i=1:nn    pick=rand;    while pick=0         pick=rand; &