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