MATLAB實(shí)驗(yàn)報(bào)告,遺傳算法解最短路徑以及函數(shù)最小值問(wèn)題

1、碩士生考查課程考試試卷考試科目： MATLAB教程 考生姓名： 考生學(xué)號(hào)： 學(xué) 院： 專 業(yè)： 考 生 成 績(jī)： 任課老師 (簽名) 考試日期：20 年 月 日 午 時(shí)至 時(shí)MATLAB教程試題：A、利用MATLAB設(shè)計(jì)遺傳算法程序，尋找下圖11個(gè)端點(diǎn)的最短路徑，其中沒(méi)有連接的端點(diǎn)表示沒(méi)有路徑。要求設(shè)計(jì)遺傳算法對(duì)該問(wèn)題求解。B、設(shè)計(jì)遺傳算法求解f(x)極小值，具體表達(dá)式如下：要求必須使用m函數(shù)方式設(shè)計(jì)程序。C、利用MATLAB編程實(shí)現(xiàn)：三名商人各帶一個(gè)隨從乘船渡河，一只小船只能容納二人，由他們自己劃行，隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨，但是如何乘船渡河的大權(quán)掌握在商

2、人手中，商人們?cè)鯓硬拍馨踩珊?？D、結(jié)合自己的研究方向選擇合適的問(wèn)題，利用MATLAB進(jìn)行實(shí)驗(yàn)。以上四題任選一題進(jìn)行實(shí)驗(yàn)，并寫(xiě)出實(shí)驗(yàn)報(bào)告。選擇題目： A 一、問(wèn)題分析（10分）如圖如示，將節(jié)點(diǎn)編號(hào)，依次為1.2.3.4.5.6.7.8.9.10.11，由圖論知識(shí)，則可寫(xiě)出其帶權(quán)鄰接矩陣為： 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 50

3、0 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0注：為避免計(jì)算時(shí)無(wú)窮大數(shù)吃掉小數(shù)，此處為令inf=500。問(wèn)題要求求出任意兩點(diǎn)間的最短路徑，F(xiàn)loyd算法采用的是在兩點(diǎn)間嘗試插入

4、頂點(diǎn)，比較距離長(zhǎng)短的方法。我思考后認(rèn)為，用遺傳算法很難找到一個(gè)可以統(tǒng)一表示最短路徑的函數(shù)，但是可以對(duì)每一對(duì)點(diǎn)分別計(jì)算，然后加入for循環(huán)，可將相互之間的所有情況解出。觀察本題可發(fā)現(xiàn)，所有節(jié)點(diǎn)都是可雙向行走，則可只計(jì)算i到j(luò)的路徑與距離，然后將矩陣按主對(duì)角線翻折即可得到全部數(shù)據(jù)。二、實(shí)驗(yàn)原理與數(shù)學(xué)模型（20分）實(shí)現(xiàn)原理為遺傳算法原理：按所選擇的適應(yīng)度函數(shù)并通過(guò)遺傳中的復(fù)制、交叉及變異對(duì)個(gè)體進(jìn)行篩選，使得適應(yīng)度高的個(gè)體被保留下來(lái)，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。數(shù)學(xué)模型如下： 設(shè)圖 由非空點(diǎn)集合 和邊集合 組成，

5、其中 又設(shè) 的值為 ， 故 可表示為一個(gè)三元組則求最短路徑的數(shù)學(xué)模型可以描述為：實(shí)驗(yàn)具體：第一：編碼與初始化因采用自然編碼，且產(chǎn)生的編碼不能重復(fù)，于是我采用了randperm函數(shù)產(chǎn)生不重復(fù)的隨機(jī)自然數(shù)。因解題方法是使用的是計(jì)算每一對(duì)點(diǎn)，則我們編碼時(shí)將第一個(gè)節(jié)點(diǎn)單獨(dú)放入，合并成完整編碼。因?yàn)楣?jié)點(diǎn)有11個(gè)，可采用一個(gè)1行11列的矩陣儲(chǔ)存數(shù)據(jù)，同時(shí)，由于編號(hào)為數(shù)字，可直接使用數(shù)字編碼表示路徑的染色體。具體如下：采用等長(zhǎng)可變?nèi)旧w的方式，例如由2到9的路徑，染色體編碼可能為（2，5，1，8，4，6，9，3，10，7，11），超過(guò)9之后的編碼，用來(lái)進(jìn)行算子的運(yùn)算，不具備實(shí)際意義。第二：計(jì)算適應(yīng)度，因取最

