【正文】 land給出模式定理 ： 具有短的定義長度、低階、并且模式采樣的平均適應(yīng)值在種群平均適應(yīng)值以上的模式在遺傳迭代過程中將按指數(shù)增長率 被采樣模式定理可表達(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 表示 串的長度 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ù)量級的結(jié)果 . 模式定理中模式適應(yīng)度難以計(jì)算和分析 Walsh函數(shù)進(jìn)行遺傳算法的模式處理并引入模式變換的概念采用 Walsh函數(shù)的離散形式有效地計(jì)算出模式的平均適應(yīng)度并對遺傳算法進(jìn)行了有效的分析 . 1972年 Frantz首先發(fā)現(xiàn)一種常使 GA從全局最優(yōu)解發(fā)散出去的問題 ， 稱為 GA欺騙 題 [5]. Goldberg最早運(yùn)用 Walsh模式轉(zhuǎn)換設(shè)計(jì)出最小的 GA欺騙問題并進(jìn)行了詳細(xì)分析 . (2)遺傳算法的新模型 . 由于遺傳算法中的模式 定理和隱性并行性存在不足之處 ，為了搞清楚遺傳算法的機(jī)理 ， 近幾年來人們建立了各種形式的新模型最為典型的是馬氏鏈模型遺傳算法的馬氏鏈模型 [67]， 主要由三種分別是種群馬氏鏈模型、 Vose模型和 Cerf 擾動(dòng)馬氏鏈模型 . 種群馬氏鏈模型將遺傳算法的種群迭代序列視為一個(gè)有限狀態(tài)馬氏鏈來加以研究 ， 運(yùn)用種群馬氏鏈模型轉(zhuǎn)移概率矩陣的某些一般性質(zhì)分析遺傳算法的極限行為 ， 但轉(zhuǎn)移概率的具體形式難以表達(dá)妨礙了對遺傳算法的有限時(shí)間行為的研究 ； Vose模型是在無限種群假設(shè)下利用相對頻率導(dǎo)出 ， 表示種群的概率的向量的迭代方程 ， 通過這一 迭代方程的研究 ， 可以討論種群概率的不動(dòng)點(diǎn)及其穩(wěn)定性 ， 從而導(dǎo)致對遺傳算法的極限行為的 刻畫 ， 但對解釋有限種群遺傳算法的行為的能力相對差一些 . Cerf擾動(dòng)模型是法國學(xué)者 Cerf將遺傳算法看成一種特殊形式的廣義模擬退火模型 ， 利用了動(dòng)力系統(tǒng)的隨機(jī)擾動(dòng)理論 ， 對遺傳算法的極限行為及收斂速度進(jìn)行了研究 . 還有其它改進(jìn)模型 ， 例如張鈴、張鈸等人提出的理想濃度模型 ， 它首先引入濃度和家族的概念 ， 通過濃度計(jì)算建立理想濃度模型 [810]， 其濃度變化的規(guī)律為 ： 6 c(Hi， t +1)=c(H， t). ? ?? ?? ?tf tOHf i , (2) c(Hi， t+1)表示模式 Hi在 t時(shí)刻的濃度 ， 并對其進(jìn)行分析 ， 得出結(jié)論 ： 遺傳算法本質(zhì)上是一個(gè)具有定向制導(dǎo)的隨機(jī)搜索技術(shù) ， 其定向制導(dǎo)原則是導(dǎo)向適應(yīng)度高的模式為祖先的染色體“家族”方向 . (3)遺傳算法的收斂性理論 . 對于遺傳算法的馬氏鏈分析本身就是建立遺傳算法的收斂性理論 [1112]， Eiben等用馬爾可夫鏈證明了保留最優(yōu)個(gè)體的遺傳算法的概率性全局收斂 ， Rudolph用齊次有限馬爾可夫 鏈證明了具有復(fù)制、交換、突變操作的標(biāo)準(zhǔn)遺傳算法收斂不到全局最優(yōu)解 ， 不適合于靜態(tài)函數(shù)的優(yōu)化問題 ， 建議改變復(fù)制策略以達(dá)到全局收斂 ， Back和 Muhlenbein研究了達(dá)到全局最優(yōu)解的算法的時(shí)間復(fù)雜性問題 ， 近 幾年 ， 徐宗本等人建立起鞅序列模型 ， 利用鞅序列收斂定理證明了遺傳算法的收斂性 . 遺傳算法所涉及的五大要素 ： 參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定 ， 其具體內(nèi)容如下 ： (1)參數(shù)編碼 . 遺傳算法中常用的編碼方法是二進(jìn)制編碼 ， 它將問題空間的參數(shù)用字符集 {0， 1}構(gòu)成染色體位串 ， 符合最小字符集原則 ， 操作簡單 ， 便于用模式定理分析 . (2)適應(yīng)度函數(shù)的設(shè)計(jì) . 適應(yīng)度函數(shù)是評價(jià)個(gè)體適應(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è)計(jì) . 包括選擇、交叉、變異 . ①選擇 (Selection). 選擇是用來確定交叉?zhèn)€體 ， 以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體 . 其主要思想是個(gè)體的復(fù)制概率正比于其適應(yīng)值 ， 但按比例選擇不一定能達(dá)到好的效果 . 選擇操作從早期的輪盤賭選擇發(fā)展到現(xiàn)在最佳個(gè)體保存法、排序選擇法、聯(lián)賽選擇法、隨機(jī)遍歷抽樣法、局部選擇法、柔性分段復(fù)制、穩(wěn)態(tài)復(fù)制、最優(yōu)串復(fù)制、最優(yōu)串保留等 . ②交叉 (Crossover). 交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作 ， 其作用是組合出新的個(gè)體 ， 在串空間進(jìn)行有效搜索 ， 同時(shí)降低對有效模式的破壞概率 . 各種交叉算子均包含兩個(gè)基本內(nèi)容 ： 確定交叉點(diǎn)的位置和進(jìn)行部分基因的 7 交換 . 常用的交叉操作方法有單點(diǎn) 交叉、雙點(diǎn)交叉、一致交叉、均勻交叉、算術(shù)交叉、二維交叉、樹結(jié)構(gòu)交叉、部分匹配交叉、順序交叉和周期交叉等等 . ③變異 (Mutation). 變異是指將個(gè)體編碼串中的某些基因值用其它基因值來替換 ,形成一個(gè)新的個(gè)體 . 遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法 ， 其目的是使遺傳算法具有局部的隨機(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. 在自然界 ， 由于組成生物群體中各個(gè)體之間的差異 ， 對所處環(huán)境有不同的適應(yīng)和生存能力 ， 遵照自然界生物進(jìn)化的基本原則 ， 適者生存、優(yōu)勝劣汰 ， 將要淘汰那些最差個(gè)體 ， 通過交配將父本優(yōu)秀的染色體和基因遺傳給子代 ， 通過染色體核基因的重新組合產(chǎn)生生命力更強(qiáng)的新的個(gè)體與由它們組成的新群體 . 在特 定的條件下 ， 基因會(huì)發(fā)生突變 ,產(chǎn)生新基因和生命力更強(qiáng)的新個(gè)體 ； 但突變是非遺傳的 ， 隨著個(gè)體不斷更新 ， 群體不斷朝著最優(yōu)方向進(jìn)化 ， 遺傳算法是真實(shí)模擬自然界生物進(jìn)化機(jī)制進(jìn)行尋優(yōu)的 . 在此算法中 ,被研究的體系的響應(yīng)曲面看作為一個(gè)群體 ， 相應(yīng)曲面上的每一個(gè)點(diǎn)作為群體中的一個(gè)個(gè)體 ， 個(gè)體用多維向量或矩陣來描述 ， 組成矩陣和向量的參數(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) . 遺傳算法是一種迭代算法 ， 它在每一次迭代時(shí)都擁有一組解 ， 這組解最初是隨機(jī)生成的 ， 在每次迭代時(shí)又有一組新的解由模擬進(jìn)化和繼承的遺傳操作生成 ， 每個(gè)解都有一目標(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為種群中染色體的個(gè)數(shù) ； (2)利用隨機(jī)數(shù)發(fā)生器產(chǎn)生種群 ； (3)對種群中每一染色體 vi ， 計(jì)算其對應(yīng)適應(yīng)度 eval(vi )， i=1， 2， ? ， Popsize； (4)計(jì)算種群適應(yīng)度之和 F： F= ? ?vevaliPopsizei??1 (4) (5)計(jì)算每個(gè)染色體選擇概率 Pi： ? ?F vevalp ii ? (5) i=1， 2， ... ， Popsize ； 編碼、生成初始種群 種群中個(gè)體適應(yīng)渡的計(jì)算與評 價(jià)價(jià) 物種的選擇 雜交 變異 9 (6)計(jì)算每個(gè)染色體的累加概率 qi ： qi =??ij jp1 (6) i=1， 2， ...， Popsize ； (7)產(chǎn)生一個(gè)位于 [0， 1]區(qū)間的隨機(jī)數(shù)序列 ， 其長度為 N， 如果其中任意一數(shù) rq1 ，則選擇第一個(gè)染色體 ， 若 qi1? rqi ， 則選擇第 i個(gè)染色體 ， i=1， 2， ... Popsize， 這樣可以獲得新一代種群 ； (8)對新一代種群進(jìn)行交叉運(yùn)算 ： 設(shè)交叉概率為 pc ， 首先產(chǎn)生一個(gè)位于區(qū)間 [0,1]內(nèi)的隨機(jī)數(shù)序列 ， 其長度為 N， 如果其中任意一數(shù) rpc ， 則對應(yīng)染色體被選中 (如果選中奇數(shù)個(gè) ， 則可以去掉一個(gè) )， 然后在 [1， m1]區(qū)間中產(chǎn)生隨機(jī)數(shù) ， 個(gè)數(shù)為選中的染色體數(shù)的一半 ， 然后根據(jù)隨機(jī)數(shù)在對應(yīng)位置進(jìn)行交換操作 ， 從而構(gòu)成新的染色體 ； (9)變異操作 ： 設(shè)變異概率為 pm ， 產(chǎn)生 m N個(gè)位于區(qū)間 [0， 1]上的隨機(jī)數(shù) .如果某一隨機(jī)數(shù) rpm ， 則選中對應(yīng)位 變異 ， 構(gòu)成新的種群 ； (10)第一代計(jì)算完畢 ， 返回③繼續(xù)計(jì)算 ， 直到達(dá)到滿意的結(jié)果為止 . 隨機(jī)初始化種群 p(0)={x1， x2， ...， xn}； t=0； 計(jì)算 p(0)中個(gè)體的適應(yīng)值 ； while(不滿足終止條件 ) { 根據(jù)個(gè)體的適應(yīng)值及選擇策略從 p(t)中選擇下一代生成的父體 p(t)； 執(zhí)行交叉 ,變異和再生成新的種群 p(t+1) ； 計(jì)算 p(t+1)中個(gè)體的適應(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)用遺傳算法求解問題時(shí) ， 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后 ， 算法將利用進(jìn)化過程中獲得的信息自行組織搜索 . 由于基于自然的選擇策略“適者生存、不適者被淘汰” ， 因而適應(yīng)度大的個(gè)體具有較高的生存概率 . 通常適應(yīng)度大的個(gè)體 具有更適應(yīng)環(huán)境的基因結(jié)構(gòu) ， 再通過基因重組和基因突變等遺傳操作 ， 就可能產(chǎn)生更適應(yīng)環(huán)境的后代 . 進(jìn)化算法的這種自組織、自適應(yīng)特征 ， 使它同時(shí)具有能根據(jù)環(huán)境變化來自動(dòng)發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力 . 自然選擇消除了算法設(shè)計(jì)過程中的一個(gè)最大障礙 ， 即需要事先描述問題的全部特點(diǎn) ， 并要說明針對問題的不同特點(diǎn)算法應(yīng)采取的措施 .因此 ， 利用遺傳算法 ， 我們可以解決那些復(fù)雜的非結(jié)構(gòu)化問題 . (2)遺傳算法的本質(zhì)并行性 . 遺傳算法按并行方式搜索一個(gè)種群數(shù)目的點(diǎn) ， 而不是單點(diǎn) . 它的并行性表現(xiàn)在兩個(gè)方面 ， 一是遺傳算法是內(nèi)在并行的 ( inherent parallelism)， 即遺傳算法本身非常適合大規(guī)模并行 . 最簡單的并行方式是讓幾百甚至數(shù)千臺計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算 ， 運(yùn)行過程中甚至不進(jìn)行任何通信 (獨(dú)立的種群之間若有少量的通信一般會(huì)帶來更好的結(jié)果 )， 等到運(yùn)算結(jié)束時(shí)才通信比較 ， 選取最佳個(gè)體 .這種并行處理方式對并行系統(tǒng)結(jié)構(gòu)沒有什么限制和要求 ， 可以說 ， 遺傳算法適合在目前所有的并行機(jī)或分布式系