演化算法完整版本

演化算法理論研究一、研究背景1、引言演化計(jì)算采用簡(jiǎn)單的編碼技術(shù)來(lái)表示各種復(fù)雜的結(jié)構(gòu),并通過(guò)對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)勝劣汰的自然選擇來(lái)指導(dǎo)學(xué)習(xí)和確定搜索的方向。由于它采用種群(即一組表示)的方式組織搜索,這使得它可以同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域。而且用種群組織搜索的方式使得演化算法持別適合大規(guī)模并行。在賦予演化計(jì)算自組織、自適應(yīng)、自學(xué)習(xí)等特征的同時(shí),優(yōu)勝劣汰的自然選擇和簡(jiǎn)單的遺傳操作使演化計(jì)算具有不受其搜索空間限制性條件(如可微、連續(xù)、單峰等)的約束及不需要其它輔助信息(如導(dǎo)數(shù))的特點(diǎn)。這些嶄新的特點(diǎn)使得演化算法不僅能獲得較高的效率而且具有簡(jiǎn)單、易于操作和通用的特性,而這些特性正是演化計(jì)算越來(lái)越受到人們青睞的主要原因之一。2、演化算法的分支演化計(jì)算最初具有三大分支:遺傳算法（GA）、演化規(guī)劃（EP）、演化策略（ES）。20世紀(jì)90年代初,在遺傳算法的基礎(chǔ)上又發(fā)展了一個(gè)分支:遺傳程序設(shè)計(jì)（GP）。雖然這幾個(gè)分支在算法實(shí)現(xiàn)方面具有一些細(xì)微的差別,但它們具有一個(gè)共同的特點(diǎn),即都是借助生物演化的思想和原理來(lái)解決實(shí)際問(wèn)題。2.1遺傳算法把計(jì)算機(jī)科學(xué)與進(jìn)化論結(jié)合起來(lái)的嘗試開(kāi)始于20世紀(jì)50年代末,但由于缺乏一種通用的編碼方案,使得人們只能依賴變異而不是交配來(lái)產(chǎn)生新的基因結(jié)構(gòu),故而收效甚微。到20世紀(jì)60年代中期,美國(guó)Michigan大學(xué)的JohnHolland在Fraser和Bremermann等人工作的基礎(chǔ)上提出了位串編碼技術(shù),這種編碼既適合于變異又適合交配操作,并且他強(qiáng)調(diào)將交配作為主要的遺傳操作。隨后,J.Holland將該算法用于自然和人工系統(tǒng)的自適應(yīng)行為的研究之中,并于1975年出版其開(kāi)創(chuàng)性的著作《AdaptationinNaturalandArtificialSystems》。后來(lái)JHolland與他的學(xué)生們將該算法加以推廣并應(yīng)用到優(yōu)化及機(jī)器學(xué)習(xí)等問(wèn)題之中,而且正式定名為遺傳算法。遺傳算法的通用編碼技術(shù)及簡(jiǎn)單有效的遺傳操作為其廣泛的應(yīng)用和成功奠定了基礎(chǔ)。2.2演化策略在20世紀(jì)60年代初,當(dāng)時(shí)在柏林工業(yè)大學(xué)的I.Rechenberg和H.P.Schwfel等在進(jìn)行風(fēng)洞實(shí)驗(yàn)時(shí),由于在設(shè)計(jì)中描述物體形狀的參數(shù)難以用傳統(tǒng)的方法進(jìn)行優(yōu)化,從而他們利用生物變異的思想來(lái)隨機(jī)地改變參數(shù)值并獲得了較好的結(jié)果。隨后,他們便對(duì)這種方法進(jìn)行了深入的研究和發(fā)展,形成了演化計(jì)算的另一個(gè)分支——演化策略。2.3演化規(guī)劃演化規(guī)劃的方法最初是由LJ.Fogel等在20世紀(jì)60年代提出的。他們?cè)谌斯ぶ悄艿难芯恐邪l(fā)現(xiàn),智能行為即是要具有能預(yù)測(cè)其所處環(huán)境的狀態(tài),并按照給定的目標(biāo)作出適當(dāng)響應(yīng)的能力。在研究中,他們將模擬環(huán)境描述成是由有限字符集中的符號(hào)組成的序列。于是問(wèn)題便轉(zhuǎn)化為:怎樣根據(jù)當(dāng)前觀察到的符號(hào)序列作出響應(yīng)以獲得最大的收益,這里收益的計(jì)算是按照環(huán)境中將要出現(xiàn)的下一個(gè)符號(hào)及預(yù)先定義好的效益目標(biāo)來(lái)確定的。演化規(guī)劃中常用有限態(tài)自動(dòng)機(jī)(簡(jiǎn)稱FSM)來(lái)表示這樣的策略。這樣,問(wèn)題便成為:如何設(shè)計(jì)出一個(gè)有效的FSM?LJ.Fogel等借用演化的思想對(duì)一群FSM進(jìn)行演化以獲得較好的FSM。他們將此方法應(yīng)用到數(shù)據(jù)診斷、模式識(shí)別和分類(lèi)以及控制系統(tǒng)的設(shè)計(jì)等問(wèn)題之中,并取得了較好的結(jié)果。后來(lái),D.B.Fogel借助于演化策略方法對(duì)演化規(guī)劃進(jìn)行了發(fā)展,并用到數(shù)值優(yōu)化及神經(jīng)網(wǎng)絡(luò)的訓(xùn)練等問(wèn)題之中。2.4遺傳程序設(shè)計(jì)自計(jì)算機(jī)出現(xiàn)以來(lái),計(jì)算機(jī)科學(xué)的一個(gè)重要目標(biāo)即是讓計(jì)算機(jī)自動(dòng)進(jìn)行程序設(shè)計(jì),即只要明確地告訴計(jì)算機(jī)要解決的問(wèn)題,而不需要告訴它如何去做,遺傳程序設(shè)計(jì)便是在該領(lǐng)域的一種嘗試。它采用遺傳算法的基本思想,但使用一種更為靈活的表示方式——分層結(jié)構(gòu)來(lái)表示解空間。這些分層結(jié)構(gòu)的葉結(jié)點(diǎn)是問(wèn)題的原始變量,個(gè)間結(jié)點(diǎn)則是組合這些原始變量的函數(shù)。它們很類(lèi)似于LISP語(yǔ)言中的S—表達(dá)式。這樣的每一個(gè)分層結(jié)構(gòu)對(duì)應(yīng)問(wèn)題的一個(gè)解,也可以理解為求解該問(wèn)題的一個(gè)計(jì)算機(jī)程序。遺傳程序設(shè)計(jì)即是使用一些遺傳操作動(dòng)態(tài)地改變這些結(jié)構(gòu)以獲得解決該問(wèn)題的可行的計(jì)算機(jī)程序。遺傳程序設(shè)計(jì)的思想是stanford大學(xué)的J.R.Koza在20世紀(jì)90年代初提出的。3、演化算法的特點(diǎn)3.1智能性演化計(jì)算的智能性包括自組織、自適應(yīng)和自學(xué)習(xí)性等。采用演化計(jì)算求解問(wèn)題時(shí),在確定了編碼方案、適應(yīng)值函數(shù)及遺傳算子以后,算法將利用演化過(guò)程中獲得的信息自行組織搜索。由于基于自然的選擇策略為:適者生存、不適應(yīng)者淘汰,故而適應(yīng)值大的個(gè)體具有較高生存概率。通常適應(yīng)值大的個(gè)體具有與環(huán)境更適應(yīng)的基因結(jié)構(gòu),再通過(guò)雜交和基因突變等遺傳操作就可能產(chǎn)生與環(huán)境更適應(yīng)的后代。演化算法的這種自組織、自適應(yīng)特征同時(shí)也賦予了它具有能根據(jù)環(huán)境的變化自動(dòng)發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力。自然選擇消除了算法設(shè)計(jì)過(guò)程中的一個(gè)最大障礙:即需要事先描述問(wèn)題的全部特點(diǎn),并說(shuō)明針對(duì)問(wèn)題的不同特點(diǎn)算法應(yīng)采取的措施。于是,利用演化計(jì)算的方法我們可以解決那些結(jié)構(gòu)尚無(wú)人能理解的復(fù)雜問(wèn)題。3.2本質(zhì)并行性演化計(jì)算的本質(zhì)并行性表現(xiàn)在兩個(gè)方面:一是演化計(jì)算是內(nèi)在并行的,即演化算法本身非常適合大規(guī)模并行。最簡(jiǎn)單的并行方式是讓幾百甚至數(shù)千臺(tái)計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算,運(yùn)行過(guò)程中甚至不進(jìn)行任何通信(獨(dú)立的種群之間若有少量的通信一般會(huì)帶來(lái)更好的結(jié)果),等到運(yùn)算結(jié)束時(shí)才通信比較,選取最佳個(gè)體,這種并行處理方式對(duì)并行系統(tǒng)結(jié)構(gòu)也沒(méi)有什么限制和要求。可以說(shuō),演化計(jì)算適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行處理,而且對(duì)其并行效率沒(méi)有太大的影響。二是演化計(jì)算的內(nèi)合并行性。由于演化計(jì)算采用種群的方式組織搜索,從而它可以同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域,并相互交流信息,這種搜索方式使得它雖然每次只執(zhí)行與種群規(guī)模成比例的計(jì)算,而實(shí)質(zhì)上已進(jìn)行了大約O(N3)次有效搜索。這使得演化計(jì)算能以較少的計(jì)算獲得較大的收益。4、展望隨著演化計(jì)算研究熱潮的興起,人工智能再次成為人們關(guān)注的一個(gè)焦點(diǎn)。有些學(xué)者甚至提出演化計(jì)算是人工智能的未來(lái)。目前,演化計(jì)算與神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)一起已形成一個(gè)新的研究方向——計(jì)算智能。人工智能已從傳統(tǒng)的基于符號(hào)處理的符號(hào)主義向以神經(jīng)網(wǎng)絡(luò)為代表的連接主義和以演化計(jì)算為代表的演化主義方向發(fā)展。由于演化計(jì)算在機(jī)器學(xué)習(xí)、過(guò)程控制、經(jīng)濟(jì)預(yù)測(cè)、工程優(yōu)化等領(lǐng)域取得的成功,已引起了包括數(shù)學(xué)、物理學(xué)、化學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)、社會(huì)科學(xué)、經(jīng)濟(jì)學(xué)及工程應(yīng)用等領(lǐng)域科學(xué)家們的極大興趣。自80年代中期以來(lái),世界上許多國(guó)家都掀起了演化計(jì)算的研究熱潮。目前,有數(shù)種以演化計(jì)算為主題的國(guó)際會(huì)議在世界各地定期召開(kāi)。國(guó)際互聯(lián)網(wǎng)上也有多種相關(guān)的mailing1ist,USENET上還有專門(mén)的新聞組。而由于演化計(jì)算應(yīng)用范圍之廣泛,從一些雜志及國(guó)際會(huì)議論文集中都比較容易看到有關(guān)演化計(jì)算應(yīng)用方面的文章?，F(xiàn)在已出版兩種專門(mén)關(guān)于演化計(jì)算的新雜志:“EvolutionaryComputation”(由MITPress出版,1993年創(chuàng)刊)和“IEEETransactionsonEvo1utionaryComputation”(IEEE匯刊,1997年創(chuàng)刊),而且一些國(guó)際性期刊也競(jìng)相出版以演化計(jì)算為主題的?？?。甚至新的一輪日本計(jì)算機(jī)發(fā)展規(guī)劃—RWC計(jì)劃(RealWorldComputingProgram)也把演化計(jì)算作為它的主要支撐技術(shù)之一,以進(jìn)行信息的集成、學(xué)習(xí)及組織等。另外,某些學(xué)者研究了演化計(jì)算的自現(xiàn)行為后聲稱,演化計(jì)算將與混沌理論和分形幾何一道成為人們研究非線性現(xiàn)象和復(fù)雜系統(tǒng)的新的三大方法,并將與神經(jīng)網(wǎng)絡(luò)一道成為人們研究認(rèn)知過(guò)程的重要工具。當(dāng)前,演化計(jì)算的研究?jī)?nèi)容十分廣泛,如演化算法的設(shè)計(jì)與分析、演化計(jì)算的理論基礎(chǔ)及其在各個(gè)領(lǐng)域中的應(yīng)用等等?？梢灶A(yù)料,隨著演化計(jì)算理論研究的不斷深入和應(yīng)用領(lǐng)域的不斷拓廣,演化計(jì)算必將取得更大的成功。二、演化算法2.1演化算法的基本結(jié)構(gòu)不同的編碼方案、選擇策略和遺傳算子相結(jié)合,可構(gòu)成不同的演化算法,但其基本結(jié)構(gòu)可描述如下:PROCEDURE{隨機(jī)初始化種群P(0)={X1,X2,…,Xn},t:=0;計(jì)算P(0)中個(gè)體的適應(yīng)值;While(不滿足終止準(zhǔn)則)do{由P(t)通過(guò)遺傳操作形成新的種群P(t+1);計(jì)算P(t+1)中個(gè)體的適應(yīng)值,t=t+1;}輸出結(jié)果;}可以看出,上述基本結(jié)構(gòu)是一個(gè)比較粗略的框架。在具體實(shí)現(xiàn)時(shí),可使用較為詳細(xì)的結(jié)構(gòu)。如按種群的組織方式,可分為非重疊和重疊種群的演化算法,以及單種群和多種群的演化算法;按遺傳算子的執(zhí)行方式,可分為非重疊和重疊遺傳操作的演化算法等。下面給個(gè)列舉：（1）種群非重疊：從P(t)中選擇個(gè)體進(jìn)行遺傳操作，用后代替換掉整個(gè)群體產(chǎn)生新種群P(t+1)。（2）種群重疊：從P(t)中選擇N1個(gè)個(gè)體進(jìn)行遺傳操作，用產(chǎn)生的N1個(gè)后代替換掉P(t)中N1個(gè)較差的個(gè)體，生成新種群P(t+1)。（3）遺傳操作非重疊：for(k=0;k<N,k=k+2){在P(t)中選擇兩個(gè)父體;r=random[0,1];if(r≤pr)執(zhí)行繁殖操作，即將兩個(gè)父體直接插入到P(t+1);elseif(r≤pr+pc)執(zhí)行雜交操作，將兩個(gè)后代插入到P(t+1);else對(duì)兩個(gè)父體分別執(zhí)行變異操作，將兩個(gè)后代插入到P(t+1);}（4）遺傳操作重疊：for(k=0;k<N,k=k+2){在P(t)中選擇兩個(gè)父體;r=random[0,1];if(r≤pr)執(zhí)行繁殖操作，并變異后插入到P(t+1);else執(zhí)行雜交操作，并變異后插入到P(t+1);}2.2設(shè)計(jì)演化算法的基本步驟在設(shè)計(jì)演化算法時(shí)，通常按以下步驟進(jìn)行：(1)確定編碼方案：用演化算法求解問(wèn)題時(shí)所做的演化操作不是直接作用于問(wèn)題的解空間上，而是首先將解對(duì)應(yīng)于某種編碼表示，操作是在編碼空間上進(jìn)行的。選擇何種編碼表示有時(shí)對(duì)算法的性能、效率等產(chǎn)生很大的影響；(2)確定適應(yīng)度函數(shù)：適應(yīng)值是對(duì)解的質(zhì)量的一種度量，它通常依賴于解的行為與環(huán)境（即種群）的關(guān)系。一般以目標(biāo)函數(shù)或費(fèi)用函數(shù)的形式來(lái)表示。解的適應(yīng)值是演化過(guò)程中進(jìn)行選擇的唯一依據(jù)；(3)選擇策略的確定：優(yōu)勝劣汰的選擇機(jī)制使得適應(yīng)值大的個(gè)體有較高的存活概率，這是演化算法與一般搜索算法的主要區(qū)別之一。不同的選擇策略對(duì)算法的性能也有較大的影響；(4)控制參數(shù)的選取：控制參數(shù)主要包括種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行不同遺傳操作的概率以及其它一些輔助性的控制參數(shù)；(5)遺傳算子的設(shè)計(jì)：演化算法中的遺傳算子，主要包括繁殖、雜交、變異以及其它高級(jí)操作；(6)確定算法的終止準(zhǔn)則：由于演化計(jì)算沒(méi)有利用目標(biāo)函數(shù)的梯度等信息，所以在演化過(guò)程中，無(wú)法確定個(gè)體在解空間的位置，從而無(wú)法用傳統(tǒng)的方法來(lái)判定算法的收斂與否以終止算法。常用的辦法是預(yù)先規(guī)定一個(gè)最大的演化代數(shù)或算法在連續(xù)多少代以后解的適應(yīng)值沒(méi)有什么明顯的改進(jìn)時(shí)即終止；(7)編程上機(jī)運(yùn)行：完成上述工作后,即可按演化計(jì)算的算法結(jié)構(gòu)編程,進(jìn)行問(wèn)題求解。由于演化算法的隨機(jī)性及不確定性等特點(diǎn),通常要多運(yùn)行幾次才能得到可靠的解。應(yīng)該注意的是,上述基本步驟密切相關(guān),編碼方案與遺傳算子的設(shè)計(jì)等是同步考慮的,有時(shí)甚至需要上機(jī)運(yùn)行與算法設(shè)計(jì)交替進(jìn)行。2.3演化算法的編碼表示設(shè)計(jì)演化算法的一個(gè)重要步驟是,對(duì)所解問(wèn)題的變量進(jìn)行編碼表示,編碼表示方案的選取在很大程度上依賴于問(wèn)題的性質(zhì)及遺傳算子的設(shè)計(jì)。通常,在設(shè)計(jì)演化算法時(shí),只有兩個(gè)方面與所求問(wèn)題有關(guān),即問(wèn)題的編碼表示與適應(yīng)函數(shù)的確定。根據(jù)編碼方式的不同,演化算法的編碼策略大致可分為二進(jìn)制編碼、實(shí)數(shù)編碼、有序串編碼與結(jié)構(gòu)性編碼等。二進(jìn)制編碼就是將原問(wèn)題的解空間映射到位串空間Bl={0,1}l上,然后在位串空間上進(jìn)行遺傳操作,結(jié)果再通過(guò)解碼過(guò)程還原成其表現(xiàn)型,以進(jìn)行適應(yīng)值的評(píng)估。當(dāng)變量不止一個(gè)分量時(shí),我們可以對(duì)各分量分別進(jìn)行編碼,然后合并成一個(gè)長(zhǎng)串。解碼時(shí),根據(jù)其對(duì)應(yīng)的子串分別進(jìn)行解碼即可。采用二進(jìn)制編碼時(shí),一般要先給出求解精度以確定串長(zhǎng)。而一旦精度確定后,就很難在算法執(zhí)行過(guò)程中進(jìn)行調(diào)整,因而算法缺乏微調(diào)(fine-tuning)的功能。在求解高維優(yōu)化問(wèn)題或要求精度很高時(shí),二進(jìn)制串很長(zhǎng),因而算法的搜索效率很低。基于上述原因,有人提出了Gray編碼、動(dòng)態(tài)編碼等策略。Gray編碼是將二進(jìn)制編碼通過(guò)Gray變換后得到的編碼,目的是為了減少翻轉(zhuǎn)次數(shù),克服二進(jìn)制編碼的Hamming懸崖(Hammingcliffs)的缺點(diǎn)。動(dòng)態(tài)編碼是當(dāng)算法收斂到某局部最優(yōu)時(shí),增加搜索的精度。辦法是,在保持二進(jìn)制串長(zhǎng)不變的前提下減小搜索區(qū)域。為了克服二進(jìn)制編碼的缺點(diǎn),對(duì)于問(wèn)題的變量是實(shí)向量的情況,也可直接采用實(shí)進(jìn)制進(jìn)行編碼。這樣,可直接在解的表現(xiàn)型上進(jìn)行遺傳操作,從而便于引入與問(wèn)題領(lǐng)域相關(guān)的啟發(fā)式信息,以增加演化算法的搜索能力。從演化計(jì)算的各分支看,在求解數(shù)值優(yōu)化問(wèn)題時(shí),演化策略及演化規(guī)劃都采用實(shí)數(shù)編碼,而且在早期不使用雜交算子(演化策略中現(xiàn)在使用的重組算子非常類(lèi)似雜交算子)。遺傳算法則較多地采用二進(jìn)制編碼。近幾年,遺傳算法在求解高維或復(fù)雜優(yōu)化問(wèn)題時(shí)也大多使用實(shí)數(shù)編碼。由于實(shí)數(shù)編碼表示比較自然,而且較易引入相關(guān)的領(lǐng)域知識(shí),因此,我們認(rèn)為其使用將越來(lái)越廣泛。對(duì)很多組合優(yōu)化問(wèn)題,目標(biāo)函數(shù)的值不僅與表示解的字符串中各字符的值有關(guān),而且與其所在字符串的位置有關(guān),這樣的問(wèn)題稱為有序問(wèn)題。若目標(biāo)函數(shù)的值只與表示解的字符串中各字符的位置有關(guān),與其具體的字符值無(wú)關(guān),則稱為純有序問(wèn)題。對(duì)這類(lèi)問(wèn)題,較自然的編碼表示就是有序串編碼。用演化算法求解有序問(wèn)題時(shí),傳統(tǒng)的遺傳操作可能產(chǎn)生非法的后代。因此,對(duì)這類(lèi)問(wèn)題要針對(duì)具體問(wèn)題專門(mén)設(shè)計(jì)有效且能保證后代合法的遺傳算子。這類(lèi)編碼方案較多地用在組合優(yōu)化問(wèn)題中。對(duì)很多問(wèn)題,更自然的表示是樹(shù)或圖的形式。這時(shí),采用其它形式的編碼可能很困難。這種將問(wèn)題的解表示成樹(shù)或圖的形式的編碼稱為結(jié)構(gòu)式編碼。對(duì)這種非線性編碼方式,我們應(yīng)非常謹(jǐn)慎地設(shè)計(jì)遺傳算子,以便不產(chǎn)生或少產(chǎn)生非法的后代。對(duì)結(jié)構(gòu)式編碼要討論通用的遺傳算子很困難,一般是就具體問(wèn)題具體分析。因?yàn)檫z傳算子直接在解的表現(xiàn)型上進(jìn)行操作,所以比較容易加入與領(lǐng)域有關(guān)的知識(shí)和一些啟發(fā)式信息。2.4適應(yīng)函數(shù)的確定在自然界中,個(gè)體的適應(yīng)值就是其繁殖能力,這將直接關(guān)系到其后代的數(shù)量。在演化計(jì)算中,適應(yīng)函數(shù)是區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn),是算法演化過(guò)程的驅(qū)動(dòng)力,是進(jìn)行自然選擇的唯一依據(jù)。改變種群內(nèi)部結(jié)構(gòu)的操作都通過(guò)適應(yīng)值進(jìn)行控制。在演化計(jì)算中,度量適應(yīng)性的方法有很多種,既可以用目標(biāo)函數(shù)的形式給出,也可以用目標(biāo)函數(shù)變換的方式來(lái)定義。在協(xié)同演化(coevolution)時(shí),適應(yīng)值通常由某一對(duì)策與群體中相佐的對(duì)策進(jìn)行抗衡的獲利來(lái)確定。個(gè)體在種群中的存活量和繁殖量也可以作為適應(yīng)值的一種度量,這種度量方式常在人工生命的研究中使用。目前,我們?cè)谠O(shè)計(jì)演化算法時(shí),群體規(guī)模一般在幾十到幾百之間,與實(shí)際物種的規(guī)模相差甚遠(yuǎn)。因此,個(gè)體繁殖數(shù)量的調(diào)節(jié)在演化計(jì)算中比較重要。如果群體中出現(xiàn)了超級(jí)個(gè)體,即該個(gè)體的適應(yīng)值大大超過(guò)群體的平均適應(yīng)值,則按適應(yīng)值比例進(jìn)行選擇時(shí),該個(gè)體很快會(huì)在群體中占有絕對(duì)的比例,從而導(dǎo)致算法較早地收斂到一個(gè)局部最優(yōu)點(diǎn),這種現(xiàn)象稱為過(guò)早收斂。又如在搜索過(guò)程的后期,雖然群體中存在足夠的多樣性,但群體的平均適應(yīng)值可能會(huì)接近群體的最優(yōu)適應(yīng)值。在這種情況下,群體中實(shí)際上已不存在競(jìng)爭(zhēng),因而搜索目標(biāo)難以得到改善,這種現(xiàn)象稱為停滯現(xiàn)象?；谏鲜鲈?改變算法性能的方法之一,就是對(duì)適應(yīng)值進(jìn)行調(diào)節(jié),即通過(guò)變換來(lái)改變?cè)m應(yīng)值間的比例關(guān)系。常用的比例變換有線性變換及指數(shù)函數(shù)變換等。2.5選擇策略選擇策略對(duì)算法性能有舉足輕重的影響作用。不同的選擇策略將導(dǎo)致不同的選擇壓力,即下一代中父代個(gè)體的復(fù)制數(shù)目的分配關(guān)系不同。較大的選擇壓力使最優(yōu)個(gè)體具有較高的復(fù)制數(shù)目,從而使算法收斂速度較快,但也容易出現(xiàn)過(guò)早收斂現(xiàn)象。相對(duì)地,較小的選擇壓力一般能使群體保持足夠的多樣性,從而增大了算法收斂到全局最優(yōu)的概率,但算法的收斂速度一般較慢。按選擇機(jī)制的不同,常用的選擇策略可分為基于適應(yīng)值比例的選擇、基于排名的選擇和基于局部競(jìng)爭(zhēng)機(jī)制的選擇。基于適應(yīng)值比例的選擇包括繁殖池選擇、輪盤(pán)式選擇、Boltzmann選擇等?；谂琶倪x擇主要包括基于線性排名和基于非線性排名的選擇?；诰植扛?jìng)爭(zhēng)機(jī)制的選擇主要包括錦標(biāo)賽選擇、(μ,λ)和(μ+λ)選擇、Boltzmann錦標(biāo)賽選擇等。2.6遺傳算子的設(shè)計(jì)遺傳算子的設(shè)計(jì)是演化計(jì)算中最富有特色和創(chuàng)造性的部分。基本的演化算法只使用再生、雜交和變異三種操作。編碼策略的不同造成了遺傳操作的多樣性。對(duì)二進(jìn)制編碼,雜交算子有點(diǎn)式雜交和均勻雜交方式,且點(diǎn)式雜交算子又分為單點(diǎn)式雜交和多點(diǎn)式雜交。其它編碼方式的雜交算子和變異算子更是豐富多彩。自然界的遺傳操作按操作對(duì)象的不同可分為基因級(jí)、個(gè)體級(jí)和群體級(jí)三個(gè)層次?；镜难莼惴ㄋ褂玫娜N操作屬于個(gè)體級(jí)層次的遺傳操作。為此,有的研究者便將其它層次的一些遺傳操作(稱為高級(jí)操作)引入到演化算法中。雖然高級(jí)操作的引入對(duì)演化算法的穩(wěn)健性有一定改善,但它們?cè)黾恿祟~外的計(jì)算開(kāi)銷(xiāo)且適應(yīng)的編碼種類(lèi)較少,而且不少人對(duì)采用這些操作能否增強(qiáng)演化算法的計(jì)算性能和求解效率持懷疑態(tài)度。在演化計(jì)算中使用的基因級(jí)的高級(jí)操作包括:倒位(inversion)、顯性基因(dominance)、二倍體(diploidy)、重復(fù)(duplication)、缺失(deletion)、易位(