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

PAGE畢業(yè)設計（論文）基于遺傳算法求解背包問題院別專業(yè)名稱班級學號學生姓名指導教師2012年6月15日

第46頁基于遺傳算法求解背包問題摘要背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題,本文首先介紹了基本遺傳算法的基本原理、特點及其基本實現(xiàn)技術，接著針對背包問題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應用情況。并且結合背包問題實例，給出了具體的編碼方法，運行參數(shù)，群體大小，最大迭代次數(shù)，以及合適的遺傳算子。最后，簡單說明了遺傳算法在求解背包問題中的應用并對遺傳算法解決背包問題的前景提出了展望。關鍵詞：背包問題，遺傳算法，遺傳算子

GeneticAlgorithmforKPAuthor：YangDongTutor：KongZhiAbstractKP(KnapsackProblem)isacombinatorialoptimizationofNP-completeproblem.Theprimaryknowledge,characteristicsandthebasictechniquesofGAareintroducedfirstly.Theencodingmodelandgeneticoperators(includingselectionoperation,crossoveroperationandmutationoperation)solvingKParediscussedsecondly.Combinedwithexamplesofknapsackproblem,wehavegiventhespecificencodingmethod,operatingparameters,popsize,maxgeneration,andsuitablegeneticoperator.Atlast,theapplicationofgeneticalgorithmissimplepresented,andtheprospectforthefutureofgeneticalgorithminsolvingKPhasbeengiven.KeyWords:KP,geneticalgorithm,geneticoperators

