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

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