基于遺傳算法求解背包問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 畢業(yè)設(shè)計（論文）基于遺傳算法求解背包問題院 別專業(yè)名稱班級學(xué)號學(xué)生姓名指導(dǎo)教師2012年6月15日基于遺傳算法求解背包問題摘 要背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題,本文首先介紹了基本遺傳算法的基本原理、特點及其基本實現(xiàn)技術(shù)，接著針對背包問題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應(yīng)用情況。并且結(jié)合背包問題實例，給出了具體的編碼方法，運行參數(shù)，群體大小，最大迭代次數(shù)，以及合適的遺傳算子

2、。最后，簡單說明了遺傳算法在求解背包問題中的應(yīng)用并對遺傳算法解決背包問題的前景提出了展望。關(guān)鍵詞：背包問題，遺傳算法，遺傳算子Genetic Algorithm for KP Author：Yang Dong Tutor：Kong ZhiAbstract KP (Knapsack Problem) is a combinatorial optimization of NP - complete problem. The primary knowledge, characteristics and the basic techniques of GA are introduced firstly

3、. The encoding model and genetic operators (including selection operation, crossover operation and mutation operation) solving KP are discussed secondly. Combined with examples of knapsack problem, we have given the specific encoding method, operating parameters, popsize, maxgeneration, and suitable

4、 genetic operator. At last, the application of genetic algorithm is simple presented, and the prospect for the future of genetic algorithm in solving KP has been given.Key Words: KP, genetic algorithm, genetic operators目 錄TOC t 標(biāo)題 1,2,標(biāo)題 2,3,章標(biāo)題,1 h 1緒論1.1 引言 現(xiàn)代科學(xué)理論研究與實踐中存在著大量與優(yōu)化、自適應(yīng)相關(guān)的問題，但除了一些簡單的情況

5、之外，人們對于大型復(fù)雜系統(tǒng)的優(yōu)化和自適應(yīng)問題仍然無能為力。然而，自然界中的生物卻在這方面表現(xiàn)出了其優(yōu)異的能力，它們能夠以優(yōu)勝劣汰、適者生存的自然進化規(guī)則生存和繁衍，并逐步產(chǎn)生出對其生存環(huán)境適應(yīng)性很高的優(yōu)良物種。遺傳算法正是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局優(yōu)化自適應(yīng)概率搜索算法。 遺傳算法是中用于解決的搜索，是的一種。進化算法最初是借鑒了中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括、以及等。遺傳算法通常實現(xiàn)方式為一種。對于一個最優(yōu)化問題，一定數(shù)量的（稱為個體）的抽象表示（稱為）的向更好的解進化。傳統(tǒng)上，解用表示（即0和1的串），但也可以用其他表示方法。進化從完全個體的種群開始，之后一

6、代一代發(fā)生。在每一代中，整個種群的被評價，從當(dāng)前種群中隨機地選擇多個個體（基于它們的適應(yīng)度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。 背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題,對這個問題的求解前人己經(jīng)研究出了不少的經(jīng)典的方法,例如解析法，窮舉法等，但是這些傳統(tǒng)的優(yōu)化方法存在一些缺點，如算法復(fù)雜度太高。與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有以下優(yōu)點:在每一時刻，GA同時在多個子空間內(nèi)進行搜索，對初始值不作要求;基本不用搜索空間的知識或其他輔助信息，而僅用適應(yīng)度來評估個體優(yōu)劣;具有很強的魯棒性。因此遺傳算法在背包問題求解方面的應(yīng)用研

7、究，對于構(gòu)造合適的遺傳算法框架、建立有效的遺傳作以及有效地解決背包問題等有著多方面的重要意義5。1.2 背包問題概述1.2.1 背包問題的描述它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將它們放到背包中來加密消息。背包中的物品總重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而引人注目。背包問題(Knapsack problem)是一種組合優(yōu)化的。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總

8、重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？它是在1978年由Merkel和Hellman提出的。 1.2.1.1 01背包問題概述題目有N件物品和一個容量為V的背包。第i件物品的重量是ci，價值是wi。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大?；舅悸愤@是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即fiv表示前i件物品恰放

9、入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：fiv=maxfi-1v,fi-1v-ci+wi?？梢詨嚎s空間，fv=maxfv,fv-ci+wi這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為fi-1v；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-ci的背包中”，此時能獲得的最大價值就是f

