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