毕业论文外文翻译-一种新的改进遗传算法及其性能分析

《毕业论文外文翻译-一种新的改进遗传算法及其性能分析》由会员分享，可在线阅读，更多相关《毕业论文外文翻译-一种新的改进遗传算法及其性能分析（16页珍藏版）》请在装配图网上搜索。

1、天津大学学报2003年 9卷 2期一种新的改进遗传算法及其性能分析罗批，李锵，郭继昌，腾建辅（天津大学电子信息工程系，天津300072）摘要：虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法，它的主要思想是：在进化的开始阶段，我们使用短一些的变异染色体长度和高一些的交叉变异概率来解决，在全局最优解附近，使用长一些的变异染色体长度和低一些的交叉变异概率。最后，一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保

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

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

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

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

6、步骤以及提高算法收敛速度。算法的执行步骤如下：第一步：初始化群体，并计算个体平均适应度favg0，然后设置改变参数的标志flag。flag设为1.第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异，并计算当代个体的累积平均适应度favg第三步：如果 且flag = 1，把染色体的长度增加至自身的m倍，减少交叉和变异概率，并设置flag等于0;否则继续进化。第四步：如果满足结束条件，停止；否则转自第二步。2. 测试和分析我们采用以下两种方法来测试我们的方法，和只保留最佳个体的遗传算法进行比较： 2.1 收敛的分析在功能测试中，我们进行了以下政策：轮盘赌选择，单点交叉，位变异。种群的规模

7、是60。L是染色体长度，Pc和Pm分别是交叉概率和变异概率。我们随机选择4个遗传算法所保留的最佳个体来与我们的方法进行比较，它们具有不同的固定染色体长度和交叉和变异的概率。表1给出了在100次测试的平均收敛代。 在我们的方法中，我们采取的初始参数是l0 = 10，Pc0 = 0.3，Pm0 = 0.1和k = 1.2，当满足改变参数的条件时，我们调整参数l = 30，Pc = 0.1，Pm = 0.01。从表1中得知，我们的方法显著提高了遗传算法的收敛速度，正符合上述分析。表1 功能测试结果方法我们的算法l=10Pc=0.1,Pm=0.1l=10Pc=0.1,Pm=0.1l=30Pc=0.1,

8、Pm=0.1l=30Pc=0.1,Pm=0.1f1257152363579116264363f2198269734237445054332.2 在线和离线性能的分析 Dejong提出了遗传算法的定量评价方法，包括在线和离线性能评价。前者测试动态性能，而后者评估收敛性能。为了更好地分析测试功能的在线和离线性能，我们把个体的适应性乘以10，并f1和f2分别给出了4 000和1 000代的曲线：(a) 在线 (b) 离线图1 f1的在线与离线性能(a) 在线 (b) 离线图2 f2的在线与离线性能 从图1和图2可以看出，我们方法的在线性能只比第四种情况差一点点，但比第二种、第三种、第五种好很多，这几

9、种情况下的在线性能几乎完全相同。同时，我们方法的离线性能也比其他四种好很多。3. 结论本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。附件有了第一部分中假定的条件，定理1和定理2的验证是显而易见的。下面给出定理3和定理4的证明过程：定理3 单点交叉的染色体搜索步骤的数学期望Ec(x)是 Ec (x) = Pc其中Pc是交叉概率证明：如图A1所示，我们假设交叉发生在第k个基因位点，从k到l的父基因位点没有变化，基因位点1到k上的基因改变了。在交叉过程中，1到k基因位点上的基

10、因改变的概率为0.5(“1”变化”0”或者”0”变为”1”)，因此，交叉之后，基因位点上的染色体搜索步骤从1到k的数学期望是此外，每个位点的染色体发生交叉的概率是相等的，即Pc。交叉后，染色体搜索步骤的数学期望是把Eq. ( A1)替换为Eq. ( A2)，我们得到其中l是非常大的， 所以图1 单点交叉定理4 位变异的染色体搜索步骤的数学期望是其中Pm是变异概率。证明：每个基因位点上的基因的变异概率是相等的，比如Pm，因此变异搜索步骤的数学期望是：参考1 Li Haimin, Wu Chengke. 自适应变异概率的遗传算法以及其性能分析. J. Acta Electronia Sinica

11、,1999, 27( 5) : 89 - 92.2 Nara Koichi. 基于大规模的分布式系统损失最小化的改进遗传算法. A. 进化计算IEEE会议 C . 1995: 120 - 125.3 Lei Yin, Wei Hong. 一种改进的遗传算法以及它在E计划波导过滤器设计重点额应用 J . Acta Electronia Sinica, 2000, 28( 6) : 121- 124.4 Enrique Alba, Jose M T roya.迁移策略在结构化的随机交配群体中的并行分布遗传算法的影响. J . 应用智能 , 2000, 12: 163 - 181.5 Rudolph

