遗传算法中英文对照外文翻译文献

1、遗传算法中英文对照外文翻译文献遗传算法中英文对照外文翻译文献（文档含英文原文和中文翻译）Improved Gen etic Algorithm and Its Performa nee An alysisAbstract: Although gen etic algorithm has become very famous with its global searching, parallel computing, better robustness, and not needing differential information during evolution. However, it

2、also has some demerits, such as slow con verge ncespeed. In this paper, based on several general theorems, an improved genetic algorithm using variant chromosome length and probability of crossover and mutati on is proposed, and its main idea is as follows : at the beg inning of evoluti on, our solu

3、tion with shorter length chromosome and higher probability of crossover and mutatio n; and at the vic in ity of global optimum, with Ion ger len gth chromosome and lower probability of crossover and mutation. Finally, testing with some critical functions shows that our soluti on can improve the con

4、verge nee speed of gen etic algorithm significantly , its comprehensive performance is better than that of the gen etic algorithm which only reserves the best in dividual.Genetic algorithm is an adaptive searching technique based on a selection and reproduct ion mecha nism found in the n atural evol

5、uti on process, and it was pion eered by Holla nd in the 1970s. It has become very famous with its global search ing, parallel computing, better robustness, and not needing differential information during evolution. However, it also has some demerits, such as poor local searching, premature convergi

6、ng, as well as slow convergenee speed. In recent years, these problems have bee n 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 conv erge nee speed sig nifica

7、 ntly, and its comprehe nsive performa nee is better tha n that of the gen etic algorithm which only reserves the best in dividual.In section 1, our new approach is proposed. Through optimization examples, in sect ion 2, the efficie ncy of our algorithm is compared with the gen etic algorithm which

8、only reserves the best in dividual. And secti on 3 gives out the con clusi ons. Fi nally, some proofs of relative theorems are collected and prese nted in appe ndix.1 Descripti on of the algorithm1.1 Some theoremsBefore proposing our approach, we give out some general theorems (see appendix) as foll

9、ows: Let us assume there is just one variable (multivariable can be divided into many sect ions, one sect ion for one variable) x a, b , x R, and chromosome len gth with binary en cod ing is 1.Theorem 1Mi nimal resoluti on of chromosome is2l 1Theorem 2 Weight value of the ith bit of chromosome is 害

10、2( i = 1,2，l )2l 1Theorem 3 Mathematical expectati on Ec(x) of chromosome searchi ng step with on e-po int crossover isb aEc (x) =Pc2lwhere Pc is the probability of crossover.Theorem 4 Mathematical expectation Em ( x ) of chromosome searching step with bit mutati on isEm ( x ) = ( b- a) P m1.2 Mecha

11、 nism of algorithmDuring evolutionary process, we presume that value domains of variable are fixed, and the probability of crossover is a con sta nt, so from Theorem 1 and 3, we know that the Ion ger chromosome len gth is, the smaller search ing step of chromosome, and the higher resolutio n; and vi

12、ce versa. Mean while, crossover probability is in direct proportio n to search ing step. From Theorem 4, cha nging the len gth of chromosome does not affect searchi ng step of mutati on, while mutati on probability is also in direct proporti on to searchi ng step.At the beginning of evolution, short

13、er length chromosome( can be too shorter, otherwise it is harmful to population diversity ) and higher probability of crossover and mutatio n in creases searchi ng step, which can carry out greater doma in search ing, and avoid falli ng in to local optimum. While at the vic in ity of global optimu m

14、, Ion ger length chromosome and lower probability of crossover and mutation will decrease search ing step, and Ion ger len gth chromosome also improves resolutio n of mutati on, which avoid wandering near the global optimum, and speeds up algorithm con verg ing.Fin ally, it should be poin ted out th

15、at chromosome len gth cha nging keeps in dividual fit ness un cha nged, hence it does not affect select ion (with roulette wheel select ion).1.3 Descripti on of the algorithmOwing to basic genetic algorithm not converging on the global optimum, while the gen etic algorithm which reservesthe best in

16、dividual at curre nt gen erati on can, our approach adopts this policy. During evolutionary process, we track cumulative average of in dividual average fit ness up to curre nt gen erati on .It is writte n asavg (t)1 GX(t)=-G t 1avg is in dividual averagewhere G is the current evolutionary generation

