畢業(yè)論文遺傳算法外文翻譯

1、武漢科技大學(xué)本科畢業(yè)論文外文翻譯本科畢業(yè)論文外文翻譯外文譯文題目（中文） ：一種新的改進(jìn)遺傳算法及其性能分析學(xué) 院:計(jì)算機(jī)科學(xué)與技術(shù)專 業(yè):軟件工程學(xué) 號(hào):200813138032學(xué)生姓名:王 月指導(dǎo)教師:張 葵日 期:二一二年六月Improved Genetic Algorithm and Its Performance AnalysisLUO Pi, LI Qiang, GUO Ji chang, TENG Jian fuTransactions of Tianjin University, 2003, 9(2): 140143一種新的改進(jìn)遺傳算法及其性能分析羅批，李鏘，郭繼昌，騰建輔天津

2、大學(xué)學(xué)報(bào)，2003，9（2）：140143摘要：雖然遺傳算法以其全局搜索、并行計(jì)算、更好的健壯性以及在進(jìn)化過程中不需要求導(dǎo)而著稱，但是它仍然有一定的缺陷，比如收斂速度慢。本文根據(jù)幾個(gè)基本定理，提出了一種使用變異染色體長度和交叉變異概率的改進(jìn)遺傳算法，它的主要思想是：在進(jìn)化的開始階段，我們使用短一些的變異染色體長度和高一些的交叉變異概率來解決，在全局最優(yōu)解附近，使用長一些的變異染色體長度和低一些的交叉變異概率。最后，一些關(guān)鍵功能的測試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。關(guān)鍵字：編譯染色體長度；變異概率；遺傳算法；在線離線性能文章編號(hào)：100

3、6 4982(2003) 02 0140 04遺傳算法是一種以自然界進(jìn)化中的選擇和繁殖機(jī)制為基礎(chǔ)的自適應(yīng)的搜索技術(shù)，它是由Holland 1975年首先提出的。它以其全局搜索、并行計(jì)算、更好的健壯性以及在進(jìn)化過程中不需要求導(dǎo)而著稱。然而它也有一些缺點(diǎn)，如本地搜索不佳，過早收斂，以及收斂速度慢。近些年，這個(gè)問題被廣泛地進(jìn)行了研究。本文提出了一種使用變異染色體長度和交叉變異概率的改進(jìn)遺傳算法。一些關(guān)鍵功能的測試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。在第一部分，提出了我們的新算法。第二部分，通過幾個(gè)優(yōu)化例子，將該算法和只保留最佳個(gè)體的遺傳算法進(jìn)行

4、了效率的比較。第三部分，就是所得出的結(jié)論。最后，相關(guān)定理的證明過程可見附錄。1 算法的描述1.1 一些定理在提出我們的算法之前，先給出一個(gè)一般性的定理（見附件），如下：我們假設(shè)有一個(gè)變量（多變量可以拆分成多個(gè)部分，每一部分是一個(gè)變量）x a, b , x R，二進(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是變異概率。

5、1.2 算法機(jī)制在進(jìn)化過程中，我們假設(shè)變量的值域是固定的，交叉的概率是一個(gè)常數(shù)，所以從定理1和定理3我們知道，較長的染色體長度有著較少的染色體搜索步驟和較高的分辨率；反之亦然。同時(shí)，交叉概率與搜索步驟成正比。由定理4，改變?nèi)旧w的長度不影響變異的搜索步驟，而變異概率與搜索步驟也是成正比的。進(jìn)化的開始階段，較短染色體（可以是過短，否則它不利于種群多樣性）和較高的交叉和變異概率會(huì)增加搜索步驟，這樣可進(jìn)行更大的域名搜索，避免陷入局部最優(yōu)。而全局最優(yōu)的附近，較長染色體和較低的交叉和變異概率會(huì)減少搜索的步驟，較長的染色體也提高了變異分辨率，避免在全局最優(yōu)解附近徘徊，提高了算法收斂速度。最后，應(yīng)當(dāng)指出，染

6、色體長度的改變不會(huì)使個(gè)體適應(yīng)性改變，因此它不影響選擇（輪盤賭選擇）。1.3 算法描述由于基本遺傳算法沒有在全局優(yōu)化時(shí)收斂，而遺傳算法保留了當(dāng)前一代的最佳個(gè)體，我們的方法采用這項(xiàng)策略。在進(jìn)化過程中，我們跟蹤到當(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 ( k> 1, k R) 倍，我們將染色體長度變?yōu)槠渥陨淼膍 (m 是一個(gè)正整數(shù)) 倍，然后減小交叉和變異的概率，可以提高個(gè)體分辨率、減少搜索步驟以及提高算法收斂速度。算法的執(zhí)行步驟如下：第一步：初始化群體，并計(jì)算個(gè)體平均適應(yīng)度fa

