智能控制作業(yè)-遺傳算法求解背包問題(編輯修改稿)
2025-08-31 17:12 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 件，就不一定表示可行解，也就是說這種編碼方案會(huì)產(chǎn)生很多無效染色體。對(duì)于這些不滿足約束條件的基因編碼串，我們可以利用貪婪算法的思想進(jìn)行修復(fù)。修復(fù)的基本思想為：在Xj=1的所有物品中，將價(jià)值重量比（C/W)最小的物品取出，直到滿足背包的容量約束為止。由此可產(chǎn)生一些新的基因編碼串，并且這些新編碼串總是相對(duì)來說質(zhì)量比較好的，特別是它們肯定滿足問題的約束條件。（3）適應(yīng)度函數(shù) 由于對(duì)每個(gè)個(gè)體使用貪婪算法修正已保證了不會(huì)產(chǎn)生無效染色體，所以在進(jìn)行個(gè)體適應(yīng)度評(píng)價(jià)時(shí)無須引入罰函數(shù)項(xiàng)，而是直接用目標(biāo)函數(shù)值作為適應(yīng)度函數(shù)值，即： （4）選擇： 采用輪盤賭的方式進(jìn)行選擇。在本算法中，將各基因的適應(yīng)值事先作處理：fi(i)=fit(i)min(fit)+1。以防止適廊度函數(shù)值出現(xiàn)小于零的情況，并且可以在一定程度上防止適應(yīng)值差別過大時(shí)丟失低適應(yīng)值基因的有用信息。（5）交叉： 采用單點(diǎn)交叉方式，隨機(jī)選取一點(diǎn)作為基因的交叉點(diǎn)，交叉概率pc =。（6）變異： 采用一個(gè)較小的值如pm=。算法步驟：初始化數(shù)據(jù)和各個(gè)參數(shù)用貪婪算法修正各個(gè)解輪盤選擇、交叉、變異等操作對(duì)得到的解再進(jìn)行貪婪算法修正是否滿足結(jié)束遺傳操作條件結(jié)束，輸出迭代的結(jié)果是否3. 不使用貪婪算法的遺傳算法求解背包問題。為了通過對(duì)比顯示出使用貪婪算法的遺傳算法的優(yōu)勢(shì)，使用純粹的遺傳算法解決背包問題。適應(yīng)度函數(shù)與使用貪婪算法不同，需要加入懲罰項(xiàng)。fit =v*value39。cf*v*value39。./(v*c39。).*((v*c39。m1)0).*(v*c39。m1)。cf表示懲罰力度其他過程與加入貪婪算法的基本一致。五．背包問題的遺傳算法應(yīng)用程序（matlab）、遺傳算法結(jié)合解決背包問題：源代碼：%遺傳算法解決背包問題 clc。clear。close all。%初始化物品價(jià)值value和質(zhì)量cc=[98 92 95 70 72 70 83 80 65 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 56 50 30 20 15 10 8 5 3 1 ]。value=[300 318 298 192 180 180 265 242 160 138 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 20 25 15 10 20 10 7 5 2 2]。g=value./c。 %價(jià)值重量比，用于貪婪算法m1=1000。 %總重量約束值v = 2*rand(50,50)1。v=hardlim(v)。 %v為50*50隨機(jī)產(chǎn)生的矩陣 值為0或1%貪婪算法修復(fù)解%v=greedy(v,c,g,m1)。[N,L] = size(v)。 ger = 500。 pc = 。 pm = 。disp(sprintf(39。代數(shù): %d39。,ger))。disp(sprintf(39。種群大小: %d39。,N))。disp(sprintf(39。交叉概率: %.3f39。,pc))。disp(sprintf(39。變異概率: %.3f39。,pm))。% 初始化與參數(shù)設(shè)定sol1=1。 it = 1。 updatef=10。 %soll為當(dāng)前算出的總價(jià)值，it為代數(shù)fit =v*value39。t0 = clock。 %記錄初始時(shí)間figure(1)。hold on。while it = ger % 選擇（輪盤賭方法） for i=1:N fi(i)=fit(i)min(fit)+1。 end for i=1:N sp(i)=fi(i)/sum(fi)。 end for i=2:N sp(i)=sp(i1)+sp(i)。 end for i=1:N p=rand(1)。 sindex=1。 while p sp(sindex) sindex=sindex+1。 %尋找要選擇個(gè)體的位置 end newv(i,:)=v(sindex,:)。 end for i=1:N v(i,:)=newv(i,:)。%用選擇出的個(gè)體構(gòu)成的種群替代舊的種群 end % 交叉 for i=1:N cindex(i)=i。 end for i=1:N %產(chǎn)生要配對(duì)的父代的序號(hào)；經(jīng)過N次順序調(diào)換，將原有順序打亂，使相鄰兩個(gè)個(gè)體作為交叉的父代 point=unidrnd(Ni+1)。 temp=cindex(i)。 cindex(i)=cindex(i+point1)。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1