智能控制作業(yè)-遺傳算法求解背包問(wèn)題-文庫(kù)吧
2025-07-20 17:12 本頁(yè)面
【正文】 For i:=1 To M Do For j:=1 To N Do If iproblem[j].time=0 Then Begin t:=problem[j].point+f[iproblem[j].time]。 If tf[i] Then f[i]:=t。 End。 Writeln(f[M])。 End. 。 求自然數(shù)n本質(zhì)不同的質(zhì)數(shù)和的表達(dá)式的數(shù)目。 思路一：生成每個(gè)質(zhì)數(shù)的系數(shù)的排列，在一一測(cè)試，這是通法。 procedure try(dep:integer)。 var i,j:integer。 begin cal。 {此過(guò)程計(jì)算當(dāng)前系數(shù)的計(jì)算結(jié)果，now為結(jié)果} if nown then exit。 {剪枝} if dep=l+1 then begin {生成所有系數(shù)} cal。 if now=n then inc(tot)。 exit。 end。 for i:=0 to n div pr[dep] do begin xs[dep]:=i。 try(dep+1)。 xs[dep]:=0。 end。 end。 思路二：遞歸搜索效率較高 procedure try(dep,rest:integer)。 var i,j,x:integer。 begin if (rest=0) or (dep=l+1) then begin if rest=0 then inc(tot)。 exit。 end。 for i:=0 to rest div pr[dep] do try(dep+1,restpr[dep]*i)。 end。 {main: try(1,n)。 } 思路三：可使用動(dòng)態(tài)規(guī)劃求解 設(shè)V個(gè)物品，背包容量為n，求放法總數(shù)。 轉(zhuǎn)移方程： Procedure update。 var j,k:integer。 begin c:=a。 for j:=0 to n do if a[j]0 then for k:=1 to n div now do if j+now*k=n then inc(c[j+now*k],a[j])。 a:=c。 end。 {main} begin read(now)。 {讀入第一個(gè)物品的重量} i:=0。 {a[i]為背包容量為i時(shí)的放法總數(shù)} while i=n do begin a[i]:=1。 inc(i,now)。 end。 {定義第一個(gè)物品重的整數(shù)倍的重量a值為1，作為初值} for i:=2 to v do begin read(now)。 update。 {動(dòng)態(tài)更新} end。 writeln(a[n])。三．算法綜述 遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群開(kāi)始的，而一個(gè)種群則由經(jīng)過(guò)基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開(kāi)始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼，可以作為問(wèn)題近似最優(yōu)解。貪婪算法是從眼前最大的利益出發(fā)，尋找最優(yōu)解的方法，雖然很多情況下不能找到最優(yōu)解，但是找到較好的解的可能性還是比較大的。這似乎一種符合人的直覺(jué)的算法，時(shí)間復(fù)雜度比較低。四．遺傳算法求解背包問(wèn)題 1. 貪婪算法求解背包問(wèn)題貪婪算法屬于一步式啟發(fā)算法，即每采用一個(gè)貪婪準(zhǔn)則便做出一個(gè)不可撤回的決策。用貪婪算法求解背包問(wèn)題的特點(diǎn)是每一步迭代選一物品入包，直到無(wú)法再裝。該算法沒(méi)有在兩個(gè)可行解之間比較選擇，算法結(jié)束時(shí)得到一個(gè)可行解。常用的貪婪準(zhǔn)則是價(jià)值密度（價(jià)值重量比C/W）貪婪算法，這種選擇準(zhǔn)則為：從剩余物品中選擇可裝入包的C/W值最大的物品，這也是通常所使用的貪婪策略，因?yàn)樗且粋€(gè)直覺(jué)上的近似的解。2. 基于貪婪算法的混合遺傳算法求解背包問(wèn)題將貪婪算法與遺傳算法相結(jié)合構(gòu)成的混合遺傳算法，通過(guò)遺傳算法的擇優(yōu)，不斷重復(fù)執(zhí)行選擇、雜交和變異以及貪婪算法的修正這樣一個(gè)過(guò)程，所求解將不斷進(jìn)化越來(lái)越接近最優(yōu)解。（1）基因編碼 基因編碼將n個(gè)Xi的值順序排列，就可構(gòu)成背包問(wèn)題的遺傳編碼。即我們使用的是等長(zhǎng)度的二進(jìn)制編碼方法，編碼串中1表示將對(duì)應(yīng)的物品放入背包中，0表示不將其放入。例如“11100111000000000000……00000011”就代表一個(gè)解，它表示將第1，2，3，6，7，8，…n1，n號(hào)物品放入背包中，其他的物品則不放入。（2）編碼修復(fù) 上述基因編碼的方案雖然比較直觀，但對(duì)于任意一個(gè)編碼串，或者由交叉，變異所產(chǎn)生的任意一個(gè)個(gè)體，由于它們不一定滿(mǎn)足約束條
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1