12、 R. 经典遗传算法的收敛分析. J . 基于神经网络的IEEE转录, 1994, 5( 1) : 96 - 101.Transactions of Tianjin UniversityVol. 9 No.2 Jun. 2003Improved Genetic Algorithm and Its Performance AnalysisLUO Pi ( 罗批 ) , LI Qiang ( 李锵 ) , GUO Ji chang( 郭继昌 ) , TENG Jian fu( 滕建辅)( School of Electronic Information Engineering, Tianjin U

13、niversity , Tianjin 300072, China)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

14、, 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 a

15、nd 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 performanc

16、e 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 performanceArticle ID: 1006 4982(2003) 02 0140 04Genetic algorithm is an adaptive searching technique based on a sele

17、ction 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 deme

18、rits, 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 t

19、hat 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 c

20、ompared 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 algorithm1.1 Some theoremsBefore proposing our approach, we give out some genera

21、l 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 iss = Theorem 2 Weight value of the

22、 ith bit of chromosome is wi = ( i = 1,2,l )Theorem 3 Mathematical expectation Ec(x) of chromosome searching step with one-point crossover isEc (x) = Pcwhere Pc is the probability of crossover.Theorem 4 Mathematical expectation Em ( x ) of chromosome searching step with bit mutation isEm ( x ) = ( b

23、- a) Pmwhere Pm is the probability of mutation.1. 2 Mechanism of algorithmDuring 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 ste

24、p 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 s

25、tep.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

26、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 shou

27、ld 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 algorithmOwing to basic genetic algorithm not converging on the global optimum, while the genetic algorithm which reserv

28、es 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 asX(t) = (t)where G is the current evolutionary generation, is individual average fitness.

29、 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 s

30、tep, 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, crossove

31、r 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 en

32、d condition is satisfied, stop; otherwise go to Step 2.2 Test and analysisWe 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 convergenceDuring function testing, we carry out the follo

33、wing 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 chr

34、omosome 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 t

35、o 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 testingFunctionsOuralgorithml=10Pc=0.1,Pm=0.1l=10Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1f125715236357911

36、6264363f2198269734237445054332. 2 Analysis of online and offline performanceQuantitative 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

37、 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) onlineFig. 1 Online and offline performance of f1(a) online (b) online Fig. 2 Online and offline performan

38、ce of f2From 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

39、 is better than that of other four cases.3 ConclusionIn 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

40、 genetic algorithm significantly, and its comprehensive performance is better than that of the genetic algorithm which only reserves the best individual.AppendixWith the supposed conditions of section 1, we know that the validation of Theorem 1 and Theorem 2 are obvious.Theorem 3 Mathematical expect