10、i-1v-ci再加上通過放入第i件物品獲得的價值wi。注意fv有意義當(dāng)且僅當(dāng)存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是fN V，而是fN0.V的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項fv-1，這樣就可以保證fN V就是最后的答案。至于為什么這樣就可以，由你自己來體會了。優(yōu)化空間復(fù)雜度以上方法的時間和空間復(fù)雜度均為O(N*V），其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(N）。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1.N，每次算出來二維數(shù)組fi0.V的所有值。那么，如果只用一個數(shù)組f

11、 0.V，能不能保證第i次循環(huán)結(jié)束后fv中表示的就是我們定義的狀態(tài)fiv呢？fiv是由fi-1v和f i-1v-ci兩個子問題遞推而來，能否保證在推fv時（也即在第i次主循環(huán)中推fv時）能夠得到fv和fv -ci的值呢？事實上，這要求在每次主循環(huán)中我們以v=V.0的順序推fv，這樣才能保證推fv時fv-ci保存的是狀態(tài)fi-1v-ci的值。偽代碼如下：for i=1.Nfor v=V.0fv=maxfv,fv-ci+wi;其中的fv=maxfv,fv-ci一句恰就相當(dāng)于我們的轉(zhuǎn)移方程fiv=maxfi-1v,fi-1v-ci，因為現(xiàn)在的fv-ci就相當(dāng)于原來的fi-1v-ci。如果將v的循環(huán)順

12、序從上面的逆序改成順序的話，那么則成了fiv由fiv-ci推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。 總結(jié)0/1背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成0/1背包問題求解。1.2.1.2 完全背包問題題目有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c，價值是w。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。基本思路這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物

13、品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件等很多種。如果仍然按照解01背包時的思路，令fi,v表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：fi,v=maxfi,v-vi+wi,fi-1,v。這跟01背包問題一樣有O(N*V）個狀態(tài)需要求解，但求解每個狀態(tài)的時間則不是常數(shù)了，求解狀態(tài)fv的時間是O(v/c），總的復(fù)雜度是超過O(VN）的。將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復(fù)雜度。簡單有效的

14、優(yōu)化完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c=wj，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復(fù)雜度，因為有可能特別設(shè)計的數(shù)據(jù)可以一件物品也去不掉。總結(jié)完全背包問題也是一個相當(dāng)基礎(chǔ)的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN）的算法“的小節(jié)中給出。希望你能夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實

15、上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。 1.2.1.3 多重背包問題題目有N種物品和一個容量為V的背包。第i種物品最多有n件可用，每件體積是c，價值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大?；舅惴ㄟ@題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有n+1種策略：取0件，取1件取 n件。令fv表示前i種物品恰放入一個容量為v的背包的最大權(quán)值，則：fv=maxfv-k*c+ k*w|0=k0的最大整數(shù)。例如，如果n為13，就將這種物品分成系數(shù)分別

16、為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為n，表明不可能取多于n件的第i種物品。另外這種方法也能保證對于0.n間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0.2k-1和2k.n兩段來分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(log n）種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*log n）的01背包問題，是很大的改進。O(VN）的算法多重背包問題同樣有O(VN）的算法。這個算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊列的方法使每個狀態(tài)的值可以以均攤O的時間求解。小結(jié)這里我們看到了將一個算法的復(fù)雜度由O(V*n）改進到O(V*log n）的

17、過程，還知道了存在應(yīng)用超出NOIP范圍的知識的O(VN）算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實現(xiàn)。1.2.1.4 混合三種背包問題問題如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個上限（多重背包）。應(yīng)該怎么求解呢？01背包與完全背包的混合考慮到在P01和P02中最后給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個物品應(yīng)用轉(zhuǎn)移方程時，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復(fù)雜度是O(VN）

18、。偽代碼如下：for i=1.Nif 第i件物品是01背包for v=V.0fv=maxfv,fv-c+w;else if 第i件物品是完全背包for v=0.Vfv=maxfv,fv-c+w;再加上多重背包 如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN）的解法：遇到多重背包類型的物品用單調(diào)隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個這類物品分成O(log n）個01背包的物品的方法也已經(jīng)很優(yōu)了。小結(jié)有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難

19、題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎(chǔ)扎實，領(lǐng)會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。 1.2.1.5 二維費用的背包問題問題二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設(shè)這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a和b。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w。算法費用加了一維，只需狀態(tài)也加一維即可。設(shè)fv表示前i件物品付出兩種代價分別為v和u

20、時可獲得的最大價值。狀態(tài)轉(zhuǎn)移方程就是：fiivu=maxfi-1vu,fi-1v-aiu-bi+wi。如前述方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時變量v和u采用逆序的循環(huán)，當(dāng)物品有如完全背包問題時采用順序的循環(huán)。當(dāng)物品有如多重背包問題時拆分物品。物品總個數(shù)的限制有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當(dāng)于每件物品多了一種“件數(shù)”的費用，每個物品的件數(shù)費用均為1，可以付出的最大件數(shù)費用為M。換句話說，設(shè)fvm表示付出費用v、最多選m件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多重）用不同的方法循環(huán)更新，最后在f0.V0.M范圍內(nèi)尋

21、找答案。另外，如果要求“恰取M件物品”，則在f0.VM范圍內(nèi)尋找答案。小結(jié)事實上，當(dāng)發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法。1.2.1.6 分組的背包問題問題有N件物品和一個容量為V的背包。第i件物品的費用是c，價值是w。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。算法這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設(shè)fkv表示前k組物品花費費用v能取得的最大權(quán)值，則有fkv=maxfk-1v,fk-1v-c+w|物

22、品i屬于第k組。使用一維數(shù)組的偽代碼如下：for 所有的組k for v=V.0for 所有的i屬于組k fv=maxfv,fv-c+w另外，顯然可以對每組中的物品應(yīng)用P02中“一個簡單有效的優(yōu)化”。小結(jié)分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題（例如P07），由分組的背包問題進一步可定義“”的概念，十分有利于解題。1.2.1.7 有依賴的背包問題簡化的問題這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設(shè)沒有某個物品既依賴于別的物品，又被別的物品所依賴

23、；另外，沒有某件物品同時依賴多件物品。算法這個問題由NOIP2006的預(yù)算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇主件后再選擇兩個附件無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略。（事實上，設(shè)有n個附件，則策略有2n+1個，為指數(shù)級。）考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實

24、際上對應(yīng)于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應(yīng)于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。再考慮P06中的一句話：可以對每組中的物品應(yīng)用P02中“一個簡單有效的優(yōu)化”。這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結(jié)果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0.V-c所有這些值時相應(yīng)的最大價值f0.V-c。那么這個主件及它的附件集合相當(dāng)于V-c+1個物品的物品組，其中費用為c+k的物品的價值為

25、fk+w。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為 V-c+1個物品的物品組，就可以直接應(yīng)用P06的算法解決問題了。更一般的問題更一般的問題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。解決這個問題仍然可以用將每個主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品組，然后用分組的背包問題解出主件及其

26、附件集合所對應(yīng)的附件組中各個費用的附件所對應(yīng)的價值。事實上，這是一種樹形DP，其特點是每個父節(jié)點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了“泛化物品”的思想?？赐關(guān)08后，你會發(fā)現(xiàn)這個“依賴關(guān)系樹”每一個子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應(yīng)的泛化物品相當(dāng)于求其所有兒子的對應(yīng)的泛化物品之和。小結(jié)用物品組的思想考慮那題中極其特殊的依賴關(guān)系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發(fā)現(xiàn)一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質(zhì)。1.2.1.8 泛化物品定義考慮這樣一種物品，它并沒有固定的費用和價值，而是它

27、的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。更嚴(yán)格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0.V中的整數(shù)的函數(shù)h，當(dāng)分配給它的費用為v時，能得到的價值就是h(v）。這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數(shù)組h0.V，給它費用v，可得到價值hV。一個費用為c價值為w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函數(shù)值都為0的一個函數(shù)。如果它是完全背包中的物品，那么它可以看成這樣一個函數(shù)，僅當(dāng)v被c整除時有h(v)=v/c*w，其它函數(shù)值均為0。如果它是多重背包中重復(fù)次數(shù)最多為n的物品，那么它對應(yīng)的泛化物品的函數(shù)有

28、h(v)=v/c*w僅當(dāng)v被c整除且v/c=n，其它情況函數(shù)值均為0。一個物品組可以看作一個泛化物品h。對于一個0.V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v）為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價于一個物品組，自然也可看作一個泛化物品。泛化物品的和如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎么求呢？事實上，對于一個給定的費用v，只需枚舉將這個費用如何分配給兩個泛化物品就可以了。同樣的，對于0.V的每一個整數(shù)v，可以求得費用v分配到h和l中的最大價值f(v）。也即f(v)=maxh(k) +l(v-k)|0

29、=k=v。可以看到，f也是一個由泛化物品h和l決定的定義域為0.V的函數(shù)，也就是說，f是一個由泛化物品h和 l決定的泛化物品。由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=maxh(k)+l(v-k)|0=k=v，則稱f是h與l的和，即f=h+l。這個運算的時間復(fù)雜度是O(V2）。泛化物品的定義表明：在一個背包問題中，若將兩個泛化物品代以它們的和，不影響問題的答案。事實上，對于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設(shè)此和為s，則答案就是s0.V中的最大值。1.2.1.9 背包問題的泛化物品一個背包問題中，可能會給出很多條

30、件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關(guān)系等。但肯定能將問題對應(yīng)于某個泛化物品。也就是說，給定了所有條件以后，就可以對每個非負整數(shù)v求得：若背包容量為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數(shù)集上的一件泛化物品。這個泛化物品或者說問題所對應(yīng)的一個定義域為非負整數(shù)的函數(shù)包含了關(guān)于問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0.V）的值之后，就可以根據(jù)這個函數(shù)的取值得到背包問題的最終答案。小結(jié)綜上所述，一般而言，求解背包問題，即求解這個問題所對應(yīng)的一個函數(shù)，即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物

31、品的和然后求之。1.2.1.10 關(guān)于本文本文討論的是0-1背包問題，問題描述如下：指定給n件物品和一個背包，物品i 的重量是wi，其價值為vi，背包的容量為C，求從這n 件物品中選取一部分物品且對每件物品,或者選取,或者不選,每種物品只能裝入背包一次,且要求滿足放入背包中的物品總重量不超過背包容量。求出裝入背包中物品價值總和最大的方案。注意：在本題中，所有的重量值均為整數(shù)。數(shù)學(xué)模型限制條件為：所求表達式為：其中，表示物品放入背包，表示物品未放入背包。1.2.2 研究背包問題的意義背包問題是組合優(yōu)化領(lǐng)域中的一個典型問題，涉及求多個變量的函數(shù)的最大值。雖然它陳述起來很簡單，但求解卻很困難，并且已

32、經(jīng)被證明是NP完全問題。至今尚未找到有效的求解方法，在理論上枚舉法可以解這一問題，但是當(dāng)n較大時，解題的時間消耗會使枚舉法顯得沒有任何實際價值。因此尋求一種求解時間短，能滿足實際問題精度要求的解，成為解決該問題的主要途徑8。 背包問題的求解，一直以來倍受人們的關(guān)注。對于這樣一個典型的、易于描述卻難以處理的NP難題，有效地解決它在可計算理論上有著重要的理論價值。并且，背包問題是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式。背包問題也可描述為決定性問題，相似問題經(jīng)常出現(xiàn)在商業(yè)、投資組合優(yōu)化、組合數(shù)學(xué)，計算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中，因此具有廣泛的實際應(yīng)用領(lǐng)域。1.3 遺傳算法1.3.

33、1 遺傳算法概述遺傳算法（GA）是一類借鑒生物界自然選擇和自然遺傳機制的隨機化的搜索算法，也是一種抽象于生物進化過程的基于自然選擇和生物遺傳機制的優(yōu)化技術(shù)。它是在1975年首次由美國密西根大學(xué)的D. J. Holland教授和他的同事們借鑒生物界自然選擇和進化機制基礎(chǔ)之上提出的。經(jīng)過近30年的研究、應(yīng)用，遺傳算法已被廣泛地應(yīng)用于函數(shù)優(yōu)化、機器人系統(tǒng)、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)過程、模式識別、圖象處理、工業(yè)優(yōu)化控制等領(lǐng)域。其主要特點是群體搜索策略、群體中個體之間的信息交換和搜索不依賴于梯度信息19。 遺傳算法是將問題的每一個可能性解看作是群體中的一個個體(染色體)，并將每一個染色體編碼成串的形式，再根據(jù)預(yù)定的

34、目標(biāo)函數(shù)對每個個體進行評價，給出一個適應(yīng)度值。算法將根據(jù)適應(yīng)度值對它進行尋優(yōu)的過程，遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個遺傳算子來具體實現(xiàn)的，它的搜索能力由選擇算子和雜交算子決定，變異算子則保證了算法能夠搜索到問題空間的每一個點，從而使其具有搜索全局最優(yōu)的能力。遺傳算法的高效性和強壯性可由Holland提出的模式定理(Schema Theorem)和隱式并行性得以解釋。近年來，遺傳算法從理論到實際都已經(jīng)取得了許多重要成果。由于它具有良好的全局搜索能力，是目前解決各種優(yōu)化問題的最有效的方法，已經(jīng)成為研究熱點。1.3.2 遺傳算法的特點 從整體上來講，遺傳算法是進化算法中產(chǎn)生最早、影響最大

35、、應(yīng)用也比較廣泛的一個研究方向和領(lǐng)域，它不僅包含了進化算法的基本形式和全部優(yōu)點，同時還具備若干獨特的性能。161)在求解問題時，遺傳算法首先要選擇編碼方式，它直接處理的對象是參數(shù)的編碼集而不是問題參數(shù)本身，搜索過程既不受優(yōu)化函數(shù)連續(xù)性的約束，也沒有優(yōu)化函數(shù)倒數(shù)必須存在的要求。通過優(yōu)良染色體基因的重組，遺傳算法可以有效地處理傳統(tǒng)上非常復(fù)雜的優(yōu)化函數(shù)求解過程；2)若遺傳算法在每一代對群體規(guī)模為n的個體進行操作，實際上處理了大約個模式,具有很高的并行性，因而具有顯著的搜索效率；3)在所求解問題為非連續(xù)、多峰以及有噪聲的情況下，能夠以很大的概率收斂到最優(yōu)解或滿意解，因而具有較好的全局最優(yōu)解求解能力；4

36、)對函數(shù)的性態(tài)無要求，針對某一問題的遺傳算法經(jīng)簡單修改即可適應(yīng)于其他問題，或者加入特定問題的領(lǐng)域知識，或者與已有算法相結(jié)合，能夠較好地解決一類復(fù)雜問題，因而具有較好的普適性和易擴充性；5）遺傳算法的基本思想簡單，運行方式和實現(xiàn)步驟規(guī)范，便于具體使用；遺傳算法的這些特點使得它一經(jīng)提出即在理論上引起了高度重視，能夠應(yīng)用于一些到目前為止人們知之甚少的困難問題領(lǐng)域，產(chǎn)生大量的成功案例。1.3.3 遺傳算法的應(yīng)用領(lǐng)域遺傳算法的主要應(yīng)用領(lǐng)域包括以下幾個方面：函數(shù)優(yōu)化問題。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性能評價的常用例子。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)來評價遺傳算法的性能。

37、而且對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。組合優(yōu)化問題。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復(fù)雜問題，人們己意識到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于求解組合優(yōu)化問題非常有效。遺傳算法已經(jīng)在求解旅行商問題、圖形劃分問題等方面得到成功的應(yīng)用。 生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以求解，也會因簡化太多而使求解結(jié)果與實際相差甚遠

38、。由于可以采用字符編碼，而且不必使用恰好的目標(biāo)函數(shù)估值，遺傳算法也成為解決復(fù)雜調(diào)度問題的有效工具。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配、虛擬企業(yè)中的伙伴選擇方面遺傳算法都得到了有效的應(yīng)用。自動控制。在自動控制領(lǐng)域有很多與優(yōu)化相關(guān)的問題需要求解，而且這些優(yōu)化問題通常要么是通過積分表達的，要么是寫不出明確而嚴(yán)格的解析表達式。遺傳算法在求解這類自動控制問題方面已顯示出其獨特的優(yōu)點。例如，用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、用遺傳算法優(yōu)化設(shè)計透平機械、設(shè)計模糊控制器等，都取得了較好的效果。機器學(xué)習(xí)。學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所應(yīng)具備的特征之一?；谶z傳算法的機器學(xué)習(xí)在很多方面都得到成

39、功應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則、確定模糊集的隸屬函數(shù)、改進模糊系統(tǒng)的性能;被用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)及網(wǎng)絡(luò)拓撲優(yōu)化。此外，遺傳算法還被應(yīng)用到反問題求解、機器人學(xué)習(xí)、生物計算、圖像處理、人工智能以及遺傳編程等領(lǐng)域。2遺傳算法的基本原理 在遺傳算法里，優(yōu)化問題的解被稱為個體，它表示為一個變量序列，叫做或者。染色體一般被表達為簡單的字符串或數(shù)字串，不過也有其他的依賴于特殊問題的表示方法適用，這一過程稱為編碼。首先，算法生成一定數(shù)量的個體，有時候操作者也可以對這個隨機產(chǎn)生過程進行干預(yù)，以提高初始種群的質(zhì)量。在每一代中，每一個個體都被評價，并通過計算得到一個數(shù)值。種群中的個體被按照適應(yīng)

40、度，適應(yīng)度高的在前面。這里的“高”是相對于初始的種群的低適應(yīng)度來說的。 下一步是產(chǎn)生下一代個體并組成種群。這個過程是通過選擇和完成的，其中繁殖包括交配(crossover，在算法研究領(lǐng)域中我們稱之為交叉操作）和突變(mutation)。選擇則是根據(jù)新個體的適應(yīng)度進行的，但同時并不意味著完全的以適應(yīng)度高低作為導(dǎo)向，因為單純選擇適應(yīng)度高的個體將可能導(dǎo)致算法快速收斂到局部最優(yōu)解而非全局最優(yōu)解，我們稱之為早熟。作為折中，遺傳算法依據(jù)原則：適應(yīng)度越高，被選擇的機會越高，而適應(yīng)度低的，被選擇的機會就低。初始的數(shù)據(jù)可以通過這樣的選擇過程組成一個相對優(yōu)化的群體。之后，被選擇的個體進入交配過程。一般的遺傳算法都

41、有一個交配概率（又稱為交叉概率），范圍一般是0.61，這個交配概率反映兩個被選中的個體進行交配的。例如，交配概率為0.8，則80%的“夫妻”會生育后代。每兩個個體通過交配產(chǎn)生兩個新個體，代替原來的“老”個體，而不交配的個體則保持不變。交配父母的染色體相互交換，從而產(chǎn)生兩個新的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。不過這里的半段并不是真正的一半，這個位置叫做交配點，也是隨機產(chǎn)生的，可以是染色體的任意位置。再下一步是，通過突變產(chǎn)生新的“子”個體。一般遺傳算法都有一個固定的（又稱為變異概率），通常是0.1或者更小，這代表變異發(fā)生的概率。根據(jù)這個概率，新個體的染

42、色體隨機的突變，通常就是改變?nèi)旧w的一個字節(jié)（0變到1，或者1變到0）。 經(jīng)過這一系列的過程（選擇、交配和突變），產(chǎn)生的新一代個體不同于初始的一代，并一代一代向增加整體適應(yīng)度的方向發(fā)展，因為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個體逐漸被淘汰掉。這樣的過程不斷的重復(fù)：每個個體被評價，計算出適應(yīng)度，兩個個體交配，然后突變，產(chǎn)生第三代。周而復(fù)始，直到終止條件滿足為止。一般終止條件有以下幾種：進化次數(shù)限制；計算耗費的資源限制（例如計算時間、計算占用的內(nèi)存等）；一個個體已經(jīng)滿足最優(yōu)值的條件，即最優(yōu)值已經(jīng)找到；適應(yīng)度已經(jīng)達到飽和，繼續(xù)進化不會產(chǎn)生適應(yīng)度更好的個體；人為干預(yù)；以及以上兩種或更

43、多種的組合。2.1 基本流程遺傳算法需要涉及五大要素:編碼、群體初始化、適應(yīng)性函數(shù)的設(shè)定、遺傳操作的設(shè)計和控制參數(shù)的設(shè)定。具體步驟如下：(l)編碼，把問題的解轉(zhuǎn)化成位串表示形式;(2)定義適應(yīng)性函數(shù);(3)確定遺傳算法的各算子及參數(shù)，包括選擇、交叉、變異方法，交叉率、變異率、群體容量、最大遺傳代數(shù)等;(4)隨機初始化群體;(5)計算群體中每一個染色體的適應(yīng)值;(6)按照遺傳操作形成下一代群體;從當(dāng)前群體中由事先設(shè)定好的選擇方法選出兩個染色體;根據(jù)給定的交叉率，對選出的兩個染色體進行交叉操作;根據(jù)給定的變異率，對每個染色體進行變異操作;重復(fù)、步，直到新的一代群體被創(chuàng)建出來;判斷新產(chǎn)生的群體是否能

44、滿足結(jié)束指標(biāo)，如果滿足，則算法結(jié)束，如果不滿足，則返回步驟(6)。2.2 編碼按照遺傳算法的工作流程，當(dāng)用遺傳算法求解問題時，必須在目標(biāo)問題實際表示與遺傳算法的染色體位串結(jié)構(gòu)之間建立關(guān)系，即確定編碼和解碼運算。編碼就是將問題的解用一種碼來表示，從而將問題的狀態(tài)空間與GA的編碼空間相對應(yīng)，編碼的選擇是影響算法性能與效率的重要因素。常用的編碼方法有如下幾種：二進制編碼：二進制編碼將問題空間的參數(shù)表示為基于字符集0,1構(gòu)成的染色體位串，是最常用的一種編碼方式。大字符集編碼:除基于字符集0,1的二進制編碼之外，可以結(jié)合實際問題的特征采用D進制數(shù)或字符集來表示長度為L的位串。序列編碼：用排列法進行編碼顯

45、得更為自然、合理。實數(shù)編碼：實數(shù)編碼具精度高、大空間搜索的優(yōu)點。樹編碼：樹編碼是一種非固定常用編碼模式，其表示空間是開放的。在搜索過程中樹可以自由生長，但是不便于形成更具有結(jié)構(gòu)化和層次性的問題解，實際應(yīng)用中往往可以加以限制。自適應(yīng)編碼：實現(xiàn)選擇合適的固定編碼方式對潛在的遺傳算法用戶來說是一個難題。事實上，提出合適的編碼同解決問題本身一樣困難。因此，許多用戶認為既然要用遺傳算法解決問題，為什么不讓它同時調(diào)整編碼呢?一些專家就采用了自適應(yīng)編碼11。2.3 適應(yīng)度函數(shù)適應(yīng)度評價是通過適應(yīng)度函數(shù)對個體質(zhì)量的一種測量，是進化過程中自然的唯一依據(jù)。因此適應(yīng)度函數(shù)的選擇至關(guān)重要，直接影響到遺傳算法的收斂速度

46、以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。對目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換。適應(yīng)度函數(shù)的設(shè)計主要滿足以下條件：單值、連續(xù)、非負、最大化:這個條件是容易理解和實現(xiàn)的。合理、一致性：要求適應(yīng)度值反映對應(yīng)解的優(yōu)劣程度，這個條件的達成比較難以衡量。計算量小：適應(yīng)度函數(shù)設(shè)計應(yīng)盡可能簡單，這樣可以減小計算時間和空間上的復(fù)雜性，降低成本。通用性強：適應(yīng)度函數(shù)對具體問題應(yīng)盡可能具有通用性，最好無需使用者改變適應(yīng)度函數(shù)中的參數(shù)。適應(yīng)度函數(shù)的尺度變換有線性變換法、幕函數(shù)變換法、指數(shù)變換法10。2.4 遺傳算子標(biāo)準(zhǔn)的遺傳算子一般都包括選擇、交叉和變異三種。它們構(gòu)成了遺傳算法的核

47、心，使得算法具有強大的搜索能力。2.4.1 選擇算子選擇操作就是用來確定如何從父代種群中按照某種方法選取哪些個體遺傳到下一代種群的遺傳運算。它是根據(jù)個體適應(yīng)度函數(shù)值的大小正比于其被放入候選的概率的過程。在備選集中按照一定的選擇概率進行操作，這個概率取決于種群中個體的適應(yīng)度及其分布。其主要作用是避免了基因缺失，提高全局收斂性和計算效率。選擇算子可看作是種群空間到父體空間的隨機映射，它按照某種準(zhǔn)則或概率分布從當(dāng)前種群中以高的概率選取那些好的個體組成不同的父體以供生成新的個體。目前常用的選擇策略有賭盤賭選擇算子、排序選擇算子、最優(yōu)保存選擇算子和錦標(biāo)賽選擇算子等8。在遺傳算法中，目前常用的選擇機制有以

48、下幾種：適應(yīng)度比例方法適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或蒙特卡羅選擇。在該方法中，各個個體的選擇概率和其適應(yīng)度值成比例。設(shè)群體大小為n，其中個體i的適應(yīng)度值為fi，則i被選擇的概率psi為：psi=fi / fi （4-1） 顯然，概率psi反映了個體i的適應(yīng)度在整個群體的個體適應(yīng)度總和中所占的比例。個體適應(yīng)度越大，其被選擇的概率就越高，反之則被選擇的概率越低。最佳個體保存方法最佳個體保留進化策略的基本思想是當(dāng)前群體中適應(yīng)度最高的個體不參與交叉運算和變異運算，而是用來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個體。具體操作過程是：1)找出

49、當(dāng)前群體中適應(yīng)度最高的個體和適應(yīng)度最低的個體。2)若當(dāng)前群體中最佳個體的適應(yīng)度比總的迄今為止的最好個體的適應(yīng)度還要高，則以當(dāng)前群體中的最佳個體作為新的迄今為止的最好個體。3)用迄今為止的最好個體替換掉當(dāng)前群體中的最差個體。期望值方法在賭輪選擇機制中，當(dāng)個體數(shù)不太多時，依據(jù)產(chǎn)生的隨機數(shù)有可能會出現(xiàn)不正確地反映個體適應(yīng)度的選擇，即存在統(tǒng)計誤差。也就是說，適應(yīng)度高的個體也有可能被淘汰(當(dāng)然，適應(yīng)度低的個體也有可能被選擇)，為克服這種誤差，期望值方法用了如下思想。1)計算群體中每個個體在下一代生存的期望數(shù)目：M=fi /=fi / fi/n （4-2）2)若某個體被選中并要參與配對和交叉，則它在下一代

50、中的生存的期望值數(shù)目減去0.5；若不參與配對和交叉，則該個體的生存期望數(shù)目減去1。3)在2)的兩種情況下，若一個個體的期望值小于0時，則該個體不參與選擇。排序選擇機制排序選擇方法的主要著眼點是個體適應(yīng)度之間的大小關(guān)系，對個體適應(yīng)度是否取正值或負值以及個體適應(yīng)度之間的數(shù)值差異程度并無特別要求。排序選擇機制的主要思想是：對群體中的所有個體按其適應(yīng)度大小進行排序，基于這個排序來分配各個體被選中的概率。其具體操作過程是：1)對群體中的所有個體按其適應(yīng)度大小進行降序排序。2)根據(jù)具體求解問題，設(shè)計一個概率分配表，將各個概率值按上述排列次序分配給各個個體。3)以各個個體所分配到的概率值作為其能夠被遺傳到下

