【正文】 19 努力的方向 19 參考文獻(xiàn) 20 致 謝 21 附 錄 22 1 1 引言 遺傳算法 (Geic Algorithm)是模擬自然界生物進(jìn)化機(jī)制的一種算法即遵循適者生存 、 優(yōu)勝劣汰的法則也就是尋優(yōu)過(guò)程中有用的保留無(wú)用 的則去除 . 在科學(xué)和生產(chǎn)實(shí)踐中表現(xiàn)為在所有可能的解決方法中找出最符合該問(wèn)題所要求的條件的解決方法即找出一個(gè)最優(yōu)解 . 這種算法是 1960年由 Holland提出來(lái)的其最初的目的是研究自然系統(tǒng)的自適應(yīng)行為并設(shè)計(jì)具有自適應(yīng)功能的軟件系統(tǒng) . 它的特點(diǎn)是對(duì)參數(shù)進(jìn)行編碼運(yùn)算不需要有關(guān)體系的任何先驗(yàn)知識(shí)沿多種路線(xiàn)進(jìn)行平行搜索不會(huì)落入局部較優(yōu)的陷阱 ， 能在許多局部較優(yōu)中找到全局最優(yōu)點(diǎn)是一種全局最優(yōu)化方法 [13]. 近年來(lái) ， 遺傳算法已經(jīng)在國(guó)際上許多領(lǐng)域得到了應(yīng)用 . 該 文將從遺傳算法的理論和技術(shù)兩方面概述目前的研究現(xiàn)狀 描述遺傳算 法的主要特點(diǎn) 、 基本原理以及 改進(jìn)算法 ， 介紹遺傳算法的應(yīng)用領(lǐng)域 ， 并 用 MATLAB實(shí)現(xiàn)了 遺傳算法 及最優(yōu)解的求解 . 2 文獻(xiàn)綜述 國(guó)內(nèi) 外 有不少的專(zhuān)家和學(xué)者對(duì)遺傳算法的進(jìn)行 研究與 改進(jìn) . 比如 ： 1991年 在他的論文中提出了基于領(lǐng)域交叉的交叉算子 （ ADJACENCY BASED CROSSOVER），這個(gè)算子是特別針對(duì)用序號(hào)表示基因的個(gè)體的交叉， 并將其應(yīng)用到了 TSP問(wèn)題中，通過(guò)實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證 . 2021年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想 ，對(duì)不同種群基于不同的遺傳策略，如 變異概率，不同的變異算子等來(lái)搜索變量空間 ，并利用種群間遷移算子來(lái)進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法 的收斂到局部最優(yōu)值問(wèn)題 . 國(guó)內(nèi)外很多文獻(xiàn)都對(duì)遺傳算法進(jìn)行了研究 . 現(xiàn) 查閱到的國(guó)內(nèi)參考文獻(xiàn) [119]中 , 周勇、周明 分別 在文獻(xiàn) [1]、 [2]中 介紹了 遺傳算法的 基本原理；徐宗本在文獻(xiàn) [3]中探討了包括遺傳算法在內(nèi)的解全局優(yōu)化問(wèn)題的各類(lèi)算法 ，文本次論文寫(xiě)作提出了明確的思路；張文修 、 王小平、張鈴分別 在文獻(xiàn) [4]、 [5]、 [6]從遺傳算法的理論和技術(shù)兩方面概述目前的研 究現(xiàn)狀；李敏強(qiáng)、 吉根林、 玄光南分別 在文獻(xiàn) [7]、 [8]、 [9]中都不同程度的介紹了遺傳算法的特點(diǎn)以及改進(jìn)算法但未進(jìn)行深入研究； 馬玉明、張麗萍、戴曉輝、柴天佑 分別 在文獻(xiàn) [10]、[11]、 [12]、 [13]中探討了遺傳算法產(chǎn)生的背景、起源和發(fā)展； 李敏強(qiáng)、徐小龍、林丹、張文修 分別 在文獻(xiàn) [14]、 [15]、 [16]、 [17]探討了遺傳算法的發(fā)展現(xiàn)狀及以后的發(fā)展動(dòng)向； 李敏強(qiáng)，寇紀(jì)凇，林丹，李書(shū)全在 文獻(xiàn) [18]中主要論述了 遺傳算法的 具體的實(shí)施步 2 驟、應(yīng)用領(lǐng)域及特點(diǎn) ； 孫祥，徐流 美 在文獻(xiàn) [19]中 主要介紹了 Matlab的編程語(yǔ)句及基本用法 . 所有的參考文獻(xiàn)都從不同 角度 不 同程度的介紹了 遺傳算法但都不夠系統(tǒng)化不夠詳細(xì)和深入 . 隨著研究的深入 ， 人們逐漸認(rèn)識(shí)到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能 ， 也不現(xiàn)實(shí) ， 因而求出近似最優(yōu)解或滿(mǎn)意解是人們的主要著眼點(diǎn)之一 . 很多人構(gòu)造出了各種各樣的復(fù)雜形式的測(cè)試函數(shù) ， 有連續(xù)函數(shù) ， 有離散函數(shù) ， 有凸函數(shù) ， 也有凹函數(shù) ， 人們用這些幾何特性各異的函數(shù)來(lái)評(píng)價(jià)遺傳算法的性能 . 而對(duì)于一些非線(xiàn)性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題用其他優(yōu)化方法較難求解遺傳算法卻可以方便地得到較好的結(jié)果 . 鑒于遺傳算法在函數(shù)優(yōu)化方面的重要性 ， 該文在參考文獻(xiàn) [119]的基礎(chǔ)上 ，用 Matlab語(yǔ)言編寫(xiě)了遺傳算法程序 , 并通過(guò)了調(diào)試用一個(gè)實(shí)際例子來(lái)對(duì)問(wèn)題進(jìn)行了驗(yàn)證 ， 這對(duì)在 Matlab環(huán)境下用遺傳算法來(lái)解決優(yōu)化問(wèn)題有一定的意義 . 3 遺傳算法的理論研究 科學(xué)研究、工程實(shí)際與國(guó)民經(jīng)濟(jì)發(fā)展中的眾多問(wèn)題可歸結(jié)作 “ 極大化效益、極小化代價(jià) ” 這類(lèi)典型模型 . 求解這類(lèi)模型導(dǎo)致尋求某個(gè)目標(biāo)函數(shù)（有解析表達(dá)式或無(wú)解析表達(dá)式）在特定區(qū)域上的最優(yōu)解 . 而為解決最優(yōu)化問(wèn)題目標(biāo)函數(shù)和約束條件種類(lèi)繁多 ， 有的是線(xiàn)性的 ， 有的是非線(xiàn)性的 ； 有的是連續(xù)的 ， 有的是離散的 ； 有的是單 峰值的 ， 有的是多峰值的 . 隨著研究的深入 ， 人們逐漸認(rèn)識(shí)到 ： 在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能 ， 也不現(xiàn)實(shí) ， 因而求出近似最優(yōu)解或滿(mǎn)意解是人們的主要著眼點(diǎn)之一 . 總的來(lái)說(shuō) ， 求最優(yōu)解或近似最優(yōu)解的方法有三種 : 枚舉法、啟發(fā)式算法和搜索算法 . (1)枚舉法 . 枚舉出可行解集合內(nèi)的所有可行解以求出精確最優(yōu)解 . 對(duì)于連續(xù)函數(shù) ， 該方法要求先對(duì)其進(jìn)行離散化處理 ， 這樣就有可能產(chǎn)生離散誤差而永遠(yuǎn)達(dá)不到最優(yōu)解 . 另外 ， 當(dāng)枚舉空間比較大時(shí)該方法的求解效率比較低 ， 有時(shí)甚至在目前最先進(jìn)的計(jì)算工具上都無(wú)法求解 . (2)啟發(fā) 式算法 . 尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則以找到一個(gè)最優(yōu)解或近似最優(yōu)解 . 該方法的求解效率雖然比較高 ， 但對(duì)每一個(gè)需要求解的問(wèn)題都必須找出其特有的 3 啟發(fā)式規(guī)則 ， 這個(gè)啟發(fā)式規(guī)則無(wú)通用性不適合于其它問(wèn)題 . (3)搜索算法 . 尋求一種搜索算法 ， 該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作以找到問(wèn)題的最優(yōu)解或近似最優(yōu)解 . 該方法雖然保證了一定能夠得到問(wèn)題的最優(yōu)解 ， 但若適當(dāng)?shù)乩靡恍﹩l(fā)知識(shí)就可在近似解的質(zhì)量和求解效率上達(dá)到一種較好的平衡 . 隨著問(wèn)題種類(lèi)的不同以及問(wèn)題規(guī)模的擴(kuò)大 ， 要尋求一種能以有限的代價(jià)來(lái)解決上述最優(yōu)化問(wèn)題 的通用方法仍是一個(gè)難題 . 而遺傳算法卻為我們解決這類(lèi)問(wèn)題提供了一個(gè)有效的途徑和通用框架開(kāi)創(chuàng)了一種新的全局優(yōu)化搜索算法 . 遺傳算法的起源 50年代末到 60年代初 ， 自然界生物進(jìn)化的理論被廣泛接受生物學(xué)家 Fraser， 試圖通過(guò)計(jì)算的方法來(lái)模擬生物界“遺傳與選擇”的進(jìn)化過(guò)程 ， 這是遺傳算法的最早雛形 . 受一些生物學(xué)家用計(jì)算機(jī)對(duì)生物系統(tǒng)進(jìn)行模擬的啟發(fā) ， Holland開(kāi)始應(yīng)用模擬遺傳算子研究適應(yīng)性 . 在 1967年 ， Bagley關(guān)于自適應(yīng)下棋程序的論文中 ， 他應(yīng)用遺傳算法搜索下棋游戲評(píng) 價(jià)函數(shù)的參數(shù)集并首次提出了遺傳算法這一術(shù)語(yǔ) . 1975年 ， Holland出版了遺傳算法歷史上的經(jīng)典著作《自然和人工系統(tǒng)中的適應(yīng)性》 ， 首次明確提出遺傳算法的概念 . 該著作中系統(tǒng)闡述了遺傳算法的基本理論和方法 ， 并提出了模式 (schemat atheorem)[4]，證明在遺傳算子選擇、交叉和變異的作用下具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將以指數(shù)級(jí)增長(zhǎng) . Holand創(chuàng)建的遺傳算法 ， 是基于二進(jìn)制表達(dá)的概率搜索方法 . 在種群中通過(guò)信息交換重新組合新串 ； 根據(jù)評(píng)價(jià)條件概率選擇適應(yīng)性好的串進(jìn) 入下一代 ； 經(jīng)過(guò)多代進(jìn)化種群最后穩(wěn)定在適應(yīng)性好的串上 . Holand最初提出的遺傳算法被認(rèn)為是簡(jiǎn)單遺傳算法的基礎(chǔ) ， 也稱(chēng)為標(biāo)準(zhǔn)遺傳算法 . 遺傳算法的發(fā)展 (1)20世紀(jì) 60年代 ， John Holland教授和他的數(shù)位博士受到生物模擬技術(shù)的啟發(fā) ，認(rèn)識(shí)到自然遺傳可以轉(zhuǎn)化為人工遺傳算法 . 1962年 ， John Holland提出了利用群體進(jìn)化模擬適應(yīng)性系統(tǒng)的思想 ， 引進(jìn)了群體、適應(yīng)值、選擇 、 變異、交叉等基本概念 . (2)1967年 ， “遺傳算法”的概念 . (3)1975年 ， Holland出版了《自然與人工系統(tǒng)中的適應(yīng)性行為》（ Adaptation in Natural and Artificial System） .該書(shū)系統(tǒng)地闡述了遺傳算法的基本理論和方法 ， 提出了遺傳算法的基本定理 — 模式定理 ， 從而奠定了遺傳算法的理論基礎(chǔ) . 同年 De Jong 4 在其博士論文中 ， 首次把遺傳算法應(yīng)用于函數(shù)優(yōu)化問(wèn)題對(duì)遺傳算法的機(jī)理與參數(shù)進(jìn)行了較為系統(tǒng)地研究并建立了著名的五函數(shù)測(cè)試平臺(tái) . (4)20世紀(jì) 80年代初 ， Holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng) — 分類(lèi)器系統(tǒng)（ Classifier System簡(jiǎn)稱(chēng) CS） ， 開(kāi)創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念 . (5)1989年 ， David Goldberg出版了《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（ Geic Algorithms in Search Optimization and Machine Learning） .該書(shū)全面系統(tǒng)地總結(jié)了當(dāng)時(shí)關(guān)于遺傳算法的研究成果 ， 結(jié)合大量的實(shí)例完整的論述了遺傳算法的基本原理及應(yīng)用 ， 奠定了現(xiàn)代遺傳算法的基礎(chǔ) . (6)1992年 ， John 《遺傳編程》（ Geic Programming）提出了遺傳編程的概念 ， 并成功地把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號(hào)處理等方面 . 隨著遺傳算法的不斷深入和發(fā)展 ， 關(guān)于遺傳算法的國(guó)際學(xué)術(shù)活動(dòng)越來(lái)越多 ， 遺傳算法已成為一個(gè)多學(xué)科、多領(lǐng)域的重要研究方向 . 今天遺傳算法的研究已經(jīng)成為國(guó)際學(xué)術(shù)界跨學(xué)科的熱門(mén)話(huà)題之一 . 遺傳算法是一種有廣泛應(yīng)用前景的算法 ， 但是它的研究和應(yīng)用在國(guó)內(nèi)尚處于起步階段 . 近年來(lái)遺傳算法已被成功地應(yīng)用于工業(yè)、經(jīng)濟(jì)管理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(lǐng)域解決了許多問(wèn)題 .例如可靠性?xún)?yōu)化、流水車(chē)間調(diào)度、作業(yè)車(chē)間調(diào)度、機(jī)器調(diào)度、設(shè)備布局設(shè)計(jì)、 圖像處理以及數(shù)據(jù)挖掘等 . 遺傳算法的 數(shù)學(xué)基礎(chǔ)研究 模式定理及隱含并行性原理被看作遺傳算法的兩大基石 ， 后來(lái)又提出了建筑塊假設(shè) ， 但是模式定理無(wú)法解釋遺傳算法實(shí)際操作中的許多現(xiàn)象 ， 隱性并行性的論證存在嚴(yán)重漏洞 ， 而建筑塊假設(shè)卻從未得到過(guò)證明 . 對(duì)遺傳算法的基礎(chǔ)理論的研究主要分三個(gè)方面 ： 模式定理的拓廣和深入、遺傳算法的新模型、遺傳算法的收斂性理論 . (1)模式定理的拓廣和深入 . Holland給出模式定理 ： 具有短的定義長(zhǎng)度、低階、并且模式采樣的平均適應(yīng)值在種群平均適應(yīng)值以上的模式在遺傳迭代過(guò)程中將按指數(shù)增長(zhǎng)率 被采樣模式定理可表達(dá)為 ： m(H,t+1)? m(H,t). ? ?fHf. ? ? ?????? ??? PHOlP mHc . ? (1) 其中 m(Ht)： 在 t代群體中存在模式 H 的串的個(gè)數(shù) . 5 ? ?Hf ： 在 t 代群體中包含模式 H 的串的平均適應(yīng)值 . f ： t代群體中所有串的平均適應(yīng)值 . l 表示 串的長(zhǎng)度 pc 表示交換概率 pm 表示變異概率 . Holland的模式定理奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)根據(jù)隱性并行性得出每一代處理有效模式的下限值是 ? ?l 2113 .其中 n是種群的大小 c1 是小整數(shù) . Bertoui和 Dorigo進(jìn)行了深入的研究獲得當(dāng) 2?ln? ,β 為任意值時(shí)處理多少有效模式的表達(dá)式 . 上海交通大學(xué)的惲為民等獲得每次 至少產(chǎn)生 ? ?21?no 數(shù)量級(jí)的結(jié)果 . 模式定理中模式適應(yīng)度難以計(jì)算和分析 Walsh函數(shù)進(jìn)行遺傳算法的模式處理并引入模式變換的概念采用 Walsh函數(shù)的離散形式有效地計(jì)算出模式的平均適應(yīng)度并對(duì)遺傳算法進(jìn)行了有效的分析 . 1972年 Frantz首先發(fā)現(xiàn)一種常使 GA從全局最優(yōu)解發(fā)散出去的問(wèn)題 ， 稱(chēng)為 GA欺騙 題 [5]. Goldberg最早運(yùn)用 Walsh模式轉(zhuǎn)換設(shè)計(jì)出最小的 GA欺騙問(wèn)題并進(jìn)行了詳細(xì)分析 . (2)遺傳算法的新模型 . 由于遺傳算法中的模式 定理和隱性并行性存在不足之處 ，為了搞清楚遺傳算法的機(jī)理 ， 近幾年來(lái)人們建立了各種形式的新模型最為典型的是馬氏鏈模型遺傳算法的馬氏鏈模型 [67]， 主要由三種分別是種群馬氏鏈模型、 Vose模型和 Cerf 擾動(dòng)馬氏鏈模型 . 種群馬氏鏈模型將遺傳算法的種群迭代序列視為一個(gè)有限狀態(tài)馬氏鏈來(lái)加以研究 ， 運(yùn)用種群馬氏鏈模型轉(zhuǎn)移概率矩陣的某些一般性質(zhì)分析遺傳算法的極限行為 ， 但轉(zhuǎn)移概率的具體形式難以表達(dá)妨礙了對(duì)遺傳算法的有限時(shí)間行為的研究 ； Vose模型是在無(wú)限種群假設(shè)下利用相對(duì)頻率導(dǎo)出 ， 表示種群的概率的向量的迭代方程 ， 通過(guò)這一 迭代方程的研究 ， 可以討論種群概率的不動(dòng)點(diǎn)及其穩(wěn)定性 ， 從而導(dǎo)致對(duì)遺傳算法的極限行為的 刻畫(huà) ， 但對(duì)解釋有限種群遺傳算法的行為的能力相對(duì)差一些 . Cerf擾動(dòng)模型是法國(guó)學(xué)者 Cerf將遺傳算法看成一種特殊形式的廣義模擬退火模型 ， 利用了動(dòng)力系統(tǒng)的隨機(jī)擾動(dòng)理論 ， 對(duì)遺傳算法的極限行為及收斂速度進(jìn)行了研究 . 還有其它改進(jìn)模型 ， 例如張鈴、張鈸等人提出的理想濃度模型 ， 它首先引入濃度和家族的概念 ， 通過(guò)濃度計(jì)算建立理想濃度模型 [810]， 其濃度變化的規(guī)律為 ： 6 c(Hi， t +1)=c(H， t). ? ?? ?? ?tf tOHf i , (2) c(Hi， t+1)表示模式 Hi在 t時(shí)刻的濃度 ， 并對(duì)其進(jìn)行分析 ， 得出結(jié)論 ： 遺傳算法本質(zhì)上是一個(gè)具有定向制導(dǎo)的隨機(jī)搜索技術(shù) ， 其定向制導(dǎo)原則是導(dǎo)向適應(yīng)度高的模式為祖先的染色體“家族”方向 . (3)遺傳算法的收斂性理論 . 對(duì)于遺傳算法的馬氏鏈分析本身就是建立遺傳算法的收斂性理論 [1112]， Eiben等用馬爾可夫鏈證明了保留最優(yōu)個(gè)體的遺傳算法的概率性全局收斂 ， Rudolph用齊次有限馬爾可夫 鏈證明了具有復(fù)制、交換、突變操作的標(biāo)準(zhǔn)遺傳算法收斂不到全局最優(yōu)解 ， 不適合于靜態(tài)函數(shù)的優(yōu)化問(wèn)題 ， 建議改變復(fù)制策略以達(dá)到全局收斂 ， Back和 Muhlenbein研究了達(dá)到全局最優(yōu)解的算法的時(shí)間復(fù)雜性問(wèn)題 ， 近 幾年 ， 徐宗本等人建立起鞅序列模型 ， 利用鞅序列收斂定理證明了遺傳算法的收斂性 . 遺傳算法所涉及的五大要素 ： 參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