41、ation Ec(x) of chromosome searching step with one point crossover isEc(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 cr

42、ossover, change probability of genes on the locus from 1 to k is (“1” to “0” or “0” to “1”). So, after crossover, mathematical expectation of chromosome searching step on locus from 1 to k isFurthermore, probability of taking place crossover on each locus of chromosome is equal, namely Pc. Therefore

43、, after crossover, mathematical expectation of chromosome searching step isSubstituting Eq. ( A1) into Eq. ( A2) , we obtainwhere l is large, , so Fig. A1 One point crossoverTheorem 4 Mathematical expectation of chromosome searching step with bit mutation , where Pm is the probability of mutation.Pr

44、oof Mutation probability of genes on each locus of chromosome is equal, say Pm, therefore, mathematical expectation of mutation searching step isReferences 1 Li Haimin, Wu Chengke. Genetic algorithm with adaptive mutation probability and analysis of its property J . Acta Electronia Sinica ,1999, 27(

45、 5) : 89 - 92. 2 Nara Koichi. Improved genetic algorithm for large scale distribution systems loss minimum problem A . Proceedings of the IEEE Conference on Evolutionary Computation C . 1995: 120 - 125. 3 Lei Yin, Wei Hong. An improved genetic algorithm and it s applicationin E-plane waveguide filte

46、r design J . Acta Electronia Sinica, 2000, 28( 6) : 121 - 124. 4 Enrique Alba, Jose M T roya. Influence of the migration policy in parallel distributed GAs with structured and panmictic populations J . Applied Intelligence , 2000, 12: 163-181. 5 Rudolph R. Convergence analysis of canonical genetic a

47、lgorithm J . IEEE Trans on Neural Networks, 1994, 5( 1) : 96 - 101. 五分钟搞定5000字毕业论文外文翻译，你想要的工具都在这里!在科研过程中阅读翻译外文文献是一个非常重要的环节，许多领域高水平的文献都是外文文献，借鉴一些外文文献翻译的经验是非常必要的。由于特殊原因我翻译外文文献的机会比较多，慢慢地就发现了外文文献翻译过程中的三大利器：Google“翻译”频道、金山词霸（完整版本）和CNKI“翻译助手。具体操作过程如下： 1.先打开金山词霸自动取词功能，然后阅读文献； 2.遇到无法理解的长句时，可以交给Google处理，处理后的

48、结果猛一看，不堪入目，可是经过大脑的再处理后句子的意思基本就明了了； 3.如果通过Google仍然无法理解，感觉就是不同，那肯定是对其中某个“常用单词”理解有误，因为某些单词看似很简单，但是在文献中有特殊的意思，这时就可以通过CNKI的“翻译助手”来查询相关单词的意思，由于CNKI的单词意思都是来源与大量的文献，所以它的吻合率很高。 另外，在翻译过程中最好以“段落”或者“长句”作为翻译的基本单位，这样才不会造成“只见树木，不见森林”的误导。四大工具： 1、Google翻译： google，众所周知，谷歌里面的英文文献和资料还算是比较详实的。我利用它是这样的。一方面可以用它查询英文论文，当然这方

49、面的帖子很多，大家可以搜索，在此不赘述。回到我自己说的翻译上来。下面给大家举个例子来说明如何用吧比如说“电磁感应透明效应”这个词汇你不知道他怎么翻译，首先你可以在CNKI里查中文的，根据它们的关键词中英文对照来做，一般比较准确。 在此主要是说在google里怎么知道这个翻译意思。大家应该都有词典吧，按中国人的办法，把一个一个词分着查出来，敲到google里，你的这种翻译一般不太准，当然你需要验证是否准确了，这下看着吧，把你的那支离破碎的翻译在google里搜索，你能看到许多相关的文献或资料，大家都不是笨蛋，看看，也就能找到最精确的翻译了，纯西式的！我就是这么用的。 2、CNKI翻译： CNKI

50、翻译助手，这个网站不需要介绍太多，可能有些人也知道的。主要说说它的有点，你进去看看就能发现：搜索的肯定是专业词汇，而且它翻译结果下面有文章与之对应（因为它是CNKI检索提供的，它的翻译是从文献里抽出来的），很实用的一个网站。估计别的写文章的人不是傻子吧，它们的东西我们可以直接拿来用，当然省事了。网址告诉大家，有兴趣的进去看看，你们就会发现其乐无穷！还是很值得用的。 3、网路版金山词霸（不到1M）： 4、有道在线翻译：翻译时的速度：这里我谈的是电子版和打印版的翻译速度，按个人翻译速度看，打印版的快些，因为看电子版本一是费眼睛，二是如果我们用电脑，可能还经常时不时玩点游戏，或者整点别的，导致最终S

51、PPEED变慢，再之电脑上一些词典（金山词霸等）在专业翻译方面也不是特别好，所以翻译效果不佳。在此本人建议大家购买清华大学编写的好像是国防工业出版社的那本英汉科学技术词典，基本上挺好用。再加上网站如：google CNKI翻译助手，这样我们的翻译速度会提高不少。具体翻译时的一些技巧（主要是写论文和看论文方面） 大家大概都应预先清楚明白自己专业方向的国内牛人，在这里我强烈建议大家仔细看完这些头上长角的人物的中英文文章，这对你在专业方向的英文和中文互译水平提高有很大帮助。 我们大家最蹩脚的实质上是写英文论文，而非看英文论文，但话说回来我们最终提高还是要从下大工夫看英文论文开始。提到会看，我想它是有

52、窍门的，个人总结如下： 1、把不同方面的论文分夹存放，在看论文时，对论文必须做到看完后完全明白（你重视的论文）；懂得其某部分讲了什么（你需要参考的部分论文），在看明白这些论文的情况下，我们大家还得紧接着做的工作就是把论文中你觉得非常巧妙的表达写下来，或者是你论文或许能用到的表达摘记成本。这个本将是你以后的财富。你写论文时再也不会为了一些表达不符合西方表达模式而烦恼。你的论文也降低了被SCI或大牛刊物退稿的几率。不信，你可以试一试 2、把摘记的内容自己编写成检索，这个过程是我们对文章再回顾，而且是对你摘抄的经典妙笔进行梳理的重要阶段。你有了这个过程。写英文论文时，将会有一种信手拈来的感觉。许多文笔我们不需要自己再翻译了。当然前提是你梳理的非常细，而且中英文对照写的比较详细。 3、最后一点就是我们往大成修炼的阶段了，万事不是说成的，它是做出来的。写英文论文也就像我们小学时开始学写作文一样，你不练笔是肯定写不出好作品来的。所以在此我鼓励大家有时尝试着把自己的论文强迫自己写成英文的，一遍不行，可以再修改。最起码到最后你会很满意。呵呵，我想我是这么觉得的。