51、一代的概率，基于這些概率值用比例選擇的方法來產(chǎn)生下一代群體。是指在計算每個個體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個體排序，然后把事先設(shè)計好的概率表按序分配給個體，作為各自的選擇概率。2.4.2 交叉算子交叉操作是遺傳算法中最主要的遺傳操作。它是模仿自然界有性繁殖的基因重組過程，對兩個父代個體進行基因操作，其作用在于把原有優(yōu)良基因遺傳到下一代種群中，并生成包含更復(fù)雜基因結(jié)構(gòu)的新個體。交叉算子可看作是父體空間到個體空間的隨機映射，它通常的作用方式是：隨機地確定一個或多個分量位置為交叉點，由此將一對父體的兩個個體分為有限個片斷再以概率（稱為交叉概率）交換相應(yīng)片斷得到新的個體。2.4.3 變異算子

52、在生物種群中總是存在著變異，變異指的是子代和父代之間具有某些不相似的現(xiàn)象，即因為存在著變異現(xiàn)象，所以子代和父代之間中總是不完全相同的。變異是生物進化過程中不可缺少的，它為生物的進化和發(fā)展創(chuàng)造了條件。在遺傳算法中，變異是指父代染色體中的某些基因片，以相對較小的概率發(fā)生隨機改變的操作過程。所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。在遺傳算法中使用變異算子主要有以下兩個目的：改善遺傳算法的局部搜索能力。遺傳算法使用交叉算子已經(jīng)從全局的角度出發(fā)找到了一些較好的個體編碼結(jié)構(gòu)，它們已接近或有助于接近問題的最優(yōu)解。但僅使用交叉算子無法對