6、短路徑值，即最小值，常用方法為C-F(x)或C/F(x)（C為一常數(shù)），此處采用前一種方式。于是，可進(jìn)一步計(jì)算相對(duì)適應(yīng)度。第三：選擇與復(fù)制采用輪盤(pán)賭算法，產(chǎn)生一個(gè)隨機(jī)值，比較它與累計(jì)相對(duì)適應(yīng)度的關(guān)系，從而選擇出優(yōu)良個(gè)體進(jìn)入下一代。第四：交叉。因編碼是不重復(fù)的數(shù)字，所以采用傳統(tǒng)的交叉方法，即上一行與下一行對(duì)位交叉，會(huì)產(chǎn)生無(wú)效路徑，于是，采用了不同的交叉方法，具體如下：（1）在表示路徑的染色體Tx 和Ty中，隨機(jī)選取兩個(gè)基因座（不能為起點(diǎn)基因座）i和j, 即將i個(gè)基因座和第j個(gè)基因座之間的各個(gè)基因座定義為交叉域，并將交叉的內(nèi)容分別記憶為temp1和temp2。（2）根據(jù)交叉區(qū)域中的映射關(guān)系，在個(gè)體

7、Tx中找出所有與temp2相同的元素，在個(gè)體Ty中找出所有與temp1相同的元素，全部置為0。（3）將個(gè)體Tx、Ty進(jìn)行循環(huán)左移，遇到0就刪除，直到編碼串中交叉區(qū)域的左端不再有0：然后將所有空位集中到交叉區(qū)域，而將交叉區(qū)域內(nèi)原有的基因依次向后移動(dòng)。因0元素可能較多，在程序?qū)崿F(xiàn)時(shí)，我是將非零元素提出，后面再合成。（4）將temp2插入到Tx的交叉區(qū)域，temp1插入到Ty的交叉區(qū)域。形成新的染色體1。第五：變異染色體編碼為從1到11的無(wú)重復(fù)編碼，所以不能采用一般的生成一個(gè)隨機(jī)數(shù)替代的辦法。此處采用交換變異法。即隨機(jī)產(chǎn)生兩個(gè)數(shù)，交換兩個(gè)節(jié)點(diǎn)的順序。例： 則新染色體編碼為：三、實(shí)驗(yàn)過(guò)程記錄（含基本步

8、驟、程序代碼及異常情況記錄等）（60分）首先，寫(xiě)程序，修復(fù)Bug。然后，調(diào)試種群數(shù)量，遺傳代數(shù)，交叉概率，變異概率等，不斷運(yùn)行程序，以達(dá)到較理想的狀態(tài)。有一次異常情況：算出來(lái)的最短距離均為0，最短路徑?jīng)]有終點(diǎn)出現(xiàn)，經(jīng)過(guò)分析發(fā)現(xiàn)，因?yàn)榻徊嫣幍拇a較復(fù)雜，弄錯(cuò)了一點(diǎn)，導(dǎo)致新基因有部分為非法基因。最后采用提出非零數(shù)值組成向量，再合成新基因的方式解決。Matlab程序代碼如下：clc;clear;%初始化參數(shù) %注：popsize=200,MaxGeneration=100,約跑2分鐘。若不要求太精確，可減少循環(huán)次數(shù)。pointnumber=11; %節(jié)點(diǎn)個(gè)數(shù)Popsize=200; %種群規(guī)模，只能

9、取偶數(shù)（因67行的循環(huán)）MaxGeneration=100; %最大代數(shù)Pc=0.8;Pm=0.3; %交叉概率和變異概率A=0 2 8 1 50 50 50 50 50 50 50 2 0 6 50 1 50 50 50 50 50 50 8 6 0 7 50 1 50 50 50 50 50 1 50 7 0 50 50 9 50 50 50 50 50 1 50 50 0 3 50 2 50 50 50 50 50 1 50 3 0 4 50 6 50 50 50 50 50 9 50 4 0 50 50 1 50 50 50 50 50 2 50 50 0 7 50 9 50 50 5

10、0 50 50 6 50 7 0 1 2 50 50 50 50 50 50 1 50 1 0 4 50 50 50 50 50 50 50 9 2 4 0; %帶權(quán)鄰接矩陣。A(A=50)=500; %取值50過(guò)小而修正為500；Bestindividual=zeros(MaxGeneration,1);outdistance=zeros(11,11);outpath=cell(11,11); %用于存放11個(gè)點(diǎn)相互之間的最短路徑%* 生成初始種群 *for a=1:pointnumber %起點(diǎn)的編號(hào)%a=1; tempvary=1 2 3 4 5 6 7 8 9 10 11;tempva

