南京航空航天大學(xué)遺傳算法大作業(yè)

1、南 京 航 空 航 天 大 學(xué)研究生課程考試答題紙 共 頁(yè) 第 1 頁(yè)2013 -2014 學(xué)年第 1 學(xué)期計(jì)算智能技術(shù)的MATLAB實(shí)現(xiàn)課程學(xué)院 航空宇航學(xué)院 姓名 成績(jī) 1. 最好結(jié)合自己的課題，提取其科學(xué)問(wèn)題并建立其數(shù)學(xué)模型或選擇一數(shù)學(xué)問(wèn)題，任意選擇一種智能算法進(jìn)行求解。要求論述清楚你所選擇的科學(xué)問(wèn)題（或數(shù)學(xué)問(wèn)題）及所選擇的智能算法的控制參數(shù)（若選擇遺傳算法求解，控制參數(shù)包括適應(yīng)度函數(shù)形式、最大遺傳代數(shù)參考值、交叉率、變異率、代溝、插入概率、子種群個(gè)數(shù)、遷移率等；若選擇二進(jìn)制編碼，要說(shuō)明自變量取值范圍及取值要求精確到小數(shù)點(diǎn)后幾位，如何確定二進(jìn)制編碼位數(shù)；要求必須使用適應(yīng)度排序和子代插入命

2、令；要求繪出所建數(shù)學(xué)模型的最佳解及種群均值隨迭代次數(shù)的變化曲線；輸出函數(shù)的極值及對(duì)應(yīng)的自變量取值；）若所建的數(shù)學(xué)模型有顯函數(shù)形式，需繪出該函數(shù)圖像；要求盡可能發(fā)揮自己的想像力和創(chuàng)造力，提出新問(wèn)題、新解法，若問(wèn)題過(guò)于復(fù)雜，無(wú)法寫出目標(biāo)函數(shù)求解過(guò)程中的一些中間量，可略去其過(guò)程，論述清楚你所選擇的其它輔助軟件或工具的功能及其與智能算法程序的連接思想或方法即可；具體要求在大作業(yè)中有問(wèn)題描述和理論分析、圖像或曲線、結(jié)果輸出、程序源代碼等，并提交電子版，任何人的程序不得重復(fù)，否則按不及格論處！商旅問(wèn)題的MATLAB實(shí)現(xiàn)商旅問(wèn)題可描述為：一位銷售商從n個(gè)城市中的某一城市出發(fā)，不重復(fù)地走完其余n-1個(gè)城市并回

3、到原出發(fā)點(diǎn)，在所有可能路徑中求出路徑長(zhǎng)度最短的一條。遺傳算法求解商旅問(wèn)題的控制參數(shù)1.種群初始化。個(gè)體編碼方法有二進(jìn)制編碼和實(shí)數(shù)編碼，在解決商旅問(wèn)題過(guò)程中個(gè)體編碼方法為實(shí)數(shù)編碼。對(duì)于商旅問(wèn)題，實(shí)數(shù)編碼為1-n的實(shí)數(shù)的隨機(jī)排列，初始化的參數(shù)有種群個(gè)數(shù)M、染色體基因個(gè)數(shù)N（即城市的個(gè)數(shù)）、最大遺傳代數(shù)參考值C=100、交叉概率Pc=0.4、變異概率Pmutation=0.2。2.適應(yīng)度函數(shù)。在商旅問(wèn)題中，對(duì)于任意兩個(gè)城市之間的距離D(i,j)已知，每個(gè)染色體（即n個(gè)城市的隨機(jī)排列）可計(jì)算出總距離，因此可將一個(gè)隨機(jī)全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)，即距離越短，適應(yīng)度函數(shù)越好，滿足商旅問(wèn)題要求。fi

4、tness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001).m3.選擇操作。遺傳算法選擇操作有輪盤賭法、錦標(biāo)賽法等多種方法，本程序采用基于適應(yīng)度比例的選擇，即適應(yīng)度越好的個(gè)體被選擇的概率越大，同時(shí)在選擇中保存適應(yīng)度最高的個(gè)體。4.交叉操作。遺傳算法中交叉操作有多種方法。本程序中對(duì)于個(gè)體，隨機(jī)選擇兩個(gè)個(gè)體，在對(duì)應(yīng)位置交換若干個(gè)基因片段，同時(shí)保證每個(gè)個(gè)體依然是1-n的隨機(jī)排列，防止進(jìn)入局部收斂。5.變異操作。本程序中對(duì)于變異操作，隨機(jī)選取個(gè)體，同時(shí)隨機(jī)選取個(gè)體的兩個(gè)基因進(jìn)行交換以實(shí)現(xiàn)變異操作。圖1 初始種群分布圖2 未進(jìn)行遺傳迭代的結(jié)果圖3 進(jìn)行了

5、迭代優(yōu)化后的結(jié)果圖4 優(yōu)化后的最優(yōu)解的變化和種群均值的變化源程序主函數(shù)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('解的變化','種群均值的變化');個(gè)體距離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對(duì)調(diào) 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適應(yīng)度f(wàn)it.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連點(diǎn)畫圖 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主函數(shù)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; &