【正文】 .......................................................................................................................36 結論 .........................................................................................................................................................36 展望 ........................................................................................................................................................36總結與體會 .......................................................................................................................................................38 設計（論文）專用紙 第 III 頁致謝 ...................................................................................................................................................................40參考文獻 ...........................................................................................................................................................41附錄一 源程序 .................................................................................................................................................43MATLAB 主程序 .........................................................................................................................................43GUI 界面設計程序 ........................................................................................................................................51附錄二 外文文獻翻譯 .....................................................................................................................................60附錄三 外文文獻原文 .....................................................................................................................................71 設計（論文）專用紙 第 IV 頁前言背包問題(Knapsack Problem)是一種組合優(yōu)化NP完全問題，相似的問題經常出現(xiàn)在商業(yè)、組合數(shù)學，計算復雜性理論、密碼學和應用數(shù)學等領域中。背包問題可分為一維背包，二維背包問題，完全背包問題，多重背包問題、分組背包問題等等。01背包問題作為最基礎背包問題，它包含了背包問題的設計狀態(tài)，方程的最基本思想，因此，其他背包問題也可以轉化成為01背包問題進行求解。遺傳算法（Geic Algorithm）是一類借鑒生物界的進化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機制）演化而來的隨機化搜索方法。首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數(shù)連續(xù)性的限定；具有內在的并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質，已被人們廣泛地應用于組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域。它是現(xiàn)代有關智能計算中的關鍵技術。在論文首先詳細介紹了遺傳算法的數(shù)學基礎、基本原理、實現(xiàn)過程，以及使用遺傳算法求解 01 背包問題的 2 個算例并得到相關仿真結果，并對仿真結果進行分析。接著通過設置不同的種群規(guī)模、交叉概率和迭代次數(shù)來探討這些算子對于遺傳算法求解背包問題性能的影響。最后在 matlab 環(huán)境中進行 GUI 界面設計，通過 GUI界面可以直觀的看到 01 背包問題的 2 個算例在不同參數(shù)設置下仿真曲線的變化情況。 設計（論文）專用紙0第一章 緒 論 背包問題簡介 01 背包問題背景背包問題（Knapsack Problem）是由 Markel 和 Hellman[1]提出的一類具有實際應用背景的經典 NP 問題。背包問題主要思路是假定一個人擁有大量物品，物品的重量各不相同，他要選擇一些物品放入背包中。物品的重量是已知的，所有可能的物品也是已知的，但是背包中的物品是保密的，此外還附加了背包的重量限制。對于大規(guī)模的背包問題要列出所有可能的物品在計算上是不可能實現(xiàn)的。在多種背包問題類型中，01 背包問題是最基本的背包問題，其他背包問題往往也可以轉化成 01背包問題求解。在我們的現(xiàn)實生活中許多問題都可以用背包問題來描述，例如工廠中的下料問題、管理中的資源分配問題、裝箱問題、資金預算問題等等都可以建模為背包問題。此外背包問題還常常作為其他復雜組合優(yōu)化問題的一個子問題出現(xiàn)，對于由簡單結構組合而成的復雜結構體而言，對簡單問題的深入探索往往可以使復雜的問題迎刃而解。所以在前人研究經驗的基礎上開展對背包問題的研究具有重要意義。 背包問題的研究現(xiàn)狀Dantzing 在上世紀 50 年代首先進行了開創(chuàng)性的研究，利用貪婪算法 [2]求得了01 背包問題的最優(yōu)解上界。此后 20 幾年背包問題沒有較大的發(fā)展，直到 1974 年，hoeowitz 和 salmi 利用分支節(jié)點法 [3]解答背包問題，他們提出背包問題的可分性，為該問題的求解指出了一條新型道路。隨后 balas 和 zemel 提出了背包問題的“核”思想使得背包問題的研究獲得了較大的發(fā)展。上世紀九十年代以后，隨著生物仿生技術和網(wǎng)絡技術的飛速發(fā)展，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，例如：遺傳算法已經在 01 背包問題上得到了較好的應用，螞蟻算法等仿生算法也很 設計（論文）專用紙1好的應用到了組合優(yōu)化問題中。近幾年還出現(xiàn)了許多將幾種算法結合起來的混合算法用來解決背包問題并取得了不錯的效果。傳統(tǒng)求解背包問題的方法可以概括為精確算法和近似算法，其中精確算法有動態(tài)規(guī)劃法，回溯法和分支限界法，近似算法有遺傳算法，貪婪算法和蟻群算法，由于精確算法的時間復雜性和空間復雜性等缺點，近年來利用近似算法求解背包問題已成為重點。前人已經對背包問題做了一些深入的研究，得到了一些經典的方法，有些方法對于解決背包問題雖然能得到不錯的結果，但是也存在著很多不足之處。首先，很多算法的計算量都很大，迭代的時間很長。例如：窮舉法和動態(tài)規(guī)劃法簡單易行,但是效率很低、魯棒性不強,只能用于較小規(guī)模的問題求解，但在現(xiàn)實問題中有時面對的問題搜索空間可能非常大，慢慢求解效率就會很低。第二，貪婪算法速度快，爬坡能力強，但是它適用于搜索局部最優(yōu)解,可能會陷入局部極值而得不到全局最優(yōu)解。第三，蟻群算法可以得到近似最優(yōu)解,但是當數(shù)據(jù)規(guī)模較大的時候收斂太慢；第四，新出現(xiàn)的知識進化算法和 DNA 計算等方法也可以有效的解決背包問題，但這些理論還不太完善，背包問題屬于組合最優(yōu)化問題，在嚴格意義上求取最優(yōu)解非常困難，所以研究高速近似的算法是一個重要的發(fā)展方向。與以上幾種算法相比遺傳算法具有一定的優(yōu)勢。首先，遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學要求，由于他的進化特性，搜素過程中不需要問題的內在性質，對于任意形式的目標函數(shù)和約束，無論是線性的還是非線性的，離散的還是連續(xù)的都可處理。其次，進化算子的各態(tài)歷經性使得遺傳算法能夠非常有效地進行概率意義的全局搜索。最后，遺傳算法對于各種特殊問題可以提供極大的靈活性來混合構造領域獨立的啟發(fā)式，從而保證算法的有效性。本文將對遺傳算法做進一步研究并結合應用于背包問題的求解，并通過實驗證明遺傳算法對求解背包問題是比較有效的。 遺傳算法簡介遺傳算法(Geic Algorithms)是計算數(shù)學中用于解決最優(yōu)化的搜索算法，是 設計（論文）專用紙2進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，它借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質是一種高效、并行、全局搜索的方法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優(yōu)的方法。在遺傳法操作使用適者生存的原則，在潛在的解決方案種群中逐次產生一個近似的最優(yōu)方案。在遺傳算法的每一代中，根據(jù)個體在問題領域中的適應度值和從自然遺傳學中借鑒來的再造方法進行選擇，產生一個新的近似解。這個過程導致種群中個體的進化，得到新的個體比原來的個體更能適應環(huán)境，就像自然界中的改造一樣。 遺傳算法的研究現(xiàn)狀與發(fā)展趨勢查克斯達爾文的自然選擇學說認為生物進化的動力和機制在于自然選擇，生物通過生存斗爭，其中具有有利變異的個體容易存活下來，并有更多的機會將這種變異遺傳給后代，而具有不利變異的個體將被淘汰且產生后代的機會也會少。凡是在生存斗爭中獲勝的個體對環(huán)境的適應性都比較強，因此生物進化的過程就是這種“物競天擇，適者生存”的過程，這種過程是一個緩慢的、連續(xù)和長期的過程。遺傳和變異是決定生物進化的內在因素，推動生物的進化和發(fā)展。基于生物進化理論，從 20 世紀 60 年代起科學家們就嘗試用計算的方法模擬生物遺傳和選擇進化過程。美國的 Holland 教授于 1975 年出版了關于遺傳算法的開創(chuàng)性著作《Adaptation in Natural and Artificial Systems》 [4]，開創(chuàng)性的提出了遺傳算法的概念，系統(tǒng)性的闡述了遺傳算法的理論，奠定了遺傳算法理論的數(shù)學基礎，并將其應用到了優(yōu)化和機器學習的領域中。他將遺傳算法定義為適應算法，可以廣泛的應用于系統(tǒng)最優(yōu)化的研究，1975 年 DeJone 做了大量實驗，建立了著名的DeJone 的測試函數(shù) [5]。1989 年 Goldberg 博士出版本了專著《Geic algorithm in search，optimization and machine learning 》 [6]，這是第一本關于遺傳算法的教科書，全面論述了遺傳算法的原理與應用，并與實例結合給出了大量的可用的 設計（論文）專用紙3源程序，使技術專家可以借鑒參考并進行實際應用。在此之后世界范圍內掀起了關于遺傳算法研究與應用的高潮。從 1985 年開始關于遺傳算法及其應用的國際會議兩年舉辦一次，很多人工智能領域的專家開始發(fā)表有關遺傳算法的論文。1991 年Davis 在他的《Hand book of geic algorithm》 [7]一書中介紹了大量的實例。遺傳算法由于能有效解決 NP 類型的組合優(yōu)化問題和多目標函數(shù)優(yōu)化問題，得到很多學科的高度重視。在國內，武漢大學成立了一個軟件工程國家重點實驗室。以進化計算作為一個重要的研究方向，他們的研究成果目前在國內處于領先水平；中國科技大學的陳國良出版本了關于遺傳算法的專著；此外，太原理工大學的謝克明教授模擬人類思維進化過程提出的思維進化算法也成為進化計算領域的一個重要分支。 遺傳算法在應用方面取得的豐碩成果,使人們對它的發(fā)展前景充滿信心。認識到這一點,遺傳算法的奠基人之一,Goldsberg D 戲言:“已不再需要水晶球”。今后幾年,可以預期,拓廣更加多樣的應用領域,其中包括各種遺傳算法程序設計環(huán)境的開發(fā)仍將是遺傳算法發(fā)展的主流。事實上這也是本世紀高新技術迅速發(fā)展帶有規(guī)律性的特點,即面向應用。與此同時,這并不意味著理論研究會被忽視, 這方面同樣有大量工作要做。例如: 控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行遺傳算法和分布式遺傳算法的研究；其他類型生物機制的模仿,如免疫、 病毒、寄生等,以豐富遺傳算法的內容,等等。自然,不論從理論還是應用的角度看,最緊迫的應是關于算法收斂性問