【文章內(nèi)容簡介】 更新。 遺傳算法的特點a. 算法從問題解的串集開始搜索，而不是從單一解開始。這是遺傳算法與傳統(tǒng)算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。b. 求解時使用特定問題的信息極少，容易形成通用算法程序。由于遺傳算法使用時應(yīng)值這一信息進行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。遺產(chǎn)算法只需自適應(yīng)值和串編碼等通用信息，故幾乎可以處理任何問題。c. 算法有極強的容錯能力。遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠的信息。通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串。這就是一個強烈的過濾過程，并且是一個并行濾波機制。故而，遺傳算法有很高的容錯能力。d. 算法中的選擇、交叉、和變異都是隨機操作，而不是確定的精確規(guī)則。這說明遺傳算法是采用隨機方法進行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。 遺傳算法分類（1）混合遺傳算法單用簡單的遺傳算法在許多情況下不是十分有效，容易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問題，于是提出了多種混合算法。例如，Ackley 推薦的遺傳爬山法；Mathefoud 提出的遺傳模擬退火算法；采用遺傳算法中增加局部改善運算等等?；旌线z傳算法的基本思想是：對于每個新產(chǎn)生的后代在其進入下一代群體之前應(yīng)用局部優(yōu)化技術(shù)(如爬山法、模擬退火算法等)，使之移動到最近的局部最優(yōu)點。在混合遺傳算法中，運用啟發(fā)式方法作局部優(yōu)化，采用遺傳算法作全局最優(yōu)點的探索。由于遺傳算法與傳統(tǒng)優(yōu)化方法的互補性，混合遺傳算法通常比單一算法優(yōu)越。（2）并行遺傳算法遺傳算法在解決一些實際問題時，由于它一般具有較大的群體規(guī)模，需要對較多的個體進行大量的遺傳和進化操作，特別是要對大量的個體進行適應(yīng)度計算或評價，從而使得算法的進化運算過程進展緩慢，難以達到計算速度的要求，因而遺傳算法的并行計算問題受到重視。并行遺傳算法主要從下列四個方面對其進行改進和發(fā)展。個體適應(yīng)度的評價或計算在遺傳算法的運行過程中所占用的運行時間比較長。通過對個體適應(yīng)度并行計算方法的研究可找到并行評價個體適應(yīng)度的算法。互依賴關(guān)系，這樣各個個體的適應(yīng)度計算過程就可以相互獨立、并行地進行。即不同個體的適應(yīng)度計算可以在不同的處理機上同時進行。在父代群體產(chǎn)生下一代群體過程中，選擇操作只與個體的適應(yīng)度有關(guān)，而交叉和變異操作只與參加運算的個體編碼有關(guān)。這樣，產(chǎn)生群體過程中的選擇、交叉、變異操作就可以相互獨立地并行進行?？梢詫θ后w按一定的方式進行分組，分組后各組的個體遺傳進化過程可以在不同的處理機上相互獨立地進行，在適當(dāng)?shù)臅r候，各處理機之間相互交換信息。目前，遺傳算法在很多科學(xué)、工程領(lǐng)域得到廣泛的應(yīng)用。其典型應(yīng)用領(lǐng)域如下。隨著組合優(yōu)化問題規(guī)模的增加，其搜索空間也急劇增加，在計算機上用窮舉法不可能求出其最優(yōu)解，而遺傳算法可以在此類問題上尋求問題的滿意解。目前，GA 已經(jīng)在旅行商問題（TSP） [10]、背包問題 [11]、網(wǎng)絡(luò)路由、貨倉裝載 [12]等具有 NP難度的組合優(yōu)化等方面取得了成功的應(yīng)用。函數(shù)優(yōu)化是 GA的經(jīng)典應(yīng)用領(lǐng)域。學(xué)者構(gòu)造了各種復(fù)雜的測試函數(shù)，既有連續(xù)函數(shù)也有離散函數(shù)，有高維的也有低維的，有凹的也有凸的，有多峰的也有單峰的，遺傳算法較其他優(yōu)化方法便于得到較好的結(jié)果。函數(shù)優(yōu)化也是對遺傳算法進行評價的常用工具。，遺傳算法在自動控制領(lǐng)域的應(yīng)用日益增加并取得了較好的成果。目前 GA進行系統(tǒng)辨識、模糊控制器設(shè)計、航空系統(tǒng)的優(yōu)化等方面取得了一定的成就。遺傳算法在圖像的處理的圖像恢復(fù)、圖像邊緣特征提取方面得到了成功應(yīng)用。目前基于 GA的機器學(xué)習(xí)在很多領(lǐng)域得到了應(yīng)用。例如：利用 GA的機器學(xué)習(xí)來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的權(quán)值等；利用 GA學(xué)習(xí)模糊控制的奴隸度函數(shù)以改進模糊控制系統(tǒng)的性能。數(shù)據(jù)挖掘就是大型數(shù)據(jù)庫中提取人們感興趣的、隱含的、有潛在應(yīng)用價值的知識。數(shù)據(jù)挖掘問題可以看做是搜索問題，把數(shù)據(jù)庫看作是搜索空間，而把挖掘算法看作搜索策略，這樣就可以使用遺傳算法對數(shù)據(jù)庫中的數(shù)據(jù)進行搜索，對于隨機產(chǎn)生的一組規(guī)則進行進化，直至數(shù)據(jù)庫能被該規(guī)則覆蓋，進而挖掘出大型數(shù)據(jù)庫中的隱含的規(guī)則。a. 介紹了 01背包問題的概念，接著論述求解該問題的各種傳統(tǒng)算法，并對 01背包問題進行數(shù)學(xué)描述。b. 對遺傳算法進行了理論研究。介紹了進化算法的基本理論，對典型的幾種進化算法進行了簡要說明，并對遺傳算法的基本理論、應(yīng)用情況和研究趨勢做了較為詳細(xì)的論述。c. 應(yīng)用遺傳算法解決 01背包問題，通過設(shè)置不同參數(shù)探究遺傳算法求解背包問題的可行性并將算法在 Matlab仿真平臺上進行實現(xiàn)。d. 在 matlab環(huán)境中進行 GUI界面設(shè)計，運行界面中遺傳算法主要的參數(shù)可通過手動輸入自行修改，同時通過 GUI界面可以直接觀察到仿真曲線的變化情況。第二章 基于遺傳算法的 01背包問題研究遺傳算法是模擬生物在自然界中的遺產(chǎn)進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早是有沒過密歇根大學(xué)的 Holland教授提出的，起源于 60年代對自然和人工自適應(yīng)系統(tǒng)的研究 [13]。70 年代 Dc Jong基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗 [14]。在一系列研究工作基礎(chǔ)上。80 年代有Goldberg進行歸納總結(jié)，形成了遺傳算法的基本框架。生物進化是以集團為主體的，與此相適應(yīng)的，遺傳算法的運算對象是由 M個個體所組成的集合，成為群體。與生物一代一代的自然進化過程相似，遺傳算法也是一個反復(fù)迭代的過程，第 t代群體記作 P（t）經(jīng)過一代遺傳和進化之后，得到第t+1代群體，它們是由多個個體組成的集合記作 P（t+1） 。這個群體不斷的經(jīng)過遺傳和進化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個體更多的遺傳到下一代，這樣最終在種群中將會得到一個優(yōu)良的個體 X，它所對應(yīng)的的表現(xiàn)型 X將達到或接近問題的最優(yōu)解 X*。遺傳算法有四個構(gòu)成要素：a) 染色體編碼方法：使用固定長度的二進制符號串來表示群體中的個體，其等位基因是由二值符號集{0，l}所組成的。b) 個體適應(yīng)度評價：基本遺傳算法按與個體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個個體遺傳到下一代群體中的機會多少。c) 遺傳算子：使用比例選擇算子、單點交叉算子、基本位變異算子或均勻變異算子。d) 運行參數(shù)：群體大小 M；遺傳運算的終止進化代數(shù) T乃一般取為 100500；交叉概率 Pc，一般取為 ；變異概率 Pm，一般取為 。對一個需要進行優(yōu)化計算的實際應(yīng)用問題，一般可按下述步驟來構(gòu)造求解該問題的遺傳算法：第一步：確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X和問題的解空間；第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型(是求目標(biāo)函數(shù)的最大值。還是求目標(biāo)函數(shù)的最小值)及其數(shù)學(xué)描述形式或量化方法；第三步：確定表示可行解的染色體編碼方法，即確定出個體的基因型 X及遺傳算法的搜索空間；第四步：確定解碼方法，即確定出由個體基因型 x和個體表現(xiàn)型 X的對應(yīng)關(guān)系或轉(zhuǎn)換方法；第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值 f(x)個體適應(yīng)度 F(X)的轉(zhuǎn)換規(guī)則；第六步：設(shè)計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法；第七步：確定遺傳算法的有關(guān)運行參數(shù)，即確定出遺傳算法的 M，Pc，Pm 等參數(shù)。遺傳算法在機理方面具有搜索過程和優(yōu)化機制等屬性，數(shù)學(xué)方面的性質(zhì)可通過模式定理和積木塊假設(shè)等分析加以討論，Markov 鏈也是分析遺傳算法的一個有效工具。遺傳算法的執(zhí)行過程包括了大量的隨機性操作，因此有必要對其數(shù)學(xué)機理進行分析。模式定理 [15’16’17]是由 John Holland在 1971年提出的，它是 GA的基本定理。它將 GA的運算過程理解為模式運算過程，并從模式運算的角度解釋 GA的性能特點。定義 模式(schema)是一個描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。因此模式也可解釋為相同的構(gòu)形。定義 模式階(schema order)模式 H中確定位置的個數(shù)稱為該模式的階，記作 o(H)。例如：o(011*1*)=4。模式階用來反映不同模式問確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。定義 定義距(defining length)模式 H中的第一個確定位置和最后一個確定位置之間的距離稱為該模式的定義距，記作 δ(H)。例如：δ（011*1**）=4。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。模式定理可以用數(shù)學(xué)形式表示為： (,1)(,)(/)[1()/1()]c mmHttfHPHloP????????式中，m（H,t+1）辨識在 t+1代種群中存在模式 H的個數(shù)f(H)表示在 t代種群包含模式 H的個體平均適應(yīng)度ｌ表示個體長度Pc表示交叉概率Pm表示變異概率δ(H) 表示模式 H的定義距；o（H）表示模式 H的階。模式定理是遺傳算法的基本理論，保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了一種數(shù)學(xué)工具。定義 積木塊(building block)在模式定理中所指的具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式被定義為積木塊。積木塊假設(shè)(Building block hypothesis)[18]低階、短定義距、高平均適應(yīng)度的基因塊通過選擇、交叉和變異等遺傳算子的作用，能夠互相拼接在一起，形成高階、長定義距、高平均適應(yīng)度的模式，最終接近全局最優(yōu)解。滿足這個假設(shè)的條件比較簡單，包括兩方面：a) 表現(xiàn)型相近的個體，其基因型相近；b) 遺傳因子間相關(guān)性低。目前大量的實踐支持積木塊假設(shè)，它在許多領(lǐng)域內(nèi)都取得了成功，例如平滑多峰問題、帶干擾多峰問題以及組合優(yōu)化問題等。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而滿足求最優(yōu)解的必要條件，即遺傳算法存在找到全局最優(yōu)解的可能性；而積木塊假設(shè)指出，遺傳算法具備尋找全局最優(yōu)解的能力，即積木塊在遺傳算子的作用下，能生成低階、短距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。雖然模式定理在一定意義上解決了基本遺傳算法的有效性，但它仍有以下的缺點：a) 模式定理只對二進制編碼適用，對其他編碼方案尚沒有相應(yīng)的結(jié)論成立；b) 模式定理只給出了在下世代包含模式 H的個體數(shù)的下限。我們無法據(jù)此推斷算法的收斂性；c) 模式定理沒有解決算法設(shè)計中控制參數(shù)選取等問題。典型的遺傳算法 CGA[19] (Canonical Geic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：考慮對于一群長度為 L的二進制編碼 bi，i=1，2，…，n；有 bi{0，l}L 給定目標(biāo)函數(shù) f，有 f(bi)0同時 f(bi)≠f(b i+1)，求滿足式max{f(bi)｜b i{0，1}L}的 bi；。很明顯，遺傳算法是一種最優(yōu)化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產(chǎn)生新的解，最后收斂到一個特定的串 bi處，即求出最優(yōu)解。長度為 L的 n個二進制串 bi(i=1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個串中，每個二進制位就是個體染色體的基因。根據(jù)進化術(shù)語，對群體執(zhí)行的操作有三種：a) 選擇(Selection)：這是從群體中選擇出較適應(yīng)環(huán)境的個體。這些選中的個體用于繁殖下一代。故有時也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproduction)。b) 交叉(Crossover)：這是在選中用于繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而產(chǎn)生新的個體。c) 變異(Mutation)：這是在選中的個體中，對個體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串 bi中，如果某位基因為 l，產(chǎn)生變異時就是把它變成 0；反之亦然。遺傳算法的原理可以簡要給出如下：選擇初始值，確定合適的值，完成選擇；進行交叉，變異；重復(fù)直到得到最優(yōu)解這里所指的某種結(jié)束準(zhǔn)則一般是指個體的適應(yīng)度達到給定的閥值；或者個體的適應(yīng)度的變化率為零。遺傳算法是模擬達爾文的生物自然選擇學(xué)說和自然界的生物進化過程的一種自適應(yīng)全局概率搜索算法。在解決具體問題時先大致確定問題的潛在解的一個集合，這個集合就是算法的初始種群。種群由計算機生成(一般是隨機生成)的一定數(shù)目的個體組成，個體就是潛在解的計算機編碼，那么我們最后要求的解就由這些初始生成的個體進化而來的。每個個體具有其自的特征，我們根據(jù)這些個體的不同的特征來確定其存活到下一代的可能性高低，按照優(yōu)勝劣汰的法則，我們由父代來產(chǎn)生子代，如此來繁衍。當(dāng)然在具體的進化過程中為了保持種群多樣性防止過早收斂，還要在其中使個體以一定小概率發(fā)生變異。這樣在最后滿足收斂條件后的種群最優(yōu)個體就是問題的近似最優(yōu)解。遺傳算法的實現(xiàn)過程主要包括編碼、產(chǎn)生群體、計算適應(yīng)度、復(fù)制、交換、變異等操作。概括地講，遺傳算法求解組合優(yōu)化問題的具體步驟可描述如下：(1)初始化：選擇一個群體，即選擇一個串或個體的集合 bi，i=l，2，…n。這個初始的群體也就是問題假設(shè)解的集合。一般取 n=30通常以隨機方法產(chǎn)生串或個體的集合 bi，i=1，2