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