./智能所"暑期學校"科研實習報告題目：用遺傳算法求解多維背包問題姓名：吳遜專業：智能科學與技術指導老師、職務：尚榮華副教授日期：二零一一年八月摘要首先簡單介紹了基本的遺傳算法。然后將貪婪算法與簡單遺傳法相結合構成一種混合遺傳算法,用該混合遺傳算法求解背包問題。通過對標準測試集中的27個問題進行測試,發現用這種方法求解大規模背包問題,其解的質量和求解性能較簡單遺傳算法和貪婪算法都有所改善。關鍵詞：遺傳算法,多維背包問題緒論遺傳算法是模擬生物界自然進化過程的一種計算模型,其思想主要來源于達爾文進化論、孟德爾遺傳學說及現代生物學對生命遺傳過程的研究。對它的研究起源于20世紀70年代,由美國Michigan大學的J.Holland教授于1975年正式提出。GA的主要特點是群體搜索策略和群體中個體之間的信息交換,搜索不依賴于梯度信息。尤其適用于處理傳統搜索方法難于解決的復雜和非線性問題,可廣泛用于組合優化、機器學習、自適應控制等領域。本文將先就遺傳算法介紹其思想來源及基本思路,并提出GA應用的5個關鍵點。接著對一類典型的組合優化問題——0-1背包問題分別進行簡單遺傳算法與混合遺傳算法的求解,并將結果與貪婪算法進行對比。遺傳算法概述2.1達爾文進化論與孟德爾學說19世紀中葉,達爾文創立了科學的生物進化學說,它第一次對整個生物界的發生、發展,作出了唯物的、規律性的解釋,使生物學發生了一次革命性的變革。達爾文進化論認為生物不是靜止的,而是進化的。物種不斷變異,舊物種消失,新物種產生。而且生物的進化是連續和逐漸,不會發生突變。生物之間存在一定的親緣關系,他們具有共同的祖先；而另一方面,由于生物過渡繁殖,但是它們的生存空間和食物有限,從而面臨生存斗爭,包括:種、種間以及生物與環境的斗爭。總結起來為兩部分容：遺傳變異與自然選擇。其中自然選擇是達爾文進化論的核心。1857年,孟德爾通過對植物進行一系列仔細的實驗。揭示了遺傳學的兩條基本定律：分離定律和獨立分配定律,統稱為孟德爾遺傳定律。分離定律是指基因作為獨特的獨立單位而代代相傳。細胞中有成對的基本遺傳單位,在雜交的生殖細胞中,一個來自雄性親本,一個來自雌性親本.獨立分配定律則指出在一對染色體上的基因對中的等位基因能夠獨立遺傳。孟德爾的這兩條遺傳基本定律就是新遺傳學的起點,孟德爾也因此被后人稱為現代遺傳學的奠基人。將達爾文進化論和孟德爾-摩根基因相結合,成為現被廣泛接受的新達爾文主義。新達爾文主義認為,只用種群上和物種的少量統計過程就可以充分地解釋大多數生命歷史,這些過程就是繁殖、變異、競爭、選擇。繁殖是所有生命的共同特性；變異保證了任何生命系統能在正熵世界中連續繁殖自己；對于限制在有限區域中的不斷膨脹的種群來說,競爭和選擇是不可避免的結論。2.2生物學中的遺傳概念在生物細胞中,控制并決定生物遺傳特性的物質是脫氧核糖核酸,簡稱DNA。染色體是其載體。DNA是由四種堿基按一定規則排列組成的長鏈。四種堿基不同的排列決定了生物不同的表現性狀。例如,改變DNA長鏈中的特定一段〔稱為基因,即可改變人體的身高。細胞在分裂時,DNA通過復制而轉移到新產生的細胞中,新的細胞就繼承了上一代細胞的基因。有性生殖生物在繁殖下一代時,兩個同元染色體之間通過交叉而重組,亦即在兩個染色體的某一相同位置處DNA被切斷,其前后兩串分別交叉形成兩個新的染色體。在細胞進行復制時可能以很小的概率產生某些復制差錯,從而使DNA發生某種變異,產生新的染色體。這些新的染色體將決定新的個體〔后代的新的性狀。在一個群體中,并不是所有的個體都能得到相同的繁殖機會,對生存環境適應度高的個體將獲得更多的繁殖機會；對生存環境適應度較低的個體,其繁殖機會相對較少,即所謂自然選擇。而生存下來的個體組成的群體,其品質不斷得以改良,稱為進化。生物的進化是經過無數次有利的進化積累而成的,不同的環境保留了不同的變異后代。遺傳算法的基本思想首先實現從性狀到基因得映射,即編碼工作,然后從代表問題可能潛在解集得一個種群開始進行進化求解。初代種群〔編碼集合產生后,按照優勝劣汰的原則,根據個體適應度大小挑選〔選擇個體,進行復制、交叉、變異,產生出代表新的解集的群體,再對其進行挑選以及一系列遺傳操作,如此往復,逐代演化產生出越來越好的近似解。選擇是指通過適應度的計算,淘汰不合理的個體。類似于自然界的物競天擇。復制指編碼的拷貝,類似于細胞分裂中染色體的復制。交叉即編碼的交叉重組,類似于染色體的交叉重組。變異是指編碼按小概率擾動產生的變化,類似于基因的突變這個過程將導致種群像自然進化一樣,后代種群比前代更加適應環境,末代種群中得最優個體經過解碼〔從基因到性狀的映射,可以作為問題近似最優解。遺傳算法的基本框架如下：遺傳算法需解決的5個問題基本的遺傳算法可定義為一個八元組：GA=〔C,E,,M,Φ,Γ,Ψ,T式中：C—個體的編碼方式；E—個體的適應度函數；—初始種群；M—種群大小；Φ—選擇算子；Γ—交叉算子；Ψ—變異算子；T—算法終止條件。基于以上認識,總結之,認為完成一個遺傳算法主要需解決以下五個問題：1編碼選擇合適的編碼方式會使原問題映射到基因空間后變得簡單明了、易于解決。編碼需考慮染色體的可行性、合法性〔通過解碼是否為問題的一個解以及映射的唯一性。有二進制編碼、實數編碼、整數排列編碼等。2群體初始化通常有兩種方法,一種是完全隨即產生；一種是根據某些先驗知識產生一組必須滿足的要求,在滿足這些要求的解中隨機選取樣本。經證明,在二進制編碼的前提下,若個體長度為L,則種群規模的最優值為〔即全解。但這個數字通常情況下都很大,所以一般取20-100。3個體評價適應度函數的選取直接影響遺傳算法的收斂速度及能否找到最優解,對一般優化問題,通常直接選取其目標函數作為適應度函數。在計算適應度時,對不可行解的處理常用的方法有修正法和罰函數法,實驗證明修正法要優于罰函數法。4遺傳算子〔全局:選擇；局部：交叉、變異選擇：其基礎是適者生存理論,指導GA搜索在整個搜索空間中朝最有利的區域發展。確定合適的選擇壓力對其很重要,在進化之初保持低壓可以保留種群多樣性,而在進化后期選擇高壓可以加快收斂速度。常用的選擇機制有輪盤賭,確定性選擇,混合選擇等。交叉、變異:分別模擬生物界的有性生殖過程和基因突變現象,常用的有單點交叉,多點交叉,隨機、插入及交換變異等方法。5參數選擇； 對于一般的問題,通常需要確定的主要參數有：迭代次數；種群大小；交叉、變異概率。這幾種參數的變化對算法性能的影響非常明顯,需針對不同問題具體分析。遺傳算法的特點遺傳算法的主要特點是群體搜索策略和群體中個體之間的信息交換,具體而言,它有以下不同于傳統算法的優點：從許多點開始并行計算,計算速度快,避免收斂于局部最優解；通過目標函數計算匹配度,對問題的依賴性小；在解空間進行高效的啟發式搜索,而非盲目窮舉；應用圍廣；計算簡單,功能強,適合解決大規模復雜問題。0-1背包問題問題描述：給定背包的m種資源,如大小、承重等,其中第j種資源取值,j=1,2,...,m;另給定n件物品,其中第i件物品的價值為,對應資源j的占用量為,i=1,2...n。受背包條件限制,若只能挑選一部分物品裝入背包,那么如何選擇物品使背包裝入物品的價值最大,數學描述為：式中：f<x>表示裝入背包物品的總價值；參數>0,>0,0<<；x=<,,...>表示一組物品的選擇策略,=i表示物品j被選中放入背包,=0表示物品i沒有被選中。當m取值為1時,問題即變為簡單0-1背包問題。背包問題屬典型的組合優化問題,并且是NP難問題。已有的求解方法可分為精確算法,如枚舉法,動態規劃法,分支定界法,圖論法等指數級方法以及近似算法,如貪婪算法,遺傳算法,免疫算法等兩大類。背包問題的研究對于解決復雜組合優化問題有重要的意義。用遺傳算法求解多維0-1背包問題4.1算法描述本章將采用一種將貪婪算法與遺傳算法相結合的混合遺傳算法來求解多維背包問題,并將此算法與簡單遺傳算法和貪婪算法進行對比,以提供一種利用遺傳算法求解問題的新思路。傳統的貪婪算法是基于價值密度的,例如物品單位體積價值或單位質量價值。這在一維背包問題中很適合,但是對于多維背包問題就需要做一下修改,因為包的限制條件有多個〔如體積、質量等,無法只用上述簡單的價值密度來解決。為此,我們提出了"綜合價值密度"的概念,所謂"綜合價值密度"就是對各種單一價值密度的綜合,用來表示,具體定義如下：=其中,表示第i種物品占用"總資源"的加權量。的意義是包的對第j種資源限制的相對大小,越大說明包對對第j種資源限制的越小,所以在該種資源在中占的比例就越小。 用貪婪算法求解多維0-1背包問題的步驟如下：Step1：求解各物品的價值密度ρ；Step2:將物體按ρ由大到小的順序排序。不妨記新的排序為；Step3:若對任意一種資源j,均有,則=1,否則=0.k=k+1；Step4：IFk=n+1stop; ELSEreturnstep3.貪婪算法簡單直觀,易于理解,但并不能保證能得到全局最優解。在簡單遺傳算法中加入適當的局部搜索方式,利用啟發式信息或與領域相關的知識,使得算法既具有遺傳算法的整體優化等特性,又能加快算法的收斂速度,從而在求解各類應用問題中具有更大的優越性,這樣的算法稱為混合遺傳算法。遺傳算法的幾個步驟〔編碼,初始化,選擇,交叉,變異等已經有許多很好的方法,例如輪盤賭選擇法、單點交叉等,這些方法簡單,效果好,而且有通用性,我們可以直接用來解決各種問題。解決多維背包問題的關鍵在于包的限制條件的處理,遺傳算法中經過交叉、變異的個體是隨機的,很可能不滿足包的限制條件,所以要用合理的修復算法修復每個個體使其滿足限制條件。基于對以上分析,可以利用在簡單遺傳算法中加入用基于上述貪婪算法的修復算法,這樣既能將不可行解改造成可行解,又能使個體趨于較好的解。具體步驟如下:Step1:依據上述貪婪算法將物品重新排序.Step2:依據上述貪婪選擇機制依次修復每個個體。本實驗中其它算子的選擇如下：〔1編碼：采用二進制編碼,即直接使用原問題描述中的x表示個體。〔2評價函數：取目標函數f<x>。〔3初始化種群：隨機產生,種群規模為100。〔4選擇：輪盤賭算法。〔5交叉：單點交叉,交叉概率為pc=0.5.〔6變異：單點變異,變異概率為pm=0.01.〔7終止條件：設置一定的迭代次數。本實驗中取100次。4.2實驗與分析本實驗共選取了標準測試集中的27個問題,對每個問題進行了5次實驗,統計結果如下：問題mn簡單遺傳算法混合遺傳算法貪婪算法已知最優解Weing2Weing1Weing3Weing7Weing8Weish01Weish02Weish06Weish07Weish10Weish11Weish14Weish15Weish18Weish19Weish22Weish24Weish26Weish27Weish30PB1PB2PB4PB5PB6sento1sento2222225555555555555554421030303028282810510530304040505060607070808090909027342920406060130314.0140115.895642.8994757.0479457.84504.84420.05336.45330.45882.45142.26168.46804.88688.26499.27563.08836.07669.28152.09306.82975.62975.891132.82090.6743.27327.48208.4102273.0117071.571296.3855858.1310523.33423.73424.34194.64089.14144.73484.74393.54452.26523.54561.15518.46871.05528.25764.67082.02454.52320.969256.81625.6447.55153.76854.9130687.0141227.895677.01011575.3616782.74554.04503.55351.65555.76304.75559.06875.07328.79349.07566.38837.39826.79348.39656.0108642977.03054.395168.02077.3776.07669.08646.3120317.8129795.990744.8858794.1555688.94228.04182.14959.55014.65585.74956.65969.06604.38232.56600.588368512.68207.48278.99376.92509.12620.584542.21776.9681.67117.97808.012188013927893278108836562006045344483550355676265555069027199922470518836981892789764108192792282590909192572376068709130883141278956771095445624319455445365557556763395643695474869580769889471022095849819111913090318695168213977677728722由以上實驗數據可以看出：當m、n較小時,SGA的結果要優于貪婪算法,而當數據量增大時,SGA將次于greedy,且差