【正文】 ......................................................... 43 MATLAB 主程序 .............................................................................................................................................. 43 GUI 界面設計程序 ............................................................................................................................................ 51 附錄二 外文文獻翻譯 ......................................................................................................................................... 60 附錄三 外文文獻原文 ......................................................................................................................................... 71 設計（論文）專用紙 第 V 頁 前言 背包問題 (Knapsack Problem)是一種組合優(yōu)化 NP完全問題 ，相似的問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學，計算復雜性理論、密碼學和應用數(shù)學等領域中。 01背包問題作為最基礎背包問題，它包含了背包問題的設計狀態(tài)，方程的最基本思想，因此，其他背包問題也可以轉(zhuǎn)化成為 01背包問題進行求解。它是由 美國 的 1975年首先提出，其主要特點是直接對結(jié)構(gòu)對象進 行操作，不存在求導和函數(shù)連續(xù)性的限定；具有內(nèi)在的并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則。它是現(xiàn)代有關 智能計算 中的 關鍵技術(shù)。接著通過設置不同的種群規(guī)模、交叉概率和迭代次數(shù)來探討這些算子對 于遺傳算法求解背包問題性能的影響。 設計（論文）專用紙 1 第一章 緒 論 背包問題簡介 01背包問題背景 背包問題（ Knapsack Problem）是由 Markel 和 Hellman[1]提出的一類具有實際應用背景的經(jīng)典 NP問題。物品的重量是已知的，所有可能的物品也是已知的，但是背包中 的物品是保密的，此外還附加了背包的重量限制。在多種背包問題類型中， 01 背包問題是最基本的背包問題，其他背包問題往往也可以轉(zhuǎn)化成 01背包問題求解。此外背包問題還常常作為其他復雜組合優(yōu)化問題的一個子問題出現(xiàn)，對于由簡單結(jié)構(gòu)組合而成的復雜結(jié)構(gòu)體而言，對簡單問題的深入探索往往可以使復雜的問題迎刃而解。 背包問題的研究現(xiàn)狀 Dantzing在上世紀 50年代首先進行了開創(chuàng)性的研究，利用貪婪算法 [2]求得了 01背包問題的最優(yōu)解上界。隨后 balas 和 zemel 提出了背包問題的“核”思想使得背包問題的研究獲得了較大的發(fā)展。近幾年還出現(xiàn)了許多將幾種算法結(jié)合起來的混合算法用來解決背包問題并取得了不錯的效果。 前人已經(jīng) 對背包問題做了一些深入的研究，得到了一些經(jīng)典 的方法，有些方法對于解決背包問題雖然能得到不錯的結(jié)果，但是也存在著很多不足之處。例如：窮舉法和動態(tài)規(guī)劃法簡單易行 ,但是效率很低、魯棒性不強 ,只能用于較小規(guī)模的問題求解，但在現(xiàn)實問題中有時面對的問題搜索空間可能非常大，慢慢求解效率就會很低。第三，蟻群算法可以得到近似最優(yōu)解 ,但是當數(shù)據(jù)規(guī)模較大的時候收斂太慢；第四，新出現(xiàn)的知識進化算法和 DNA計算等方法也可以有效的解決 背包問題，但這些理論還不太完善，背包問題屬于組合最優(yōu)化問題，在嚴格意義上求取最優(yōu)解非常困難，所以研究高速近似的算法是一個重要的發(fā)展方向。首先， 遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學要求，由于他的進化特性，搜素過程中不需要問題的內(nèi)在性質(zhì)，對于任意形式的目標函數(shù)和約束，無論是線性的還是非線性的，離散的還是連續(xù)的都可處理。 最后， 遺傳算法對于各種特殊問題可以提供極大的靈活性來混合構(gòu)造領域獨立的啟發(fā) 式，從而保證算法的有效性。 遺傳算法 (Geic Algorithms)是計算數(shù)學中用于解決最優(yōu)化的搜索算法，是進化算法的一種。 遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，它借鑒了達爾文的進化論和孟德爾的遺傳學說。在遺傳法操作使用適者生存的原則，在潛在的解決方案種群中逐次產(chǎn)生一個近似的最優(yōu)方案。這個過程導致種群中個體的進化，得到新的個體比原來的個體更能適應環(huán)境，就像自然界中的改造一樣。達爾文的自然選擇學說認為生物進化的動力和機制在于自然選擇，生物通過生存斗爭，其中具有 有利變異的個體容易存活下來，并有更多的機會將這種變異遺傳給后代，而具有不利變異的個體將被淘汰且產(chǎn)生后代的機會也會少。遺傳和變異是決定生物進化的內(nèi)在因素，推動生物的進化和發(fā)展。美國的 Holland 教授于 1975 年出版了關于遺傳算法的開創(chuàng)性著作《 Adaptation in Natural and Artificial Systems》 [4]，開創(chuàng)性的提出了遺傳算法的概念，系統(tǒng)性的闡述了遺傳算法的理論，奠定了遺傳算法理論的數(shù)學基礎，并將其應用到了優(yōu)化和機器學習的領域中。 1989 年 Goldberg 博士出版本了專著《 Geic algorithm in search，optimization and machine learning 》 [6]，這是第一本關于遺傳算法的教科書，全面論述了遺傳算法的原理與應用，并與實例結(jié)合給出了大量的可用的源程序，使技術(shù)專家可以借鑒參考并進行實際應用。從 1985 年開始關于遺傳算法及其應用的國際會議兩年舉辦一次，很多人工智能領域的專家開始發(fā)表有關遺傳算法的論文。遺傳算法由于能有效解決 NP類型的組合優(yōu)化問題和多目標函數(shù)優(yōu)化問題，得到很多學科的高度重 視。以進化計算作為一個重要的研究方向，他們的研究成果目前在國內(nèi)處于領先水平；中國科技大學的陳國良出版本了關于遺傳算法的專著；此外，太原理工大學的謝克明教授模擬人類思維進化過程提出的思維進化算法也成為進化計算領域的一個重要分支。 認識到這一點 ,遺傳算法的奠基人之一 ,Goldsberg D 戲言 :“ 已不再需要水晶球 ” 。 事實上這也是本世紀高新技術(shù)迅速發(fā)展帶有規(guī)律性的特點 ,即面向應用 。例如 : 控制參數(shù)的選擇 ； 交換和突變這兩類最重要的算子的確切作用 ； 并行遺傳算法和分布式遺傳算法的研究 ； 其他類型生物機制的模仿 ,如免疫、 病毒、寄生等 ,以豐富遺傳算法的內(nèi)容 ,等等 。 這對遺傳算法的實際應用關系重大 。眾所周知 ,FL 有較強的知識表達能力 ,NN 的長處在于自學習 ,它們與遺傳算法相結(jié)合形成新的集成化技術(shù) ,即所謂的混合智能系統(tǒng) (Hybrid Intellectual System )。應該指出 ,我國學者對這一趨勢的認識較早 。 就遺傳算法本身的研究而言 ,應該說 ,我國起步較晚 ,近幾年才陸續(xù)看到一些介紹性的文章、不多于兩三部的專著以及初步的研究報告 ，與 國外工作比較 ,一個顯著區(qū)別是 ,國內(nèi)工作多只停留在論文這一層 次 ,幾乎沒有看到具體實際應用 ,與研究成果商品化的差距就更遠 。 因此 ,在我國發(fā)展遺傳算法 ,當前應該特別重視它的應用和推廣普及 。 國家組建的工程研究中心應該在這方面發(fā)揮更大的作用 。 例如 ,工科運籌學和最優(yōu)化方法的課程應該適當加入有關遺傳算法等方面的內(nèi)容 ,以開闊 學生的視野 ,同時也有利于加快傳統(tǒng)課程內(nèi)容的更新 。 這是遺傳算法與傳統(tǒng)算法的極大區(qū)別。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。 由于遺傳算法使用時應值這一信息進行搜索，并不需要問題導數(shù)等與問題直接相關的信息。 c. 算法有極強的容錯能力。通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串。故而，遺傳算法有很高的容錯能力。 這說明遺傳算法是采用隨機方法進行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。例如， Ackley 推薦的遺傳爬山法；Mathefoud 提出的遺傳模擬退火算法；采用遺傳算法中增加局部改善運算等等。在混合遺傳算法中，運用啟發(fā)式方法作局部優(yōu)化，采用遺傳算法作全局最優(yōu)點的探索。 （ 2） 并行遺傳算法 遺傳算法在 解 決一些實際問題時，由于它一般具有較大的群體規(guī)模，需要對較多的個體進 行大量的遺傳和進化操作，特別是要對大量的個體進行適應度計算或評價，從而使得算法的進化運算過程進展緩慢，難以達到計算速度的要求，因而遺傳算法的并行計算問題受到重視。 。通過對個體適應度并行計算方法的研究可找到并行評價個體適應度的算法。即不同個體的適應度計算可以在不同的處理機上同時進行。 在父代 群體產(chǎn)生下一代群體過程中，選擇操作只與個體的適應度有關，而交叉和變異操作只與參加運算的個體編碼有關。 。 設計（論文）專用紙 7 遺傳算法的應用 目前，遺傳算法在很多科學、工程領域得到廣泛的應用。 。目前， GA 已經(jīng)在旅行商問題（ TSP） [10]、背包問題 [11]、網(wǎng)絡路由、貨倉裝載 [12]等具有NP難度的組合優(yōu)化等方面取得了成功的應用。函數(shù)優(yōu)化是 GA 的經(jīng)典應用領域。函數(shù)優(yōu)化也是對遺傳 算法進行評價的常用工具。目前 GA 進行系統(tǒng)辨識、模糊控制器設計、航空系統(tǒng)的優(yōu)化等方面取得了一定的成就。遺傳算法在圖像的處理的圖像恢復、圖像邊緣特征提取方面得到了成功應用。目前基于 GA的機器學習在很多領域得到了應用。 。數(shù)據(jù)挖掘問題可以看做是搜索問題，把數(shù)據(jù)庫看作是搜索空間，而把挖掘算法看作搜索策略，這樣就可以使用遺傳算法對數(shù)據(jù)庫中的數(shù)據(jù)進行搜索，對于隨機產(chǎn)生的一組規(guī)則進行進化，直至數(shù)據(jù)庫能被該規(guī)則覆蓋，進而挖掘出大型數(shù)據(jù)庫中的隱含的規(guī)則。 設計（論文）專用紙 8 b. 對遺傳算法進行了理論研究。 c. 應用遺傳算法解決 01背包問題，通過設置不同參數(shù)探究遺傳算法求解背包問題的可行性并將算法在 Matlab 仿真平臺上進行實現(xiàn)。 設計（論文）專用紙 9 第二章 基于遺傳算法的 01 背包問題研究 遺傳算法是模擬生物在自然界中的遺產(chǎn)進化過程而形成的一種自適應全局優(yōu)化概率搜索算法。 70 年代 Dc Jong 基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗 [14]。 80 年代有Goldberg 進行歸納總結(jié)，形成了遺傳算法的基本框架。與生物一代一代的自然進化過程相似，遺傳算法也是一個反復迭代的過程，第 t 代群體記作 P（ t）經(jīng)過一代遺傳和進化之后，得到第 t+1 代群體，它們是由多個個體組成的集合記作 P（ t+1）。 遺傳算法有四個構(gòu)成要素： a) 染色體編碼方法：使用固定長度的二進制符號串來表示群體中的個體，其等位基因是由二值符號集 {0， l}所組成的。 c) 遺傳算子：使用比例選擇算子、單點交叉算子、基本位變異算子或均勻變異算子。 對一個需要進行優(yōu)化計算的實際應用問題，一般可按下述步驟來構(gòu)造求解該問題的遺傳算法： 設計（論文）專用紙 10 第一步：確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X 和問題的解空間； 第二步：建立優(yōu)化模型，即確定出目標函數(shù)的類型 (是求目標函數(shù)的最大值。 遺傳算法的數(shù)學基礎 遺傳算法在機理方面具有搜索過程和優(yōu)化機制等屬性，數(shù)學方面的性質(zhì)可通過模式定理和積木塊假設等分析加以討論， Markov 鏈也是分析遺傳算法的一個有效工具。 模式定理 [15’ 16’ 17]是由 John Holland 在 1971 年提出的，它是 GA的基本定理。 定義 模式 (schema)是一個描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。 定義 模式階 (schema order)模式 H中確定位置的個數(shù)稱為該模式的階，記作 o(H)。 模式階用 來反映不同模式問確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。例如：δ（ 011*1**） =4。 模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應度高于種群平均適應度的模式在子代中呈指數(shù)增長。 模式定理是遺傳算法的基本理論，保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了一種數(shù)學工具。 積木塊假設 (Building block hypothesis)[18]低階、短定義距、高平均適應度的基因塊 通過選擇、交叉和