分類號(hào)C/TP18密級(jí)內(nèi)部遺傳算法運(yùn)行機(jī)理的研究THERESEARCHONRUNNINGMECHANISMOFGENETICALGORITHM作者郭東偉指導(dǎo)教師劉大有周春光教授教授單位吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)名稱計(jì)算機(jī)軟件論文答辯日期2002年6月13日授予學(xué)位日期答辯委員會(huì)主席孫吉貴教授論文評(píng)閱人史忠植梁艷春二零零二年四月論文提交日期2002年5月8日論文答辯日期2002年6月13日關(guān)鍵詞遺傳算法、收斂性、動(dòng)力學(xué)形態(tài)KEYWORDSGENETICALGORITHM,CONVERGENCE,DYNAMICALSHAPE總頁(yè)數(shù)130頁(yè)開本16開有圖表未經(jīng)本論文作者書面授權(quán)，收存和保管本論文書面版本、電子版本的任何單位和個(gè)人，均不得對(duì)論文的全部或部分內(nèi)容進(jìn)行任何形式的復(fù)制、修改、發(fā)行、出租、改編等有礙作者著作權(quán)的商業(yè)性使用（但純學(xué)術(shù)性使用不在此限）。否則，應(yīng)承擔(dān)侵權(quán)的法律責(zé)任。提要相對(duì)于進(jìn)化算法的廣泛應(yīng)用，它的理論基礎(chǔ)仍有待進(jìn)一步研究。本文對(duì)進(jìn)化算法，特別是遺傳算法的運(yùn)行機(jī)理進(jìn)行一定的研究。使用動(dòng)力學(xué)方法對(duì)包含選擇算子、交叉算子的標(biāo)準(zhǔn)遺傳算法進(jìn)行建模，得到了標(biāo)準(zhǔn)遺傳算法的在平凡不動(dòng)點(diǎn)處的局部收斂性條件，明確了局部極值點(diǎn)的定義。以上結(jié)論不僅對(duì)于基于適應(yīng)度比例選擇的選擇算子和兩點(diǎn)交叉算子成立，對(duì)于其他形式的選擇算子和交叉算子也有類似結(jié)論。同時(shí)，本文中針對(duì)一個(gè)典型問(wèn)題分析了遺傳算法的全局動(dòng)力學(xué)形態(tài)，計(jì)算了不同收斂區(qū)域之間的分割和比例。本文明確定義了適應(yīng)度比例選擇算子的取代時(shí)間，得出了取代時(shí)間的階與適應(yīng)度函數(shù)的選取及初始群體的分布無(wú)關(guān)的結(jié)論。同時(shí)，提出了一種基于聚類分析和資源競(jìng)爭(zhēng)模型的生境遺傳算法，可以在一定程度上解決多模函數(shù)的優(yōu)化問(wèn)題。1目錄第一章緒論111進(jìn)化計(jì)算112進(jìn)化算法簡(jiǎn)史213進(jìn)化算法的研究?jī)?nèi)容與前景314本文的研究?jī)?nèi)容4第二章進(jìn)化算法基礎(chǔ)721進(jìn)化算法（EVOLUTIONARYALGORITHMS,EAS）7211進(jìn)化規(guī)劃（EVOLUTIONARYPROGRAMMING，EP）8212進(jìn)化策略（EVOLUTIONSTRATEGIES，ES）8213遺傳算法（GENETICALGORITHMS,GA）922進(jìn)化算法的基本結(jié)構(gòu)9221編碼10222適應(yīng)度度量12223進(jìn)化算子1323遺傳算法的基本結(jié)構(gòu)14231GA中的選擇算子15232GA中的變異算子17233GA中的交叉算子1824小結(jié)18第三章進(jìn)化算法的理論分析方法1931收斂性的含義2032GA建模使用的數(shù)學(xué)方法21321隨機(jī)變量21322矩陣初步23323隨機(jī)過(guò)程24324動(dòng)力系統(tǒng)2533GA建模的非MARKOV方法282331模式進(jìn)化28332群體適應(yīng)度的累積度29333等位基因邊際分布3034使用MARKOV鏈的模型31341有限搜索空間上的齊次模型32342有限搜索空間上的非齊次GA3335獨(dú)立算子的收斂性結(jié)果35351選擇壓力35352基因漂移36353隨機(jī)漫游3736其他GA建模方法3837小結(jié)40第四章GA的動(dòng)力學(xué)模型及收斂性分析4141齊次GA的動(dòng)力系統(tǒng)模型4142SGA的一般動(dòng)力學(xué)模型4243單點(diǎn)交叉算子的數(shù)學(xué)特性4444SGA的局部收斂性4645一般形式的遺傳算法5046不同選擇算子的模型52461基于排名的選擇策略52462基于錦標(biāo)賽方式的選擇策略55463不同選擇算子的局部收斂性的比較5647GA的收斂條件對(duì)算法改進(jìn)的指導(dǎo)作用59471交叉概率的影響60472適應(yīng)度函數(shù)的變化60473編碼方式的變化61474交叉算子的變化61475基因連鎖6248小結(jié)62第五章遺傳算法的全局動(dòng)力學(xué)形態(tài)64351全局動(dòng)力學(xué)形態(tài)64522BIT問(wèn)題的動(dòng)力學(xué)模型6453SGA的模型及分析67531全部重組，沒(méi)有變異的模型67532世代重疊模型71533部分交叉模型74534帶有變異算子的模型7654小結(jié)78第六章遺傳算法取代時(shí)間的分析7961選擇壓力7962選擇算子與取代時(shí)間7963適應(yīng)度比例選擇算子的取代時(shí)間8164不同選擇算子的取代時(shí)間的比較8465小結(jié)85第七章生境遺傳算法8671背景8672生境機(jī)制86721擁擠87722共享88723聚類8973基于聚類分析的資源競(jìng)爭(zhēng)BCRC算法90731算法結(jié)構(gòu)90732改進(jìn)的KMEANS算法90733算法中其他事項(xiàng)9174數(shù)學(xué)分析92741穩(wěn)態(tài)時(shí)各生境所占的比例92742生境穩(wěn)定存在的條件93743BCRC算法與生境規(guī)則94744BCRC算法的穩(wěn)定性9575實(shí)驗(yàn)測(cè)試95476小結(jié)98第八章結(jié)論和進(jìn)一步工作99致謝102在讀期間完成的主要研究工作103參考文獻(xiàn)104第一章緒論1第一章緒論11進(jìn)化計(jì)算進(jìn)化論的出現(xiàn)作為19世紀(jì)三大重要自然發(fā)現(xiàn)之一，對(duì)人類文明的發(fā)展產(chǎn)生重要影響。在隨后的一百多年來(lái)，人們逐漸意識(shí)到，進(jìn)化論作為一種方法論，其影響遠(yuǎn)遠(yuǎn)超出了生物學(xué)，擴(kuò)展到很多其他學(xué)科。近30年來(lái)，在計(jì)算機(jī)科學(xué)和數(shù)學(xué)的交叉領(lǐng)域，人們對(duì)借助進(jìn)化規(guī)律解決問(wèn)題的方法，產(chǎn)生了越來(lái)越深厚的興趣。進(jìn)化算法（EVOLUTIONARYALGORITHM,EA）是其中一種具有代表性的方法。這種方法借鑒生物進(jìn)化過(guò)程，通過(guò)維持潛在解的群體，模擬自然界生物的繁殖、遺傳和變異等機(jī)制，采用“優(yōu)勝劣汰”的進(jìn)化原則，形成了一系列用來(lái)進(jìn)行問(wèn)題求解的算法。更確切的說(shuō)，進(jìn)化算法是在使用計(jì)算機(jī)的問(wèn)題求解系統(tǒng)中，基于進(jìn)化概念的隨機(jī)優(yōu)化算法。這種研究和使用進(jìn)化算法的新興領(lǐng)域被稱作進(jìn)化計(jì)算（EVOLUTIONARYCOMPUTING,EC）42。和其他優(yōu)化算法相比，進(jìn)化計(jì)算的主要特點(diǎn)有98智能性進(jìn)化計(jì)算的智能性包括自組織、自適應(yīng)和自學(xué)習(xí)性等。自然選擇消除了算法設(shè)計(jì)過(guò)程中的一個(gè)最大障礙，即需要實(shí)現(xiàn)描述問(wèn)題的全部特性，并說(shuō)明針對(duì)問(wèn)題的不同特點(diǎn)算法應(yīng)采取的措施。因此，使用進(jìn)化計(jì)算的方法可以解決那些不了解具體結(jié)構(gòu)的問(wèn)題。從這個(gè)角度來(lái)看，進(jìn)化算法屬于人工智能中所說(shuō)的弱方法，也就是不對(duì)問(wèn)題領(lǐng)域作更多的假設(shè)，算法的結(jié)構(gòu)和基礎(chǔ)不依賴于領(lǐng)域相關(guān)知識(shí)，因此具有廣泛的適應(yīng)性。另一方面，經(jīng)過(guò)針對(duì)實(shí)際問(wèn)題仔細(xì)設(shè)計(jì)的編碼方案、進(jìn)化算子和適應(yīng)度度量后，進(jìn)化算法完全可以克服傳統(tǒng)弱方法的缺點(diǎn)，以較快的時(shí)間得到優(yōu)化解或較優(yōu)解，避免了“組合爆炸”問(wèn)題。本質(zhì)并行性進(jìn)化計(jì)算的本質(zhì)并行性表現(xiàn)在兩個(gè)方面一是內(nèi)在并行性（INHERENT第一章緒論2PARALLELISM）。即算法本身非常適合于大規(guī)模并行處理。二是隱含并行性（IMPLICITPARALLELISM）。由于進(jìn)化計(jì)算采用種群的方式組織搜索，從而可以搜索解空間內(nèi)的多個(gè)區(qū)域，并相互交流信息。例如，由遺傳算法的隱含并行性定理54可以得知，雖然算法每代的計(jì)算量只與種群規(guī)模N成正比，而實(shí)質(zhì)上已進(jìn)行了大約ON3次有效搜索。另外，進(jìn)化算法還具有全局優(yōu)化性、通用性和可操作性強(qiáng)等特點(diǎn)。12進(jìn)化算法簡(jiǎn)史進(jìn)化算法的初步嘗試可以追溯到20世紀(jì)50年代。在50到60年代間的早期的嘗試，沒(méi)有吸引更多的追隨者；在70到80年代間，獨(dú)立發(fā)展了三個(gè)研究方向，即進(jìn)化規(guī)劃、進(jìn)化策略和遺傳算法。在1990年，出現(xiàn)了進(jìn)化算法這個(gè)名詞。作為一個(gè)超類，它包含了上述所有的分支和所有其他在問(wèn)題求解領(lǐng)域基于進(jìn)化感知的技術(shù)。從90年代早期，又提出了幾種新的進(jìn)化算法，其中，遺傳規(guī)劃（GENETICPROGRAMMING,GP）77是其中具有代表性的一種算法。雖然每一類算法都有自己的特點(diǎn)，但在過(guò)去幾年間，不同算法之間的界限變得越來(lái)越模糊。進(jìn)化計(jì)算在其早期沒(méi)有得到應(yīng)有的重視，其主要原因在于，在當(dāng)時(shí)的人工智能領(lǐng)域，以自動(dòng)推理、專家系統(tǒng)為代表的基于符號(hào)處理（知識(shí)或規(guī)則）的方法處于統(tǒng)治地位。到了80年代，人們逐漸意識(shí)到傳統(tǒng)人工智能方法的局限性，因而提出了很多其他方法。以計(jì)算為基礎(chǔ)的智能算法，如神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)等，走上了舞臺(tái)。這些導(dǎo)致了人們對(duì)進(jìn)化計(jì)算進(jìn)行了廣泛和深入的研究。目前，進(jìn)化計(jì)算在諸如問(wèn)題優(yōu)化、自動(dòng)控制、機(jī)器學(xué)習(xí)、模型預(yù)測(cè)等各個(gè)領(lǐng)域都有廣泛應(yīng)用。計(jì)算機(jī)科學(xué)、數(shù)學(xué)、物理學(xué)、化學(xué)、生物學(xué)和、經(jīng)濟(jì)學(xué)、社會(huì)科學(xué)及工程應(yīng)用等各方面科學(xué)家都開展了進(jìn)化計(jì)算的應(yīng)用。在計(jì)算機(jī)科學(xué)領(lǐng)域，它涉及到人工智能、可計(jì)算性與計(jì)算復(fù)雜性、計(jì)算方法、并行處理和程序設(shè)計(jì)等方向的諸多課題。從80年代中期開始，世界上許多國(guó)家都掀起了進(jìn)化計(jì)算的研究熱潮。目前，有數(shù)種以進(jìn)化計(jì)算為主題的國(guó)際會(huì)議定期召開第一章緒論33,11,12,14,15,27,33,43,45,47,50,64,65,67,78,90,92,107,117,118,132,133；互聯(lián)網(wǎng)上有諸多關(guān)于進(jìn)化計(jì)算的網(wǎng)站、郵件列表和新聞組。現(xiàn)已出版了兩種關(guān)于進(jìn)化計(jì)算的專門性國(guó)際期刊“EVOLUTIONARYCOMPUTATION”，由MITPRESS出版，1993年創(chuàng)刊；“IEEETRANSACTIONONEVOLUTIONARYCOMPUTATION”，由IEEE發(fā)布，1997年創(chuàng)刊。此外，在其他刊物和學(xué)術(shù)會(huì)議上也能找到進(jìn)化計(jì)算方面的文章。從下面的數(shù)字中可以看出進(jìn)化計(jì)算，特別是遺傳算法的發(fā)展速度。在1986年5月由GOLDBERGDE等人匯編的遺傳算法的參考文獻(xiàn)匯總中62，只有180篇文章，而截止到2000年12月，仍由GOLDBERG等人重新修訂的匯總中63，包括了9000個(gè)文章引用。這兩個(gè)數(shù)字的比較說(shuō)明，遺傳算法在十幾年間得到了蓬勃發(fā)展。13進(jìn)化算法的研究?jī)?nèi)容與前景進(jìn)化計(jì)算的研究?jī)?nèi)容相當(dāng)廣泛，反映了多學(xué)科相互交叉的特點(diǎn)。目前，進(jìn)化計(jì)算的研究主要涉及到理論和應(yīng)用兩個(gè)方面在實(shí)際應(yīng)用方面，需要大量的實(shí)踐，以積累各種有價(jià)值的經(jīng)驗(yàn)和改進(jìn)方法。在應(yīng)用方式上，需要設(shè)計(jì)新的計(jì)算模型，如新近提出的免疫系統(tǒng)模型、協(xié)同演化模型和螞蟻模型等。在實(shí)際計(jì)算中，并行和分布式計(jì)算方法對(duì)算法的影響日益得到重視。在應(yīng)用領(lǐng)域中，除問(wèn)題優(yōu)化外，還涉及到工程應(yīng)用的各個(gè)方面。在計(jì)算機(jī)科學(xué)領(lǐng)域，機(jī)器學(xué)習(xí)、模式識(shí)別和自動(dòng)程序設(shè)計(jì)等子域也有廣闊應(yīng)用前景。進(jìn)化計(jì)算中的各個(gè)分支之間的相互融合，進(jìn)化計(jì)算與其他計(jì)算智能方法的結(jié)合成為目前研究的熱點(diǎn)之一。為使進(jìn)化計(jì)算真正進(jìn)入實(shí)際應(yīng)用，需要開發(fā)商品級(jí)的軟件系統(tǒng)。在計(jì)算機(jī)體系結(jié)構(gòu)領(lǐng)域，如果設(shè)計(jì)出適合進(jìn)化計(jì)算的硬件，那么不僅會(huì)推動(dòng)進(jìn)化計(jì)算的應(yīng)用，而且也將會(huì)對(duì)傳統(tǒng)的馮諾依曼體系結(jié)構(gòu)產(chǎn)生巨大的挑戰(zhàn)。與進(jìn)化計(jì)算方法廣泛應(yīng)用相比，在理論研究方面，尚存在很多不足。由于進(jìn)化計(jì)算缺乏統(tǒng)一、完整的理論體系，目前一些理論結(jié)果主要集中在收斂性分析上，而且很難給出收斂速度的估計(jì)。如編碼方案、控制參數(shù)和遺傳算子等因素對(duì)算法性能的影響等問(wèn)題，只能具體問(wèn)題具體分析，并且在多數(shù)情況下還只能依賴于計(jì)算機(jī)模擬的實(shí)驗(yàn)數(shù)據(jù)。當(dāng)前，迫切需要嚴(yán)密、第一章緒論4科學(xué)的一般規(guī)律和方法，對(duì)進(jìn)化計(jì)算的研究進(jìn)行指導(dǎo)。從90年代初開始，進(jìn)化計(jì)算、神經(jīng)計(jì)算和模糊系統(tǒng)等逐步形成了一個(gè)新的研究方向計(jì)算智能（COMPUTATIONALINTELLIGENCE,CI）。與傳統(tǒng)人工智能（ARTIFICIALINTELLIGENCE,AI）方法相比，CI得到了更加廣泛的注意，也取得了很大進(jìn)展。這主要由于CI有以下特征57可縮放的結(jié)果傳統(tǒng)的AI方法在實(shí)驗(yàn)室階段能夠工作，而對(duì)真實(shí)世界無(wú)能為力。而從最開始，CI就是為了處理不同規(guī)模的問(wèn)題，并隨著CI的發(fā)展，能夠處理的領(lǐng)域越來(lái)越大。實(shí)際性傳統(tǒng)的AI方法只能處理理想環(huán)境，而CI從一開始就針對(duì)實(shí)際的計(jì)算問(wèn)題如復(fù)雜仿真、優(yōu)化、自動(dòng)控制等。這種特性現(xiàn)在仍在繼續(xù)得到發(fā)揚(yáng)。小而經(jīng)濟(jì)的模型當(dāng)早期的AI似乎滿足于嚴(yán)格算法理論與實(shí)際問(wèn)題之間的屏障時(shí)，CI找出了一套足夠復(fù)雜以滿足其設(shè)計(jì)的模型。雖然CI丟失了一些嚴(yán)格性，但這也正是使CI能夠得到廣泛應(yīng)用的優(yōu)點(diǎn)之一。目前的人工智能領(lǐng)域已經(jīng)包括傳統(tǒng)的基于符號(hào)處理的符號(hào)主義學(xué)派、以神經(jīng)網(wǎng)絡(luò)為代表的連接主義學(xué)派、以人工生命為代表的現(xiàn)場(chǎng)學(xué)派和以進(jìn)化計(jì)算為代表的進(jìn)化主義學(xué)派等，呈現(xiàn)出百花齊放的態(tài)勢(shì)。14本文的研究?jī)?nèi)容本文針對(duì)進(jìn)化算法，特別是遺傳算法進(jìn)行了一些理論上的探討。這些探討主要涉及遺傳算法的收斂性、收斂速度和全局動(dòng)力形態(tài)等方面，同時(shí)對(duì)目前得到廣泛重視的生境遺傳算法進(jìn)行了初步研究。對(duì)于標(biāo)準(zhǔn)遺傳算法，建立數(shù)學(xué)模型，分析模型的收斂性是遺傳算法理論研究中的重要一環(huán)。前人對(duì)此已做了許多研究工作，其中使用MARKOV模型的方法，雖然討論了交叉算子的作用，只是將其作為一個(gè)模型中狀態(tài)轉(zhuǎn)換的算子，最終結(jié)論的取得需要依賴于變異算子的不可約性。在這種方法中，遺傳算法中起關(guān)鍵作用的交叉算子，成為算法收斂性證明中的一個(gè)障礙，從而未體現(xiàn)出其在引導(dǎo)收斂目標(biāo)中的作用。在動(dòng)力系統(tǒng)的方法中，由于交叉算子的非線性，建模和分析的過(guò)程變得更加復(fù)雜。本文使用動(dòng)力第一章緒論5系統(tǒng)的方法建立了包含選擇算子和交叉算子的標(biāo)準(zhǔn)遺傳算法的數(shù)學(xué)模型。首次闡明了局部極值點(diǎn)的含義，證明了算法在局部極值點(diǎn)的局部收斂性。在分析過(guò)程中，使用了按照海明距離重新排列基因型的方法，明確指出了交叉算子在算法收斂性中的作用。并將這個(gè)結(jié)論擴(kuò)展到其他的選擇算子和交叉算子上。為深入了解遺傳算法的運(yùn)行機(jī)制，不僅要知道算法的收斂性，還需要了解算法在沒(méi)有達(dá)到收斂時(shí)的特性。本文針對(duì)一個(gè)特定問(wèn)題，深入到算法的運(yùn)行過(guò)程，描述了其在各種算法參數(shù)時(shí)的全局狀態(tài)，并說(shuō)明了變異算子對(duì)算法全局動(dòng)力形態(tài)的影響。在討論單一算子的作用時(shí)，選擇算子收斂速度的衡量指標(biāo)是取代時(shí)間。在以前定義取代時(shí)間時(shí)，混淆了群體規(guī)模和基因型種類這兩個(gè)變量，因此本文重新定義了這個(gè)概念。并證明了取代時(shí)間的階與適應(yīng)度函數(shù)的選取和初始群體分布無(wú)關(guān)。進(jìn)而提出了能更清晰反映選擇算子效果的取代時(shí)間系數(shù)這個(gè)概念。目前，采用生境遺傳算法解決多模函數(shù)優(yōu)化問(wèn)題，得到了密切重視。本文將聚類分析和生境算法相結(jié)合，提出了一種新的生境遺傳算法。該算法能夠自適應(yīng)地排除適應(yīng)度較小的局部極值點(diǎn)。本文同時(shí)對(duì)這種算法作了初步的數(shù)學(xué)分析和實(shí)驗(yàn)驗(yàn)證。本文的結(jié)構(gòu)如下在第二章中，回顧了進(jìn)化算法的歷史發(fā)展，介紹了進(jìn)化算法的基本結(jié)構(gòu)，對(duì)算法中的重要因素，如編碼、適應(yīng)度度量等問(wèn)題作了說(shuō)明。對(duì)遺傳算法的各個(gè)組成部分進(jìn)行了描述。為后面為算法的建模做出了準(zhǔn)備。在第三章中，針對(duì)遺傳算法，介紹了目前常見的各種理論分析工具和方法，并簡(jiǎn)要介紹了各種方法所得到的成果。對(duì)于我們后面使用的動(dòng)力系統(tǒng)等方法，介紹了一些數(shù)學(xué)準(zhǔn)備知識(shí)。對(duì)于標(biāo)準(zhǔn)遺傳算法，在第四章中證明了在無(wú)限群體和忽略變異算子時(shí)，其在局部極值點(diǎn)的收斂性，以及局部極值點(diǎn)的出現(xiàn)條件。證明首先是對(duì)適應(yīng)度比例選擇算子和單點(diǎn)交叉算子進(jìn)行的。然后擴(kuò)展到基于排名和基于錦標(biāo)賽的選擇算子，以及其他類型的交叉算子。然后根據(jù)這些結(jié)論，對(duì)改進(jìn)遺傳算法給出了一些理論上的建議和指導(dǎo)。第一章緒論6為進(jìn)一步說(shuō)明遺傳算法的運(yùn)行特性，在第五章中，我們討論了遺傳算法的全局動(dòng)力形態(tài)。我們對(duì)于一個(gè)特定問(wèn)題，建立了其在各種算法參數(shù)時(shí)的數(shù)學(xué)模型，找到了模型的全局吸引點(diǎn)和排斥不動(dòng)點(diǎn)，并對(duì)全局吸引點(diǎn)計(jì)算了吸引區(qū)間。在這一章中，我們還對(duì)變異算子對(duì)算法全局動(dòng)力形態(tài)的影響作了說(shuō)明。在第六章中，為了說(shuō)明遺傳算法，尤其是選擇算子的收斂速度，我們重新明確定義了取代時(shí)間的概念，計(jì)算了適應(yīng)度比例選擇算子的取代時(shí)間，并證明了這個(gè)時(shí)間的階不依賴于適應(yīng)度函數(shù)的具體形式和初始群體的分布狀態(tài)。在第七章中，提出了一種新的基于聚類分析和資源競(jìng)爭(zhēng)模型的生境遺傳算法。這種算法將聚類分析、共享技術(shù)和擁擠技術(shù)有機(jī)地結(jié)合起來(lái)，可以有效地對(duì)多模函數(shù)進(jìn)行優(yōu)化，而無(wú)需事先確定生境的具體數(shù)目和生境半徑的大小。通過(guò)數(shù)學(xué)分析，證明了這種算法可以控制收斂到的生境的數(shù)目，避免找到無(wú)效的極值點(diǎn)。第八章是本文的結(jié)論和進(jìn)一步的研究工作。第二章進(jìn)化算法基礎(chǔ)7第二章進(jìn)化算法基礎(chǔ)21進(jìn)化算法（EVOLUTIONARYALGORITHMS,EAS）進(jìn)化算法的基本思想是模擬自然界的進(jìn)化方式。DARWIN的進(jìn)化論的基本思想是“物競(jìng)天擇”。在EA中，獲得一個(gè)給定問(wèn)題的解可以看作是一個(gè)生存任務(wù)可行解之間為生存（或繁殖）的權(quán)利進(jìn)行競(jìng)爭(zhēng)，根據(jù)生物進(jìn)化的經(jīng)驗(yàn)，這種競(jìng)爭(zhēng)可以產(chǎn)生出一個(gè)最具有適應(yīng)性的解，也就是問(wèn)題的優(yōu)化解。更詳細(xì)地說(shuō)，EA維護(hù)一個(gè)群體，通過(guò)一定的進(jìn)化算子來(lái)進(jìn)行進(jìn)化，這些算子包括選擇、重組和變異。群體中的每一個(gè)個(gè)體都在進(jìn)化，并賦予一個(gè)環(huán)境定義的適應(yīng)度。選擇操作著重于那些高適應(yīng)度的個(gè)體，起到挖掘（EXPLOITING）可用的適應(yīng)度信息的作用；重組和變異算子改變這些個(gè)體，起到啟發(fā)式擴(kuò)展（EXPLORATION）的作用。雖然從生物進(jìn)化的角度來(lái)看，這些算子比較簡(jiǎn)單，但已經(jīng)可以提供足夠健壯（ROBUST）和自適應(yīng)ADAPTIVE的搜索機(jī)制。目前，越來(lái)越多的領(lǐng)域涉及到優(yōu)化問(wèn)題。這類問(wèn)題目前尚沒(méi)有快速合理的算法，其中很多問(wèn)題屬于NP問(wèn)題，雖然NPP問(wèn)題尚未得到最后證明，但多數(shù)專家傾向于成立。因此這類問(wèn)題在多項(xiàng)式時(shí)間內(nèi)難以得到解決。對(duì)于這類優(yōu)化問(wèn)題，可以被看作是對(duì)潛在解空間的一種搜索過(guò)程。如果規(guī)模較小，尚可以使用窮舉搜索方法。當(dāng)空間較大時(shí)，這種方法就不能使用了。當(dāng)問(wèn)題具有明確的數(shù)學(xué)特征時(shí)，可以使用基于數(shù)學(xué)的各種搜索算法，如線性規(guī)劃、梯度下降及其他基于梯度的搜索算法等。對(duì)于沒(méi)有顯著的數(shù)學(xué)特征，經(jīng)常是由離散空間組成的問(wèn)題，如TSP問(wèn)題（TRAVELINGSALESMANPROBLEM）、布線問(wèn)題（WIREROUTING）等，需要使用一些其他的人工智能技術(shù)。進(jìn)化算法作為一種概率算法，可以有效的對(duì)解空間進(jìn)行搜索。同時(shí)，進(jìn)化算法具有較強(qiáng)的通用性和適用性，它不依賴于問(wèn)題的具體形式和領(lǐng)域知識(shí)（當(dāng)然，引入領(lǐng)域知識(shí)可能有利于算法的運(yùn)行），同時(shí)又具有內(nèi)在的并第二章進(jìn)化算法基礎(chǔ)8行性，因此能夠在較快時(shí)間內(nèi)找到最優(yōu)解或準(zhǔn)最優(yōu)解。下面我們介紹進(jìn)化算法的發(fā)展歷史和主要分支。211進(jìn)化規(guī)劃（EVOLUTIONARYPROGRAMMING，EP）EP由FOGEL在十九世紀(jì)六十年代年提出46,48,49。EP根據(jù)問(wèn)題使用特定的表現(xiàn)型，例如，在浮點(diǎn)優(yōu)化問(wèn)題中，個(gè)體的表示是實(shí)數(shù)值的向量；在TSP問(wèn)題中使用有向序列表；在有限狀態(tài)機(jī)問(wèn)題中使用圖。通常EP作為優(yōu)化器使用，使用實(shí)數(shù)向量作為基因編碼。在初始化之后，所有的個(gè)體被選擇為父本，然后變異，產(chǎn)生P個(gè)后代。這些個(gè)體被評(píng)價(jià)，然后使用概率的錦標(biāo)賽選擇算法從2P個(gè)個(gè)體中選擇出P個(gè)個(gè)體組成下一代。通常保留最好的精英個(gè)體（ELITISM），以保證一旦得出優(yōu)化解，就不會(huì)丟失。變異算子的形式基于表現(xiàn)型，通常是自適應(yīng)的。例如，對(duì)于實(shí)數(shù)向量，個(gè)體中的每一個(gè)分量都有一個(gè)自適應(yīng)的變異比例，變異通常是期望為零的分布（如正態(tài)分布）。在EP中不使用重組算子，由于變異的形式具有很強(qiáng)的機(jī)動(dòng)性（FLEXIBLE），可以產(chǎn)生和重組類似的效果。對(duì)于EP，收斂定理保證基本算法以概率1全局收斂。這個(gè)結(jié)論是使用離散空間的MARKOV鏈得到的，也可以在計(jì)算機(jī)上由數(shù)值表現(xiàn)出來(lái)。在離散空間的格點(diǎn)上，對(duì)于包含距離最優(yōu)點(diǎn)最近的個(gè)體組成的所有可能的群體，由于精英個(gè)體的存在，存在一個(gè)吸收態(tài)。212進(jìn)化策略（EVOLUTIONSTRATEGIES，ES）ES由RECHENBERG在1973年提出108,109，使用單個(gè)體的群體，選擇和變異算子。后來(lái)，SCHWEFUL引入了重組算子，擴(kuò)展到一個(gè)以上的個(gè)體，并與其他典型的優(yōu)化技術(shù)進(jìn)行了比較。由于最初是解決水力學(xué)問(wèn)題，典型的ES使用實(shí)數(shù)向量表示個(gè)體。在初始化和評(píng)價(jià)個(gè)體之后，隨機(jī)均勻地選擇個(gè)體作為父代。在典型的重組ES中，父代通過(guò)重組操作產(chǎn)生子代，然后子代通過(guò)變異算子進(jìn)行變化。子代的數(shù)量大于父代的數(shù)量P。生存選擇是決定性的，通過(guò)下面兩種方法之一來(lái)實(shí)現(xiàn)。第一種方法允許P個(gè)最好的子代個(gè)體存活，然后使用這些個(gè)體替換父代。這稱之為（,）方式，指群體規(guī)模，指產(chǎn)生的子第二章進(jìn)化算法基礎(chǔ)9代數(shù)目。第二種方法稱為（）方式，允許在父代和子代中選擇最好的個(gè)存活。（）方法是一種精英算法，而（,）算法不是。和EP一樣，也是用自適應(yīng)的變異算子。但和EP不一樣在于，在ES中變異算子不扮演重要的角色。ES研究的很多理論涉及到收斂速率，試圖加快這個(gè)速率。目前已有對(duì)于（）ES算法的全局概率收斂證明。但對(duì)（,）算法還沒(méi)有得到類似的結(jié)論。213遺傳算法（GENETICALGORITHMS,GA）GA由HOLLAND在1975年提出71，更早的思想可以追溯到六十年代70。典型的GA使用獨(dú)立于問(wèn)題的表示形式，也就是二進(jìn)制位串，這種編碼既適合于變異又適合于交叉，并且HOLLAND強(qiáng)調(diào)交叉算子的搜索能力。隨后，在其著作ADAPTATIONINNATURALANDARTIFICIALSYSTEM中，他將其引入到自適應(yīng)系統(tǒng)中，后來(lái)又推廣到其他領(lǐng)域。GA的進(jìn)化對(duì)象是由多個(gè)個(gè)體（INDIVIDUALS）組成的群體（POPULATION）。在初始化之后，通過(guò)基于適應(yīng)度的概率選擇算法選擇父代，并通過(guò)交叉（CROSSOVER）和變異（MUTATION）來(lái)維持群體的多樣性。如此演化下去，直到期待的終止條件。作為進(jìn)化算法中最具有代表性的算法，遺傳算法以其簡(jiǎn)單通用的編碼技術(shù)和明白有效的進(jìn)化操作得到了廣泛的應(yīng)用。目前的遺傳算法已經(jīng)不再局限于二進(jìn)制編碼。最近很多的應(yīng)用嘗試使用其他的形式，如圖、LISP表達(dá)式、有序列表和實(shí)數(shù)向量等。這些改進(jìn)說(shuō)明，遺傳算法在很大程度上與其他的進(jìn)化算法已經(jīng)融合在一起。22進(jìn)化算法的基本結(jié)構(gòu)假設(shè)我們欲解決的優(yōu)化問(wèn)題如下MAXXXF這里是問(wèn)題空間，可以是離散空間，也可以是連續(xù)空間，即實(shí)空間NR的一個(gè)子集。第二章進(jìn)化算法基礎(chǔ)10使用進(jìn)化計(jì)算方法進(jìn)行優(yōu)化通常是將原始問(wèn)題進(jìn)行編碼（ENCODING），然后再進(jìn)行優(yōu)化的。這種編碼就是將問(wèn)題空間中的點(diǎn)映射到基因空間O的過(guò)程。記作F?；蚩臻gO既可以是二進(jìn)制位串表示，也可以是實(shí)空間NR的一個(gè)子集。編碼的逆過(guò)程稱之為解碼（DECODING）。對(duì)于我們重點(diǎn)研究的二進(jìn)制位串空間，L1,0，L稱為染色體長(zhǎng)度。稱問(wèn)題空間中的點(diǎn)為表現(xiàn)型（PHENOTYPE），基因空間中的點(diǎn)為基因型（GENOTYPE）。對(duì)于一個(gè)特定的基因型，其對(duì)應(yīng)的表現(xiàn)型的優(yōu)化函數(shù)值稱為適應(yīng)度（FITNESS）。當(dāng)基因空間的編碼方式為位串時(shí)，也稱之為染色體（CHROMOSOME），其中的每一位稱之為基因（GENE）?；虻娜≈捣秶凶龅任换颍ˋLLELE）。進(jìn)化算法通常是針對(duì)多個(gè)潛在解同時(shí)進(jìn)行的。這些潛在解構(gòu)成一個(gè)數(shù)量為N的群體（POPULATION）。群體中的每一個(gè)潛在解稱之為個(gè)體（INDIVIDUAL）。進(jìn)化是按代施加到群體上的。廣義的進(jìn)化算法由以下幾個(gè)步驟組成1初始化群體2DO3計(jì)算適應(yīng)度4根據(jù)適應(yīng)度選擇下一代中存活的個(gè)體5產(chǎn)生新的個(gè)體6UNTIL滿足終止條件。對(duì)于一個(gè)典型的EA，通常是從隨機(jī)的初始化群體開始，在某些情況下，也可以使用相關(guān)的領(lǐng)域知識(shí)創(chuàng)建初始群體。適應(yīng)度量度取決于個(gè)體對(duì)環(huán)境的價(jià)值。適應(yīng)度的計(jì)算可以是一個(gè)簡(jiǎn)單的數(shù)學(xué)公式，也可能復(fù)雜到運(yùn)行一個(gè)特定的過(guò)程。選擇通常分為兩種繁殖選擇和生存選擇。繁殖選擇決定誰(shuí)將成為父代和可以產(chǎn)生多少個(gè)后代，后代通過(guò)重組及變異來(lái)產(chǎn)生。生存選擇決定群體中誰(shuí)將存活。下面以GA為主要代表，詳細(xì)介紹進(jìn)化算法的一些概念。221編碼在使用進(jìn)化算法計(jì)算之前，需要對(duì)所求解問(wèn)題進(jìn)行編碼。編碼方法決定了基因型和表現(xiàn)型之間的轉(zhuǎn)換方法，某些特定類型的編碼方法還決定了第二章進(jìn)化算法基礎(chǔ)11遺傳算子的選擇。編碼的好壞在很大程度上決定了算法的優(yōu)劣。由于編碼方案取決于具體問(wèn)題的情況，因此上并沒(méi)有一定的直到理論和評(píng)價(jià)原則。作為參考，DEJONG提出了兩條操作性比較強(qiáng)的編碼原則38一、（有意義積木塊原則）應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的具有低階、短定義長(zhǎng)度的編碼方案。二、（最小字符集編碼原則）應(yīng)使用能使問(wèn)題得到自然表示或描述的具有最小編碼字符集的編碼方案。這兩條原則具有一般的指導(dǎo)性。隨著時(shí)間的推移，使用的編碼方式也越來(lái)越豐富。在實(shí)際使用時(shí)，我們還需要考慮其他的原則。尤其是對(duì)于約束優(yōu)化問(wèn)題，可能存在大量致死基因（LETHAL）。一種方法是在編碼時(shí)避免不合法個(gè)體的存在，這樣有可能造成編碼和算子的復(fù)雜化與不一致性。另一種方法是對(duì)于不合法的個(gè)體，對(duì)其適應(yīng)度加以懲罰。位串編碼對(duì)于標(biāo)準(zhǔn)的遺傳算法，最常用的編碼方式為位串編碼。也就是說(shuō)，在進(jìn)行進(jìn)化操作時(shí)，將基因看作一個(gè)有序的位串序列，而不考慮每一位的含義。這種編碼類似于生物染色體的組成，交叉和變異等遺傳操作很容易進(jìn)行。使用位串編碼時(shí)，二進(jìn)制編碼同時(shí)表示的模式數(shù)最多。并且實(shí)現(xiàn)簡(jiǎn)單，對(duì)于很多離散優(yōu)化問(wèn)題（如背包問(wèn)題等），基因型與表現(xiàn)型的對(duì)應(yīng)關(guān)系非常明確。因此得到廣泛應(yīng)用。對(duì)于連續(xù)優(yōu)化問(wèn)題，二進(jìn)制編碼的主要問(wèn)題是，相鄰整數(shù)之間的HAMMING距離可能很大，帶來(lái)很多不必要的局部極值點(diǎn)（詳見第四章），影響算法的搜索性能。這一缺點(diǎn)問(wèn)題也稱為HAMMING懸崖（HAMMINGCLIFF）?？朔@一缺點(diǎn)的一種方法是使用GRAY編碼87。GRAY編碼與二進(jìn)制編碼的對(duì)應(yīng)關(guān)系如下設(shè)二進(jìn)制串,121NN，對(duì)應(yīng)的GRAY編碼串為,110NN，則第二章進(jìn)化算法基礎(chǔ)12ELSE,1KIF,11KKK21，同樣ELSE,1KIF,11KKK22這里表示模2加法，也就是異或操作。GRAY編碼的顯著特點(diǎn)是對(duì)于距離為1的二進(jìn)制表示，其GRAY編碼之間的HAMMING距離為1。因此可以在一定程度上克服上面提到的缺點(diǎn)。實(shí)數(shù)編碼當(dāng)問(wèn)題空間是實(shí)數(shù)連續(xù)空間時(shí)，可以直接采用實(shí)數(shù)進(jìn)行編碼。對(duì)于實(shí)數(shù)編碼，從理論上講，二進(jìn)制編碼的各種遺傳操作都可以使用，但實(shí)際應(yīng)用時(shí)通常都使用專門針對(duì)實(shí)數(shù)編碼設(shè)計(jì)的算子。從進(jìn)化計(jì)算的歷史上來(lái)看，進(jìn)化策略和遺傳規(guī)劃都采用實(shí)數(shù)編碼。近年來(lái)，遺傳算法在求解復(fù)雜連續(xù)優(yōu)化問(wèn)題時(shí)也經(jīng)常使用實(shí)數(shù)編碼。實(shí)際上，使用實(shí)數(shù)編碼的遺傳算法和進(jìn)化策略的區(qū)別已經(jīng)越來(lái)越小。結(jié)構(gòu)化編碼對(duì)于很多具有明確的數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，更加自然地表示是直接對(duì)這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作。稱之為結(jié)構(gòu)化編碼。常見的編碼方式有樹和圖。這種編碼方式一般是針對(duì)具體問(wèn)題設(shè)計(jì)具體的編碼和遺傳算子。很難具有通用性。對(duì)于由KOZA提出的遺傳規(guī)劃（GENETICPROGRAMMING）77，可以看作是使用逆波蘭表達(dá)式的二叉樹作為結(jié)構(gòu)化編碼的進(jìn)化算法的例子。222適應(yīng)度度量在自然界中，適應(yīng)度反映個(gè)體對(duì)于環(huán)境的適應(yīng)程度，是自然選擇的唯一參考因素。同樣，在進(jìn)化算法中，適應(yīng)度用來(lái)反映個(gè)體的優(yōu)化程度。在選擇算子使用適應(yīng)度時(shí)，一般要求適應(yīng)度是一個(gè)正實(shí)數(shù)；在某些策略下，也可以使用非數(shù)值化的適應(yīng)度度量。從代數(shù)結(jié)構(gòu)的角度來(lái)看，個(gè)體的適應(yīng)度集合一般需要構(gòu)成一個(gè)有序集，至少要構(gòu)成一個(gè)格（LATTICE）。也就是說(shuō)，至少要在兩個(gè)適應(yīng)度之間明確定義“小于”關(guān)系。當(dāng)欲求解的原始問(wèn)題是數(shù)值優(yōu)化問(wèn)題時(shí)，可以直接將求解函數(shù)作為適應(yīng)度。個(gè)體的適應(yīng)度取值通常為正的實(shí)數(shù)值。一般情況下，要求當(dāng)個(gè)體的第二章進(jìn)化算法基礎(chǔ)13性能越好時(shí)，其適應(yīng)度值越大，而且要求非負(fù)（如GA中的比例選擇策略）。因此，有時(shí)需要對(duì)原始的適應(yīng)度函數(shù)進(jìn)行變換。當(dāng)原始問(wèn)題是非數(shù)值優(yōu)化問(wèn)題時(shí)，一種方案是選擇恰當(dāng)?shù)亩攘亢瘮?shù)充當(dāng)適應(yīng)度函數(shù)，將某個(gè)可行解的適應(yīng)度變換到正實(shí)數(shù)空間；另外一種方案是使用不基于適應(yīng)度函數(shù)具體數(shù)值的選擇策略。如下文提到的排名選擇和錦標(biāo)賽選擇。在很多情況下，原始的適應(yīng)度函數(shù)（及其簡(jiǎn)單變換）存在一些不適合選擇使用的特點(diǎn)。有時(shí)，適應(yīng)度值之間的差別較小，導(dǎo)致選擇效果不明顯；有時(shí)，優(yōu)勢(shì)個(gè)體的適應(yīng)度值過(guò)大，可能產(chǎn)生早熟收斂。在這些情況下，需要對(duì)原始的適應(yīng)度函數(shù)進(jìn)行某種變換，以得到更好的性能。這種變換的具體形式通常是由經(jīng)驗(yàn)和試驗(yàn)的方式獲得的。223進(jìn)化算子一般來(lái)說(shuō),各種進(jìn)化算法的不同點(diǎn)在于產(chǎn)生新的個(gè)體與選擇的方式不同。這種方式也稱之為算子（OPERATOR），也有的文獻(xiàn)稱之為策略（STRATEGY）。進(jìn)化算子可以分為兩類選擇算子和演化算子。在有些算法的具體實(shí)現(xiàn)中，這兩種算子是混合在一起的。選擇算子充當(dāng)自然進(jìn)化中自然選擇的角色，起到指引搜索方向的作用。其目的是提高具有較高適應(yīng)度的個(gè)體或其后代存活的概率。通過(guò)選擇算子，可以使群體向更高適應(yīng)度的方向前進(jìn)。不同的選擇算子導(dǎo)致不同的選擇壓力（SELECTIONINTENSITY）。選擇壓力較大，算法的收斂速度較快，但也容易導(dǎo)致早熟收斂。選擇算子按照選擇階段可分為繁殖選擇和生存選擇；按照比較范圍可分為種群選擇和生境選擇；按照計(jì)算方式可分為確定性選擇和概率性選擇。繁殖選擇指通過(guò)選擇確定那些個(gè)體可以用來(lái)產(chǎn)生下一代；生存選擇指通過(guò)選擇確定那些個(gè)體可以存活。種群選擇指選擇是在整個(gè)種群的范圍內(nèi)進(jìn)行的，個(gè)體的適應(yīng)度要和整個(gè)種群的適應(yīng)度分布進(jìn)行比較；生境選擇指選擇是在兩個(gè)或幾個(gè)個(gè)體（通常具有血緣關(guān)系）之間進(jìn)行的。確定性選擇算子使用確定性的算法進(jìn)行選擇；而概率性選擇算子在選擇過(guò)程中引入了隨機(jī)性的因素。第二章進(jìn)化算法基礎(chǔ)14演化算子充當(dāng)自然進(jìn)化中繁殖過(guò)程中遺傳和變異的角色，起到維護(hù)種群個(gè)體構(gòu)成多樣性（DIVERSITY）的作用。它包括交叉（CROSSOVER）和變異（MUTATION）兩種。交叉算子又稱重組（RECOMBINATION）算子，用于從兩個(gè)父本產(chǎn)生一個(gè)新的個(gè)體。演化算子在進(jìn)化算法中起到構(gòu)造的作用，可以從一個(gè)、兩個(gè)或多個(gè)個(gè)體出發(fā)，構(gòu)造出新的個(gè)體。在產(chǎn)生和維護(hù)群體多樣性的同時(shí)，也起到局部搜索的作用。23遺傳算法的基本結(jié)構(gòu)遺傳算法和其他進(jìn)化算法相比的顯著特征是使用交叉算子產(chǎn)生下一代個(gè)體；使用繁殖選擇式的選擇算子、根據(jù)適應(yīng)度隨機(jī)選取父本；一般使用二進(jìn)制位串式編碼及相應(yīng)的交叉算子。遺傳算法的基本結(jié)構(gòu)如下算法隨機(jī)化初始群體P0,T0。WHILE不滿足終止準(zhǔn)則DO計(jì)算所有個(gè)體的適應(yīng)度計(jì)算每個(gè)個(gè)體的選擇概率均勻隨機(jī)選擇PGN個(gè)個(gè)體，直接插入到下一代群體PT1中。FORI0IT時(shí)，有1TFTF?；蛘咧赶到y(tǒng)以極限方式趨于一個(gè)固定的狀態(tài)，即STFTFLIM。在GA的運(yùn)行中，上面所說(shuō)的收斂性，即是算法運(yùn)行到一定次數(shù)后，群體中所有個(gè)體均維持不變的狀態(tài)。這種收斂并不意味著群體中所有的個(gè)體均相同。但在GA的使用中，我們更關(guān)心的是這樣一種狀態(tài)，群體中所有的個(gè)體具有一致的基因型，并維持不變。我們這種狀態(tài)為強(qiáng)收斂；相對(duì)的，上面所說(shuō)的狀態(tài)稱之為弱收斂。也就是說(shuō)，“收斂到不變狀態(tài)”與“收斂到一致狀態(tài)”是兩個(gè)不同的概念。在關(guān)于GA的收斂性研究中，一般都指強(qiáng)收斂。在本文中，在不引起歧義的情況下，強(qiáng)收斂也簡(jiǎn)稱為收斂。第三章進(jìn)化算法的理論分析方法21對(duì)于實(shí)際問(wèn)題，我們希望GA能夠?qū)ふ业侥繕?biāo)函數(shù)的全局極值點(diǎn)。當(dāng)GA進(jìn)入強(qiáng)收斂狀態(tài)，并且所有個(gè)體均為全局極值點(diǎn)時(shí)，稱為全局收斂。如果收斂到的目標(biāo)函數(shù)的非全局極值點(diǎn)，稱為局部收斂。從實(shí)際中可以發(fā)現(xiàn)，GA常常不能全局收斂。因此研究算法全局收斂的條件具有重要的應(yīng)用價(jià)值。綜上所述，為得到妥善的收斂理論，需要逐次證明以下幾點(diǎn)。1算法的弱收斂性和收斂條件2算法的強(qiáng)收斂性和收斂條件3算法全局收斂的條件。32GA建模使用的數(shù)學(xué)方法在進(jìn)行理論分析之前，需要建立適當(dāng)?shù)臄?shù)學(xué)模型。這個(gè)過(guò)程叫做建模。由于進(jìn)化算法是一個(gè)新興的交叉學(xué)科，在成長(zhǎng)過(guò)程中從生物學(xué)、應(yīng)用數(shù)學(xué)、物理學(xué)等學(xué)科吸取了很多營(yíng)養(yǎng)。它的理論分析也涉及到了數(shù)學(xué)中的很多分支。在介紹這些建模和分析方法之前，需要了解一下必需的數(shù)學(xué)知識(shí)。一般說(shuō)來(lái)，對(duì)于有限群體模型，由于GA的隨機(jī)性，會(huì)涉及許多概率論與隨機(jī)過(guò)程的知識(shí)；對(duì)于無(wú)限群體，還要了解動(dòng)力系統(tǒng)的知識(shí)和方法。在這里簡(jiǎn)單介紹一下隨機(jī)過(guò)程和動(dòng)力系統(tǒng)的一些準(zhǔn)備知識(shí)。這里列出的定義和定理可以在介紹概率論、線性代數(shù)、隨機(jī)過(guò)程和動(dòng)力系統(tǒng)的書中找到31,137。321隨機(jī)變量以下關(guān)于概率論和隨機(jī)過(guò)程的定義和定理可以在定義21如果某個(gè)變量的取值隨偶然因素而變化，但又服從一定的概率分布規(guī)律，稱之為隨機(jī)變量。這里給出的定義是一種直觀的說(shuō)明，嚴(yán)格的定義可以由概率公理給出，或者使用測(cè)度論的方式描述31。給定隨機(jī)變量，可以用XPXF定義的分布函數(shù)來(lái)刻畫它的概率規(guī)律。分布函數(shù)需要滿足單調(diào)性、右連續(xù)性和邊界性。第三章進(jìn)化算法的理論分析方法22定義22如果隨機(jī)變量只取有限個(gè)值或在可數(shù)集合上取值，稱之為離散型隨機(jī)變量。如果其分布函數(shù)能夠表示為XDTTPXF，則稱為連續(xù)型隨機(jī)變量。定義23若,21N是聯(lián)系于同一組條件下的N個(gè)隨機(jī)變量，則稱之為N維隨機(jī)變量。若,21NXXX是實(shí)數(shù)空間RN中的一點(diǎn)，則事件,2211NNXXX的概率稱為這個(gè)隨機(jī)變量的聯(lián)合分布。如果從上面N個(gè)變量中取出M個(gè)分量構(gòu)成的M維隨機(jī)變量，則稱這M維隨機(jī)變量的聯(lián)合分布函數(shù)為M維邊緣分布函數(shù)。定義24設(shè)為一隨機(jī)變量，事件B的概率PB0，則稱BXPBXF為在事件B已經(jīng)發(fā)生的條件下的條件分布函數(shù)。隨機(jī)變量的數(shù)學(xué)期望（或均值）記為E，它描述了隨機(jī)變量的取值中心。隨機(jī)變量2E的數(shù)學(xué)期望稱為的方差，記為D，D的平方根稱為的均方差（或標(biāo)準(zhǔn)差），它們描述了隨機(jī)變量的可能取值與均值的偏差的疏密程度。對(duì)于連續(xù)型隨機(jī)變量DXXPEXXDFEXDDXXXPXXDFE2221對(duì)于離散型隨機(jī)變量121KKKKKKPEXDPXE22期望與方差之間滿足22EED23當(dāng)0R時(shí)，隨機(jī)變量RRE和的數(shù)學(xué)期望（假設(shè)存在）分別稱為隨機(jī)變量的R階原點(diǎn)矩和R階中心矩。特別的，均值是一階原點(diǎn)矩，方差是二階中心矩。第三章進(jìn)化算法的理論分析方法23322矩陣初步在關(guān)于MARKOV模型和動(dòng)力系統(tǒng)研究中，都要使用很多關(guān)于矩陣的概念和定理，下面作一初步介紹。定義25設(shè)A是一個(gè)N階方陣，若對(duì)于矩陣中任何元素都有0IJA，則稱A是非負(fù)的，記作A0；若任何元素都有0IJA，則稱A是正的，記作A0。定義26設(shè)A是一個(gè)N階非負(fù)矩陣，1如果存在正整數(shù)K，使得AK是正的，則稱A是本原的PRIMITIVE。2如果存在方陣C,T，通過(guò)相同的行列置換可以將矩陣變換為如下形式TROC，則稱A是可約的REDUCIBLE，否則稱A是不可約的。3如果對(duì)于任意一行，都有11NJIJA，稱矩陣A是隨機(jī)的STOCHASTIC。容易驗(yàn)證，隨機(jī)矩陣的乘積還是隨機(jī)矩陣。定義27設(shè)A是一個(gè)N階方陣，如果存在一個(gè)N維非零向量A和一個(gè)數(shù)，使得AAA，則稱為A的特征值EIGENVALUE，A為此特征值對(duì)應(yīng)的特征向量EIGENVECTOR。特征值和特征向量滿足以下性質(zhì)1設(shè)A的N個(gè)特征值分別為N,21，則它們的和等于A的跡，它們的積等于A的行列式，即AAININIIINIIATR101,2實(shí)對(duì)稱矩陣的特征值都是實(shí)數(shù)，并且有N個(gè)線性無(wú)關(guān)，正交的特征向量。3矩陣的特征值在相似變換下不變。定義28若實(shí)對(duì)稱矩陣A的所有特征值都大于零，則稱之為正定POSITIVEDEFINITE矩陣，若所有特征值都不小于零，稱之為半正定的POSITIVESEMIDEFINITE。定義29若矩陣A的對(duì)角線以下的元素都為0，則稱A為上三角矩陣。第三章進(jìn)化算法的理論分析方法24上三角矩陣的和、差、積以及數(shù)乘的結(jié)果仍然是上三角矩陣。同時(shí)，上三角矩陣的特征值就是其對(duì)角線元素。323隨機(jī)過(guò)程若對(duì)于每個(gè)TT（T是某個(gè)固定的指標(biāo)集合），T是個(gè)隨機(jī)變量，則把這樣的隨機(jī)變量族稱為隨機(jī)過(guò)程。如果T是整數(shù)集或其子集，則稱之為離散時(shí)間的隨機(jī)過(guò)程，也稱為隨機(jī)序列。如果T是實(shí)數(shù)集或其子集，則稱之為連續(xù)時(shí)間的隨機(jī)過(guò)程。定義210對(duì)于T是非負(fù)整數(shù)集合的隨機(jī)序列TNNX，如果滿足，|,|11001111NNNNNNIXJXPIXIXIXJXP則稱此隨機(jī)序列為馬爾可夫鏈（MARKOVCHAIN）。MARKOV鏈描述的隨機(jī)過(guò)程，可以直觀地理解為，“將來(lái)”的狀態(tài)只取決于“當(dāng)前”的狀態(tài)，而與“過(guò)去”的狀態(tài)無(wú)關(guān)。用2,1TTPIJ表示已知在時(shí)刻T1，系統(tǒng)處于EI的狀態(tài)下，在時(shí)刻T2系統(tǒng)處于狀態(tài)EJ的概率。也叫做轉(zhuǎn)移概率。若轉(zhuǎn)移概率只與兩個(gè)時(shí)刻的差有關(guān)，而與具體時(shí)刻無(wú)關(guān)，即,IJIJPTTP，稱此MARKOV鏈為齊次的（HOMOGENEOUS）。否則稱為非齊次的。對(duì)于齊時(shí)MARKOV鏈，一次轉(zhuǎn)移概率可以排列為一個(gè)概率轉(zhuǎn)移矩陣11100100PPPPPPIJN步的轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的N次冪。定義211稱狀態(tài)空間E的一個(gè)子集C為閉集，若C以外的任意狀態(tài)都不能從C中任意狀態(tài)到達(dá)。若E中不存在真子集為閉集，則稱此鏈為不可約的。定義212（狀態(tài)的分類）對(duì)于狀態(tài)EJ，1若單點(diǎn)集EJ為閉集，就稱之為吸引狀態(tài)，2若11NNJJP，則稱此狀態(tài)為常返的；若小于1，則為非常返的。第三章進(jìn)化算法的理論分析方法253若此狀態(tài)為常返的，則當(dāng)1NNJJPN時(shí)，稱之為積極常返的，否則稱之為消極常返的。4若正整數(shù)集0NJJPN的最大公約數(shù)T大于1，則稱此狀態(tài)是周期的，周期為T。否則稱之為非周期的。5若此狀態(tài)為常返的、非周期的，則稱之為遍歷的。定理21（遍歷性定理）對(duì)于不可約的，非周期的常返的MARKOV鏈，它是積極鏈的充分必要條件是存在唯一的平穩(wěn)分布，這個(gè)平穩(wěn)分布也是鏈的極限分布，并且各個(gè)分量嚴(yán)格為正。324動(dòng)力系統(tǒng)在十九世紀(jì)末到二十世紀(jì)初，POINCAR等人從經(jīng)典力學(xué)和微分方程的定性理論的研究中，提出了動(dòng)力系統(tǒng)的概念。從二十世紀(jì)七十年代開始，這一學(xué)科在各個(gè)領(lǐng)域中得到廣泛應(yīng)用。如氣象預(yù)報(bào)、統(tǒng)計(jì)力學(xué)、化學(xué)反應(yīng)、生態(tài)問(wèn)題、數(shù)量遺傳學(xué)和經(jīng)濟(jì)數(shù)學(xué)等方面。下面簡(jiǎn)要介紹動(dòng)力系統(tǒng)的一些概念137。動(dòng)力系統(tǒng)研究的目的是研究系統(tǒng)狀態(tài)變量隨時(shí)間變化的特性，它主要考察變量的變化方式和最終特性，如是否存在不動(dòng)點(diǎn)、周期點(diǎn)或極限環(huán)，它們是吸引的還是排斥的，它們的吸引空間等。簡(jiǎn)單地說(shuō)，對(duì)于一個(gè)變換H，及其迭代構(gòu)成了差分動(dòng)力系統(tǒng)。更嚴(yán)格的定義如下定義213設(shè)X是拓?fù)淇臻g，XXR是連續(xù)映射，如果F滿足XXXRTSXTSXTSXXX,0則稱F為X上的連續(xù)動(dòng)力系統(tǒng)。如果對(duì)此動(dòng)力系統(tǒng)進(jìn)行離散采樣，得到的序列稱之為離散動(dòng)力系統(tǒng)。本文只涉及實(shí)數(shù)空間的離散動(dòng)力系統(tǒng)，即狀態(tài)空間NR。根據(jù)O的維數(shù)可分為一維或高維動(dòng)力系統(tǒng)。定義214如果HXX，則X是H的不動(dòng)點(diǎn)。如果XXNH，則X是周期為N的周期點(diǎn)。滿足上式的最小正N稱為真周期。第三章進(jìn)化算法的理論分析方法26對(duì)于一維動(dòng)力系統(tǒng)的不動(dòng)點(diǎn)，如果其鄰域的點(diǎn)經(jīng)過(guò)變換收斂到此點(diǎn)，稱之為吸引點(diǎn)。如果鄰域的點(diǎn)都逃離此點(diǎn)，稱之為排斥點(diǎn)。定理22設(shè)P是FX的不動(dòng)點(diǎn)，且導(dǎo)數(shù)1PF，則存在包含P的開區(qū)間V，PXFVXNNLIM,則若。點(diǎn)P稱為吸引不動(dòng)點(diǎn)（又稱吸引子）。定理23設(shè)P是FX的不動(dòng)點(diǎn)，且導(dǎo)數(shù)1PF，則存在包含P的開區(qū)間V，使VXFNPXVXN,0,則存在若。點(diǎn)P稱為排斥不動(dòng)點(diǎn)（又稱排斥子）。對(duì)于高維動(dòng)力系統(tǒng)中，存在類似的概念。定義215（JACOBIN矩陣）設(shè)有定義在某一N維區(qū)域D上的關(guān)于N個(gè)自變量的N個(gè)函數(shù),2121222111NNNNNXXXFYXXXFYXXXFY，或簡(jiǎn)記為向量形式FXY并且關(guān)于自變量有連續(xù)偏導(dǎo)數(shù)。則由這些偏導(dǎo)數(shù)組成的矩陣NNNNNNXYXYXYXYXYXYXYXYXY212221212111DFX稱為函數(shù)組的JACOBIN矩陣。在高維動(dòng)力系統(tǒng)中，這個(gè)矩陣的作用與一維系統(tǒng)中的導(dǎo)數(shù)的作用相類似。定理24（多元函數(shù)微分的連鎖法則）設(shè)有兩個(gè)函數(shù)組FXY，GTX。它們的連鎖函數(shù)FGTY的JACOBIN矩陣等于兩個(gè)函數(shù)組的JACOBIN矩陣的乘積。定義216若N維動(dòng)力系統(tǒng)NNRRF的不動(dòng)點(diǎn)為P，如果F在P點(diǎn)的JACOBIN矩陣DF的所有特征值的絕對(duì)值都不為1，稱P為雙曲不動(dòng)點(diǎn)。定義P的類型如下第三章進(jìn)化算法的理論分析方法27若所有特征值的絕對(duì)值都小于1，則P是吸引不動(dòng)點(diǎn)。若所有特征值的絕對(duì)值都大于1，則P是排斥不動(dòng)點(diǎn)。若有些特征值的絕對(duì)值大于1，有些小于1，則P是鞍點(diǎn)。定理25設(shè)映射F在P點(diǎn)是吸引不動(dòng)點(diǎn)，那么在P處有一開集，其中一切點(diǎn)在F的迭代下趨于P。定理26設(shè)映射F在P點(diǎn)是排斥不動(dòng)點(diǎn)，那么存在一個(gè)包含P的開集，其中一切點(diǎn)在F的逆向迭代下趨于P。定義217如果映射YXF是一對(duì)一的，滿的，連續(xù)的，則稱之為同胚HOMEOMORPHISM。定義218稱兩個(gè)同胚YYGXXF，是拓?fù)涔曹椀模绻嬖谕遈XH，使得XHGXFH。拓?fù)涔曹椀膬蓚€(gè)系統(tǒng)，具有相同的不動(dòng)點(diǎn)和軌道結(jié)構(gòu)，因此可以通過(guò)研究某系統(tǒng)的拓?fù)涔曹椣到y(tǒng)來(lái)研究原來(lái)的系統(tǒng)。定理27（HARTMAN線性化定理）設(shè)動(dòng)力系統(tǒng)F以0為雙曲不動(dòng)點(diǎn)，由F在0點(diǎn)的JACOBIN矩陣定義的線性映射為DF，則存在0的開鄰域V，使得F和DF在V內(nèi)拓?fù)涔曹?。定?8（不穩(wěn)定流形定理）若N維動(dòng)力系統(tǒng)NNRRF存在一個(gè)鞍點(diǎn)P，在鞍點(diǎn)處其JACOBIN矩陣DF的特征值中有K個(gè)小于1。必存在0和一定義在鞍點(diǎn)附近的N1維光滑流形NKR,，流形可以由含參數(shù)T的參數(shù)方程來(lái)表示。使得10,0TRP20是DFP的一個(gè)不穩(wěn)定的特征向量3在1F作用下，不變4當(dāng)M時(shí)，PTRFM這個(gè)定理的含義指在鞍點(diǎn)附近存在一個(gè)不穩(wěn)定流形，流形上的點(diǎn)經(jīng)過(guò)變換后仍然處于此流形，上面的一切點(diǎn)在1F迭代下都趨向此不動(dòng)點(diǎn)。此定理對(duì)于穩(wěn)定和不穩(wěn)定流形具有全局性的對(duì)等概念。在鞍點(diǎn)處同樣也存在一個(gè)穩(wěn)定流形，其維數(shù)等于JACOBIN矩陣的特征值中大于1的個(gè)數(shù)，流形上的點(diǎn)經(jīng)過(guò)正變換后趨向于鞍點(diǎn)。第三章進(jìn)化算法的理論分析方法28在高維動(dòng)力系統(tǒng)中，穩(wěn)定流形和不穩(wěn)定流形將狀態(tài)空間劃分開來(lái)，確定各自的收斂目標(biāo)。高維動(dòng)力系統(tǒng)的全局形態(tài)是相當(dāng)復(fù)雜的，除了不動(dòng)點(diǎn)的三種分類外，還可能存在周期點(diǎn)（甚至是無(wú)限多個(gè)），極限環(huán)，以及混沌等。33GA建模的非MARKOV方法在這里簡(jiǎn)要地列出GA建模的一些非MARKOV方法，同時(shí)也列出了一些根據(jù)這些建模方法而改進(jìn)的方法。這些方法中的大多數(shù)考慮二進(jìn)制串的搜索空間，每一個(gè)串作為等位基因（ALLELES）的長(zhǎng)度為L(zhǎng)的向量。在第一節(jié)中回顧了和說(shuō)明了模式理論；第二節(jié)說(shuō)明了從物理學(xué)中借來(lái)的一種方法，估計(jì)群體適應(yīng)度分布的進(jìn)化；第三節(jié)研究等位基因的邊際分布的進(jìn)化。這種方法在最近5年中得到更多的注意，產(chǎn)生了很多改進(jìn)的算法。這些算法不能保證找到全局極值點(diǎn)，但可以比SGA收斂得更快。331模式進(jìn)化關(guān)于GA的最開始的探索是基于模式的進(jìn)化，集中在算法的宏觀視角。模式定理最初在71中證明，然后在54中得到擴(kuò)展。仍考慮以下基本GA二進(jìn)制空間E0,1L，使用比例選擇，單點(diǎn)交叉和1L變異。模式（SCHEME）H被定義為E中的一個(gè)子集，其中某些位的值可以不確定。模式中取確定值位置的數(shù)目稱為模式的階，記作HO。H為模式中第一個(gè)取確定值的位置和最后一個(gè)取確定值的位置之間的距離，稱為模式的定義長(zhǎng)度。定理31（模式定理）54,71設(shè)標(biāo)準(zhǔn)GA的變異概率為CP，交叉概率為MP，NH,N為群體在第N代時(shí)模式H所代表的元素的數(shù)目，則11,1,HOPLHPTFTHFNHNNHNEMC31第三章進(jìn)化算法的理論分析方法29模式定理的含義是在群體中，定義長(zhǎng)度較短的，低階的，且適應(yīng)值超過(guò)平均適應(yīng)度的模式H，在群體中的數(shù)目的期望值在下一代中增長(zhǎng)。在近似無(wú)限群體時(shí)，模式所代表的數(shù)目的期望可以用它的實(shí)際值所替換。一個(gè)明顯的結(jié)論是大于平均適應(yīng)度的模式試圖擴(kuò)展到整個(gè)群體。模式理論的有效性已經(jīng)遭到嚴(yán)重的質(zhì)疑6,26,34,66,93,105,126,134。首先，由于群體的平均適應(yīng)度每代都在變化，模式定理并沒(méi)有表達(dá)出這種變化的影響。因此它只在一代中有效，不能多次迭代，不能用來(lái)研究長(zhǎng)期特性。模式理論不能解決GA的動(dòng)力學(xué)行為和極限行為。其次，它隱含的假設(shè)問(wèn)題可以被分解為幾個(gè)片斷，對(duì)于一般性的適應(yīng)度函數(shù)，這種假設(shè)不能成立。目前，為克服這種限制，一些學(xué)者提出了“構(gòu)造塊假設(shè)”（BUILDINGBLOCKHYPOTHESIS）4,120,121,128，將模式通過(guò)交叉和變異而重建的影響考慮在內(nèi)，提供了模式和進(jìn)化之間新的聯(lián)系，試圖解釋GA的運(yùn)行機(jī)理。對(duì)于一些簡(jiǎn)單的適應(yīng)度函數(shù)，如BININ