2023年机器人算法外文翻译.docx

《2023年机器人算法外文翻译.docx》由会员分享，可在线阅读，更多相关《2023年机器人算法外文翻译.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023年机器人算法外文翻译 Improved Genetic Algorithm and Its Performance Analysis Abstract: Although genetic algorithm has become very famous with its global searching, parallel computing, better robustne, and not needing differential information during evolution.However, it also has some demerits, such as slo

2、w convergence speed.In this paper, based on several general theorems, an improved genetic algorithm using variant chromosome length and probability of croover and mutation is proposed, and its main idea is as follows : at the beginning of evolution, our solution with shorter length chromosome and hi

3、gher probability of croover and mutation; and at the vicinity of global optimum, with longer length chromosome and lower probability of croover and mutation.Finally, testing with some critical functions shows that our solution can improve the convergence speed of genetic algorithm significantly , it

4、s comprehensive performance is better than that of the genetic algorithm which only reserves the best individual.Genetic algorithm is an adaptive searching technique based on a selection and reproduction mechanism found in the natural evolution proce, and it was pioneered by Holland in the 1970s.It

5、has become very famous with its global searching, parallel computing, better robustne, 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 h

6、ave 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 al

7、gorithm 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

8、 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 aume there is just one variable (multivariable can be divided into many sections,

9、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 = b-a 2l-1Theorem 2 Weight value of the ith bit of chromosome is wi = b-ai-1 2 ( i = 1,2,l ) 2l-1Theorem 3 Mathematical expectation Ec(x) of chromosome searchi

10、ng step with one-point croover is Ec (x) = b-aPc 2lwhere Pc is the probability of croover. Theorem 4 Mathematical expectation Em ( x ) of chromosome searching step with bit mutation is Em ( x ) = ( b- a) Pm 1.2 Mechanism of algorithm During evolutionary proce, we presume that value domains of variab

11、le are fixed, and the probability of croover 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, croover probability is in direct proportion to searching step.From Theorem

12、 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 prob

13、ability of croover 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 croover and mutation will decrease searching step, and longer length

14、 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 fitne unchanged, hence it does not affect select ion ( with roulette wheel selection)

15、 . 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 proce, we track cumulative average of individual av

16、erage fitne up to current generation.It is written as 1X(t) = GGft=1avg(t) where G is the current evolutionary generation, fitne. favg is individual average When the cumulative average fitne increases to k times ( k 1, k R) of initial individual average fitne, we change chromosome length to m times

17、( m is a positive integer ) of itself , and reduce probability of croover 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 fitne and set chang

18、e parameter flag.Flag equal to 1. favg0, Step 2 Based on reserving the best individual of current generation, carry out selection, regeneration, croover and mutation, and calculate cumulative average of individual average fitne up to current generation favg ; favgStep 3 If favg0k and Flag equals 1,

19、increase chromosome length to m times of itself, and reduce probability of croover 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 appr

20、oach, and compare it with the genetic algorithm which only reserves the best individual: f1(x,y)=0.5-sin2x2+y2-0.51+0.01x+y(222) x,y -5,5 -1,1 f2(x,y)=4-(x2+2y2-0.3cos(3x)-0.4cos(4y) x,y2.1 Analysis of convergence During function testing, we carry out the following policies: roulette wheel select io

21、n, one point croover, bit mutation, and the size of population is 60, l is chromosome length, Pc and Pm are the probability of croover and mutation respectively.And we randomly select four genetic algorithms reserving best individual with various fixed chromosome length and probability of croover an

22、d 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

23、 that our approach improves convergence speed of genetic algorithm significantly and it accords with above analysis.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 dy

24、namic performance; and the latter evaluates convergence performance.To better analyze online and offline performance of testing function, w e multiply fitne 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 an

25、d 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 perf

26、ormances 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 croover and mutation is proposed.Te

27、sting 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 t

28、he validation of Theorem 1 and Theorem 2 are obvious.Theorem 3 Mathematical expectation Ec(x) of chromosome searching step with one point croover is b-aPc2lEc(x) = where Pc is the probability of croover.Proof As shown in Fig.A1, we aume that croover happens on the kth locus, i.e.parents locus from k

29、 to l do not change, and genes on the locus from 1 to k are exchanged. 1During croover, change probability of genes on the locus from 1 to k is 2 (“1” to “0” or “0” to “1”).So, after croover, mathematical expectation of chromosome searching step on locus from 1 to k is k11b-a1b-aEck(x)=wj=l2j-1=l(2k

30、-1) 22-12-1j=12j=12Furthermore, probability of taking place croover on each locus of k1chromosome is equal, namely l Pc.Therefore, after croover, mathematical expectation of chromosome searching step is 1Ec(x)=PcEck(x) k=1lSubstituting Eq.( A1) into Eq.( A2) , we obtain l-1Pb-aP(b-a)11b-a1Pcl(2k-1)=

31、cl(2i-1)-l=c(1-l)22-12l2-12l2-1k=1llb-a0, so Ec(x)Pc where l is large, l2l2-1Ec(x)=l-1 Fig.A1 One point croover Theorem 4 Mathematical expectation Em(x) of chromosome searching step with bit mutation Em(x)=(b-a)Pm, where Pm is the probability of mutation.Proof Mutation probability of genes on each l

32、ocus of chromosome is equal, say Pm, therefore, mathematical expectation of mutation searching step is Em(x)=Pmwi=Pmi=1i=1llb-ai-1b-a2=P(2i-1)=(b-a)Pm mli2-12-1 一种新的改进遗传算法及其性能分析 摘要：虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法，它的主要思想是：在进化的开始阶段，我

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

34、功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。 在第一部分，提出了我们的新算法。第二部分，通过几个优化例子，将该算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分，就是所得出的结论。最后，相关定理的证明过程可见附录。 1算法的描述 1.1 一些定理 在提出我们的算法之前，先给出一个一般性的定理（见附件），如下：我们假设有一个变量（多变量可以拆分成多个部分，每一部分是一个变量）x a, b , x R，二进制的染色体编码是1.定理1 染色体的最小分辨率是 s = b-a l2-1定理2 染色体的第i位的权重值是 b-ai-1 2 (

35、i = 1,2,l ) 2l-1定理3 单点交叉的染色体搜索步骤的数学期望Ec(x)是 wi = Ec (x) = b-aPc 2l其中Pc是交叉概率 定理4 位变异的染色体搜索步骤的数学期望Em(x)是 Em ( x ) = ( b- a) Pm 其中Pm是变异概率 算法机制 在进化过程中，我们假设变量的值域是固定的，交叉的概率是一个常数，所以从定理1 和定理3我们知道，较长的染色体长度有着较少的染色体搜索步骤和较高的分辨率；反之亦然。同时，交叉概率与搜索步骤成正比。由定理4，改变染色体的长度不影响变异的搜索步骤，而变异概率与搜索步骤也是成正比的。 进化的开始阶段，较短染色体（可以是过短，否

36、则它不利于种群多样性）和较高的交叉和变异概率会增加搜索步骤，这样可进行更大的域名搜索，避免陷入局部最优。而全局最优的附近，较长染色体和较低的交叉和变异概率会减少搜索的步骤，较长的染色体也提高了变异分辨率，避免在全局最优解附近徘徊，提高了算法收敛速度。 最后，应当指出，染色体长度的改变不会使个体适应性改变，因此它不影响选择（轮盘赌选择）。 算法描述 由于基本遗传算法没有在全局优化时收敛，而遗传算法保留了当前一代的最佳个体，我 们的方法采用这项策略。在进化过程中，我们跟踪到当代个体平均适应度的累计值。它被写成： 1GX(t) = favg(t) Gt=1其中G是当前进化的一代，favg是个体的平均

37、适应度。 当累计平均适用性增加到最初个体平均适应度的k ( k 1, k R) 倍，我们将染色体长度变为其自身的m (m 是一个正整数) 倍，然后减小交叉和变异的概率，可以提高个体分辨率、减少搜索步骤以及提高算法收敛速度。算法的执行步骤如下： 第一步：初始化群体，并计算个体平均适应度favg0，然后设置改变参数的标志flag。flag设为1.第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异，并计算当代个体的累积平均适应度favg favg0第三步：如果 favgk 且flag = 1，把染色体的长度增加至自身的m倍，减少交叉和变异概率，并设置flag等于0;否则继续进化。 第四步：

38、如果满足结束条件，停止；否则转自第二步。 测试和分析 我们采用以下两种方法来测试我们的方法，和只保留最佳个体的遗传算法进行比较： f1(x,y)=0.5-sin2x2+y2-0.51+0.01x+y(222) -5,5 x,y -1,1 f2(x,y)=4-(x2+2y2-0.3cos(3x)-0.4cos(4y) x,y收敛的分析 在功能测试中，我们进行了以下政策：轮盘赌选择，单点交叉，位变异。种群的规 模是60。L是染色体长度，Pc和Pm分别是交叉概率和变异概率。我们随机选择4个遗传算法所保留的最佳个体来与我们的方法进行比较，它们具有不同的固定染色体长度和交叉和变异的概率。表1给出了在10

39、0次测试的平均收敛代。 在我们的方法中，我们采取的初始参数是l0 = 10，Pc0 = 0.3，Pm0 = 0.1和k = 1.2，当满足改变参数的条件时，我们调整参数l = 30，Pc = 0.1，Pm = 0.01。 1.1 在线和离线性能的分析 Dejong提出了遗传算法的定量评价方法，包括在线和离线性能评价。前者测试动态性能，而后者评估收敛性能。为了更好地分析测试功能的在线和离线性能，我们把个体的适应性乘以10，并f1和f2分别给出了4 000和1 000代的曲线： (a) 在线 (b) 离线 图1 f1的在线与离线性能 (a) 在线 (b) 离线 从图1和图2可以看出，我们方法的在线

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

41、父基因位点没有变化，基因位点1到k上的基因改变了。 在交叉过程中，1到k基因位点上的基因改变的概率为0.5(“1”变化”0”或者”0”变为”1”)，因此，交叉之后，基因位点上的染色体搜索步骤从1到k的数学期望是 k11b-a1b-aEck(x)=wj=l2j-1=l(2k-1) 22-12-1j=12j=121此外，每个位点的染色体发生交叉的概率是相等的，即lPc。交叉后，染色 k体搜索步骤的数学期望是 1Ec(x)=PcEck(x)k=1l 把Eq.( A1)替换为Eq.( A2)，我们得到 l-1Pb-aP(b-a)11b-a1Pcl(2k-1)=cl(2i-1)-l=c(1-l) l22

42、l2l2-12-12-1k=1lb-a0， 所以Ec(x)Pc 其中l是非常大的，l2l2-1Ec(x)=l-1图1 单点交叉 定理4 位变异的染色体搜索步骤的数学期望是 Em(x)=(b-a)Pm 其中Pm是变异概率。 证明： 每个基因位点上的基因的变异概率是相等的，比如Pm，因此变异搜索步骤的数学期望是： Em(x)=Pmwi=Pmi=1i=1ll b-ai-1b-a2=P(2i-1)=(b-a)Pmmli2-12-1 机器人算法外文翻译 机器人外文翻译 爬墙机器人外文翻译 智能机器人外文翻译 外文翻译 樱桃收获机器人 管道机器人外文翻译（优秀） 工业机器人的发展外文翻译 屋顶清扫机器人外文翻译 机器人及机器人传感技术(毕业论文外文翻译). 外文翻译六自由度机器人