【文章內(nèi)容簡介】 應(yīng)值、選擇 、 變異、交叉等基本概念 . (2)1967年 ， 士論文中首次提出了“遺傳算法”的概念 . (3)1975年 ， Holland出版了《自然與人工系統(tǒng)中的適應(yīng)性行為》（ Adaptation in 4 Natural and Artificial System） .該書系統(tǒng)地闡述了遺傳算法的基本理論和方法 ， 提出了遺傳算法的基本定理 — 模式定理 ， 從而奠定了遺傳算法的理論基礎(chǔ) . 同年 De Jong在其博士論文中 ， 首次把遺傳算法應(yīng)用于函數(shù)優(yōu)化問題對遺傳算法的機(jī)理與參數(shù)進(jìn)行了較為系統(tǒng)地研究并建立了著名的五函數(shù)測試平臺 . (4)20世紀(jì) 80年代初 ， Holland教授實(shí)現(xiàn)了第一個基于 遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng) — 分類器系統(tǒng)（ Classifier System簡稱 CS） ， 開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念 . (5)1989年 ， David Goldberg出版了《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（ Geic Algorithms in Search Optimization and Machine Learning） .該書全面系統(tǒng)地總結(jié)了當(dāng)時關(guān)于遺傳算法的研究成果 ， 結(jié)合大量的實(shí)例完整的論述了遺傳算法的基本原理及應(yīng)用 ， 奠定了現(xiàn)代遺傳算法的基礎(chǔ) . (6)1992年 ， John 了專著《遺傳編程》（ Geic Programming）提出了遺傳編程的概念 ， 并成功地把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號處理等方面 . 隨著遺傳算法的不斷深入和發(fā)展 ， 關(guān)于遺傳算法的國際學(xué)術(shù)活動越來越多 ， 遺傳算法已成為一個多學(xué)科、多領(lǐng)域的重要研究方向 . 今天遺傳算法的研究已經(jīng)成為國際學(xué)術(shù)界跨學(xué)科的熱門話題之一 . 遺傳算法是一種有廣泛應(yīng)用前景的算法 ， 但是它的研究和應(yīng)用在國內(nèi)尚處于起步階段 . 近年來遺傳算法已被成功地應(yīng)用于工業(yè)、經(jīng)濟(jì)管理、交通運(yùn)輸、工業(yè)設(shè)計等不同領(lǐng)域解決了許多問題 .例如可靠性優(yōu)化、流 水車間調(diào)度、作業(yè)車間調(diào)度、機(jī)器調(diào)度、設(shè)備布局設(shè)計、圖像處理以及數(shù)據(jù)挖掘等 . 遺傳算法的 數(shù)學(xué)基礎(chǔ)研究 模式定理及隱含并行性原理被看作遺傳算法的兩大基石 ， 后來又提出了建筑塊假設(shè) ， 但是模式定理無法解釋遺傳算法實(shí)際操作中的許多現(xiàn)象 ， 隱性并行性的論證存在嚴(yán)重漏洞 ， 而建筑塊假設(shè)卻從未得到過證明 . 對遺傳算法的基礎(chǔ)理論的研究主要分三個方面 ： 模式定理的拓廣和深入、遺傳算法的新模型、遺傳算法的收斂性理論 . (1)模式定理的拓廣和深入 . Holland給出模式定理 ： 具有短的定義長度、低階、并且模式采樣的平均適應(yīng)值在種群 平均適應(yīng)值以上的模式在遺傳迭代過程中將按指數(shù)增長率被采樣模式定理可表達(dá)為 ： m(H,t+1)? m(H,t). ? ?fHf. ? ? ?????? ??? PHOlP mHc . ? (1) 5 其中 m(Ht)： 在 t代群體中存在模式 H 的串的個數(shù) . ? ?Hf ： 在 t 代群體中包含模式 H 的串的平均適應(yīng)值 . f ： t代群體中所有串的平均適應(yīng)值 . l 表示串的長度 pc 表示交換概率 pm 表示變異概率 . Holland的模式定理奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)根據(jù)隱性并行性得出每一代處理有效模式的下限值是 ? ?l 2113 .其中 n是種群的大小 c1 是小整數(shù) . Bertoui和 Dorigo進(jìn)行了深入的研究獲得當(dāng) 2?ln? ,β 為任意值時處理多少 有效模式的表達(dá)式 . 上海交通大學(xué)的惲為民等獲得每次至少產(chǎn)生 ? ?21?no 數(shù)量級的結(jié)果 . 模式定理中模式適應(yīng)度難以計算和分析 Walsh函數(shù)進(jìn)行遺傳算法的模式處理并引入模式變換的概念采用 Walsh函數(shù)的離散形式有效地計算出模式的平均適應(yīng)度并對遺傳算法進(jìn)行了有效的分析 . 1972年 Frantz首先發(fā)現(xiàn)一種常使 GA從全局最優(yōu)解發(fā)散出去的問題 ， 稱為 GA欺騙 題 [5]. Goldberg最早運(yùn)用 Walsh模式轉(zhuǎn)換設(shè)計出最小的 GA欺騙問題并進(jìn)行了詳細(xì)分析 . (2)遺傳算法的新模型 . 由于遺傳算法中的模式定理和隱性并行性存在不足之處 ，為了搞清楚遺傳算法的機(jī)理 ， 近幾年來人們建立了各種形式的新模型最為典型的是馬氏鏈模型遺傳算法的馬氏鏈模型 [67]， 主要由三種分別是種群馬氏鏈模型、 Vose模型和 Cerf 擾動馬氏鏈模型 . 種群馬氏鏈模型將遺傳算法的種群迭代序列視為一個有限狀態(tài)馬氏鏈來加以研究 ， 運(yùn)用種群馬氏鏈模型轉(zhuǎn)移概率矩陣的某些一般性質(zhì)分析遺傳算法的極限行為 ， 但轉(zhuǎn)移概率的具體形式難以表達(dá)妨礙了對遺傳算法的有限時間行為的研究 ； Vose模型是在無限種群假設(shè)下利用相對 頻率導(dǎo)出 ， 表示種群的概率的向量的迭代方程 ， 通過這一迭代方程的研究 ， 可以討論種群概率的不動點(diǎn)及其穩(wěn)定性 ， 從而導(dǎo)致對遺傳算法的極限行為的 刻畫 ， 但對解釋有限種群遺傳算法的行為的能力相對差一些 . Cerf擾動模型是法國學(xué)者 Cerf將遺傳算法看成一種特殊形式的廣義模擬退火模型 ， 利用了動力系統(tǒng)的隨機(jī)擾動理論 ， 對遺傳算法的極限行為及收斂速度進(jìn)行了研究 . 還有其它改進(jìn)模型 ， 例如張鈴、張鈸等人提出的理想濃度模型 ， 它首先引入濃度和家族的概念 ， 通過濃度計算建立理想濃度模型 [810]， 其濃度變化的規(guī)律為 ： 6 c(Hi， t +1)=c(H， t). ? ?? ?? ?tf tOHf i , (2) c(Hi， t+1)表示模式 Hi在 t時刻的濃度 ， 并對其進(jìn)行分析 ， 得出結(jié)論 ： 遺傳算法本質(zhì)上是一個具有定向制導(dǎo)的隨機(jī)搜索技術(shù) ， 其定向制導(dǎo)原則是導(dǎo)向適應(yīng)度高的模式為祖先的染色體“家族”方向 . (3)遺傳算法的收斂性理論 . 對于遺傳算法的馬氏鏈分析本身就是建立遺傳算法的收斂性理論 [1112]， Eiben等用馬爾可夫鏈證明了保留最優(yōu)個體的遺傳算法 的概率性全局收斂 ， Rudolph用齊次有限馬爾可夫鏈證明了具有復(fù)制、交換、突變操作的標(biāo)準(zhǔn)遺傳算法收斂不到全局最優(yōu)解 ， 不適合于靜態(tài)函數(shù)的優(yōu)化問題 ， 建議改變復(fù)制策略以達(dá)到全局收斂 ， Back和 Muhlenbein研究了達(dá)到全局最優(yōu)解的算法的時間復(fù)雜性問題 ， 近 幾年 ， 徐宗本等人建立起鞅序列模型 ， 利用鞅序列收斂定理證明了遺傳算法的收斂性 . 遺傳算法所涉及的五大要素 ： 參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作的設(shè)計和控制參數(shù)的設(shè)定 ， 其具體內(nèi)容如下 ： (1)參數(shù)編碼 . 遺傳算法中常用的 編碼方法是二進(jìn)制編碼 ， 它將問題空間的參數(shù)用字符集 {0， 1}構(gòu)成染色體位串 ， 符合最小字符集原則 ， 操作簡單 ， 便于用模式定理分析 . (2)適應(yīng)度函數(shù)的設(shè)計 . 適應(yīng)度函數(shù)是評價個體適應(yīng)環(huán)境的能力 ， 使選擇操作的依據(jù) ， 是由目標(biāo)函數(shù)變換而成 . 對適應(yīng)度函數(shù)唯一的要求是其結(jié)果為非負(fù)值 . 適應(yīng)度的尺度變換是對目標(biāo)函數(shù)值域的某種映射變換 ， 可克服未成熟收斂和隨機(jī)漫游現(xiàn)象 . 常用的適應(yīng)度函數(shù)尺度變化方法主要有線性變換、冪函數(shù)變換和指數(shù)變換 .[13] (3)遺傳操作的設(shè)計 . 包括選擇、交叉、變異 . ①選擇 (Selection). 選 擇是用來確定交叉?zhèn)€體 ， 以及被選個體將產(chǎn)生多少個子代個體 . 其主要思想是個體的復(fù)制概率正比于其適應(yīng)值 ， 但按比例選擇不一定能達(dá)到好的效果 . 選擇操作從早期的輪盤賭選擇發(fā)展到現(xiàn)在最佳個體保存法、排序選擇法、聯(lián)賽選擇法、隨機(jī)遍歷抽樣法、局部選擇法、柔性分段復(fù)制、穩(wěn)態(tài)復(fù)制、最優(yōu)串復(fù)制、最優(yōu)串保留等 . ②交叉 (Crossover). 交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作 ， 其作用是組合出新的個體 ， 在串空間進(jìn)行有效搜索 ， 同時降低對有效模式的破壞概率 . 各種交叉算子均包含兩個基本內(nèi)容 ： 確定交叉點(diǎn)的位 置和進(jìn)行部分基因的 7 交換 . 常用的交叉操作方法有單點(diǎn)交叉、雙點(diǎn)交叉、一致交叉、均勻交叉、算術(shù)交叉、二維交叉、樹結(jié)構(gòu)交叉、部分匹配交叉、順序交叉和周期交叉等等 . ③變異 (Mutation). 變異是指將個體編碼串中的某些基因值用其它基因值來替換 ,形成一個新的個體 . 遺傳算法中的變異運(yùn)算是產(chǎn)生新個體的輔助方法 ， 其目的是使遺傳算法具有局部的隨機(jī)搜索能力和保持群體的多樣性 . 變異算法包括確定變異點(diǎn)的位置和進(jìn)行基因值替換 . 常見的變異算子有基本位變異、均勻變異、高斯變異、二元變異、逆轉(zhuǎn)變異、自適應(yīng)變異等 . (4) 控制 參數(shù)設(shè)定 . 遺傳算法中需要確定一些參數(shù)取值 ， 主要有串長 l， 群體大小 n，交叉概率 pc、變異概率 pm等 ， 對遺傳算法性能影響很大 . 目前對參數(shù)根據(jù)情況進(jìn)行調(diào)整變化研究比較多 ， 而一般確定的參數(shù)范圍是 ： n=20～ 200， pc = 015 ～ 110， pm =0～ 0105. 在自然界 ， 由于組成生物群體中各個體之間的差異 ， 對所處環(huán)境有不同的適應(yīng)和生存能力 ， 遵照自然界生物進(jìn)化的基本原則 ， 適者生存、優(yōu)勝劣汰 ， 將要淘汰那些最差個體 ， 通過交配將父本優(yōu)秀的染色體和基因遺傳給子代 ， 通過染色體核基因的重新組合產(chǎn)生生命力更強(qiáng)的新的個體與由它們組成的新群體 . 在特定的條件下 ， 基因會發(fā)生突變 ,產(chǎn)生新基因和生命力更強(qiáng)的新個體 ； 但突變是非遺傳的 ， 隨著個體不斷更新 ， 群體不斷朝著最優(yōu)方向進(jìn)化 ， 遺傳算法是真實(shí)模擬自然界生物進(jìn)化機(jī)制進(jìn)行尋優(yōu)的 . 在此算法中 ,被研究的體系的響應(yīng)曲面看作為一個群體 ， 相應(yīng)曲面上的每一個點(diǎn)作為群體中的一個個體 ， 個體用多維向量或矩陣來描述 ， 組成矩陣和向量的參數(shù)相應(yīng)于生物種組成染色體的基因 ， 染色體用固定長度的二進(jìn)制串表述 ， 通過交換、突變等遺傳操作 ， 在參數(shù)的一定范圍內(nèi)進(jìn)行隨機(jī)搜索 ， 不斷改善數(shù)據(jù)結(jié)構(gòu) ， 構(gòu)造出不同的 向量 ， 相當(dāng)于得到了被研究的不同的解 ， 目標(biāo)函數(shù)值較優(yōu)的點(diǎn)被保留 ， 目標(biāo)函數(shù)值較差的點(diǎn)被淘汰 .[14] 由于遺傳操作可以越過位壘 ， 能跳出局部較優(yōu)點(diǎn) ， 到達(dá)全局最優(yōu)點(diǎn) . 遺傳算法是一種迭代算法 ， 它在每一次迭代時都擁有一組解 ， 這組解最初是隨機(jī)生成的 ， 在每次迭代時又有一組新的解由模擬進(jìn)化和繼承的遺傳操作生成 ， 每個解都有一目標(biāo)函數(shù)給與評判 ， 一次迭代成為一代 . 經(jīng)典的遺傳算法結(jié)構(gòu)圖如下 ： 8 圖 1 遺傳算法的結(jié)構(gòu)圖 (1)根據(jù)求解 精度的要求 ， 確定使用二進(jìn)制的長度 . 設(shè)值域的取值范圍為 [ai ,bi ]，若要求精確到小數(shù)點(diǎn)后 6位 ， 則由 (bi ai ) 1062mi 1求得 mi 的最小長度 ， 進(jìn)而可求出位于區(qū)間的任一數(shù) ： xi =ai +decimal(101 ...0012 ) 12 ??miab ii [15] (3) 其中 ， i=1， 2， ...， Popsize； Popsize為種群中染色體的個數(shù) ； (2)利用隨機(jī)數(shù)發(fā)生器產(chǎn)生種群 ； (3)對種群中每一染色體 vi ， 計算其對應(yīng)適應(yīng)度 eval(vi )， i=1， 2， ? ， Popsize； (4)計算種群適應(yīng)度之和 F： F= ? ?vevaliPopsizei??1 (4) (5)計算每個染色體選擇概率 Pi： ? ?F vevalp ii ? (5) i=1， 2， ... ， Popsize ； 編碼、生成初始種群 種群中個體適應(yīng)渡的計算與評 價價 物種的選擇 雜交 變異 9 (6)計算每個染色體的累加概率 qi ： qi =??ij jp1 (6) i=1， 2， ...， Popsize ； (7)產(chǎn)生一個位于 [0， 1]區(qū)間的隨機(jī)數(shù)序列 ， 其長度為 N， 如果其中任意一數(shù) rq1 ，則選擇第一個染色體 ， 若 qi1? rqi ， 則選擇第 i個染色體 ， i=1， 2， ... Popsize， 這樣可以獲得新一代種群 ； (8)對新一代種群進(jìn)行交叉運(yùn)算 ： 設(shè)交叉概率為 pc ， 首先產(chǎn)生一個位于區(qū)間 [0,1]內(nèi)的隨機(jī)數(shù)序列 ， 其長度為 N， 如果其中任意一數(shù) rpc ， 則對應(yīng)染色體被選中 (如果選中奇數(shù)個 ， 則可以去掉一個 )， 然后在 [1， m1]區(qū)間中產(chǎn)生隨機(jī)數(shù) ， 個數(shù)為選中的染色體數(shù)的一半 ， 然后根據(jù)隨機(jī)數(shù)在對應(yīng)位置進(jìn)行交換操作 ， 從而構(gòu)成新的染色體 ； (9)變異操作 ： 設(shè)變異概率為 pm ， 產(chǎn)生 m N個位于區(qū)間 [0， 1]上的隨機(jī)數(shù) .如果某一隨機(jī)數(shù) rpm ， 則選中對應(yīng)位變異 ， 構(gòu)成新的種群 ； (10)第一代計算完畢 ， 返回③繼續(xù)計算 ， 直到達(dá)到滿意的結(jié)果為止 . 隨機(jī)初始化種群 p(0)={x1， x2， ...， xn}； t=0； 計算 p(0)中個體的適應(yīng)值 ； while(不滿足終止條件 ) { 根據(jù)個體的適應(yīng)值及選擇策略從 p(t)中選擇下一代生成的父體 p(t)； 執(zhí)行交叉 ,變異和再生成新的種群 p(t+1) ； 計算 p(t+1)中個體的適應(yīng)值 ； t=t+1； } 偽代碼為： BEGIN： I=0； Initialize P(I)； 10 Fitness P(I)； While (not Terminate2Condition) { I++； GA2Operation P(I)； Fitness P(I)； } END. 遺傳算法不同于傳統(tǒng)的搜索和優(yōu)化方法 . 主要區(qū)別在于 ： (1)自組織、自適應(yīng)和自學(xué)習(xí)性 (智能性 ). 應(yīng)用遺傳算法求解問題時 ， 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后 ， 算法將利用進(jìn)化過程中獲得的信息自行組織搜索 . 由于基于自然的選擇策略“適者生存、不適者被淘汰” ， 因而適應(yīng) 度大的個體具有較高的生存概率 . 通常適應(yīng)度大的個體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu) ， 再通過基因重組和基因突變等遺傳操作 ， 就可能產(chǎn)生更適應(yīng)環(huán)境的后代 . 進(jìn)化算法的這種自組織、自適應(yīng)特征 ， 使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力 . 自然選擇消除了算法設(shè)計過程中的一個最大障礙 ， 即需要事先描述問題的全部特點(diǎn) ， 并要說明針對問題的不同特點(diǎn)算法應(yīng)采取的措施 .因此 ， 利用遺傳算法 ， 我們可以解決那些復(fù)雜的非結(jié)構(gòu)化問題 . (2)遺傳算法的本質(zhì)并行性 . 遺傳算法按并行方式搜索一個種群數(shù)目的點(diǎn) ， 而不是單點(diǎn) . 它的并行性表現(xiàn) 在兩個方面 ， 一是遺傳算法是內(nèi)在并行的 ( inherent par