53、搜索空間的細節(jié)進行局部搜索。這時若再使用變異算子來調(diào)整個體編碼串中的部分基因值，就可以從局部的角度出發(fā)使個體更加逼近最優(yōu)解，從而提高了遺傳算法的局部搜索能力。維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。變異算子用新的基因值替換原有基因值，從而可以改變個體編碼串的結(jié)構(gòu)，維持群體的多樣性，這樣就有利于防止出現(xiàn)早熟現(xiàn)象。2.5 參數(shù)控制在遺傳算法的運行過程中，存在著對其性能產(chǎn)生重大影響的一組參數(shù)。這組參數(shù)在初始階段或種群進化過程中需要合理地選擇和控制。主要包括種群規(guī)模n、交叉概率pc以及變異概率pm。2.5.1 群體規(guī)模大種群含有較多模式，為遺傳算法提供了足夠的模式采樣容量，可以改進GA搜索的質(zhì)量，防止早熟

54、前收斂。但大種群增加了個體適應(yīng)性評價的計算量，從而使收斂速度降低。2.5.2 交叉概率 交叉概率pc控制著交叉算子的應(yīng)用頻率，在每一代新的種群中，需要對個體的染色體結(jié)構(gòu)進行交叉操作。交叉概率越高，種群中新結(jié)構(gòu)的引入越快，已獲得的優(yōu)良基因結(jié)構(gòu)的丟失速度也相應(yīng)升高。而交叉概率太低則可能導(dǎo)致搜索阻滯。一般pc=0.601.00。2.5.3 變異概率變異操作是保持種群多樣性的有效手段，交叉結(jié)束后，交配池中的全部個體位串上的每位等位基因按概率隨機改變，因此每代中大約發(fā)生n次變異。變異概率太小，可能使某些基因位過早丟失的信息無法恢復(fù)；而變異概率過高，則搜索將變成隨機搜索。一般取pm=0.050.2。2.6

