遺傳算法的理論研究綜述_圖文

1、收稿日期 :2003-10-18作者簡介 :馬玉明 (1972- , 女 , 山東省聊城市人 , 山東輕工業(yè)學院講師 , 碩士研究生 , 主要從事自動控制和遺傳算法的研究。遺傳算法的理論研究綜述馬玉明 , 賀愛玲 , 李愛民(山東輕工業(yè)學院 計算機科學技術系 , 山東 濟南 250100摘要 : 本文簡單回顧了遺傳算法的發(fā)展歷史 , 并對遺傳算法的理論從數學基礎和改進兩個方面進行了 綜述。關鍵詞 : 遺傳算法 ; 模式定理 ; 隱性并行性中圖分類號 :TP18 文獻標識碼 :A ( -04遺傳算法 G A (G enetic 上 , 。這種算法的產生歸功于美國的 Michigan 世紀 60年

2、代末 70年代初的開創(chuàng)性工作 ,H olland 不僅設計了 , 運用統(tǒng)計決策理論對遺傳算法的搜索機理進行了分析 , 還建立了 著名的模式定理和隱性并行性原理 , 為遺傳算法的發(fā)展奠定了基礎 。在過去的三十多年里 , 人們對遺傳算法進行了大量的研究 , 從大的方面分 , 這些研究可分 為兩大類 , 即遺傳算法的應用研究和遺傳算法的理論研究 。由于遺傳算法本身具備良好的全 局搜索能力 , 信息處理的隱含并行性 , 魯棒性 , 可規(guī)模化等優(yōu)良特點 , 因此被應用于各種領域 , 例如 :自動控制 、 約束優(yōu)化 、 數據挖掘等 , 并滲透到其它許多學科如計算數學 、 交通、 計算機科 學 、 電子學等

3、 。1 遺傳算法的理論研究遺傳算法的基本步驟是編碼生成初始種群 , 爾后使用選擇 、 交叉和變異等基因操作 , 進行 有組織而又隨機的信息交換 , 使優(yōu)良品質被逐漸不斷地繼承下來 , 壞的特性被淘汰 。 遺傳算法 的理論研究主要有遺傳算法的數學基礎研究和遺傳算法的改進 。1. 1 數學基礎研究模式定理及隱含并行性原理被看作遺傳算法的兩大基石 , 后來又提出了建筑塊假設 , 但是 模式定理無法解釋遺傳算法實際操作中的許多現象 , 隱性并行性的論證存在嚴重漏洞 , 而建筑 塊假設卻從未得到過證明 。 對遺傳算法的基礎理論的研究主要分三個方面 :模式定理的拓廣 和深入 、 遺傳算法的新模型 、 遺傳

4、算法的收斂性理論 。1. 1. 1 模式定理的拓廣和深入H olland 給出模式定理 :具有短的定義長度 、 低階 、 并且模式采樣的平均適應值在種群平均 第 18卷第 3期2004年 9月 山 東 輕 工 業(yè) 學 院 學 報 JOURNA L OF SHANDONG INSTIT UTE OF LIGHT INDUSTRY Vol. 18No. 3Sep. 2004適應值以上的模式 , 在遺傳迭代過程中將按指數增長率被采樣 , 模式定理可表達為m (H , t +1 m (H , t f (1-p c l -1-O (H p m 其中 m (H , t :在 t 代群體中存在模式 H 的串

5、的個數f (H :在 t 代群體中包含模式 H 的串的平均適應值f :t 代群體中所有串的平均適應值l 表示串的長度 , p c 表示交換概率 , p m 表示變異概率 。H olland 的模式定理奠定了遺傳算法的數學基礎 , 根據隱性并行性得出每一代處理有效模 式的下限值是 n 3(C 1l 12 , 其中 n 是種群的大小 , C l 是小整數 。 Bertoui 和 Dorig o 進行了深入 的研究獲得當 n =2l , 為任意值時 , 處理多少有效模式的表達式 。 上海交通大學的惲為民等 獲得每次至少產生 O (2n -1 數量級的結果 。模式定理中模式適應度難以計算和分析 ,A.

6、 D.算法的模式處理 , 并引入模式變換的概念 , 采用均適應度 , G A 從全局最 最早運用 Walsh 模式轉換設計出最小的 G A -。1. 1. 2由于遺傳算法中的模式定理和隱性并行性存在不足之處 , 為了搞清楚遺傳算法的機理 , 近 幾年來人們建立了各種形式的新模型 , 最為典型的是馬氏鏈模型 , 遺傳算法的馬氏鏈模型主要 由三種 , 分別是種群馬氏鏈模型 、 Vose 模型和 Cerf 擾動馬氏鏈模型 。種群馬氏鏈模型將遺傳算法的種群迭代序列視為一個有限狀態(tài)馬氏鏈來加以研究 , 運用 種群馬氏鏈模型轉移概率矩陣的某些一般性質 , 分析遺傳算法的極限行為 , 但轉移概率的具體 形式

7、難以表達 , 妨礙了對遺傳算法的有限時間行為的研究 ;Vose 模型是在無限種群假設下 , 利 用相對頻率 , 導出表示種群的概率的向量的迭代方程 , 通過這一迭代方程的研究 , 可以討論種 群概率的不動點及其穩(wěn)定性 , 從而導致對遺傳算法的極限行為的刻劃 , 但對解釋有限種群遺傳 算法的行為的能力相對差一些 。 Cerf 擾動模型是法國學者 Cerf 將遺傳算法看成一種特殊形式 的廣義模擬退火模型 , 利用了動力系統(tǒng)的隨機擾動理論 , 對遺傳算法的極限行為及收斂速度進 行了研究 。還有其它它改進模型 , 例如張鈴 、 張鈸等人提出的理想濃度模型 , 它首先引入濃度和家族 的概念 , 通過濃度

8、計算建立理想濃度模型 , 其濃度變化的規(guī)律為 :c (H i , t +1 =c (H , t f (H i (0 , t f (t c (H i , t +1 表示模式 H i 在 t 時刻的濃度 , 并對其進行分析 , 得出結論 :遺傳算法本質上是 一個具有定向制導的隨機搜索技術 , 其定向制導原則是導向適應度高的模式為祖先的染色體 “ 家族” 方向 。1. 1. 3 遺傳算法的收斂性理論對于遺傳算法的馬氏鏈分析本身就是建立遺傳算法的收斂性理論 ,Eiben 等用馬爾可夫鏈 證明了保留最優(yōu)個體的遺傳算法的概率性全局收斂 ,Rudolph 用齊次有限馬爾可夫鏈證明了具 有復制 、 交換 、

9、突變操作的標準遺傳算法收斂不到全局最優(yōu)解 , 不適合于靜態(tài)函數的優(yōu)化問題 , 87山 東 輕 工 業(yè) 學 院 學 報 第 18卷97第 3期 馬玉明等 :遺傳算法的理論研究綜述 A survery o f the theory o f genetic algorithmMA Yu -ming , HE Ai -ling , LI Ai -min(Department of C om puter Science &techn ology ,shand ong Institute of Light Industry , Jinan 250100,China Abstract :Thispaper offers a sim ple overview of history of G enetic Alg orithm ,and conducts a survey of the theory of G enetic Alg orithm which includes the mathematic