外文翻譯--一種新的改進(jìn)遺傳算法及其性能分析.doc

一種新的改進(jìn)遺傳算法及其性能分析摘要：雖然遺傳算法以其全局搜索、并行計(jì)算、更好的健壯性以及在進(jìn)化過(guò)程中不需要求導(dǎo)而著稱，但是它仍然有一定的缺陷，比如收斂速度慢。本文根據(jù)幾個(gè)基本定理，提出了一種使用變異染色體長(zhǎng)度和交叉變異概率的改進(jìn)遺傳算法，它的主要思想是：在進(jìn)化的開(kāi)始階段，我們使用短一些的變異染色體長(zhǎng)度和高一些的交叉變異概率來(lái)解決，在全局最優(yōu)解附近，使用長(zhǎng)一些的變異染色體長(zhǎng)度和低一些的交叉變異概率。最后，一些關(guān)鍵功能的測(cè)試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。關(guān)鍵字：編譯染色體長(zhǎng)度；變異概率；遺傳算法；在線離線性能遺傳算法是一種以自然界進(jìn)化中的選擇和繁殖機(jī)制為基礎(chǔ)的自適應(yīng)的搜索技術(shù)，它是由Holland1975年首先提出的。它以其全局搜索、并行計(jì)算、更好的健壯性以及在進(jìn)化過(guò)程中不需要求導(dǎo)而著稱。然而它也有一些缺點(diǎn)，如本地搜索不佳，過(guò)早收斂，以及收斂速度慢。近些年，這個(gè)問(wèn)題被廣泛地進(jìn)行了研究。本文提出了一種使用變異染色體長(zhǎng)度和交叉變異概率的改進(jìn)遺傳算法。一些關(guān)鍵功能的測(cè)試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。在第一部分，提出了我們的新算法。第二部分，通過(guò)幾個(gè)優(yōu)化例子，將該算法和只保留最佳個(gè)體的遺傳算法進(jìn)行了效率的比較。第三部分，就是所得出的結(jié)論。最后，相關(guān)定理的證明過(guò)程可見(jiàn)附錄。1.算法的描述1.1一些定理在提出我們的算法之前，先給出一個(gè)一般性的定理（見(jiàn)附件），如下：我們假設(shè)有一個(gè)變量（多變量可以拆分成多個(gè)部分，每一部分是一個(gè)變量）xa,b,xR，二進(jìn)制的染色體編碼是1.定理1染色體的最小分辨率是s=定理2染色體的第i位的權(quán)重值是wi=(i=1,2,l)定理3單點(diǎn)交叉的染色體搜索步驟的數(shù)學(xué)期望Ec(x)是Ec(x)=Pc其中Pc是交叉概率定理4位變異的染色體搜索步驟的數(shù)學(xué)期望Em(x)是Em(x)=(b-a)Pm其中Pm是變異概率1.2算法機(jī)制在進(jìn)化過(guò)程中，我們假設(shè)變量的值域是固定的，交叉的概率是一個(gè)常數(shù)，所以從定理1和定理3我們知道，較長(zhǎng)的染色體長(zhǎng)度有著較少的染色體搜索步驟和較高的分辨率；反之亦然。同時(shí)，交叉概率與搜索步驟成正比。由定理4，改變?nèi)旧w的長(zhǎng)度不影響變異的搜索步驟，而變異概率與搜索步驟也是成正比的。進(jìn)化的開(kāi)始階段，較短染色體（可以是過(guò)短，否則它不利于種群多樣性）和較高的交叉和變異概率會(huì)增加搜索步驟，這樣可進(jìn)行更大的域名搜索，避免陷入局部最優(yōu)。而全局最優(yōu)的附近，較長(zhǎng)染色體和較低的交叉和變異概率會(huì)減少搜索的步驟，較長(zhǎng)的染色體也提高了變異分辨率，避免在全局最優(yōu)解附近徘徊，提高了算法收斂速度。最后，應(yīng)當(dāng)指出，染色體長(zhǎng)度的改變不會(huì)使個(gè)體適應(yīng)性改變，因此它不影響選擇（輪盤賭選擇）。1.3算法描述由于基本遺傳算法沒(méi)有在全局優(yōu)化時(shí)收斂，而遺傳算法保留了當(dāng)前一代的最佳個(gè)體，我們的方法采用這項(xiàng)策略。在進(jìn)化過(guò)程中，我們跟蹤到當(dāng)代個(gè)體平均適應(yīng)度的累計(jì)值。它被寫成：X(t)=(t)其中G是當(dāng)前進(jìn)化的一代，favg是個(gè)體的平均適應(yīng)度。當(dāng)累計(jì)平均適用性增加到最初個(gè)體平均適應(yīng)度的k(k1,kR)倍，我們將染色體長(zhǎng)度變?yōu)槠渥陨淼膍(m是一個(gè)正整數(shù))倍，然后減小交叉和變異的概率，可以提高個(gè)體分辨率、減少搜索步驟以及提高算法收斂速度。算法的執(zhí)行步驟如下：第一步：初始化群體，并計(jì)算個(gè)體平均適應(yīng)度f(wàn)avg0，然后設(shè)置改變參數(shù)的標(biāo)志flag。flag設(shè)為1.第二步：在所保留的當(dāng)代的最佳個(gè)體，進(jìn)行選擇、再生、交叉和變異，并計(jì)算當(dāng)代個(gè)體的累積平均適應(yīng)度f(wàn)avg第三步：如果且flag=1，把染色體的長(zhǎng)度增加至自身的m倍，減少交叉和變異概率，并設(shè)置flag等于0；否則繼續(xù)進(jìn)化。第四步：如果滿足結(jié)束條件，停止；否則轉(zhuǎn)自第二步。2.測(cè)試和分析我們采用以下兩種方法來(lái)測(cè)試我們的方法，和只保留最佳個(gè)體的遺傳算法進(jìn)行比較：2.1收斂的分析在功能測(cè)試中，我們進(jìn)行了以下政策：輪盤賭選擇，單點(diǎn)交叉，位變異。種群的規(guī)模是60。L是染色體長(zhǎng)度，Pc和Pm分別是交叉概率和變異概率。我們隨機(jī)選擇4個(gè)遺傳算法所保留的最佳個(gè)體來(lái)與我們的方法進(jìn)行比較，它們具有不同的固定染色體長(zhǎng)度和交叉和變異的概率。表1給出了在100次測(cè)試的平均收斂代。在我們的方法中，我們采取的初始參數(shù)是l0=10，Pc0=0.3，Pm0=0.1和k=1.2，當(dāng)滿足改變參數(shù)的條件時(shí)，我們調(diào)整參數(shù)l=30，Pc=0.1，Pm=0.01。從表1中得知，我們的方法顯著提高了遺傳算法的收斂速度，正符合上述分析。表1功能測(cè)試結(jié)果方法我們的算法l=10Pc=0.1,Pm=0.1l=10Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1f1257152363579116264363f2198269734237445054332.2在線和離線性能的分析Dejong提出了遺傳算法的定量評(píng)價(jià)方法，包括在線和離線性能評(píng)價(jià)。前者測(cè)試動(dòng)態(tài)性能，而后者評(píng)估收斂性能。為了更好地分析測(cè)試功能的在線和離線性能，我們把個(gè)體的適應(yīng)性乘以10，并f1和f2分別給出了4000和1000代的曲線：(a)在線(b)離線圖1f1的在線與離線性能(a)在線(b)離線圖2f2的在線與離線性能從圖1和圖2可以看出，我們方法的在線性能只比第四種情況差一點(diǎn)點(diǎn)，但比第二種、第三種、第五種好很多，這幾種情況下的在線性能幾乎完全相同。同時(shí)，我們方法的離線性能也比其他四種好很多。3.結(jié)論本文提出了一種使用變異染色體長(zhǎng)度和交叉變異概率的改進(jìn)遺傳算法。一些關(guān)鍵功能的測(cè)試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。附件有了第一部分中假定的條件，定理1和定理2的驗(yàn)證是顯而易見(jiàn)的。下面給出定理3和定理4的證明過(guò)程：定理3單點(diǎn)交叉的染色體搜索步驟的數(shù)學(xué)期望Ec(x)是Ec(x)=Pc其中Pc是交叉概率證明：如圖A1所示，我們假設(shè)交叉發(fā)生在第k個(gè)基因位點(diǎn)，從k到l的父基因位點(diǎn)沒(méi)有變化，基因位點(diǎn)1到k