17、, fitn ess.When the cumulative averagefitness increasesto k times ( k 1, k R) of in itial in dividual average fit ness, we cha nge chromosome len gth to m times ( m is a positive integer ) of itself , and reduce probability of crossover and mutation, which can improve in dividual resoluti on and red

18、uce search ing step, and speed up algorithm con verg ing. The procedure is as follows:Step 1 In itialize populati on, and calculate in dividual average fit ness favg0, and set cha nge parameter flag. Flag equal to 1.Step 2 Based on reserv ing the best in dividual of curre nt gen erati on, carry out

19、select ion, rege neratio n, crossover and mutati on, and calculate cumulative average of in dividual average fitn ess up to curre nt gen erati on favg ;favgStep 3 If favg0 k and Flag equals 1, increase chromosome length to m times of itself, and reduce probability of crossover and mutation, and set

20、Flag equal to 0; otherwise continue evo Iving.Step 4 If end condition is satisfied, stop; otherwise go to Step 2.2 Test and an alysisWe adopt the following two critical functions to test our approach, and compare it with the gen etic algorithm which only reserves the best in dividual:si n2Jx2 y20.5f

21、1（x, y） 0.5-x, y 5,510.01 x y 2 2f2（x, y） 4 （x 2y0.3cos（3冗 x） 0.4cos（4冗 y）x, y 1,12. 1 An alysis of conv erge neeDuring 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 an

22、d Pm are the probability of crossover and mutation respectively. And we randomly select four genetic algorithms reserving best in dividual with various fixed chromosome len gth and probability of crossover and mutation to compare with our approach. Tab. 1 gives the average converging gen erati on in

23、 100 tests.In our approach, we adopt in itial 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 convergenee speed of genetic algorithm significantly and it

24、accords with above analysis.2. 2 Analysis of online and offline performaneeQuan titative evaluati on methods of gen etic algorithm are proposed by Dejong, including online and offline performanee. The former tests dynamic performanee; and the latter evaluates convergenee performanee. To better analy

25、ze online and offli ne performa nee of testi ng function, w e multiply fit ness of each in dividual by 10, and we give a curve of 4 000 and 1 000 gen erati ons for fl and f2, respectively.(a) on li neFig. 1 Online and offli ne performa nee of flFig. 2 On li ne and offline performa nee of f2From Fig.

26、 1 and Fig. 2, we know that on li ne performa nee 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 performancesare nearly the same. At the same time, offli ne performa nee of our approach is better th

27、a n that of other four cases.3 Con clusi onIn this paper, based on some general theorems, an improved genetic algorithmusing variant chromosome length and probability of crossover and mutation is proposed. Testing with some critical functions shows that it can improve con verge nee speed of gen etic

28、 algorithm sig nifica ntly, and its comprehe nsive performa nee is better tha n that of the gen etic algorithm which only reserves the best in dividual.Appe ndixWith the supposed conditions of section 1, we know that the validation of Theorem 1 and Theorem 2 are obvious.Theorem 3 Mathematical expect

29、ation Ec(x) of chromosome searching step with one point crossover isb apEc(x) = 2lwhere Pc is the probability of crossover.Proof As show n in Fig. A1, we assumethat crossover happe ns on the kth locus, i. e. pare nt s lo(fosm k to l do not cha nge, and genes on the locus from 1 to k are excha nged.1

30、During crossover, change probability of genes on the locus from 1 to k is 2 (1” to 0” or 0” to 1”). So, after crossover, mathematical expectation ofchromosome searchi ng step on locus from 1 to k isEck(x)k 1wj j 12 J1 c b a k2?厂？(21)Furthermore, probabilityof taking place crossover on each locus ofc

31、hromosome is equal, namely lPc. Therefore, after crossover, mathematical expectati on of chromosome search ing step isl 1 1Ec(x)-?Pc?Eck(x)k 1 lSubstituting Eq. ( A1) into Eq. ( A2) , we obtainEc(x)kj ?Pc?坍异?(八)fr?(2i 1) lPc?(b a) 1 )2l (2l 1)where l is large,亠 0, so Ec(x)Pc2l 12l1 1iiiH4IkChrcitrKi

32、imi.- 2I-1Fig. A1 One point crossoverE (x)Theorem 4 Mathematical expectati on mof chromosome searchi ng stepwith bit mutation Em(x) (b a) ? Pm, where Pm is the probability of mutation.Proof Mutation probability of geneson each locus of chromosome is equal, say Pm, therefore, mathematical expectati o

