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

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

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

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

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

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

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

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

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

9、突變操作的標(biāo)準(zhǔn)遺傳算法收斂不到全局最優(yōu)解 , 不適合于靜態(tài)函數(shù)的優(yōu)化問題 , 87山 東 輕 工 業(yè) 學(xué) 院 學(xué) 報(bào) 第 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