基于遺傳算法求解背包問(wèn)題

PAGE畢業(yè)設(shè)計(jì)（論文）基于遺傳算法求解背包問(wèn)題院別專業(yè)名稱班級(jí)學(xué)號(hào)學(xué)生姓名指導(dǎo)教師2012年6月15日

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

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

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

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

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

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

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

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