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

南京航空航天大學(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)度排序和子代插入命令；要求繪出所建數(shù)學(xué)模型的最佳解及種群均值隨迭代次數(shù)的變化曲線；輸出函數(shù)的極值及對(duì)應(yīng)的自變量取值;）若所建的數(shù)學(xué)模型有顯函數(shù)形式，需繪出該函數(shù)圖像；要求盡可能發(fā)揮自己的想像力和創(chuàng)造力，提出新問(wèn)題、新解法，若問(wèn)題過(guò)于復(fù)雜，無(wú)法寫(xiě)出目標(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è)城市并回到原出發(fā)點(diǎn)，在所有可能路徑中求出路徑長(zhǎng)度最短的一條。遺傳算法求解商旅問(wèn)題的控制參數(shù).種群初始化。個(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。.適應(yīng)度函數(shù)。在商旅問(wèn)題中，對(duì)于任意兩個(gè)城市之間的距離0&門）已知，每個(gè)染色體（即n個(gè)城市的隨機(jī)排列）可計(jì)算出總距離，因此可將一個(gè)隨機(jī)全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)，即距離越短，適應(yīng)度函數(shù)越好，滿足商旅問(wèn)題要求。fitness（i,1）=（1-（len（i,1）-minlen）/（maxlen-minlen+0.0001））「m.選擇操作。遺傳算法選擇操作有輪盤(pán)賭法、錦標(biāo)賽法等多種方法，本程序采用基于適應(yīng)度比例的選擇，即適應(yīng)度越好的個(gè)體被選擇的概率越大，同時(shí)在選擇中保存適應(yīng)度最高的個(gè)體。.交叉操作。遺傳算法中交叉操作有多種方法。本程序中對(duì)于個(gè)體，隨機(jī)選擇兩個(gè)個(gè)體，在對(duì)應(yīng)位置交換若干個(gè)基因片段，同時(shí)保證每個(gè)個(gè)體依然是1-n的隨機(jī)排列，防止進(jìn)入局部收斂。.變異操作。本程序中對(duì)于變異操作，隨機(jī)選取個(gè)體，同時(shí)隨機(jī)選取個(gè)體的兩個(gè)基因進(jìn)行交換以實(shí)現(xiàn)變異操作。圖1初始種群分布

