【導(dǎo)讀】matlab環(huán)境中進(jìn)行GUI界面設(shè)計(jì)，實(shí)現(xiàn)相關(guān)參數(shù)的輸入與進(jìn)化曲線的輸出顯示。KeyWords：0-1knapsackproblem；Geicalgorithm；Popsize；Matlab；GUI

　　

【正文】 UM p=rand(1)。 index=1。 while p rtable(index) index=index+1。 end winner_index(i)=index。 end 以上程序是把所有個(gè)體的適應(yīng)度值求和，然后計(jì)算每個(gè)個(gè)體的適應(yīng)度值占總和中的比例，比例越大，該個(gè)體對(duì)應(yīng)的適應(yīng)度的范圍越大。 (5)交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染色體進(jìn)行交叉，一般采用一點(diǎn)交叉方式，交叉概率為 Pc，具體操作是在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新 設(shè)計(jì)（論文）專(zhuān)用紙 19 個(gè)體。這里嘗試用“與／或 交叉方法，這一交叉方法使子代繼承了雙親的同型基因，對(duì)于雙親的雜型基因，“與／或 交叉方法采取了兩種不同 的“支配 方式，“與”運(yùn)算是一種 0支配 l的方式，而“或 運(yùn)算是一種 1支配 0的方式，采用“與／或”交叉策略能使優(yōu)化過(guò)程更加迅速的達(dá)到全局最優(yōu)解，獲得全局最優(yōu)解的時(shí)間僅為“一點(diǎn)交叉 策略的 1／ 9到 1／ 3。 % 交叉操作 cross_index=1:POP_NUM。 %參與交叉的樣本的索引 for i=1:POP_NUM temp=unidrnd(POP_NUMi+1)。%在 1到 POP_NUMi+1之間取隨機(jī)數(shù) temp_pos=i+temp1。 temp_val=cross_index(temp_pos)。 cross_index(temp_pos)=cross_index(i)。 cross_index(i)=temp_val。 end 選擇個(gè)體中的兩個(gè)位置，把這兩個(gè)位置對(duì)應(yīng)的值進(jìn)行交換， 交叉操作 先對(duì)可能要經(jīng)行交叉的樣本進(jìn)行索引，隨機(jī)得到一個(gè)數(shù)若這個(gè)數(shù)小于交叉概率的話進(jìn)行相鄰交叉否則不交叉。 for i=1:2:POP_NUM %相鄰兩個(gè)進(jìn)行交叉 %隨機(jī)得到 一個(gè)數(shù)，小于交叉概率的話，進(jìn)行交叉 if rand(1) P_CROSS cross_pos=unidrnd(POP_NUM1 )。 %交叉點(diǎn)位置 ,[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)變異操作：染色體變異采用位點(diǎn)變異的方式。位點(diǎn)變異比較簡(jiǎn)單，針對(duì)本問(wèn)題來(lái)說(shuō)，就是把染色體的變異位 1變?yōu)?0， 0變?yōu)?1就可以了，其它位都保持不變。 設(shè)計(jì)（論文）專(zhuān)用紙 20 變異前染色體為： 1 1 1 0 0 0 1 1 0 1 變異后染色體為： 0 0 0 1 1 1 0 0 1 0 變異概率為 Pm，變異的目的是使其變異后的適應(yīng)度大于或等于其原適應(yīng)度。先選擇一個(gè)變異位進(jìn)行變異，再計(jì)算它的適應(yīng)度，看它是否大于或等于其原來(lái)的適應(yīng)度，若不是的話就重新選擇變異位進(jìn)行變異。對(duì)種群依次進(jìn)行選擇、交叉、變異后就檢驗(yàn)得到的新個(gè)體，當(dāng)某代得到的結(jié)果滿足要求或當(dāng)前代數(shù)等于結(jié)束代數(shù)時(shí)算法結(jié)束得到結(jié)果 ，否則重復(fù)選擇、交叉、變異操作，直到得到滿意的結(jié)果為止。 %變異操作，直接針對(duì)整個(gè)樣本集操作 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記錄所取得物體編號(hào) 數(shù)值試驗(yàn)以及結(jié)果分析 程序思路分析如下 ： 采用二進(jìn)制 0I 編碼。裝入背包的物品用 1 表示，未裝入的用 0表示，一種裝入方法用一個(gè)染色體表示，總共產(chǎn)生的染色體個(gè)數(shù)等于群體 規(guī)模。對(duì)各個(gè)染色體計(jì)算其適應(yīng)度值，淘汰適應(yīng)度值最低的，復(fù)制適應(yīng)度值最高的，用最高的代替最低的，這樣完成選擇；再隨機(jī)產(chǎn)生交叉點(diǎn)及相互交叉的染色體進(jìn)行交叉，計(jì)算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達(dá)到交叉最多次數(shù)未交叉成功則退出；交叉完成后就進(jìn)行變異，根據(jù)變異概率隨機(jī)選擇變異的染色體，隨機(jī)產(chǎn)生變異點(diǎn)進(jìn)行變異，變異后也需要計(jì)算染色體是否符合要求，若不符合則變異失敗，重新變異，達(dá)到變異最多次數(shù)未變異成功則退出。這樣遺傳算法的基本步驟完成，重復(fù)以上步驟，直到 設(shè)計(jì)的進(jìn)化次 設(shè)計(jì)（論文）專(zhuān)用紙 21 數(shù)才退出。 算例 1 A． 實(shí)驗(yàn)設(shè)置與仿真結(jié)果 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 表示背包中物品的價(jià)值， weight 表示相應(yīng)物品的重量， C 表示 背包的最大容量。 已知該算例的最優(yōu)解為 3103。將種群規(guī)模設(shè)置為 50，最大迭代次數(shù)為 500，交叉概率為 ，變異概率為 。 程序循環(huán)運(yùn)行 20次，結(jié)果如下表 21，仿真圖如22。 表 21 算例 1求解結(jié)果 循環(huán)次數(shù) 迭代次數(shù) 最優(yōu)值 最差值 平均值 命中最優(yōu)解概率 20 500 3103 1429 45% 從表 21可以看出在程序運(yùn)行 20次中命中了 9次最優(yōu)解 3103，平均值為 ，最優(yōu)值與最差值的差值為 1674，說(shuō)明遺傳算法求解背包問(wèn)題不易陷入局部最優(yōu)。 設(shè)計(jì)（論文）專(zhuān)用紙 22 0 2 4 6 8 10 12 14 16 18 201400160018002020220024002600280030003200 X : 1 0Y : 3 1 0 320 次循環(huán)結(jié)果最優(yōu)值最差值平均值 圖 22 算例 1運(yùn)行 20次結(jié)果仿真圖 通過(guò)圖 22，可以很清楚地看 到算法運(yùn)行 20次產(chǎn)生的最優(yōu)值、最差值以及平均值的仿真曲線。從圖中可 以看出最優(yōu)值仿真曲線和平均值的仿真曲線波動(dòng)不大，表明遺傳算法的尋優(yōu)能力比較好。而最差值波動(dòng)相對(duì)較大一些，并且從仿真曲線圖中可看到最優(yōu)值與最差值之間的差距較大，說(shuō)明種群具有一定的多樣性。 B 不同參數(shù)對(duì)算法性能的影響 （ 1） 種群規(guī)模對(duì)算法性能影響 設(shè)置交叉概率為 ，變異概率為 ，最大迭代次數(shù)為 500，染色體長(zhǎng)度為 50。當(dāng)種群規(guī)模分別為 100、 200、 400、 500 時(shí)，對(duì)算例 1 進(jìn)行求解，所得結(jié)果如表 22所示。 表 22 不同種群規(guī)模求解算例 1 的結(jié)果 種群規(guī)模 總價(jià)值 總體積 100 3094 996 200 3095 996 400 3103 1000 500 3103 1000 從上表可以看出，隨著種群規(guī)模的增大總價(jià)值和總體積也隨之增大，并且在種群 設(shè)計(jì)（論文）專(zhuān)用紙 23 規(guī)模為 400 的時(shí)候已命中最優(yōu)解 3103，同時(shí)在種群規(guī)模為 500 時(shí)也命中最優(yōu)解，說(shuō)明種群規(guī)模增大時(shí)遺傳算法在求解背包問(wèn)題的時(shí)候選擇范圍更廣，更易命中最優(yōu)解。 （ 2） 交叉概率對(duì)算法性能的影響 設(shè)置變異概率為 、最大迭代次數(shù)為 500、染色體長(zhǎng)度為 50、交叉概率分別為、 、 、 、 、 、 時(shí)對(duì)算例 1 進(jìn)行求解，所得結(jié)果 如表 23。 表 23 不同交叉概率求解算例 1的結(jié)果 交叉概率 總價(jià)值 總體積 3091 998 3095 1000 3103 1000 3103 1000 3103 1000 3103 1000 3103 1000 從表 23 可以看出當(dāng)交叉概率增大時(shí)與之對(duì)應(yīng)的總值和 總體積 也隨之增加并在交叉概率為 時(shí)命中最優(yōu)解，隨著交叉概率增加大依然保持命中最優(yōu)解。說(shuō)明 交叉的頻率越高可以越快的收斂到最優(yōu)區(qū)域。 （ 3） 最大迭代次數(shù)對(duì)算法性能的影響 設(shè)置變異概率為 、交叉概率為 、染色體長(zhǎng)度為 50、迭代次數(shù)分別為 100、200、 300、 500、 對(duì)算例 1運(yùn)行 20 次，所得結(jié)果如表 24所示 表 24 不同迭代次數(shù)求解算例 1的結(jié)果 最大迭代次數(shù) 總價(jià)值 總體積 100 3068 999 200 3084 1000 300 3091 1000 500 3103 1000 設(shè)計(jì)（論文）專(zhuān)用紙 24 從表 24 可以看出隨著迭代次數(shù)的增加總價(jià)值和總體積也隨之增加并且在迭代500 次時(shí)命中最優(yōu)解。 說(shuō)明種群演化代數(shù)增加時(shí)，求得的解會(huì)更接近或者直接命中最優(yōu)解。 綜上所述種群規(guī)模 、交叉概率以及迭代次數(shù)的設(shè)置對(duì)于遺傳算法在求解 01背包問(wèn)題時(shí)對(duì)于命中最優(yōu)解的影響是 非常明 的，通過(guò)以上實(shí)驗(yàn)的探究我可以看到當(dāng)交叉 概率為 ，迭代次數(shù)為 500 時(shí)都命中了最優(yōu)解 3103，那么我可以利用這兩個(gè)參數(shù)對(duì)算例 2進(jìn)行測(cè)試。 算例 2 設(shè)物品價(jià)值為 Pi，物品重量為 Wi，物品的 Wi 重量是（ 1,10）的隨機(jī)數(shù)，背包最大容量為 C。 Pi 與 C 的數(shù)值由以下公式得出。 5iipw?? （ 21） 112 n iicw?? ? （ 22） 設(shè)置 交叉概率 Pc=，迭代次數(shù)為 500，變異概率為 當(dāng)物品總數(shù)分別為50、 100、 150 時(shí) ，對(duì)算例 2 運(yùn)行 20 次，觀察種群規(guī)模分別為 50、 100、 200 時(shí)的 結(jié)果 。 當(dāng)物品數(shù)量為 50 時(shí)，循環(huán) 20 次的結(jié)果如表 25和仿真圖分別如圖 24,圖 25,圖 26 所示。 表 25 不同種群規(guī)模求解算例的 2結(jié)果 種群規(guī)模 迭代次數(shù) 最大值 最小值 平均值 50 500 316 176 100 500 322 161 200 500 324 160 設(shè)計(jì)（論文）專(zhuān)用紙 25 0 2 4 6 8 10 12 14 16 18 20160180200220240260280300320X : 1 3Y : 3 1 6 20 次循環(huán)結(jié)果最大值最小值平均值 圖 24 種群規(guī)模為 50算例 2的仿真圖 0 2 4 6 8 10 12 14 16 18 20160180200220240260280300320340X : 1 6Y : 3 2 2 20 次循環(huán)結(jié)果最大值最小值平均值 圖 25 種群規(guī)模為 100算例 2的仿真圖 0 2 4 6 8 10 12 14 16 18 2016018020022024026028030032034020 次循環(huán)結(jié)果 X : 1 0Y : 3 2 4最大值最小值平均值 圖 26 種群 規(guī)模為 200算例 2的 仿真圖 設(shè)計(jì)（論文）專(zhuān)用紙 26 當(dāng)物品數(shù)為 100時(shí) 循環(huán) 20次算例 2的結(jié)果如表 26和仿真圖分別圖 2圖 2圖 29 所示。 表 26 算例 2循環(huán) 20的次結(jié)果 種群規(guī)模 迭代次數(shù) 最大優(yōu)值 最小值 平均值 50 500 616 396 100 500 618 378 200 500 629 377 0 2 4 6 8 10 12 14 16 18 20350