7、vg0，然后設(shè)置改變參數(shù)的標(biāo)志flag。flag設(shè)為1.第二步：在所保留的當(dāng)代的最佳個(gè)體，進(jìn)行選擇、再生、交叉和變異，并計(jì)算當(dāng)代個(gè)體的累積平均適應(yīng)度favg第三步：如果 且flag = 1，把染色體的長度增加至自身的m倍，減少交叉和變異概率，并設(shè)置flag等于0;否則繼續(xù)進(jìn)化。第四步：如果滿足結(jié)束條件，停止；否則轉(zhuǎn)自第二步。2 測試和分析我們采用以下兩種方法來測試我們的方法，和只保留最佳個(gè)體的遺傳算法進(jìn)行比較： 2.1 收斂的分析在功能測試中，我們進(jìn)行了以下政策：輪盤賭選擇，單點(diǎn)交叉，位變異。種群的規(guī)模是60。L是染色體長度，Pc和Pm分別是交叉概率和變異概率。我們隨機(jī)選擇4個(gè)遺傳算法所保留的

8、最佳個(gè)體來與我們的方法進(jìn)行比較，它們具有不同的固定染色體長度和交叉和變異的概率。表1給出了在100次測試的平均收斂代。 在我們的方法中，我們采取的初始參數(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 功能測試結(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.1f1257152363579116264363

9、f2198269734237445054332.2 在線和離線性能的分析 Dejong提出了遺傳算法的定量評(píng)價(jià)方法，包括在線和離線性能評(píng)價(jià)。前者測試動(dòng)態(tài)性能，而后者評(píng)估收斂性能。為了更好地分析測試功能的在線和離線性能，我們把個(gè)體的適應(yīng)性乘以10，并f1和f2分別給出了4 000和1 000代的曲線：(a) 在線 (b) 離線圖1 f1的在線與離線性能(a) 在線 (b) 離線圖2 f2的在線與離線性能 從圖1和圖2可以看出，我們方法的在線性能只比第四種情況差一點(diǎn)點(diǎn)，但比第二種、第三種、第五種好很多，這幾種情況下的在線性能幾乎完全相同。同時(shí)，我們方法的離線性能也比其他四種好很多。3 結(jié)論本文提出

10、了一種使用變異染色體長度和交叉變異概率的改進(jìn)遺傳算法。一些關(guān)鍵功能的測試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。附件有了第一部分中假定的條件，定理1和定理2的驗(yàn)證是顯而易見的。下面給出定理3和定理4的證明過程：定理3 單點(diǎn)交叉的染色體搜索步驟的數(shù)學(xué)期望Ec(x)是Ec (x) = Pc其中Pc是交叉概率。證明：如圖A1所示，我們假設(shè)交叉發(fā)生在第k個(gè)基因位點(diǎn)，從k到l的父基因位點(diǎn)沒有變化，基因位點(diǎn)1到k上的基因改變了。在交叉過程中，1到k基因位點(diǎn)上的基因改變的概率為0.5(“1”變化“0”或者“0”變?yōu)椤?”)，因此，交叉之后，基因位點(diǎn)上的染色

11、體搜索步驟從1到k的數(shù)學(xué)期望是此外，每個(gè)位點(diǎn)的染色體發(fā)生交叉的概率是相等的，即Pc。交叉后，染色體搜索步驟的數(shù)學(xué)期望是把Eq. ( A1)替換為Eq. ( A2)，我們得到其中l(wèi)是非常大的， 所以圖1 單點(diǎn)交叉定理4 位變異的染色體搜索步驟的數(shù)學(xué)期望是其中Pm是變異概率。證明：每個(gè)基因位點(diǎn)上的基因的變異概率是相等的，比如Pm，因此變異搜索步驟數(shù)學(xué)期望是：參考文獻(xiàn)1 Li Haimin, Wu Chengke. 自適應(yīng)變異概率的遺傳算法以及其性能分析. J. Acta Electronia Sinica ,1999, 27( 5) : 89 - 92.2 Nara Koichi. 基于大規(guī)模的分布式系統(tǒng)損失最小化的改進(jìn)遺傳算法. A. 進(jìn)化計(jì)算IEEE會(huì)議 C . 1995: 120 - 125.3 Lei Yin, Wei Hong. 一種改進(jìn)的遺傳算法以及它在E計(jì)劃波導(dǎo)過濾器設(shè)計(jì)重點(diǎn)額應(yīng)用 J . Acta Electronia Sinica, 2000