目錄TOC\t"標題1,2,標題2,3,章標題,1"\h304331緒論 1117081.1引言 1261081.2背包問題概述 1296861.2.1背包問題的描述 2323251.2.2研究背包問題的意義 9310541.3遺傳算法 10220811.3.1遺傳算法概述 10167521.3.2遺傳算法的特點 10300131.3.3遺傳算法的應用領域 11183032遺傳算法的基本原理 13242382.1基本流程 14108652.2編碼 1486122.3適應度函數(shù) 15167092.4遺傳算子 15216732.4.1選擇算子 16322102.4.2交叉算子 17270792.4.3變異算子 17315632.5參數(shù)控制 18254782.5.1群體規(guī)模 18157882.5.2交叉概率 18315262.5.3變異概率 1945142.6算法結束條件控制 1924033求解實現(xiàn)背包問題的遺傳算法 20145153.10_1背包問題中染色體的表示 20200893.2算法求解01背包問題時用到的參數(shù) 20111883.3選擇操作 20233763.4交叉操作 21199103.5精英策略 22115063.6變異操作 23318653.7代際更新 23216843.8算法的終止 2335243.9仿真結果與測試 2468503.9.1不同交叉概率下所的測試結果 2548453.9.2極端數(shù)據(jù)對結果的影響 27138043.9.3仿真結果總結 3012192結論 3119166致謝 323777參考文獻 3313876附錄 341緒論1.1引言現(xiàn)代科學理論研究與實踐中存在著大量與優(yōu)化、自適應相關的問題，但除了一些簡單的情況之外，人們對于大型復雜系統(tǒng)的優(yōu)化和自適應問題仍然無能為力。然而，自然界中的生物卻在這方面表現(xiàn)出了其優(yōu)異的能力，它們能夠以優(yōu)勝劣汰、適者生存的自然進化規(guī)則生存和繁衍，并逐步產(chǎn)生出對其生存環(huán)境適應性很高的優(yōu)良物種。遺傳算法正是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局優(yōu)化自適應概率搜索算法。遺傳算法是計算數(shù)學中用于解決最佳化的搜索算法，是進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。遺傳算法通常實現(xiàn)方式為一種計算機模擬。對于一個最優(yōu)化問題，一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。傳統(tǒng)上，解用二進制表示（即0和1的串），但也可以用其他表示方法。進化從完全隨機個體的種群開始，之后一代一代發(fā)生。在每一代中，整個種群的適應度被評價，從當前種群中隨機地選擇多個個體（基于它們的適應度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當前種群。背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題,對這個問題的求解前人己經(jīng)研究出了不少的經(jīng)典的方法,例如解析法，窮舉法等，但是這些傳統(tǒng)的優(yōu)化方法存在一些缺點，如算法復雜度太高。與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有以下優(yōu)點:在每一時刻，GA同時在多個子空間內(nèi)進行搜索，對初始值不作要求;基本不用搜索空間的知識或其他輔助信息，而僅用適應度來評估個體優(yōu)劣;具有很強的魯棒性。因此遺傳算法在背包問題求解方面的應用研究，對于構造合適的遺傳算法框架、建立有效的遺傳作以及有效地解決背包問題等有著多方面的重要意義[5]。1.2背包問題概述1.2.1背包問題的描述它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將它們放到背包中來加密消息。背包中的物品總重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而引人注目。背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學，計算復雜性理論、密碼學和應用數(shù)學等領域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？它是在1978年由Merkel和Hellman提出的。01背包問題概述題目有N件物品和一個容量為V的背包。第i件物品的重量是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大?；舅悸愤@是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。可以壓縮空間，f[v]=max{f[v],f[v-c[i]]+w[i]}這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。注意f[v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉移方程中就要再加入一項f[v-1]，這樣就可以保證f[N][V]就是最后的答案。至于為什么這樣就可以，由你自己來體會了。優(yōu)化空間復雜度以上方法的時間和空間復雜度均為O(N*V），其中時間復雜度基本已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O(N）。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(shù)組f[0..V]，能不能保證第i次循環(huán)結束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[v]和f[v-c[i]]的值呢？事實上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值。偽代碼如下：fori=1..Nforv=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現(xiàn)在的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數(shù)組解01背包問題是十分必要的。總結0/1背包問題是最基本的背包問題，它包含了背包問題中設計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成0/1背包問題求解。完全背包問題題目有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c，價值是w。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅悸愤@個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i,v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉移方程，像這樣：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。這跟01背包問題一樣有O(N*V）個狀態(tài)需要求解，但求解每個狀態(tài)的時間則不是常數(shù)了，求解狀態(tài)f[v]的時間是O(v/c），總的復雜度是超過O(VN）的。將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。簡單有效的優(yōu)化完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c<=c[j]且w>=w[j]，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復雜度，因為有可能特別設計的數(shù)據(jù)可以一件物品也去不掉?？偨Y完全背包問題也是一個相當基礎的背包問題，它有兩個狀態(tài)轉移方程，分別在“基本思路”以及“O(VN）的算法“的小節(jié)中給出。希望你能夠?qū)@兩個狀態(tài)轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。多重背包問題題目有N種物品和一個容量為V的背包。第i種物品最多有n件可用，每件體積是c，價值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大?；舅惴ㄟ@題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有n+1種策略：取0件，取1件……取n件。令f[v]表示前i種物品恰放入一個容量為v的背包的最大權值，則：f[v]=max{f[v-k*c]+k*w|0<=k<=n}。復雜度是O(V*∑n）。轉化為01背包問題另一種好想好寫的基該方法是轉化為01背包求解：把第i種物品換成n件01背包中的物品，則得到了物品數(shù)為∑n的01背包問題，直接求解，復雜度仍然是O(V*∑n）。但是我們期望將它轉化為01背包問題之后能夠像完全背包一樣降低復雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n件——均能等價于取若干件代換以后的物品。另外，取超過n件的策略必不能出現(xiàn)。方法是：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1），n-2^k+1，且k是滿足n-2^k+1>0的最大整數(shù)。例如，如果n為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為n，表明不可能取多于n件的第i種物品。另外這種方法也能保證對于0..n間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2^k-1和2^k..n兩段來分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(logn）種物品，將原問題轉化為了復雜度為O(V*∑logn）的01背包問題，是很大的改進。O(VN）的算法多重背包問題同樣有O(VN）的算法。這個算法基于基本算法的狀態(tài)轉移方程，但應用單調(diào)隊列的方法使每個狀態(tài)的值可以以均攤O⑴的時間求解。小結這里我們看到了將一個算法的復雜度由O(V*∑n）改進到O(V*∑logn）的過程，還知道了存在應用超出NOIP范圍的知識的O(VN）算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實現(xiàn)?；旌先N背包問題問題如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個上限（多重背包）。應該怎么求解呢？01背包與完全背包的混合考慮到在P01和P02中最后給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個物品應用轉移方程時，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復雜度是O(VN）。偽代碼如下：fori=1..Nif第i件物品是01背包forv=V..0f[v]=max{f[v],f[v-c]+w};elseif第i件物品是完全背包forv=0..Vf[v]=max{f[v],f[v-c]+w};再加上多重背包如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN）的解法：遇到多重背包類型的物品用單調(diào)隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個這類物品分成O(logn）個01背包的物品的方法也已經(jīng)很優(yōu)了。小結有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。

二維費用的背包問題問題二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a和b。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w。算法費用加了一維，只需狀態(tài)也加一維即可。設f[v]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態(tài)轉移方程就是：fi[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數(shù)組：當每件物品只可以取一次時變量v和u采用逆序的循環(huán)，當物品有如完全背包問題時采用順序的循環(huán)。當物品有如多重背包問題時拆分物品。物品總個數(shù)的限制有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當于每件物品多了一種“件數(shù)”的費用，每個物品的件數(shù)費用均為1，可以付出的最大件數(shù)費用為M。換句話說，設f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多重）用不同的方法循環(huán)更新，最后在f[0..V][0..M]范圍內(nèi)尋找答案。另外，如果要求“恰取M件物品”，則在f[0..V][M]范圍內(nèi)尋找答案。小結事實上，當發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法。分組的背包問題問題有N件物品和一個容量為V的背包。第i件物品的費用是c，價值是w。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。算法這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c]+w|物品i屬于第k組}。使用一維數(shù)組的偽代碼如下：for所有的組kforv=V..0for所有的i屬于組kf[v]=max{f[v],f[v-c]+w}另外，顯然可以對每組中的物品應用P02中“一個簡單有效的優(yōu)化”。小結分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義“泛化物品”的概念，十分有利于解題。有依賴的背包問題簡化的問題這種背包問題的物品間存在某種“依賴”的關系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。算法這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。按照背包問題的一般思路，僅考慮一個主件和它的附件集合?？墒?，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇主件后再選擇兩個附件……無法用狀態(tài)轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數(shù)級。）考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。再考慮P06中的一句話：可以對每組中的物品應用P02中“一個簡單有效的優(yōu)化”。這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0..V-c所有這些值時相應的最大價值f'[0..V-c]。那么這個主件及它的附件集合相當于V-c+1個物品的物品組，其中費用為c+k的物品的價值為f'[k]+w。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉化為V-c+1個物品的物品組，就可以直接應用P06的算法解決問題了。更一般的問題更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然后用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。事實上，這是一種樹形DP，其特點是每個父節(jié)點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經(jīng)觸及到了“泛化物品”的思想。看完P08后，你會發(fā)現(xiàn)這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和。小結用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發(fā)現(xiàn)一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質(zhì)。

泛化物品定義考慮這樣一種物品，它并沒有固定的費用和價值，而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0..V中的整數(shù)的函數(shù)h，當分配給它的費用為v時，能得到的價值就是h(v）。這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數(shù)組h[0..V]，給它費用v，可得到價值h[V]。一個費用為c價值為w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函數(shù)值都為0的一個函數(shù)。如果它是完全背包中的物品，那么它可以看成這樣一個函數(shù)，僅當v被c整除時有h(v)=v/c*w，其它函數(shù)值均為0。如果它是多重背包中重復次數(shù)最多為n的物品，那么它對應的泛化物品的函數(shù)有h(v)=v/c*w僅當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)=max{h(k)+l(v-k)|0<=k<=v}?？梢钥吹?，f也是一個由泛化物品h和l決定的定義域為0..V的函數(shù)，也就是說，f是一個由泛化物品h和l決定的泛化物品。由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱f是h與l的和，即f=h+l。這個運算的時間復雜度是O(V^2）。泛化物品的定義表明：在一個背包問題中，若將兩個泛化物品代以它們的和，不影響問題的答案。事實上，對于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為s，則答案就是s[0..V]中的最大值。背包問題的泛化物品一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能將問題對應于某個泛化物品。也就是說，給定了所有條件以后，就可以對每個非負整數(shù)v求得：若背包容量為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數(shù)集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數(shù)的函數(shù)——包含了關于問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0..V）的值之后，就可以根據(jù)這個函數(shù)的取值得到背包問題的最終答案。小結綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數(shù)，即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物品的和然后求之。0關于本文本文討論的是0-1背包問題，問題描述如下：指定給n件物品和一個背包，物品i的重量是wi，其價值為vi，背包的容量為C，求從這n件物品中選取一部分物品且對每件物品,或者選取,或者不選,每種物品只能裝入背包一次,且要求滿足放入背包中的物品總重量不超過背包容量。求出裝入背包中物品價值總和最大的方案。注意：在本題中，所有的重量值均為整數(shù)。數(shù)學模型限制條件為：所求表達式為：其中，表示物品放入背包，表示物品未放入背包。1.2.2研究背包問題的意義背包問題是組合優(yōu)化領域中的一個典型問題，涉及求多個變量的函數(shù)的最大值。雖然它陳述起來很簡單，但求解卻很困難，并且已經(jīng)被證明是NP完全問題。至今尚未找到有效的求解方法，在理論上枚舉法可以解這一問題，但是當n較大時，解題的時間消耗會使枚舉法顯得沒有任何實際價值。因此尋求一種求解時間短，能滿足實際問題精度要求的解，成為解決該問題的主要途徑[8]。背包問題的求解，一直以來倍受人們的關注。對于這樣一個典型的、易于描述卻難以處理的NP難題，有效地解決它在可計算理論上有著重要的理論價值。并且，背包問題是諸多領域內(nèi)出現(xiàn)的多種復雜問題的集中概括和簡化形式。背包問題也可描述為決定性問題，相似問題經(jīng)常出現(xiàn)在商業(yè)、投資組合優(yōu)化、組合數(shù)學，計算復雜性理論、密碼學和應用數(shù)學等領域中，因此具有廣泛的實際應用領域。1.3遺傳算法1.3.1遺傳算法概述遺傳算法（GA）是一類借鑒生物界自然選擇和自然遺傳機制的隨機化的搜索算法，也是一種抽象于生物進化過程的基于自然選擇和生物遺傳機制的優(yōu)化技術。它是在1975年首次由美國密西根大學的D.J.Holland教授和他的同事們借鑒生物界自然選擇和進化機制基礎之上提出的。經(jīng)過近30年的研究、應用，遺傳算法已被廣泛地應用于函數(shù)優(yōu)化、機器人系統(tǒng)、神經(jīng)網(wǎng)絡學習過程、模式識別、圖象處理、工業(yè)優(yōu)化控制等領域。其主要特點是群體搜索策略、群體中個體之間的信息交換和搜索不依賴于梯度信息[19]。遺傳算法是將問題的每一個可能性解看作是群體中的一個個體(染色體)，并將每一個染色體編碼成串的形式，再根據(jù)預定的目標函數(shù)對每個個體進行評價，給出一個適應度值。算法將根據(jù)適應度值對它進行尋優(yōu)的過程，遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個遺傳算子來具體實現(xiàn)的，它的搜索能力由選擇算子和雜交算子決定，變異算子則保證了算法能夠搜索到問題空間的每一個點，從而使其具有搜索全局最優(yōu)的能力。遺傳算法的高效性和強壯性可由Holland提出的模式定理(SchemaTheorem)和隱式并行性得以解釋。近年來，遺傳算法從理論到實際都已經(jīng)取得了許多重要成果。由于它具有良好的全局搜索能力，是目前解決各種優(yōu)化問題的最有效的方法，已經(jīng)成為研究熱點。1.3.2遺傳算法的特點從整體上來講，遺傳算法是進化算法中產(chǎn)生最早、影響最大、應用也比較廣泛的一個研究方向和領域，它不僅包含了進化算法的基本形式和全部優(yōu)點，同時還具備若干獨特的性能。[16]1)在求解問題時，遺傳算法首先要選擇編碼方式，它直接處理的對象是參數(shù)的編碼集而不是問題參數(shù)本身，搜索過程既不受優(yōu)化函數(shù)連續(xù)性的約束，也沒有優(yōu)化函數(shù)倒數(shù)必須存在的要求。通過優(yōu)良染色體基因的重組，遺傳算法可以有效地處理傳統(tǒng)上非常復雜的優(yōu)化函數(shù)求解過程；2)若遺傳算法在每一代對群體規(guī)模為n的個體進行操作，實際上處理了大約個模式,具有很高的并行性，因而具有顯著的搜索效率；3)在所求解問題為非連續(xù)、多峰以及有噪聲的情況下，能夠以很大的概率收斂到最優(yōu)解或滿意解，因而具有較好的全局最優(yōu)解求解能力；4)對函數(shù)的性態(tài)無要求，針對某一問題的遺傳算法經(jīng)簡單修改即可適應于其他問題，或者加入特定問題的領域知識，或者與已有算法相結合，能夠較好地解決一類復雜問題，因而具有較好的普適性和易擴充性；5）遺傳算法的基本思想簡單，運行方式和實現(xiàn)步驟規(guī)范，便于具體使用；遺傳算法的這些特點使得它一經(jīng)提出即在理論上引起了高度重視，能夠應用于一些到目前為止人們知之甚少的困難問題領域，產(chǎn)生大量的成功案例。1.3.3遺傳算法的應用領域遺傳算法的主要應用領域包括以下幾個方面：函數(shù)優(yōu)化問題。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是對遺傳算法進行性能評價的常用例子。很多人構造出了各種各樣的復雜形式的測試函數(shù)來評價遺傳算法的性能。而且對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結果。組合優(yōu)化問題。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復雜問題，人們己意識到應把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于求解組合優(yōu)化問題非常有效。遺傳算法已經(jīng)在求解旅行商問題、圖形劃分問題等方面得到成功的應用。生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以求解，也會因簡化太多而使求解結果與實際相差甚遠。由于可以采用字符編碼，而且不必使用恰好的目標函數(shù)估值，遺傳算法也成為解決復雜調(diào)度問題的有效工具。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務分配、虛擬企業(yè)中的伙伴選擇方面遺傳算法都得到了有效的應用。自動控制。在自動控制領域有很多與優(yōu)化相關的問題需要求解，而且這些優(yōu)化問題通常要么是通過積分表達的，要么是寫不出明確而嚴格的解析表達式。遺傳算法在求解這類自動控制問題方面已顯示出其獨特的優(yōu)點。例如，用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、用遺傳算法優(yōu)化設計透平機械、設計模糊控制器等，都取得了較好的效果。機器學習。學習能力是高級自適應系統(tǒng)所應具備的特征之一?；谶z傳算法的機器學習在很多方面都得到成功應用。例如，遺傳算法被用于學習模糊控制規(guī)則、確定模糊集的隸屬函數(shù)、改進模糊系統(tǒng)的性能;被用來調(diào)整人工神經(jīng)網(wǎng)絡的連接權及網(wǎng)絡拓撲優(yōu)化。此外，遺傳算法還被應用到反問題求解、機器人學習、生物計算、圖像處理、人工智能以及遺傳編程等領域。

2遺傳算法的基本原理在遺傳算法里，優(yōu)化問題的解被稱為個體，它表示為一個變量序列，叫做染色體或者基因串。染色體一般被表達為簡單的字符串或數(shù)字串，不過也有其他的依賴于特殊問題的表示方法適用，這一過程稱為編碼。首先，算法隨機生成一定數(shù)量的個體，有時候操作者也可以對這個隨機產(chǎn)生過程進行干預，以提高初始種群的質(zhì)量。在每一代中，每一個個體都被評價，并通過計算適應度函數(shù)得到一個適應度數(shù)值。種群中的個體被按照適應度排序，適應度高的在前面。這里的“高”是相對于初始的種群的低適應度來說的。下一步是產(chǎn)生下一代個體并組成種群。這個過程是通過選擇和繁殖完成的，其中繁殖包括交配(crossover，在算法研究領域中我們稱之為交叉操作）和突變(mutation)。選擇則是根據(jù)新個體的適應度進行的，但同時并不意味著完全的以適應度高低作為導向，因為單純選擇適應度高的個體將可能導致算法快速收斂到局部最優(yōu)解而非全局最優(yōu)解，我們稱之為早熟。作為折中，遺傳算法依據(jù)原則：適應度越高，被選擇的機會越高，而適應度低的，被選擇的機會就低。初始的數(shù)據(jù)可以通過這樣的選擇過程組成一個相對優(yōu)化的群體。之后，被選擇的個體進入交配過程。一般的遺傳算法都有一個交配概率（又稱為交叉概率），范圍一般是0.6~1，這個交配概率反映兩個被選中的個體進行交配的概率。例如，交配概率為0.8，則80%的“夫妻”會生育后代。每兩個個體通過交配產(chǎn)生兩個新個體，代替原來的“老”個體，而不交配的個體則保持不變。交配父母的染色體相互交換，從而產(chǎn)生兩個新的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。不過這里的半段并不是真正的一半，這個位置叫做交配點，也是隨機產(chǎn)生的，可以是染色體的任意位置。再下一步是突變，通過突變產(chǎn)生新的“子”個體。一般遺傳算法都有一個固定的突變常數(shù)（又稱為變異概率），通常是0.1或者更小，這代表變異發(fā)生的概率。根據(jù)這個概率，新個體的染色體隨機的突變，通常就是改變?nèi)旧w的一個字節(jié)（0變到1，或者1變到0）。經(jīng)過這一系列的過程（選擇、交配和突變），產(chǎn)生的新一代個體不同于初始的一代，并一代一代向增加整體適應度的方向發(fā)展，因為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適應度低的個體逐漸被淘汰掉。這樣的過程不斷的重復：每個個體被評價，計算出適應度，兩個個體交配，然后突變，產(chǎn)生第三代。周而復始，直到終止條件滿足為止。一般終止條件有以下幾種：進化次數(shù)限制；計算耗費的資源限制（例如計算時間、計算占用的內(nèi)存等）；一個個體已經(jīng)滿足最優(yōu)值的條件，即最優(yōu)值已經(jīng)找到；適應度已經(jīng)達到飽和，繼續(xù)進化不會產(chǎn)生適應度更好的個體；人為干預；以及以上兩種或更多種的組合。2.1基本流程遺傳算法需要涉及五大要素:編碼、群體初始化、適應性函數(shù)的設定、遺傳操作的設計和控制參數(shù)的設定。具體步驟如下：(l)編碼，把問題的解轉化成位串表示形式;(2)定義適應性函數(shù);(3)確定遺傳算法的各算子及參數(shù)，包括選擇、交叉、變異方法，交叉率、變異率、群體容量、最大遺傳代數(shù)等;(4)隨機初始化群體;(5)計算群體中每一個染色體的適應值;(6)按照遺傳操作形成下一代群體;①從當前群體中由事先設定好的選擇方法選出兩個染色體;②根據(jù)給定的交叉率，對選出的兩個染色體進行交叉操作;③根據(jù)給定的變異率，對每個染色體進行變異操作;④重復①、②、③步，直到新的一代群體被創(chuàng)建出來;判斷新產(chǎn)生的群體是否能滿足結束指標，如果滿足，則算法結束，如果不滿足，則返回步驟(6)。2.2編碼按照遺傳算法的工作流程，當用遺傳算法求解問題時，必須在目標問題實際表示與遺傳算法的染色體位串結構之間建立關系，即確定編碼和解碼運算。編碼就是將問題的解用一種碼來表示，從而將問題的狀態(tài)空間與GA的編碼空間相對應，編碼的選擇是影響算法性能與效率的重要因素。常用的編碼方法有如下幾種：①二進制編碼：二進制編碼將問題空間的參數(shù)表示為基于字符集{0,1}構成的染色體位串，是最常用的一種編碼方式。②大字符集編碼:除基于字符集{0,1}的二進制編碼之外，可以結合實際問題的特征采用D進制數(shù)或字符集來表示長度為L的位串。③序列編碼：用排列法進行編碼顯得更為自然、合理。④實數(shù)編碼：實數(shù)編碼具精度高、大空間搜索的優(yōu)點。⑤樹編碼：樹編碼是一種非固定常用編碼模式，其表示空間是開放的。在搜索過程中樹可以自由生長，但是不便于形成更具有結構化和層次性的問題解，實際應用中往往可以加以限制。⑥自適應編碼：實現(xiàn)選擇合適的固定編碼方式對潛在的遺傳算法用戶來說是一個難題。事實上，提出合適的編碼同解決問題本身一樣困難。因此，許多用戶認為既然要用遺傳算法解決問題，為什么不讓它同時調(diào)整編碼呢?一些專家就采用了自適應編碼[11]。2.3適應度函數(shù)適應度評價是通過適應度函數(shù)對個體質(zhì)量的一種測量，是進化過程中自然的唯一依據(jù)。因此適應度函數(shù)的選擇至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應度函數(shù)是由目標函數(shù)變換而成的。對目標函數(shù)值域的某種映射變換稱為適應度的尺度變換。適應度函數(shù)的設計主要滿足以下條件：①單值、連續(xù)、非負、最大化:這個條件是容易理解和實現(xiàn)的。②合理、一致性：要求適應度值反映對應解的優(yōu)劣程度，這個條件的達成比較難以衡量。③計算量?。哼m應度函數(shù)設計應盡可能簡單，這樣可以減小計算時間和空間上的復雜性，降低成本。④通用性強：適應度函數(shù)對具體問題應盡可能具有通用性，最好無需使用者改變適應度函數(shù)中的參數(shù)。適應度函數(shù)的尺度變換有線性變換法、幕函數(shù)變換法、指數(shù)變換法[10]。2.4遺傳算子標準的遺傳算子一般都包括選擇、交叉和變異三種。它們構成了遺傳算法的核心，使得算法具有強大的搜索能力。2.4.1選擇算子選擇操作就是用來確定如何從父代種群中按照某種方法選取哪些個體遺傳到下一代種群的遺傳運算。它是根據(jù)個體適應度函數(shù)值的大小正比于其被放入候選的概率的過程。在備選集中按照一定的選擇概率進行操作，這個概率取決于種群中個體的適應度及其分布。其主要作用是避免了基因缺失，提高全局收斂性和計算效率。選擇算子可看作是種群空間到父體空間的隨機映射，它按照某種準則或概率分布從當前種群中以高的概率選取那些好的個體組成不同的父體以供生成新的個體。目前常用的選擇策略有賭盤賭選擇算子、排序選擇算子、最優(yōu)保存選擇算子和錦標賽選擇算子等[8]。在遺傳算法中，目前常用的選擇機制有以下幾種：①適應度比例方法適應度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或蒙特卡羅選擇。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為n，其中個體i的適應度值為fi，則i被選擇的概率psi為：psi=fi/∑fi（4-1）顯然，概率psi反映了個體i的適應度在整個群體的個體適應度總和中所占的比例。個體適應度越大，其被選擇的概率就越高，反之則被選擇的概率越低。②最佳個體保存方法最佳個體保留進化策略的基本思想是當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應度最低的個體。具體操作過程是：1)找出當前群體中適應度最高的個體和適應度最低的個體。2)若當前群體中最佳個體的適應度比總的迄今為止的最好個體的適應度還要高，則以當前群體中的最佳個體作為新的迄今為止的最好個體。3)用迄今為止的最好個體替換掉當前群體中的最差個體。③期望值方法在賭輪選擇機制中，當個體數(shù)不太多時，依據(jù)產(chǎn)生的隨機數(shù)有可能會出現(xiàn)不正確地反映個體適應度的選擇，即存在統(tǒng)計誤差。也就是說，適應度高的個體也有可能被淘汰(當然，適應度低的個體也有可能被選擇)，為克服這種誤差，期望值方法用了如下思想。1)計算群體中每個個體在下一代生存的期望數(shù)目：M=fi/=fi/∑fi/n（4-2）2)若某個體被選中并要參與配對和交叉，則它在下一代中的生存的期望值數(shù)目減去0.5；若不參與配對和交叉，則該個體的生存期望數(shù)目減去1。3)在2)的兩種情況下，若一個個體的期望值小于0時，則該個體不參與選擇。④排序選擇機制排序選擇方法的主要著眼點是個體適應度之間的大小關系，對個體適應度是否取正值或負值以及個體適應度之間的數(shù)值差異程度并無特別要求。排序選擇機制的主要思想是：對群體中的所有個體按其適應度大小進行排序，基于這個排序來分配各個體被選中的概率。其具體操作過程是：1)對群體中的所有個體按其適應度大小進行降序排序。2)根據(jù)具體求解問題，設計一個概率分配表，將各個概率值按上述排列次序分配給各個個體。3)以各個個體所分配到的概率值作為其能夠被遺傳到下一代的概率，基于這些概率值用比例選擇的方法來產(chǎn)生下一代群體。是指在計算每個個體的適應度后，根據(jù)適應度大小順序?qū)θ后w中個體排序，然后把事先設計好的概率表按序分配給個體，作為各自的選擇概率。2.4.2交叉算子交叉操作是遺傳算法中最主要的遺傳操作。它是模仿自然界有性繁殖的基因重組過程，對兩個父代個體進行基因操作，其作用在于把原有優(yōu)良基因遺傳到下一代種群中，并生成包含更復雜基因結構的新個體。交叉算子可看作是父體空間到個體空間的隨機映射，它通常的作用方式是：隨機地確定一個或多個分量位置為交叉點，由此將一對父體的兩個個體分為有限個片斷再以概率（稱為交叉概率）交換相應片斷得到新的個體。2.4.3變異算子在生物種群中總是存在著變異，變異指的是子代和父代之間具有某些不相似的現(xiàn)象，即因為存在著變異現(xiàn)象，所以子代和父代之間中總是不完全相同的。變異是生物進化過程中不可缺少的，它為生物的進化和發(fā)展創(chuàng)造了條件。在遺傳算法中，變異是指父代染色體中的某些基因片，以相對較小的概率發(fā)生隨機改變的操作過程。所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。在遺傳算法中使用變異算子主要有以下兩個目的：①改善遺傳算法的局部搜索能力。遺傳算法使用交叉算子已經(jīng)從全局的角度出發(fā)找到了一些較好的個體編碼結構，它們已接近或有助于接近問題的最優(yōu)解。但僅使用交叉算子無法對搜索空間的細節(jié)進行局部搜索。這時若再使用變異算子來調(diào)整個體編碼串中的部分基因值，就可以從局部的角度出發(fā)使個體更加逼近最優(yōu)解，從而提高了遺傳算法的局部搜索能力。②維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。變異算子用新的基因值替換原有基因值，從而可以改變個體編碼串的結構，維持群體的多樣性，這樣就有利于防止出現(xiàn)早熟現(xiàn)象。2.5參數(shù)控制在遺傳算法的運行過程中，存在著對其性能產(chǎn)生重大影響的一組參數(shù)。這組參數(shù)在初始階段或種群進化過程中需要合理地選擇和控制。主要包括種群規(guī)模n、交叉概率pc以及變異概率pm。2.5.1群體規(guī)模大種群含有較多模式，為遺傳算法提供了足夠的模式采樣容量，可以改進GA搜索的質(zhì)量，防止早熟前收斂。但大種群增加了個體適應性評價的計算量，從而使收斂速度降低。2.5.2交叉概率交叉概率pc控制著交叉算子的應用頻率，在每一代新的種群中，需要對個體的染色體結構進行交叉操作。交叉概率越高，種群中新結構的引入越快，已獲得的優(yōu)良基因結構的丟失速度也相應升高。而交叉概率太低則可能導致搜索阻滯。一般pc=0.60—1.00。2.5.3變異概率變異操作是保持種群多樣性的有效手段，交叉結束后，交配池中的全部個體位串上的每位等位基因按概率隨機改變，因此每代中大約發(fā)生n次變異。變異概率太小，可能使某些基因位過早丟失的信息無法恢復；而變異概率過高，則搜索將變成隨機搜索。一般取pm=0.05—0.2。2.6算法結束條件控制終止代數(shù)是表示遺傳算法運行結束條件的一個參數(shù)，它表示遺傳算法運行到指定的進化代數(shù)之后就停止運行，并將當前種群中的最優(yōu)個體作為所求問題的最優(yōu)解輸出。由于遺傳算法不同于傳統(tǒng)的優(yōu)化算法，它沒有利用目標函數(shù)的梯度等信息，所以在遺傳進化過程中，很難有明確的搜索終止準則。常用的辦法是預先給定算法的終止進化代數(shù)。一般來說，預先給定算法的終止進化代數(shù)只能找到問題在給定時限內(nèi)所能尋求的相對滿意解，但不一定是問題的最優(yōu)解或較高精度的近似解。為了獲得較高精度的近似解，通常可依據(jù)種群適應度的穩(wěn)定來適時調(diào)整終止進化代數(shù)的設置，或者在連續(xù)進化數(shù)代以后，如果解的適應度沒有明顯的改進，則終止進化過程。終止進化代數(shù)一般的取值范圍是100-1000。

3求解實現(xiàn)背包問題的遺傳算法3.10_1背包問題中染色體的表示用向量X來表示染色體，X=｛x1，x2，……，xn｝。，xi∈｛0,1｝，xi=1表示物品i裝入了背包，xi=0表示物品i未裝入背包。每個染色體對應其當前裝入背包的物品的總價值和總重量。背包中物品的中價值代表了該物品的適應度。程序中定義了這樣的一個結構來表示染色體：typedefstruct{ intWeight; //染色體代表的物品的總重量 intFitness; //染色體代表的物品的價值（適應度） intGene[NUMG];//用元素取值于定義域｛0,1｝的數(shù)組表示染色體。}GENE;3.2算法求解01背包問題時用到的參數(shù)POPSIZE：種群大小，即已知的可行解的個數(shù)。NUMG：染色體中基因的個數(shù)，即物品的總數(shù)。CAPACITY：背包的容量。MAXB：二進制表示的染色體換算之后的最大十進制整數(shù)。用于隨機產(chǎn)生一個整數(shù)，進而轉換作染色體。SIM：染色體之間的相似度閾值。當染色體之間的相似度達到閾值時，算法即停止運行。PC=1.0：交叉概率為100％。PM=0.2：變異概率為20％，變異可以保證種群的多樣性，從而防止算法收斂于某個局部解。3.3選擇操作選擇操作采用了賭輪選擇（Roulette-wheelselection）的方法。函數(shù)selectIndex()中包含了選擇染色體的具體過程。其流程圖如圖1所示。圖1賭輪選擇流程圖 程序中用一個Begin來代表當前賭輪上的指針的位置，End則用來使賭輪循環(huán)轉動。用summaryBE表示當前賭輪上的指針轉過的染色體的總價值。用summaryF表示當前全部染色體的價值總和。用randProb作為染色體選擇的閾值。randProb為介于[0,1]之間的隨機數(shù)。選擇使summaryBE/summaryF大于閾值randProb的染色體作為要選擇的染色體。3.4交叉操作單點交叉操作的簡單方式是將被選擇出的兩個個體S1和S2作為父母個體，從[0，1]中產(chǎn)生一個隨機數(shù)p，如果p<pc，將兩者的部分基因碼值進行交換。假設如下兩個父代：父代1:11421386325434324父代2:1123568563185633隨機選擇一個交叉點為11，交叉后為：子代1:11421386325485633子代2:1123568563134324交叉過程的目的就是希望新的基因是由舊的基因中好的部分組合而成的，從而新的基因比原先的基因要好。當然把舊的種群中的一部分基因完全保留到下一代中去也是很有意義的。程序中采用了單點交叉的策略。如下程序代碼所示：for(intj=0;j<partPos;j++){ nextGenome[i].Gene[j]=parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j]=parentGenome[Mother].Gene[j];}for(;j<NUMG;j++){ nextGenome[i].Gene[j]=parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j]=parentGenome[Mother].Gene[j];}partPos為隨機產(chǎn)生的整數(shù)，代表交叉的位置。第一個for循環(huán)將partPos位置之前的基因遺傳給一個后代，而第二個循環(huán)則將partPos位置之后的基因進行了交換。calculateCapacity函數(shù)用于計算交叉操作后的染色體的容量。calculateFitness函數(shù)用于計算交叉操作后的染色體的適應度。checkCapacity函數(shù)則用于檢查交叉后的染色體的合理性，容量超出背包的染色體是不合理的。這里沒有使后代死亡，而是隨機地調(diào)整了染色體中的基因。使得基因能夠適應環(huán)境（背包的容量）而繼續(xù)生存。3.5精英策略精英策略為了不使最優(yōu)解在交叉的過程中，不會丟失最優(yōu)解而采取的策略。其思想是保存上一代中的適應性強的染色體。相應地取代下一代中適應性弱的染色體。程序中精英策略由keepBestParents函數(shù)和sortFiness函數(shù)來實現(xiàn)。需要說明的是sortFitness僅僅對種群的索引進行了排序。然后用父代中20%的適應度較大的優(yōu)秀染色體替換子代中20%的適應性弱的染色體。3.6變異操作染色體的變異可以保持種群的多樣性，防止最優(yōu)解的丟失以及算法收斂到局部最優(yōu)解。變異操作由mutation函數(shù)實現(xiàn)。首先產(chǎn)生一個介于0和1之間的隨機數(shù)prob，若prob小于MP則進行變異操作：隨機產(chǎn)生一個位置partPos，然后變異前染色體的partPos位置的基因為1，則變異為0，否則變異為1；相應地要進行適應度和染色體容量的變化。3.7代際更新代際之間的更新，即用新生成的種群代替取代舊的種群。這個操作在updateGeneration函數(shù)中實現(xiàn)，同時這個操作使用了前面提及的精英策略。實際上，父代種群中優(yōu)秀的染色體已被保留，updateGeneration中只是用新種群中的優(yōu)秀染色體來代替父代中的染色體。由于對父代和子代的染色體都進行了排序，因此程序中將子代的80％視作優(yōu)秀，將父代中的前20％視作優(yōu)秀。3.8算法的終止程序中采用了一個HASH表來對子代種群的適應度進行HASH操作。HASH表中的頭結點紀錄了頭結點所指向的單鏈表的信息。如下代碼中的注釋：typedefstructHead{ intmaxFitness;//單鏈表中的最大的Fitness intCount; //HASH到該結點的染色體的數(shù)目 intDiff; //單鏈表中有多少不同的Fitness HASHNODE*Next;}HEAD;用這樣的一個HASH表結構可以只需遍歷HASH表中的頭結點，即可知當前的種群的適應度最大的染色體是否集中。具體地，如checkFitness函數(shù)中的下面幾行代碼：index=maxFitness(hashTable); doubleCPount=hashTable[index].Count/(double)POPSIZE;doublepDiff=hashTable[index].Diff/(double)POPSIZE;if(CPount>=0.9&&pDiff<=0.1){ sameFlag=false;}如果當前maxFitness最大的頭結點滿足if語句中的判斷條件，則sameFlag置為真，即算法停止迭代的條件得到了滿足。TraverseHashTable函數(shù)則用于遍歷HASH表。算法終止的另一個條件是迭代的次數(shù)。程序中設定了算法的最大迭代次數(shù)為1000。3.9仿真結果與測試試驗中用到的物品的重量和價值分別存儲于以下兩個數(shù)組之中。intWeight[NUMG]={6,9,8,8,6,1,10,5,7,1}; intValue[NUMG]={2,20,5,4,19,14,18,8,11,6};父代種群存儲于parentGenome[NUMG]中，子代種群存儲于nextGenome[NUMG]中。程序的初始狀態(tài)和結束狀態(tài)如下面的表格所示：初始的種群:WeightValue染色體中的基因21520010110101222300110001012240000110001122530100010110264510100110012453110001001122530100010110232510110100002648101011010025290111000000初始的HASH表:頭結點索引maxFitnessCountDiff單鏈表中的結點內(nèi)容0521152:1534253:403291129:6451145:9481148:10231123:12251125:3.9.1不同交叉概率下所的測試結果在程序?qū)崿F(xiàn)上，本文采用VC++6.0作為程序開發(fā)工具，測試是在奔騰2.8G，512M以上內(nèi)存的微機上進行的，操作系統(tǒng)是WinXP。當PM=0.2時，程序在運行了16次后停止運行。停止時的種群:WeightValue染色體中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時的HASH表:頭結點索引maxFitnessCountDiff單鏈表中的結點內(nèi)容0789178:12641164: 當PM=0.1時，程序在運行了3次后停止運行。停止時的種群:WeightValue染色體中的基因22530100010110225301000101102453110001001124531100010011225301000101102253010001011024531100010011225301000101102253010001011026481010110100停止時的HASH表:頭結點索引maxFitnessCountDiff單鏈表中的結點內(nèi)容1539178:9481148:當PM=0.15時，程序在運行了26次后停止運行。停止時的種群:WeightValue染色體中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時的HASH表:頭結點索引maxFitnessCountDiff單鏈表中的結點內(nèi)容0789178:12641164: 當PM=0.18時，程序在運行了13次后停止運行。停止時的種群:WeightValue染色體中的基因2978010011011129780100110111297801001101112872010010110297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時的HASH表:頭結點索引maxFitnessCountDiff單鏈表中的結點內(nèi)容0789178:7721172:對于不同變異概率下運行次數(shù)和所得值如下圖所示：從上圖我們可以總結出：變異概率太小，可能是某些基因位過早丟失的信息無法恢復，導致無法獲得最優(yōu)解變異概率過高，則搜索將變成隨機搜索，增大了搜索次數(shù)，但能得到最優(yōu)解3.9.2極端數(shù)據(jù)對結果的影響當初始種群全是零時：WeightValue染色體中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000所得結果：當初始種群為：WeightValue染色體中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000160000000001所得結果：分析：超過最大迭代次數(shù)，但相似度還沒達到0.9，所以只有一個估計值（最大值）當初始種群為：WeightValue染色體中的基因611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111所得結果：分析：超過最大迭代次數(shù)，但相似度還沒達到0.9，所以只有一個估計值（最大值）3.9.3仿真結果總結通過對以上各種情況分析，我們可知：當前01背包問題的最優(yōu)解為 X=｛0,1,0,0,1,1,0,1,1,1｝對應的最優(yōu)值是78，即當前能夠裝入背包的最大價值。通過上述仿真實驗和數(shù)據(jù)測試，可以得出利用本文算法求解背包問題能夠獲得較滿意的效果。本文的算法不但有很快的收斂速度，而且在進化過程中種群的多樣性保持很好，具有良好的全局搜索能力。因此，我們認為本文算法是可行的和有效的。

結論用遺傳算法解最優(yōu)化問題，首先應對可行域中的個體進行編碼，然后在可行域中隨機挑選指定群體大小的一些個體組成作為進化起點的第一代群體，并計算每個個體的目標函數(shù)值，即該個體的適應度值。接著就像自然界中的遺傳規(guī)律一樣，利用選擇機制從群體中隨機挑選個體作為繁殖過程前的個體樣本。選擇機制保證適應度較高的個體能夠保留較多的樣本；而適應度較低的個體則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算法對挑選后的樣本進行交換和基因突變。交叉算法交換隨機挑選的兩個個體的某些位，變異算子則直接對一個個體中的隨機挑選的某一位進行突變。這樣通過選擇和繁殖就產(chǎn)生了下一代群體。重復上述選擇和繁殖過程，直到結束條件得到滿足為止。進化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結果。與其他算法相比，遺傳算法主要有以下四個方面的不同：遺傳算法所面向的對象是參數(shù)集的編碼,而不是參數(shù)集本身；遺傳算法的搜索是基于若干個點，而不是基于一個點；遺傳算法利用目標函數(shù)的信息，而不是導數(shù)或者其他輔助信息；遺傳算法的轉化規(guī)則是概率性的，而不是確定性的。我們通過上述例子，嚴格按照遺傳算法對背包問題進行了完整的求解，事實說明，用遺傳算法來解決此類組合優(yōu)化問題也是比較有效的，而且非常好用，它的解的空間比較大，而且在最后能無限度地接近最優(yōu)解。所以，用遺傳算法來解決背包問題是一個很好的方法。遺傳算法作為一種對生物進化現(xiàn)象進行仿真的程序，取得了人工遺傳的模擬效果，具有自適應性。在遺傳算法的結構中遺傳操作和選擇機制是兩個重要的因素，其聯(lián)系可用"遺傳算法=遺傳操作+選擇過程"這個邏輯關系來表示。如果一個應用問題不能求得目標函數(shù)的全局最優(yōu)值,而只能或只希望求一定意義下的"滿意解"，這時,可供選擇的方法之一自然是遺傳算法，因為遺傳算法比其他算法有更多的優(yōu)勢。可喜的是,近年來遺傳算法在商業(yè)應用方面取得了一系列重要成果。遺傳算法的商業(yè)應用五花八門,覆蓋面甚廣。遺傳算法具有隱并行性，它可容易改造成為并行/分布式算法，用來解決那些復雜性問題。到目前，遺傳算法的理論機制仍不是很清楚，這可能和生命科學的研究一樣，將是一個永恒的研究課題，但也是一個難題。

致謝在論文即將完成之際，我非常感謝所有幫助過和支持過我的人。首先，我衷心地感謝我的指導老師孔芝老師，我的整個論文都是在孔芝老師的關懷和細心指導下完成的?？桌蠋煆恼撐牡倪x題到完成，在各方面都給予了我大力的支持、耐心的幫助和熱情地勉勵，使我能夠面對各種問題和困難，順利地完成論文