33、n of mutatio n search ing step isllb abaEm(x) = ? Pm -Wi=? Pm才二卩皿佗-“二-a)吒二二2l- 1 2i- 1一种新的改进遗传算法及其性能分析摘要：虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化 过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文 根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗 传算法，它的主要思想是：在进化的开始阶段，我们使用短一些的变异染色体 长度和高一些的交叉变异概率来解决，在全局最优解附近，使用长一些的变异 染色体长度和低一些的交叉变异概率。最后，一些关键功

34、能的测试表明，我们 的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个 体的遗传算法。遗传算法是一种以自然界进化中的选择和繁殖机制为基础的自适应的搜索 技术，它是由Holla nd 1975年首先提出的。它以其全局搜索、并行计算、更好 的健壮性以及在进化过程中不需要求导而著称。然而它也有一些缺点，如本地 搜索不佳，过早收敛，以及收敛速度慢。近些年，这个问题被广泛地进行了研 究。本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一 些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度， 其综合性能优于只保留最佳个体的遗传算法。在第一部分，提出了我们的新

35、算法。第二部分，通过几个优化例子，将该 算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分，就是所得出 的结论。最后，相关定理的证明过程可见附录。1算法的描述1.1 一些定理在提出我们的算法之前，先给出一个一般性的定理（见附件），如下：我们 假设有一个变量（多变量可以拆分成多个部分，每一部分是一个变量）x a, b , x R，二进制的染色体编码是1.定理1染色体的最小分辨率是s =定理2染色体的第i位的权重值是wi = ： a 2i 1( i = 1,2,l )2 1定理3单点交叉的染色体搜索步骤的数学期望Ec(x)是b aEc (x) =Pc2l其中Pc是交叉概率定理4位变异的染色体

36、搜索步骤的数学期望Em(x)是Em ( x ) = ( b- a) P m其中Pm是变异概率算法机制在进化过程中，我们假设变量的值域是固定的，交叉的概率是一个常数, 所以从定理1和定理3我们知道，较长的染色体长度有着较少的染色体搜索步骤和较高 的分辨率；反之亦然。同时，交叉概率与搜索步骤成正比。由定理 4,改变染色 体的长度不影响变异的搜索步骤，而变异概率与搜索步骤也是成正比的。进化的开始阶段，较短染色体(可以是过短，否则它不利于种群多样性) 和较高的交叉和变异概率会增加搜索步骤，这样可进行更大的域名搜索，避免 陷入局部最优。而全局最优的附近，较长染色体和较低的交叉和变异概率会减 少搜索的步骤

37、，较长的染色体也提高了变异分辨率，避免在全局最优解附近徘 徊，提高了算法收敛速度。最后，应当指出，染色体长度的改变不会使个体适应性改变，因此它不影 响选择(轮盘赌选择)。算法描述由于基本遗传算法没有在全局优化时收敛，而遗传算法保留了当前一代的 最佳个体，我X(t)=们的方法采用这项策略。在进化过程中，我们跟踪到当代个体平均适应度 的累计值。它被写成：favg (t)其中G是当前进化的一代，favg是个体的平均适应度。当累计平均适用性增加到最初个体平均适应度的k ( k 1, k R)倍，我们将染色体长度变为其自身的 m(m是一个正整数)倍，然后减小交叉和变异 的概率，可以提高个体分辨率、减少搜

38、索步骤以及提高算法收敛速度。算法的 执行步骤如下：第一步：初始化群体，并计算个体平均适应度favgO，然后设置改变参数的 标志flag。flag设为1.第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异，并 计算当代个体的累积平均适应度favgfavgOk第三步：如果favg且flag = 1,把染色体的长度增加至自身的 m倍，减少交叉和变异概率，并设置flag等于0;否则继续进化。第四步：如果满足结束条件，停止；否则转自第二步。测试和分析我们采用以下两种方法来测试我们的方法，和只保留最佳个体的遗传算法 进行比较：si 门花y20.5fi(x, y) 0.52 kx, y 5,510.01 x y 2 2f2(x, y) 4 (x 2y0.3cos(3冗 x) 0.4cos(4冗 y)x, y 1,1收敛的