55、 算法結(jié)束條件控制終止代數(shù)是表示遺傳算法運行結(jié)束條件的一個參數(shù)，它表示遺傳算法運行到指定的進化代數(shù)之后就停止運行，并將當(dāng)前種群中的最優(yōu)個體作為所求問題的最優(yōu)解輸出。由于遺傳算法不同于傳統(tǒng)的優(yōu)化算法，它沒有利用目標(biāo)函數(shù)的梯度等信息，所以在遺傳進化過程中，很難有明確的搜索終止準(zhǔn)則。常用的辦法是預(yù)先給定算法的終止進化代數(shù)。一般來說，預(yù)先給定算法的終止進化代數(shù)只能找到問題在給定時限內(nèi)所能尋求的相對滿意解，但不一定是問題的最優(yōu)解或較高精度的近似解。為了獲得較高精度的近似解，通?？梢罁?jù)種群適應(yīng)度的穩(wěn)定來適時調(diào)整終止進化代數(shù)的設(shè)置，或者在連續(xù)進化數(shù)代以后，如果解的適應(yīng)度沒有明顯的改進，則終止進化過程。終止進

56、化代數(shù)一般的取值范圍是100-1000。3求解實現(xiàn)背包問題的遺傳算法3.1 0_1背包問題中染色體的表示用向量X來表示染色體，X = x1，x2，xn。，xi0,1，xi=1表示物品i裝入了背包，xi =0表示物品i未裝入背包。每個染色體對應(yīng)其當(dāng)前裝入背包的物品的總價值和總重量。背包中物品的中價值代表了該物品的適應(yīng)度。程序中定義了這樣的一個結(jié)構(gòu)來表示染色體：typedef structint Weight;/染色體代表的物品的總重量int Fitness;/染色體代表的物品的價值（適應(yīng)度）int GeneNUMG; /用元素取值于定義域0,1的數(shù)組表示染色體。GENE;3.2 算法求解01背包