11、ry(a)=; %暫時(shí)剔除起點(diǎn)tempmatrix=a*ones(Popsize,1); %將起點(diǎn)單獨(dú)放一矩陣path=zeros(Popsize,pointnumber-1); %聲明矩陣大小，避免減慢速度f(wàn)or i=1:Popsize temprand=randperm(pointnumber-1); path(i,:)=tempvary(temprand(1:end); %生成一系列剔除起點(diǎn)的隨機(jī)路線endpath=tempmatrix path; %合成包括起點(diǎn)的完整路線row,col=size(path);for b=a:pointnumber %終點(diǎn)的編號(hào)%b=10;for k=1

12、:1:MaxGeneration for i=1:row position2=find(path(i,:)=b); %找出終點(diǎn)在路線中的位置 pathlong(i)=0; for j=1:position2-1 pathlong(i)=pathlong(i)+A(path(i,j),path(i,j+1); end end %計(jì)算適應(yīng)度 Fitness=length(A)*max(max(A)-pathlong; %因要求最小值，采且常數(shù)減函數(shù)值構(gòu)造適應(yīng)度 Fitness=Fitness./sum(Fitness); %* Step 1 : 選擇最優(yōu)個(gè)體 * Bestindividual(k)

13、=min(pathlong); Orderfi,Indexfi=sort(Fitness); %按照適應(yīng)度大小排序 Bestfi=Orderfi(Popsize); %Oderfi中最后一個(gè)即是最大的適應(yīng)度 BestS=path(Indexfi(Popsize),:); %記錄每一代中最優(yōu)個(gè)體的路線 %* Step 2 : 選擇與復(fù)制操作* temppath=path; roulette=cumsum(Fitness); for i=1:Popsize tempP=rand(1); for j=1:length(roulette) if tempP<roulette(j) break;

14、end end path(i,:)=temppath(j,:); end %* Step 3 : 交叉操作 * temppath2=path; for i=1:2:row tempP2=rand(1); if(tempP2<rand(1) temPm2=fix(rand(1)+0.2)*10); %因起點(diǎn)基因不能改變 temPm3=fix(rand(1)+0.2)*10); %隨機(jī)取出兩個(gè)位置為2到11基因座 temPm4=min(temPm2,temPm3); temPm5=max(temPm2,temPm3); temp1=path(i,temPm4:temPm5); %將兩點(diǎn)之間的

15、基因儲(chǔ)存，方便交叉 temp2=path(i+1,temPm4:temPm5); c d=find(ismember(path(i,:),temp2); path(i,d)=0; %找出i行在i+1行取出區(qū)域中的數(shù)，置為0 e f=find(ismember(path(i+1,:),temp1); path(i+1,f)=0; %找出i+1行在i行取出區(qū)域中的數(shù)，置為0 g h=find(path(i,:)=0); v1=path(i,h); %取出i行的非零元素，成一向量 l m=find(path(i+1,:)=0); v2=path(i+1,m); %取出i+1行的非零元素，成一向量 p

16、ath(i,:)=v1(1:temPm4-1) temp2 v1(temPm4-1+size(temp1):end); path(i+1,:)=v2(1:temPm4-1) temp1 v2(temPm4-1+size(temp2):end); %基因交叉 end end path(Popsize,:)=BestS; %* Step 4: 變異操作 * for i=1:Popsize tempPm=rand(1); if(tempPm<Pm) temPm6=fix(rand(1)+0.2)*10); temPm7=fix(rand(1)+0.2)*10); %產(chǎn)生兩個(gè)用于交換的隨機(jī)數(shù) t

17、empvessel=path(i,temPm6); %交換前用一臨時(shí)容器存放數(shù)據(jù) path(i,temPm6)=path(i,temPm7); path(i,temPm7)=tempvessel; %變異交換 end end path(Popsize,:)=BestS;endaa bb=find(BestS=b); %找出終點(diǎn)Bestpath=BestS(1:bb); %剔除后面無(wú)用的點(diǎn)，留下實(shí)際路線outdistance(a,b)=Bestindividual(k); %將最短距離寫(xiě)入矩陣outpatha,b=Bestpath; %寫(xiě)入路徑，因數(shù)據(jù)類型為矩陣，所以采用元胞數(shù)組儲(chǔ)存endend

18、for i=1:pointnumber for j=1:i outdistance(i,j)=outdistance(j,i); %實(shí)現(xiàn)距離的對(duì)稱 outpathi,j=fliplr(outpathj,i); %實(shí)現(xiàn)路徑的對(duì)稱與翻轉(zhuǎn) endend %* 結(jié)果輸出 *outdistancecelldisp(outpath)%xlswrite('tempdata.xls', outpath) %存入excel中進(jìn)行操作四、實(shí)驗(yàn)結(jié)果與總結(jié)（10分）距離矩陣：a(i,j) i表示起點(diǎn)，j表示終點(diǎn)。outdistance = 0 2 7 1 3 6 10 5 12 11 14 2 0 5

19、 3 1 4 8 3 10 9 12 7 5 0 7 4 1 5 6 7 6 9 1 3 7 0 4 8 9 6 11 10 13 3 1 4 4 0 3 7 2 9 8 11 6 4 1 8 3 0 4 5 6 5 8 10 8 5 9 7 4 0 9 2 1 4 5 3 6 6 2 5 9 0 7 8 9 12 10 7 11 9 6 2 7 0 1 2 11 9 6 10 8 5 1 8 1 0 314 12 9 13 11 8 4 9 2 3 0路徑：b(i,j) i表示起點(diǎn)，j表示終點(diǎn)。outpath:此程序運(yùn)算速度有待提高，程序的收斂速度不是很快。可能的原因如下：（1） 在變異操作

20、時(shí)，可能將本來(lái)很好的解棄掉，換來(lái)更差的染色體，導(dǎo)致收斂速度不佳。解決辦法：可以在變異操作時(shí)，增加個(gè)體求優(yōu)的自學(xué)習(xí)過(guò)程。即在某位基因變異后，計(jì)算新染色體的適應(yīng)函數(shù)值，若適應(yīng)值變大，即路徑更短，則保留；否則，保持原來(lái)的染色體不變。（2） 算法的進(jìn)一步改進(jìn)，例如可加入Floyd算法的思想，在父代產(chǎn)生子代的過(guò)程中，不是單純的交叉，可以考慮隨機(jī)加入頂點(diǎn)是否路徑變短。參考文獻(xiàn)：1康曉軍，王茂才.基于遺傳算法的最短路徑問(wèn)題的求解.計(jì)算機(jī)工程與應(yīng)用J,2008,44(23)第二題代碼：clc;clear;%Rosenbrock函數(shù)的極大值0-1編碼的GA算法%初始參數(shù)tic;Size=80; G=100; C

21、odeL=10; umax=5.12; umin=-5.12; E=round(rand(Size,3*CodeL); %生成初始種群 %主程序for k=1:1:G time(k)=k; for s=1:1:Size m=E(s,:); y1=0;y2=0; y3=0; %解碼方法m1=m(1:1:CodeL); for i=1:1:CodeL y1=y1+m1(i)*2(i-1); end x1=(umax-umin)*y1/1023+umin; m2=m(CodeL+1:1:2*CodeL); for i=1:1:CodeL y2=y2+m2(i)*2(i-1); end x2=(uma

22、x-umin)*y2/1023+umin; m3=m(2*CodeL+1:1:end); for i=1:1:CodeL y3=y3+m3(i)*2(i-1); end x3=(umax-umin)*y3/1023+umin; F(s)=x12+x22+x33; end %* Step 1 : 選擇最優(yōu)個(gè)體 * BestJ(k)=min(F); %記錄每一代中最大個(gè)體的函數(shù)值 fi=F; %適應(yīng)度函數(shù)Oderfi,Indexfi=sort(fi); %按照適應(yīng)度大小排序Bestfi=Oderfi(1); %Oderfi中最后一個(gè)即是最大的適應(yīng)度 BestS=E(Indexfi(1),:); %記錄每一代中最優(yōu)個(gè)體的0-1編碼bfi(k)=Bestfi; %記錄每一代中最優(yōu)個(gè)體的適應(yīng)度 %* Step 2 : 選擇與復(fù)制操作* fi_sum=sum(fi); fi_Size=(Oderfi/fi_sum)*Size; %計(jì)算個(gè)體相對(duì)適應(yīng)度 fi_S=floor(fi_Size); %對(duì)80個(gè)個(gè)體依據(jù)相對(duì)適應(yīng)度進(jìn)行劃分等級(jí) kk=1; for i=1:1:Size for j=1:1:fi_S(i) %選擇等級(jí)高的個(gè)體，等級(jí)越高被