畢業論文—基于遺傳算法的0-1背包問題研究-資料下載頁

【導讀】matlab環境中進行GUI界面設計，實現相關參數的輸入與進化曲線的輸出顯示。KeyWords：0-1knapsackproblem；Geicalgorithm；Popsize；Matlab；GUI. 遺傳算法的研究現狀與發展趨勢........

　　

【正文】 e=fit_arr./fit_sum。 %輪盤， rotary table %生成輪盤，類似于概率分布 For i=2:POP_NUM rtable(i)=rtable(i1)+rtable(i)。 end for i=1:POP_NUM p=rand(1)。 index=1。 while p rtable(index) index=index+1。 end winner_index(i)=index。 end 以上程序是把所有個體的適應度值求和，然后計算每個個體的適應度值占總和中的比例，比例越大，該個體對應的適應度的范圍越大。 (5)交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染色體進行交叉，一般采用一點交叉方式， 交叉概率為 Pc，具體操作是在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新 設計（論文）專用紙 19 個體。這里嘗試用“與／或 交叉方法，這一交叉方法使子代繼承了雙親的同型基因，對于雙親的雜型基因，“與／或 交叉方法采取了兩種不同的“支配 方式，“與”運算是一種 0支配 l的方式，而“或 運算是一種 1支配 0的方式，采用“與／或”交叉策略能使優化過程更加迅速的達到全局最優解，獲得全局最優解的時間僅為“一點交叉 策略的 1／ 9到 1／ 3。 % 交叉操作 cross_index=1:POP_NUM。 %參與交叉的樣本的索引 for i=1:POP_NUM temp=unidrnd(POP_NUMi+1)。%在 1到 POP_NUMi+1之間取隨機數 temp_pos=i+temp1。 temp_val=cross_index(temp_pos)。 cross_index(temp_pos)=cross_index(i)。 cross_index(i)=temp_val。 end 選擇 個體中的兩個位置，把這兩個位置對應的值進行交換， 交叉操作 先對可能要經行交叉的樣本進行索引，隨機得到一個數若這個數小于交叉概率的話進行相鄰交叉否則不交叉。 for i=1:2:POP_NUM %相鄰兩個進行交叉 %隨機得到一個數，小于交叉概率的話，進行交叉 if rand(1) P_CROSS cross_pos=unidrnd(POP_NUM1 )。 %交叉點位置 ,[1, POP_NUM1] temp_cross=samp_arr(cross_index(i), cross_pos:end)。 samp_arr(cross_index(i), cross_pos:end)= ... samp_arr(cross_index(i+1), cross_pos:end)。 samp_arr(cross_index(i+1), cross_pos:end)=temp_cross。 end end (6)變異操 作：染色體變異采用位點變異的方式。位點變異比較簡單，針對本問題來說，就是把染色體的變異位 1變為 0， 0變為 1就可以了，其它位都保持不變。 設計（論文）專用紙 20 變異前染色體為： 1 1 1 0 0 0 1 1 0 1 變異后染色體為： 0 0 0 1 1 1 0 0 1 0 變異概率為 Pm，變異的目的是使其變異后的適應度大于或等于其原適應度。先選擇一個變異位進行變異，再計算它的適應度，看它是否大于或等于其原來的適應度，若不是的話就重新選擇變異位進行變異。對種群依次進行選擇、交叉、變異后就檢驗得到的新個體，當某代得到的結果滿足要求或 當前代數等于結束代數時算法結束得到結果 ，否則重復選擇、交叉、變異操作，直到得到滿意的結果為止。 %變異操作，直接針對整個樣本集操作 muta_arr=( rand(POP_NUM, LEN) P_MUTA )。 index=find(muta_arr)。 samp_arr(index)=1samp_arr(index)。 %找到最后一代中的最佳樣本 [max_val, max_index]= max(fit_arr)。 temp=samp_arr(max_index, :)。 index=find(temp)。 %index記錄所取得物體編號 數值試驗以及結果分析 程序思路分析如下：采用二進制 0I 編碼。裝入背包的物品用 1 表示，未裝入的用 0表示，一種裝入方法用一個染色體表示，總共產生的染色體個數等于群體規模。對各個染色體計算其適應度值，淘汰適應度值最低的，復制適應度值最高的，用最高的代替最低的，這樣完成選擇；再隨機產生交叉點及相互交叉的染色體進行交叉，計算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達到交叉最多 次數未交叉成功則退出；交叉完成后就進行變異，根據變異概率隨機選擇變異的染色體，隨機產生變異點進行變異，變異后也需要計算染色體是否符合要求，若不符合則變異失敗，重新變異，達到變異最多次數未變異成功則退出。這樣遺傳算法的基本步驟完成，重復以上步驟，直到設計的進化次 設計（論文）專用紙 21 數才退出。 算例 1 A． 實驗設置與仿真結果 value = [220,208,198,192,180,180,165,162,160,158,155,130,125,122, 120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73, 72， 70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1]。 weight = [80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60, 30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30, 10,20,25,15,10,10,10,4,4,2,1 ]。 C=1000 其中， value 表示背包中物品的價值， weight 表示相應物品的重量， C 表示 背包的最大容量。 已知該算例的最優解為 3103。將種群規模設置為 50，最大迭代次數為 500，交叉概率為 ，變異概率為 。程序循環運行 20次，結果如下表 21，仿真圖如22。 表 21 算例 1求解結果 循環次數 迭代次數 最優值 最差值 平均值 命中最優解概率 20 500 3103 1429 45% 從表 21可以看出在程序運行 20次中命中了 9次最優解 3103，平均值為 ，最優值與最差值的差值為 1674，說明遺傳算法求解背包問題不易陷入局部最優。 設計（論文）專用紙 22 0 2 4 6 8 10 12 14 16 18 201400160018002020220024002600280030003200 X : 1 0Y : 3 1 0 320 次循環結果最優值最差值平均值 圖 22 算例 1運行 20次結果仿真圖 通過圖 22，可以很清楚地看 到算法運行 20次產生的最優值、最差值以及平均值的仿真曲線。從圖中可以看出最優值仿真曲線和平均值的仿真曲線波動不大，表明遺傳算法的尋優能力比較好。而最差值波動相對較大一些，并且從仿真曲線圖中可看到最優值與最差值之間的差距較大，說明種群具有一定的多樣性。 B 不同參數對算法性能的影響 （ 1） 種群規模對算法性能影響 設置交叉概率為 ，變異概率為 ，最大迭代次數為 500，染色體長度為 50。當種群規模分別為 100、 200、 400、 500 時，對算例 1 進行求解，所得結果如表 22所示。 表 22 不同種群規模求解算例 1 的結果 種群規模 總價值 總體積 100 3094 996 200 3095 996 400 3103 1000 500 3103 1000 從上表可以看出，隨著種群規模的增大總價值和總體積也隨之增大，并且在種群 設計（論文）專用紙 23 規模為 400 的時候已命中最優解 3103，同時在種群規模為 500 時也命中最優解，說明種群規模增大時遺傳 算法在求解背包問題的時候選擇范圍更廣，更易命中最優解。 （ 2） 交叉概率對算法性能的影響 設置變異概率為 、最大迭代次數為 500、染色體長度為 50、交叉概率分別為、 、 、 、 、 、 時對算例 1 進行求解，所得結果如表 23。 表 23 不同交叉概率求解算例 1的結果 交叉概率 總價值 總體積 3091 998 3095 1000 3103 1000 3103 1000 3103 1000 3103 1000 3103 1000 從表 23 可以看出當交叉概率增大時與之對應的總值和 總體積 也隨之增加并在交叉概率為 時命中最優解，隨著交叉概率增加大依然保持命中最優解。說明 交叉的頻率越高可以越快的收斂到最優區域。 （ 3） 最大迭代次數對算法性能的影響 設置變異概率為 、交叉概率為 、染色體長度為 50、迭代次數分別為 100、200、 300、 500、 對算例 1運行 20 次，所得結果如表 24所示 表 24 不同迭代次數求解算例 1的結果 最大迭代次數 總價值 總體積 100 3068 999 200 3084 1000 300 3091 1000 500 3103 1000 設計（論文）專用紙 24 從表 24 可以看出隨著迭代次數的增加總價值和總體積也隨之增加并且在迭代500 次時命中最優解。 說明種群演化代數增加時，求得的解會更接近或者直接命中最優解。 綜上所述種群規模、交叉概率以及迭代次數的設置對于遺傳算法在求解 01背包問題時對于命中最優解的影響是 非常明 的，通過以上實驗的探究我可以看到當交叉 概率為 ，迭代次數為 500 時都命中了最優解 3103，那么我可以利用這兩個參數對算例 2進行測試。 算例 2 設物品價值為 Pi， 物品重量為 Wi，物品的 Wi 重量是（ 1,10）的隨機數，背包最大容量為 C。 Pi 與 C 的數值由以下公式得出。 5iipw?? （ 21） 112 n iicw?? ? （ 22） 設置交叉概率 Pc=，迭代次數為 500，變異概率為 當物品總數分別為50、 100、 150 時 ，對算例 2 運行 20 次，觀察種群規模分別為 50、 100、 200 時的 結果 。 當物品數量為 50 時，循環 20 次的結果如表 25和仿真圖分別如圖 24,圖 25,圖 26 所 示。 表 25 不同種群規模求解算例的 2結果 種群規模 迭代次數 最大值 最小值 平均值 50 500 316 176 100 500 322 161 200 500 324 160 設計（論文）專用紙 25 0 2 4 6 8 10 12 14 16 18 20160180200220240260280300320X : 1 3Y : 3 1 6 20 次循環結果最大值最小值平均值 圖 24 種群規模為 50算例 2的仿真圖 0 2 4 6 8 10 12 14 16 18 20160180200220240260280300320340X : 1 6Y : 3 2 2 20 次循環結果最大值最小值平均值 圖 25 種群規模為 100算例 2的仿真圖 0 2 4 6 8 10 12 14 16 18 2016018020022024026028030032034020 次循環結果 X : 1 0Y : 3 2 4最大值最小值平均值 圖 26 種群 規模為 200算例 2的 仿真圖 設計（論文）專用紙 26 當物品數為 100時 循環 20次算例 2的結果如表 26和仿真圖分別圖 2圖 2