57、問題時用到的參數(shù)POPSIZE：種群大小，即已知的可行解的個數(shù)。NUMG：染色體中基因的個數(shù)，即物品的總數(shù)。CAPACITY：背包的容量。MAXB：二進制表示的染色體換算之后的最大十進制整數(shù)。用于隨機產(chǎn)生一個整數(shù)，進而轉(zhuǎn)換作染色體。SIM：染色體之間的相似度閾值。當(dāng)染色體之間的相似度達到閾值時，算法即停止運行。PC=1.0 ：交叉概率為100。PM=0.2 ：變異概率為20，變異可以保證種群的多樣性，從而防止算法收斂于某個局部解。3.3 選擇操作選擇操作采用了賭輪選擇（Roulette-wheel selection）的方法。函數(shù)selectIndex()中包含了選擇染色體的具體過程。其流程圖

58、如圖1所示。圖1 賭輪選擇流程圖程序中用一個Begin來代表當(dāng)前賭輪上的指針的位置，End則用來使賭輪循環(huán)轉(zhuǎn)動。用summaryBE表示當(dāng)前賭輪上的指針轉(zhuǎn)過的染色體的總價值。用summaryF表示當(dāng)前全部染色體的價值總和。用randProb作為染色體選擇的閾值。randProb為介于0,1之間的隨機數(shù)。選擇使summaryBE/summaryF 大于閾值randProb的染色體作為要選擇的染色體。3.4 交叉操作單點交叉操作的簡單方式是將被選擇出的兩個個體S1和S2作為父母個體，從0，1中產(chǎn)生一個隨機數(shù)p，如果ppc，將兩者的部分基因碼值進行交換。假設(shè)如下兩個父代：父代1: 1 14 2 13

