MATLAB實驗報告-遺傳算法解最短路徑以及函數(shù)最小值問題

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

2、人手中，商人們怎樣才能安全渡河？D、結(jié)合自己的研究方向選擇合適的問題，利用MATLAB進行實驗。以上四題任選一題進行實驗，并寫出實驗報告。選擇題目： A 一、問題分析（10分）如圖如示，將節(jié)點編號，依次為1.2.3.4.5.6.7.8.9.10.11，由圖論知識，則可寫出其帶權(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注：為避免計算時無窮大數(shù)吃掉小數(shù)，此處為令inf=500。問題要求求出任意兩點間的最短路徑，F(xiàn)loyd算法采用的是在兩點間嘗試插入

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

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

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

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

8、驟、程序代碼及異常情況記錄等）（60分）首先，寫程序，修復Bug。然后，調(diào)試種群數(shù)量，遺傳代數(shù)，交叉概率，變異概率等，不斷運行程序，以達到較理想的狀態(tài)。有一次異常情況：算出來的最短距離均為0，最短路徑?jīng)]有終點出現(xiàn)，經(jīng)過分析發(fā)現(xiàn)，因為交叉處的代碼較復雜，弄錯了一點，導致新基因有部分為非法基因。最后采用提出非零數(shù)值組成向量，再合成新基因的方式解決。Matlab程序代碼如下：clc;clear;%初始化參數(shù) %注：popsize=200,MaxGeneration=100,約跑2分鐘。若不要求太精確，可減少循環(huán)次數(shù)。pointnumber=11; %節(jié)點個數(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過小而修正為500；Bestindividual=zeros(MaxGeneration,1);outdistance=zeros(11,11);outpath=cell(11,11); %用于存放11個點相互之間的最短路徑%* 生成初始種群 *for a=1:pointnumber %起點的編號%a=1; tempvary=1 2 3 4 5 6 7 8 9 10 11;tempva

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

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

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

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

15、叉 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行的非零元素，成一向量 path(i,:)

16、=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(tempPmtemp %交叉條件 TempE(i,n:end)=E(i+1,n:end); TempE(i+1,n:end)=E(i,n:end); end end TempE(Size,:)=BestS; %最優(yōu)個體保留E=TempE; %種群替換 %* Step 4: 變異操作 * %pm=0.001; %pm=0.001-1:1:Size*(0.001)/Size; %自適應變異概率%pm=0.0; %沒有變異pm=0.1; %較大的變異概率 for i=1:1:Size for j=1:1:2*CodeL temp=rand; if pmtemp %變異條件 if TempE(