一種新的改進(jìn)遺傳算法及其性能分析外文翻譯/中英文翻譯/外文文獻(xiàn)翻譯

一種新的改進(jìn)遺傳算法及其性能分析外文翻譯 中英文翻譯外文文獻(xiàn)翻譯   摘要： 雖然遺傳算法以其全局搜索、并行計(jì)算、更好的健壯性以及在進(jìn)化過程中不需要求導(dǎo)而著稱，但是它仍然有一定的缺陷，比如收斂速度慢。本文根據(jù)幾個(gè)基本定理，提出了一種使用變異染色體長(zhǎng)度和交叉變異概率的改進(jìn)遺傳算法，它的主要思想是：在進(jìn)化的開始階段，我們使用短一些的變異染色體長(zhǎng)度和高一些的交叉變異概率來解決，在全局最優(yōu)解附近，使用長(zhǎng)一些的變異染色體長(zhǎng)度和低一些的交叉變異概率。最后，一些關(guān)鍵功能的測(cè)試表明，我們的解決方案可以顯著提高遺傳算法的收 斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。   關(guān)鍵字： 編譯染色體長(zhǎng)度；變異概率；遺傳算法；在線離線性能   遺傳算法是一種以自然界進(jìn)化中的選擇和繁殖機(jī)制為基礎(chǔ)的自適應(yīng)的搜索技術(shù)，它是由Holland 1975 年首先提出的。它以其全局搜索、并行計(jì)算、更好的健壯性以及在進(jìn)化過程中不需要求導(dǎo)而著稱。然而它也有一些缺點(diǎn)，如本地搜索不佳，過早收斂，以及收斂速度慢。近些年，這個(gè)問題被廣泛地進(jìn)行了研究。  本文提出了一種使用變異染色體長(zhǎng)度和交叉變異概率的改進(jìn)遺傳算法。一些關(guān)鍵功能的測(cè)試表明，我們的解決方案可以顯著提 高遺傳算法的收斂速度，其綜合性能優(yōu)于只保留最佳個(gè)體的遺傳算法。  在第一部分，提出了我們的新算法。第二部分，通過幾個(gè)優(yōu)化例子，將該算法和只保留最佳個(gè)體的遺傳算法進(jìn)行了效率的比較。第三部分，就是所得出的結(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是變異概率   1.2 算法機(jī)制  在進(jìn)化過程中，我們假設(shè)變量的值域是固定的，交叉的概率是一個(gè)常數(shù)，所以從定理 1 和定理 3 我們知道，較長(zhǎng)的染色體長(zhǎng)度有著較少的染色體搜索步驟和較高的分辨率；反之亦然。同時(shí)，交叉概率與搜索步驟成正比。由定理 4，改變?nèi)旧w的長(zhǎng)度不影響變異的搜索步驟，而變異概率與搜索步驟也是成正比的。  進(jìn)化的開始階段，較短染色體（可以是過短，否則它不利于種群多樣性）和較高的交叉和變異概率會(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 算法描述  由于基本遺傳算法沒有在全局優(yōu)化時(shí)收斂，而遺傳算法保留了當(dāng)前一代的最佳個(gè)體，我  們的方法采用這項(xiàng)策略。在進(jìn)化過程中，我們跟蹤到當(dāng)代個(gè)體平均適應(yīng)度的累計(jì)值。它被寫成：  X(t) = (t) 其中 G 是當(dāng)前進(jìn)化的一代， fav g是個(gè)體的平均適應(yīng)度。  當(dāng)累計(jì)平均適用性增加到最初個(gè)體平均適應(yīng)度的 k ( k> 1, k  R) 倍，我們將染色體長(zhǎng)度變?yōu)槠渥陨淼?m (m 是一個(gè)正整數(shù) ) 倍，然后減小交叉和變異的概率 ，可以提高個(gè)體分辨率、減少搜索步驟以及提高算法收斂速度。算法的執(zhí)行步驟如下：  第一步：初始化群體，并計(jì)算個(gè)體平均適應(yīng)度 fav g0，然后設(shè)置改變參數(shù)的標(biāo)志 flag。 flag設(shè)為 1. 第二步：在所保留的當(dāng)代的最佳個(gè)體，進(jìn)行選擇、再生、交叉和變異，并計(jì)算當(dāng)代個(gè)體的累積平均適應(yīng)度 fav g 第三步：如果   且 flag = 1，把染色體的 長(zhǎng)度增加至自身的 m 倍，減少交叉和變異概率，并設(shè)置 flag 等于 0；否則繼續(xù)進(jìn)化。  第四步：如果滿足結(jié)束條件，停止；否則轉(zhuǎn)自第二步。    2. 測(cè)試和分析  我們采用以下兩種方法來測(cè)試我們的方法，和只保留最佳個(gè)體的遺傳算法進(jìn)行比較：                             2.1 收斂的分析  在功能測(cè)試中，我們進(jìn)行了以下政策：輪盤賭選擇，單點(diǎn)交叉，位變異。種群的規(guī)  模是 60。 L 是染色體長(zhǎng)度， Pc和 Pm分別是交叉概率和變異概率。我們隨機(jī)選擇 4 個(gè)遺傳算法所保留的最佳個(gè)體來與我們的方法進(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=10 Pc=0.1,Pm=0.1 l=10 Pc=0.1,Pm=0.1 l=30 Pc=0.1,Pm=0.1 l=30 Pc=0.1,Pm=0.1 f1 257 15236 35791 1626 4363 f2 198 26973 42374 450 5433 2.2 在線和離線性能的分析      Dejong 提出了遺傳算法的定量評(píng)價(jià)方法，包括在線和離線性能評(píng)價(jià)。前者測(cè)試動(dòng)態(tài)性能，而后 者評(píng)估收斂性能。為了更好地分析測(cè)試功能的在線和離線性能，我們把個(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é)論  本文提出了一種使用變異染色體長(zhǎng)度和交叉變異概率的 改進(jìn)遺傳算法。一些關(guān)鍵功能的測(cè)試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優(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)?”1”)，因此，交叉之后，基因位點(diǎn)上的染色體搜索步驟從 1 到 k 的數(shù)學(xué)期望是   此外，每個(gè)位點(diǎn)的染色體發(fā)生交 叉的概率是相等的，即 Pc。交叉后，染色體搜索步驟的數(shù)學(xué)期望是    把 Eq. ( A1)替換為 Eq. ( A2)，我們得到   其中 l 是非常大的， ，  所以   圖 1 單點(diǎn)交叉   定理 4 位變異的染色體搜索步驟的數(shù)學(xué)期望是   其中 Pm是變異概率。  證明：  每個(gè)基因位點(diǎn)上的基因的變異概率是相等的，比如 Pm，因此變異搜索步驟的數(shù)學(xué)期望是：   參考  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, 28( 6) : 121- 124. 4  Enrique Alba, Jose M T roya.遷移策略在結(jié)構(gòu)化的隨機(jī)交配群體中的并行分布遺傳算法的影響 . J . 應(yīng)用智能  , 2000, 12: 163 - 181. 5  Rudolph R. 經(jīng)典遺傳算法的收斂分析 . J . 基于神經(jīng)網(wǎng)絡(luò)的 IEEE轉(zhuǎn)錄 , 1994, 5( 1) : 96 - 101.   Improved Genetic Algorithm and Its Performance Analysis Abstract: Although genetic algorithm has become very famous with its global searching, parallel computing, better robustness, and not needing differential information during evolution. However, it also has some demerits, such as slow convergence speed. In this paper, based on several general theorems, an improved genetic algorithm using variant chromosome length and probability of crossover and mutation is proposed, and its main idea is as follows : at the beginning of evolution, our solution with shorter length chromosome and higher probability of crossover and mutation； and at the vicinity of global optimum, with longer length chromosome and lower probability of crossover and mutation. Finally, testing with some critical functions shows that our solution can improve the convergence speed of genetic algorithm significantly , its comprehensive performance is better than that of the genetic algorithm which only reserves the best individual. Keywords: variant chromosome length； variant probability； genetic algorithm； online and offline performance Genetic algorithm is an adaptive searching technique based on a selection and reproduction mechanism found in the natural evolution process, and it was pioneered by Holland in the 1970s. It has become very famous with its global searching, parallel computing, better robustness, and not needing differential information during evolution. However, it also has some demerits, such as poor local searching, premature converging, as well as slow convergence speed. In recent years, these problems have been studied. In this paper, an improved genetic algorithm with variant chromosome length and variant probability is proposed. Testing with some critical functions shows that it can improve the convergence speed significantly, and its comprehensive performance is better than that of the genetic algorithm which only reserves the best individual. In section 1, our new approach is proposed. Through optimization examples, in section 2, the efficiency of our algorithm is compared with the genetic algorithm which only reserves the best individual. And section 3 gives out the conclusions. Finally, some proofs of relative theorems are collected and presented in appendix. 1  Description of the algorithm   1.1  Some theorems Before proposing our approach, we give out some general theorems (see appendix) as follows: Let us assume there is just one variable (multivariable can be divided into many sections, one section for one variable) x   a, b , x  R, and chromosome length with binary encoding is 1.  Theorem 1   Minimal resolution of chromosome is s =   Theorem 2   Weight value of the ith bit of chromosome is  wi =    ( i = 1,2, l ) Theorem 3   Mathematical expectation Ec(x) of chromosome searching step with one-point crossover is Ec (x) = Pc where Pc is the probability of crossover. Theorem 4   Mathematical expectation  Em ( x ) of chromosome searching step with bit mutation is Em ( x ) = ( b- a) Pm where Pm is the probability of mutation. 1. 2  Mechanism of algorithm During evolutionary process, we presume that value domains of variable are fixed, and the probability of crossover is a constant, so from Theorem 1 and 3, we know that the longer chromosome length is, the smaller searching step of chromosome, and the higher resolution； and vice versa. Meanwhile, crossover probability is in direct proportion to searching step. From Theorem 4, changing the length of chromosome does not affect searching step of mutation, while mutation probability is also in direct proportion to searching step. At the beginning of evolution, shorter length chromosome( can be too shorter, otherwise it is harmful to population diversity ) and higher probability of crossover and mutation increases searching step, which can carry out greater domain searching, and avoid falling into local optimum. While at the vicinity of global optimum, longer length chromosome and lower probability of crossover and mutation will decrease searching step, and longer  length chromosome also improves resolution of mutation, which avoid wandering near the global optimum, and speeds up algorithm converging. Finally, it should be pointed out that chromosome length changing keeps individual fitness unchanged, hence it does not affect select ion ( with roulette wheel selection) . 1. 3  Description of the algorithm Owing to basic genetic algorithm not converging on the global optimum, while the genetic algorithm which reserves the best individual at current generation can, our approach adopts this policy. During evolutionary process, we track cumulative average of individual average fitness up to current generation. It is written as X(t) = (t) where G is the current evolutionary generation,  is individual average fitness.  When the cumulative average fitness increases to k times ( k> 1, k  R) of initial individual average fitness, we change chromosome length to m times ( m is a positive integer ) of itself , and reduce probability of crossover and mutation, which can improve individual resolution and reduce searching step, and speed up algorithm converging. The procedure is as follows: Step 1  Initialize population, and calculate individual average fitness , and set change parameter flag. Flag equal to 1. Step 2  Based on reserving the best individual of current generation, carry out selection, regeneration, crossover and mutation, and calculate cumulative average of individual average fitness up to current generation  ； Step 3  If k  and Flag equals 1, increase chromosome length to m times of itself, and reduce probability of crossover and mutation, and set Flag equal to 0； otherwise continue evolving. Step 4  If end condition is satisfied, stop； otherwise go to Step 2. 2  Test and analysis We adopt the following two critical functions to test our approach, and compare it with the genetic algorithm which only reserves the best individual:                             2. 1  Analysis of convergence During function testing, we carry out the following policies: roulette wheel select ion, one point crossover, bit mutation, and the size of population is 60, l is chromosome length, Pc  and Pm are the probability of crossover and mutation respectively. And we randomly select four genetic algorithms reserving best individual with various fixed chromosome length and probability of crossover and mutation to compare with our approach. Tab. 1 gives the average converging generation in 100 tests. In our approach, we adopt initial parameter l0= 10, Pc0= 0.3, Pm0= 0.1 and k= 1.2, when changing parameter condition is satisfied, we adjust parameters to l= 30, Pc= 0.1, Pm= 0.01. From Tab. 1, we know that our approach improves convergence speed of genetic algorithm significantly and it accords with above analysis. Tab.1 Result of function testing Functions Our algorithm l=10 Pc=0.1,Pm=0.1 l=10 Pc=0.1,Pm=0.1 l=30 Pc=0.1,Pm=0.1 l=30 Pc=0.1,Pm=0.1 f1 257 15236 35791 1626 4363 f2 198 26973 42374 450 5433 2. 2  Analysis of online and offline performance Quantitative evaluation methods of genetic algorithm are proposed by Dejong, including online and offline performance. The former tests dynamic performance； and the latter evaluates convergence performance. To better analyze online and offline performance of testing function, w e multiply fitness of each individual by 10, and we give a curve of 4 000 and 1 000 generations for f1 and f2, respectively. (a) online                                   (b) online Fig. 1  Online and offline performance of f1 (a) online                                  (b) online   Fig. 2  Online and offline performance of f2   From Fig. 1 and Fig. 2, we know that online performance of our approach is just little worse than that of the fourth case, but it is much better than that of the second, third and fifth case, whose online performances are nearly the same. At the same time, offline performance of our approach is better than that of other four cases. 3 Conclusion In this paper, based on some general theorems, an improved genetic algorithm using variant chromosome length and probability of crossover and mutation is proposed. Testing with some critical functions shows that it can improve convergence speed of genetic algorithm significantly, and its comprehensive performance is better than that of the genetic algorithm which only reserves the best individual. Appendix With the supposed conditions of section 1, we know that the validation of Theorem 1 and Theorem 2 are obvious. Theorem 3  Mathematical expectation Ec(x) of chromosome searching step with one point crossover is Ec(x) =   where Pc  is the probability of crossover. Proof   As shown in Fig. A1, we assume that crossover happens on the kth locus, i. e. parents locus from k to l do not change, and genes on the locus from 1 to k are exchanged. During crossover, change probability of genes on the locus from 1 to k is  (“1” to “0” or “0” to “1