59、 8 6 3 2 5 4 3 4 3 2 4父代2: 1 12 3 5 6 8 5 6 3 1 8 5 6 3 3隨機選擇一個交叉點為11，交叉后為：子代1: 1 14 2 13 8 6 3 2 5 4 8 5 6 3 3子代2: 1 12 3 5 6 8 5 6 3 1 3 4 3 2 4交叉過程的目的就是希望新的基因是由舊的基因中好的部分組合而成的，從而新的基因比原先的基因要好。當(dāng)然把舊的種群中的一部分基因完全保留到下一代中去也是很有意義的。程序中采用了單點交叉的策略。如下程序代碼所示：for(int j=0; jpartPos ;j+)nextGenomei.Genej = parent

60、GenomeFather.Genej;nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;for(;j=0.9 & pDiff=0.1)sameFlag = false;如果當(dāng)前maxFitness最大的頭結(jié)點滿足if語句中的判斷條件，則sameFlag置為真，即算法停止迭代的條件得到了滿足。TraverseHashTable函數(shù)則用于遍歷HASH表。算法終止的另一個條件是迭代的次數(shù)。程序中設(shè)定了算法的最大迭代次數(shù)為1000。3.9 仿真結(jié)果與測試試驗中用到的物品的重量和價值分別存儲于以下兩個數(shù)組之中。int WeightNUMG=6,