【文章內(nèi)容簡(jiǎn)介】 NP類(lèi)型的組合優(yōu)化問(wèn)題和多目標(biāo)函數(shù)優(yōu)化問(wèn)題，得到很多學(xué)科的高度重視。在國(guó)內(nèi)，武漢大學(xué)成立了一個(gè)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室。以進(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è)重要分支。 遺傳算法在應(yīng)用方面取得的豐碩成果 ,使人們對(duì)它的發(fā)展前景充滿(mǎn)信心 。 認(rèn)識(shí)到這一點(diǎn) ,遺傳算法的奠基人之一 ,Goldsberg D 戲言 :“ 已不再需要水晶球 ” 。 今 后幾年 ,可以預(yù)期 ,拓廣更加多樣的應(yīng)用領(lǐng)域 ,其中包括各種 遺傳算法 程序設(shè)計(jì)環(huán)境的開(kāi)發(fā)仍將是遺傳算法發(fā)展的主流 。 事實(shí)上這也是本世紀(jì)高新技術(shù)迅速發(fā)展帶有規(guī)律性的特點(diǎn) ,即面向應(yīng)用 。 與此同時(shí) ,這并不意味著理論研究會(huì)被忽視 , 這方面同樣有大量工作要做。例如 : 控制參數(shù)的選擇 ； 交換和突變這兩類(lèi)最重要的算子的確切作用 ； 并行遺傳算法和分布式遺傳算法的研究 ； 其 他類(lèi)型生物機(jī)制的模仿 ,如免疫、 病毒、寄生等 ,以豐富遺傳算法的內(nèi)容 ,等等 。 自然 ,不論從理論還是應(yīng)用的角度看 ,最緊迫的應(yīng)是關(guān)于算法收斂性問(wèn)題的研究 ,特別是過(guò)早收斂的防止 。 這對(duì)遺傳算法的實(shí)際應(yīng)用關(guān)系重大 。 當(dāng)前一個(gè)特別值得重視的趨勢(shì)是一些面向?qū)ο蟮闹悄芗夹g(shù) ,其中主要是模糊邏輯 [8](Fuzzy Logic, FL ),神經(jīng)網(wǎng)絡(luò) [9](Neural Network, NN )以及遺傳算法等的綜合應(yīng)用。眾所周知 ,FL 有較強(qiáng)的知識(shí)表達(dá)能力 ,NN 的長(zhǎng)處在于自學(xué)習(xí) ,它們與遺傳算法相結(jié)合形成新的集成化技術(shù) ,即所謂的 混合智能系統(tǒng) (Hybrid Intellectual System )。 這一思想在 90 年代初逐步形成 ,而由模糊集論的創(chuàng)始人 ,美國(guó) Zadeh LA在 1993 年于漢城召開(kāi)的國(guó)際模糊系統(tǒng)協(xié)會(huì) ( IFSA )第五屆世界會(huì)議首先明確提出隨后在許多有關(guān)的國(guó)際學(xué)術(shù)會(huì)議上得到充分體現(xiàn)。應(yīng)該指出 ,我國(guó)學(xué)者對(duì)這一趨勢(shì)的認(rèn)識(shí)較早 。 例如 ,清華大學(xué)李衍達(dá)院士領(lǐng)導(dǎo)的研究集體在幾乎同一時(shí)期開(kāi)展了這一重要方向的研究 1995年 , Zadeh 在 IFSA 的第六屆世界會(huì)議上再次強(qiáng)調(diào)了這一方向的重要 設(shè)計(jì)（論文）專(zhuān)用紙 5 性 ,并且認(rèn)為上述所謂的混合智能系統(tǒng)的應(yīng)用將覆蓋從消 費(fèi)品生產(chǎn)到核反應(yīng)堆設(shè)計(jì)以至證券管理 ,而 “ 在未來(lái)幾年中可能無(wú)處不在 ” 。 就遺傳算法本身的研究而言 ,應(yīng)該說(shuō) ,我國(guó)起步較晚 ,近幾年才陸續(xù)看到一些介紹性的文章、不多于兩三部的專(zhuān)著以及初步的研究報(bào)告 ，與 國(guó)外工作比較 ,一個(gè)顯著區(qū)別是 ,國(guó)內(nèi)工作多只停留在論文這一層次 ,幾乎沒(méi)有看到具體實(shí)際應(yīng)用 ,與研究成果商品化的差距就更遠(yuǎn) 。 理論研究與實(shí)際應(yīng)用不夠緊密 ,阻礙了我國(guó)高新技術(shù)的迅速發(fā)展 ,幾乎已經(jīng)成為頑癥 。 因此 ,在我國(guó)發(fā)展遺傳算法 ,當(dāng)前應(yīng)該特別重視它的應(yīng)用和推廣普及 。 學(xué)術(shù)界要主動(dòng)和企業(yè)界連手開(kāi)發(fā)遺傳算法的應(yīng)用 ,要重視引進(jìn)或自行研制類(lèi) 似 于 SP licer 的程序設(shè)計(jì)環(huán)境 ,使遺傳算法的應(yīng)用更加方便和快捷 。 國(guó)家組建的工程研究中心應(yīng)該在這方面發(fā)揮更大的作用 。 工科數(shù)學(xué)教育也應(yīng)有所調(diào)整 ,以適應(yīng)高新技術(shù)發(fā)展的需要 。 例如 ,工科運(yùn)籌學(xué)和最優(yōu)化方法的課程應(yīng)該適當(dāng)加入有關(guān)遺傳算法等方面的內(nèi)容 ,以開(kāi)闊學(xué)生的視野 ,同時(shí)也有利于加快傳統(tǒng)課程內(nèi)容的更新 。 遺傳算法的特點(diǎn) a. 算法從問(wèn)題解的串集開(kāi)始搜索，而不是從單一解開(kāi)始。 這是遺傳算法與傳統(tǒng)算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。遺傳算法從串集開(kāi)始搜索，覆蓋面大，利于全局 擇優(yōu)。 b. 求解時(shí)使用特定問(wèn)題的信息極少，容易形成通用算法程序。 由于遺傳算法使用時(shí)應(yīng)值這一信息進(jìn)行搜索，并不需要問(wèn)題導(dǎo)數(shù)等與問(wèn)題直接相關(guān)的信息。遺產(chǎn)算法只需自適應(yīng)值和串編碼等通用信息，故幾乎可以處理任何問(wèn)題。 c. 算法有極強(qiáng)的容錯(cuò)能力。 遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息。通過(guò)選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串。這就是一個(gè)強(qiáng)烈的過(guò)濾過(guò)程，并且是一個(gè)并行濾波機(jī)制。故而，遺傳算法有很高的容錯(cuò)能力。 d. 算法中的選擇、交叉、和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。 這說(shuō)明遺傳算法是采用隨機(jī) 方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。 設(shè)計(jì)（論文）專(zhuān)用紙 6 遺傳算法分類(lèi) （ 1） 混合遺傳算法 單用簡(jiǎn)單的遺傳算法在許多情況下不是十分有效，容易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問(wèn)題，于是提出了多種混合算法。例如， Ackley 推薦的遺傳爬山法；Mathefoud 提出的遺傳模擬退火算法；采用遺傳算法中增加局部改善運(yùn)算等等?；旌线z傳算法的基本思想是：對(duì)于每個(gè)新產(chǎn)生的后代在其進(jìn)入下一代群體之前應(yīng)用局部?jī)?yōu)化技術(shù) (如爬山法、模擬退火算法等 )，使之移動(dòng)到最近的局部最優(yōu) 點(diǎn)。在混合遺傳算法中，運(yùn)用啟發(fā)式方法作局部?jī)?yōu)化，采用遺傳算法作全局最優(yōu)點(diǎn)的探索。由于遺傳算法與傳統(tǒng)優(yōu)化方法的互補(bǔ)性，混合遺傳算法通常比單一算法優(yōu)越。 （ 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)題受到重視。并行遺傳算法主要從下列四個(gè)方面對(duì)其進(jìn)行改進(jìn)和發(fā)展。 。 個(gè)體適應(yīng)度的評(píng)價(jià) 或計(jì)算 在遺傳算法的運(yùn)行過(guò)程中所占用的運(yùn)行時(shí)間比較長(zhǎng)。通過(guò)對(duì)個(gè)體適應(yīng)度并行計(jì)算方法的研究可找到并行評(píng)價(jià)個(gè)體適應(yīng)度的算法。 互依賴(lài)關(guān)系，這樣各個(gè)個(gè)體的適應(yīng)度計(jì)算過(guò)程就可以相互獨(dú)立、并行地進(jìn)行。即不同個(gè)體的適應(yīng)度計(jì)算可以在不同的處理機(jī)上同時(shí)進(jìn)行。 。 在父代 群體產(chǎn)生下一代群體過(guò)程中，選擇操作只與個(gè)體的適應(yīng)度有關(guān)，而交叉和變異操作只與參加運(yùn)算的個(gè)體編碼有關(guān)。這樣，產(chǎn)生群體過(guò)程中的選擇、交叉、變異操作就可以相互獨(dú)立地并行進(jìn)行。 。 可以對(duì)群體按一定的方式進(jìn)行分組，分組后各組的個(gè)體遺傳進(jìn)化過(guò)程可以在不同的處理機(jī)上相互獨(dú)立地進(jìn)行，在適當(dāng)?shù)臅r(shí)候，各處理機(jī)之間相互交換信息。 設(shè)計(jì)（論文）專(zhuān)用紙 7 遺傳算法的應(yīng)用 目前，遺傳算法在很多科學(xué)、工程領(lǐng)域得到廣泛的應(yīng)用。其典型應(yīng)用領(lǐng)域如下。 。隨著組合優(yōu)化問(wèn)題規(guī)模的增加，其搜索空間也急劇增加，在計(jì)算機(jī)上用窮舉法不可能求出其最優(yōu)解，而遺傳算法可以在此類(lèi)問(wèn)題上尋求問(wèn)題的滿(mǎn)意解。目前， 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)域。學(xué)者構(gòu)造了各種復(fù)雜的測(cè)試函數(shù)，既有連續(xù)函數(shù)也有離散函數(shù)，有高維的也有低維的，有凹的也有凸的，有多峰的也有單峰的，遺傳算法較其他優(yōu)化方法便于得到較好的結(jié)果。函數(shù)優(yōu)化也是對(duì)遺傳算法進(jìn)行評(píng)價(jià)的常用工具。 ，遺傳算法在自動(dòng)控制領(lǐng)域的應(yīng)用日益增加并取得了較好的成果。目前 GA 進(jìn)行系統(tǒng)辨識(shí)、模糊控制器設(shè)計(jì)、航空系統(tǒng)的優(yōu)化等方面取得了一定的成就。 。遺傳算法在圖像的處理的圖像恢復(fù)、圖像邊緣特征提取方面得到了成功應(yīng)用。 器學(xué)習(xí)。目前基于 GA 的機(jī)器學(xué)習(xí)在很多領(lǐng)域得到了應(yīng)用。例如：利用 GA的機(jī)器學(xué)習(xí)來(lái)調(diào)整人工神經(jīng)網(wǎng)絡(luò)的權(quán)值等；利用 GA學(xué)習(xí)模糊控制的奴隸度函數(shù)以改進(jìn)模糊控制系統(tǒng)的性能。 。數(shù)據(jù)挖掘就是大型數(shù)據(jù)庫(kù)中提取人們感興趣的、隱含的、有潛在應(yīng)用價(jià)值的知識(shí)。數(shù)據(jù)挖掘問(wèn)題可以看做是搜索問(wèn)題，把數(shù)據(jù)庫(kù)看作是搜索空間，而把挖掘算法看作搜索策略，這樣就可以使用遺傳算法對(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ī)則。 本文主要工作 a. 介紹了 01 背包 問(wèn)題的概念，接著論述求解該問(wèn)題的各種傳統(tǒng)算法，并對(duì) 01背包問(wèn)題進(jìn)行數(shù)學(xué)描述。 設(shè)計(jì)（論文）專(zhuān)用紙 8 b. 對(duì)遺傳算法進(jìn)行了理論研究。介紹了進(jìn)化算法的基本理論，對(duì)典型的幾種進(jìn)化算法進(jìn)行了簡(jiǎn)要說(shuō)明，并對(duì)遺傳算法的基本理論、應(yīng)用情況和研究趨勢(shì)做了較為詳細(xì)的論述。 c. 應(yīng)用遺傳算法解決 01背包問(wèn)題，通過(guò)設(shè)置不同參數(shù)探究遺傳算法求解背包問(wèn)題的可行性并將算法在 Matlab 仿真平臺(tái)上進(jìn)行實(shí)現(xiàn)。 d. 在 matlab 環(huán)境中進(jìn)行 GUI 界面設(shè)計(jì)， 運(yùn)行界面中遺傳算法主要的參數(shù)可通過(guò)手動(dòng)輸入自行修改，同時(shí)通過(guò) GUI 界面可以直接觀察到仿真曲線的變化情況。 設(shè)計(jì)（論文）專(zhuān)用紙 9 第二章 基于遺傳算法的 01 背包問(wèn)題研究 遺傳算法的思想 遺傳算法是模擬生物在自然界中的遺產(chǎn)進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早是有沒(méi)過(guò)密歇根大學(xué)的 Holland 教授提出的，起源于 60 年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究 [13]。 70 年代 Dc Jong 基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn) [14]。在一系列研究工作基礎(chǔ)上。 80 年代有Goldberg 進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。 生物進(jìn)化是以集團(tuán)為主體的，與此相適應(yīng)的，遺傳算法的運(yùn)算對(duì)象 是由 M個(gè)個(gè)體所組成的集合，成為群體。與生物一代一代的自然進(jìn)化過(guò)程相似，遺傳算法也是一個(gè)反復(fù)迭代的過(guò)程，第 t 代群體記作 P（ t）經(jīng)過(guò)一代遺傳和進(jìn)化之后，得到第 t+1 代群體，它們是由多個(gè)個(gè)體組成的集合記作 P（ t+1）。這個(gè)群體不斷的經(jīng)過(guò)遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多的遺傳到下一代，這樣最終在種群中將會(huì)得到一個(gè)優(yōu)良的個(gè)體 X，它所對(duì)應(yīng)的的表現(xiàn)型 X 將達(dá)到或接近問(wèn)題的最優(yōu)解 X*。 遺傳算法有四個(gè)構(gòu)成要素： a) 染色體編碼方法：使用固定長(zhǎng)度的二進(jìn)制符號(hào)串來(lái)表示群體中的個(gè)體，其等位基因是由二值 符號(hào)集 {0， l}所組成的。 b) 個(gè)體適應(yīng)度評(píng)價(jià)：基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。 c) 遺傳算子：使用比例選擇算子、單點(diǎn)交叉算子、基本位變異算子或均勻變異算子。 d) 運(yùn)行參數(shù)：群體大小 M；遺傳運(yùn)算的終止進(jìn)化代數(shù) T 乃一般取為 100500；交叉概率 Pc，一般取為 ；變異概率 Pm，一般取為 。 對(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ù)的最大值。還是求目標(biāo)函數(shù)的最小值 )及其數(shù)學(xué)描述形式或量化方法； 第三步：確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型 X及遺傳算法的搜索空間； 第四步：確定解碼方法，即確定出由個(gè)體基因型 x 和個(gè)體表現(xiàn)型 X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法； 第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值 f(x)個(gè)體適應(yīng)度 F(X)的轉(zhuǎn)換規(guī)則； 第六步：設(shè)計(jì)遺傳算子，即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法； 第七步：確定遺傳算法 的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M， Pc， Pm等參數(shù)。 遺傳算法的數(shù)學(xué)基礎(chǔ) 遺傳算法在機(jī)理方面具有搜索過(guò)程和優(yōu)化機(jī)制等屬性，數(shù)學(xué)方面的性質(zhì)可通過(guò)模式定理和積木塊假設(shè)等分析加以討論， Markov 鏈也是分析遺傳算法的一個(gè)有效工具。遺傳算法的執(zhí)行過(guò)程包括了大量的隨機(jī)性操作，因此有必要對(duì)其數(shù)學(xué)機(jī)理進(jìn)行分析。 模式定理 [15’ 16’ 17]是由 John Holland 在 1971 年提出的，它是 GA的基本定理。它將 GA 的運(yùn)算過(guò)程理解為模式運(yùn)算過(guò)程，并從模式運(yùn)算的角度解釋 GA 的性能特點(diǎn)。 定義 模式 (schema)是一個(gè)描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。因此模式也可解釋為相同的構(gòu)形。 定義 模式階 (schema order)模式 H 中確定位置的個(gè)數(shù)稱(chēng)為該模式的階，記作 o(H)。例如： o(011*1*)=4。 模式階用來(lái)反映不同模式問(wèn)確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本個(gè)數(shù)就越少。 設(shè)計(jì)（論文）專(zhuān)用紙 11 定義 定義距 (defining length)模式 H 中的第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱(chēng)為該模式的定義距，記作δ (H)。例如：δ（ 011*1**） =4。 在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)。模式定理可以用數(shù)學(xué)形式表示為： ( , 1 ) ( , ) ( (