圖2未進(jìn)行遺傳迭代的結(jié)果圖3進(jìn)行了迭代優(yōu)化后的結(jié)果圖2未進(jìn)行遺傳迭代的結(jié)果圖3進(jìn)行了迭代優(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);fori=1:Nforj=i+1:Ndis=(pos(i,1)-pos(j,1))「2+(pos(i,2)-pos(j,2))(2;D(i,j)=dis"(0.5);D(j,i)=D(i,j);endendpopm=zeros(M,N);fori=1:Mpopm(i,:)=randperm(N);endR=popm(1,:);figure(1);scatter(pos(:,1),pos(:,2),'rx');axis([-33-331);figure(2);plot_route(pos,R);axis([-33-33]);fitness=zeros(M,1);len=zeros(M,1);fori=1:Mlen(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),:);fori=1:Nfprintf('%d',R(i));endfprintf(，\n，);fitness=fitness/sum(fitness);distance_min=zeros(C+1,1);whileC>=0fprintf('迭代第%d次\n',C);nn=0;fori=1:size(popm,1)len_1(i,1)=myLength(D,popm(i,:));jc=rand*0.3;forj=1:size(popm,1)iffitness(j,1)>=jcnn=nn+1;popm_sel(nn,:)=popm(j,:);break;endendendpopm_sel=popm_sel(1:nn,:);[lenmlenindex]=min(len1);popm_sel=[popm_sel;popm(len_index,:)];nnper=randperm(nn);A=popm_sel(nnper(1),:);B=popm_sel(nnper(2),:);fori=1:nn*Pc[A,B]=cross(A,B);popm_sel(nnper(1),:)=A;popm_sel(nnper(2),:)=B;endfori=1:nnpick=rand;whilepick==0pick=rand;endifpick<=Pmutationpopm_sel(i,:)=Mutation(popm_sel(i,:));endendNN=size(popm_sel,1);len=zeros(NN,1);fori=1:NNlen(i,1)=myLength(D,popm_sel(i,:));endmaxlen=max(len);minlen=min(len);distance_min(C+1,1)=minlen;fitness=fit(len,m,maxlen,minlen);rr=find(len==minlen);fprintf('minlen=%d\n',minlen);R=popm_sel(rr(1,1),:);fori=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([-33-331);figure(4)plot(trace(1,:)');holdon;plot(trace(2,:)，,，-.，);grid;legend('解的變化'，’種群均值的變化')；個(gè)體距離mylength.mfunctionlen=myLength(D,p)[N,NN]=size(D);len=D(p(1,N),p(1,1));fori=1:(N-1)len=len+D(p(1,i),p(1,i+1));endend交叉cross.mfunction[A,B]=cross(A,B)L=length(A);ifL<10W=L;elseif((L/10)-floor(L/10))>=rand&&L>10W=ceil(L/10)+8;elseW=floor(L/10)+8;endp=unidrnd(L-W+1);fprintf('p=%d，,p);fori=1:Wx=find(A==B(1,p+i-1));y=find(B==A(1,p+i-1));[A(1,p+iT),B(1,p+iT)]=exchange(A(1,p+iT),B(1,p+iT));[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.mfunctiona=Mutation(A)index1=0;index2=0;nnper=randperm(size(A,2));index1=nnper(1);index2=nnper(2);temp=0;temp=A(index1);A(index1)=A(index2);A(index2)=temp;a=A;end適應(yīng)度f(wàn)it.mfunctionfitness=fit(len,m,maxlen,minlen)fitness=len;fori=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001))「m;end連點(diǎn)畫(huà)圖plot_route.mfunctionplot_route(a,R)scatter(a(:,1),a(:,2),'rx');holdon;plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);holdon;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);fori=1:Nforj=i+1:Ndis=(pos(i,1)-pos(j,1))「2+(pos(i,2)-pos(j,2))「2;D(i,j)=dis"(0.5);D(j,i)=D(i,j);endendpopm=zeros(M,N);fori=1:Mpopm(i,:)=randperm(N);endR=popm(1,:);figure(1);scatter(pos(:,1),pos(:,2),'rx');axis([-33-331);figure(2);plot_route(pos,R);axis([-33-33]);fitness=zeros(M,1);len=zeros(M,1);fori=1:Mlen(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),:);fori=1:Nfprintf('%d',R(i));endfprintf(，\n，);fitness=fitness/sum(fitness);distance_min=zeros(C+1,1);whileC>=0fprintf('迭代第%d次\n',C);nn=0;fori=1:size(popm,1)len_1(i,1)=myLength(D,popm(i,:));jc=rand*0.3;forj=1:size(popm,1)iffitness(j,1)>=jcnn=nn+1;popm_sel(nn,:)=popm(j,:);break;endendendpopm_sel=popm_sel(1:nn,:);[len_mlen_index]=min(len_1);popm_sel=[popm_sel;popm(len_index,:)];nnper=randperm(nn);A=popm_sel(nnper⑴，：)；B=popm_sel(nnper⑵，：)；fori=1:nn*Pc[A,B]=cross(A,B);popm_sel(nnper(1),:)=A;popm_sel(nnper(2),:)=B;endfori=1:nnpick=rand;whilepick==0pick=rand;endifpick<=Pmutationpopm_sel(i,:)=Mutation(popm_sel(i,:));endendNN=size(popm_sel,1);len=zeros(NN,1);fori=1:NNlen(i,1)=myLength(D,popm_sel(i,:));endmaxlen=max(len);minlen=min(len);distance_min(C+1,1)=minlen;fitness=fit(len,