《空间收缩粒子群优化.doc》由会员分享，可在线阅读，更多相关《空间收缩粒子群优化.doc（16页珍藏版）》请在三一文库上搜索。
1、Space Contraction Particle Swarm Optimization空间收缩粒子群优化 Xu Liyan, Shen Jihong, and Zhu LeiScience School of Harbin Engineering University,学校:哈尔滨工程大学150001,Harbin, Chinafxuliyan, shenjihong, Abstract. This paper presents a new hybrid technique for particle swarm optimization (PSO)by introduction of th
2、e space contraction mechanism.摘录。本文介绍了一种新的粒子群优化( PSO )的混合技术,阐述了空间收缩机制。The influence of important parameters to the performance of the optimizer is studied through five well-known benchmark functions.影响性能的重要参数,优化研究通过五个著名的基准功能. To evaluate its reliability and efficiency for multimodal function optimiz
3、ation, we numerically analyze the performance of our approach compared with some classical approaches.以评估其可靠性和效率,为多式联运功能优化 我们通过分析数值的方法,与一些经典方法相比较. The results obtained in experiments on benchmark test functions indicate that the proposed algorithm is competitive with others, and can be successfully
4、applied to more demanding problem domains.结果在实验基准测试函数表明,提出的算法与经典的相比较，能成功地应用到更急需解决的问题范畴. 1 Introduction1 介绍Since its introduction in 1995, numerous variations of the basic algorithm proposed in the literature have improved the performance in varying degrees2-6.自其于1995年推出，无数改善的变异基本算法在文献上发表,表现在不同程度 2-6
5、 . A general problem with PSO is that, it converges rapidly during the initial stages of a search, but often slows considerably and can get trapped in local optima.粒子群优化( PSO )的混合技术的一般问题是,它在初始阶段能快速的收敛进行搜索, 但往往到后期就大大放慢,也可能陷入局部最优. This paper presents a new hybrid approach of PSO, by introduction of th
6、e space contraction mechanism7, to speed up convergence and escape local optima.本文提出一种新的混合粒子,通过引入空间收缩机制7，为了加快收敛和逃脱局部极值. The selection of parameters problem is studied and the performance of the proposed approach is examined numerically and experimentally.参数的选取问题,是研究和表现的方法是检验数值和实验研究. Experimental res
7、ults on several benchmark test functions show that this is a very promising way to speed up convergence and enhance the quality of solutions, especially for complex functions of multi-dimension.实验结果在几个基准测试功能显示这是一个很有希望的方法,以加快收敛提高质量的办法,特别是面对功能复杂的多维情况. 2 Principle of the Particle Swarm Optimization2原理的
8、粒子群优化 The PSO approach utilizes a cooperative swarm of particles, where each particle represents a candidate solution, to explore the space of possible solutions to an optimization problem.假设粒子群优化( PSO )的混合技术方法使用一种合作群颗粒,即每个颗粒都是候选人的方法, 用于解决探索的空间的优化问题. Each particle is randomly or heuristically initia
9、lized and then flies in a N-dimensional search space.每个颗粒是随机或启发式初始化,然后飞跃,在一个N维搜索空间. At each step of the optimization, each particle is allowed to evaluate its own fitness and the fitness of its neighboring particles.在每一步的优化, 每个粒子可以评估自己的适切性和适当周边粒子. Each particle can keep track of its own solution, wh
10、ich resulted in the best fitness, as well as see the candidate solution for the best performing particle in its neighborhood.每个粒子可以跟踪自己的解决方案,其结果是在最佳适切地方以及在其邻近的地方选择表现最佳的粒子.The ith particle is represented as Xi = (xil, xi2, . , xiD). The best previous position (the position giving the best fitness val
11、ue) of the ith particle is recorded and represented as Pi = (pil, pi2, . , piD).均值颗粒是作为Xi=(xil ， xi 2,.。 , xiD). 最佳先前的立场(立场给予最好的最适合价值)的带状粒子记录, Pi=(pil ， pi 2,.。 , piD). The best particle among all the particles in the population is indexed by g.在众多所有的粒子之中的最好粒子会被 g 编入索引。The velocity (rate of the posi
12、tion change) of particle i is represented as Vi.粒子 i 的速度 (位置的比率改变) 表现就如 Vi 。At each optimization step, indexed by k, each particle, indexed by i, adjusts its flying according to the following iterative equations,在每一步优化,检索用K ,每个粒子,检索了i, 调整其飞行按照下列迭代方程 Where c1 and c2 are positive constants, r and R ar
13、e uniform random variables distributed over 0,1.而C1和C2是正面的常数, R和R是均匀随机变量的分布0,1 . Constants c1 and c2 determine the relative influence of the social and cognition components.常数C1和C2确定相对的影响粒子群和他们的认知成分. The parameter w, introduced as an inertia factor, can dynamically adjust the velocity over time, gra
14、dually focusing the PSO into a local search23.该参数W ,引入了惯性因子,可动态调整的速度随着时间的推移, 逐步集中的PSO到当地搜索2 3 . The equation (1) is used to calculate the particles new velocity according to its previous velocity and the distances of its current position from its own best experience (position) and the groups best ex
15、perience.方程( 1 )是用来计算颗粒的新的速度,根据其以往的速度和距离其当前的位置,从自己的最佳经验(位置) ,以及该组合的最佳体验. Then the particle flies toward a new positionaccording to equation (2).然后粒子飞跃推向一个新的位置,根据公式( 2 ) . The performance of each particle is measured according to a predefined fitness function, which is related to the problem to be so
16、lved.表现每个粒子测量按照预定最适合功能 这是相关的问题有待解决. A constant, Vmax, was used to arbitrarily limit the velocities of the particles and improve the resolution of the search.恒定的速度最大值Vmax ,被用来限制任意颗粒速度和提高了分辨率的搜寻. Another approach, called the constriction factor approach, was suggested by Clerc.另一种办法是Clerc提出的,称为收缩因子的方式
17、. Its update equation for velocity is as follows:其更新方程速度如下: In the formula above, K is named as constriction factor, which enhances the convergent ratio of the algorithm.在上述公式, K是命名为收缩因子,提高了收敛率的算法. Carlisle and Doziert investigated the influence of different parameters in PSO, selected c1=2.8, c2=1.
18、3, population size as 30, and proposed the Canonical PSO5.Carlisle and Doziert调查的影响,不同的参数值的,选定的C1 = 2.8, C2 =1.3 ,种群规模为30 , 并提出了典型的PSO 5 . 3 Our Proposed Algorithm3我们的算法 3.1 Background of Space Contraction Mechanics3.1背景空间收缩力学 Space contraction mechanism is a kind of method which utilizes the fine a
19、pproximate solutions provided by the evolution algorithm at a certain step to locate the new search space so as to achieve efficient search.空间收缩机制,是一种利用优良的近似解提供了进化算法 某一步寻找新的搜索空间,以实现高效率的搜索的方法. Usually it requires combining with the incomplete evolution strategy.通常它需要结合完整的演进策略. For most of evolutionar
20、y algorithms, the fitness of individuals improves quickly at the beginning running, but when it reaches a certain iteration step when the individuals scatter around the peaks of the solutions, it improves less after this.大多数进化算法,个别合适的在开始运行就很快地运转起来,但是,当它到达某一步迭代时,个人散布各地峰的解决方案, 相比以前的速度提高了. So a method
21、to end up the algorithm at this step is called as incomplete evolution strategy.这么一种下场算法在这一步被称为完整的演进策略. Repeated incomplete evolution can provide enough fine solutions for the space contraction.反复不全演化能提供足够细解空间的收缩. Some scholars have done the research using space contraction mechanics to improve the
22、ability of search for some algorithm7.一些学者也做了研究,利用空间收缩力学提高搜索能力,为某些算法7 .However, such technique has not yet been found in the particle swarm optimization algorithm.但是,这种技术尚未发现的最实用的粒子群优化算法. 3.2 Space Contraction Particle Swarm Optimization3.2空间收缩粒子群优化 As the PSO running, the search velocity of particl
23、es slow down, thus it causes loss of the diversity of the swarm, which results into premature convergent.由于粒子运行后,搜索速度粒子减速,由此引发的损失是多种多样的群,其中结果导致转化过早收敛. This paper is intended to introduce the space contraction mechanics to PSO by combining the incomplete evolution for the canonical PSO and space cont
24、raction mechanics for the search space together, to enhance the convergent ratio and the quality of solutions.本文旨在介绍我国空间收缩力学粒子组合而成的完整的演化为典型 PSO和空间收缩力学的搜索空间在一起, 以提高收敛率和质量的办法. This approach isolates the PSO evolution process and space contraction process when the evolution step is equal to a certain n
25、umber, named as contraction period, until the global optima are found (it means convergent successfully), or the maximal step predefined (it means failure to convergence).这种方法分离粒子的演化过程和空间收缩过程中,当进化步骤是恒等于某个数字时,命名为收缩时期,直到全球最优发现(这意味着收敛成功) , 或最大一步预定(这意味着失败衔接) . At each contraction of space, the search sp
26、ace is contracted with the elite particle as the center and a certain length as the radius(called as contraction radius), then particles with bad fitness are eliminated, and meanwhile the same number of random particles are given in the new space in order to maintain the size of the swarm unchanged.
27、每次收缩的空间, 搜索空间包括以精英粒子为中心,在某一长度为半径(称为 收缩半径) ,然后不合适的颗粒被淘汰, 而与此同时,同样数目的随机粒子登陆于新的空间以维持使该群的大小不变. Contraction radius is the difference between the supremum and infimum of components of all elements in the contracted space.收缩半径之间的上确界和下确界组件的所有元素包含的空间.Because the contracted space for current step is determine
28、d by the elite in the previous step, the value of the contraction radius (denoted as r(k) for the kth time) is given by iterative equation(4).因为包含的空间的前一步,是由精英在过去所走的,半径收缩的价值(简称为R ( k )的第k次)是由迭代公式( 4 ) . Where the constant a (0 a 1) is called as contraction ratio, whose value implies the amplitude of
29、the space contraction.而常数a (0 a 1)被称为收缩比率，其价值意味着振幅的空间收缩. Where fi(k) is a logical decision function to decide whether do the space contraction or not, the value is given by the following equation.如fi( K )的一个逻辑决策功能,以决定是否做空间收缩, 该值由下列公式计算. The search space, as equation(5) shows, should be contracted on
30、ly when the iteration step k equal to the predefined step (contraction period) p.搜索空间,因为方程( 5 )显示, 应签约只有一步迭代k相当于预定步骤(收缩期)p.According to the thought that the current search space is decided by the previous elite, the current contracted space must be a neighborhood of the previous best particle g, den
31、oted the search space at kth step as k据以为目前的搜索空间,是由以前的精英, 目前承包空间必须邻上届最佳颗粒G号 ,在KTH细心搜索空间 k这一步中，这就是：Where g(k) represents the position of elite at the kth time.如果G ( k )在KTH时间里代表的立场. According to the strategy of eliminating bad particles, the particles outside search space for next step are eliminated
32、, and the same number particles are distributed randomly inside k+1.根据这项战略,消除不良粒子以外寻找空间,为下一步被淘汰, 和同样数目的粒子是随机分布内k+1时. Maybe some particles change their own trajectories.也许有些颗粒改变自己的轨迹. Supposing the number of particle changing their trajectories is N, so the velocity update equation and position updat
33、e equation for the space contraction process are as follows:倘使人数粒子改变其轨迹为N , 所以更新速度方程和位置更新方程的空间收缩的过程如下: Where rand(-1, 1) and rand(0, 1) are random numbers uniformly distributed in range -1,1 and 0; 1 respectively.边缘(-1,1 )和边缘( 0 ,1 )随机数均匀地分布在距离-1,1和0 , 1 . The contraction ratio and contraction perio
34、d are two important parameters in our approach.收缩率和收缩时期两个重要参数的方法. Contraction ratio can adjust the amplitude of the space contraction and the contraction period can adjust the frequency of the space contraction.收缩率,可以有效地调节振幅的空间收缩和收缩时期,可以有效地调节频率的影响 空间收缩. Both parameters should be in a suitable range,
35、 otherwise,it will be not helpful to enhance the performance of the PSO algorithm.这两个参数应在一个合适的范围内, 否则,将不利于提高PSO效率的算法. 4 Experimental Design and Results4实验设计及结果 4.1 Benchmark Functions and Experimental Design4.1基准功能和实验设计 The benchmark functions on which the proposed algorithm has been tested and comp
36、ared to other approaches in the literature, as well as the equations and the corresponding parameters are listed in the table189.基准的功能,该算法已经过测试,相对于其他方式,在文献上 以及方程和相应的参数列于表8 9 . To avoid the influence of different initial swarms and make unbiased comparisons,we implement 100 experiments for each test
37、and the maximum iteration step of PSO is set to be 1000(MaxIter), swarm size is 30. Parameters used in other PSO approaches are loyal to the related literature346.为了避免影响不同初始蜂涌而作出公正的比较,我们实施100个试点,每个测试和 最大迭代步几秒定为1000 ( maxiter ) ,群大小为30 . 参数用于其他PSO的办法是忠于相关文献3 4 6 . All algorithms are programmed in Mat
38、lab 6.5 and the simulations are executed on a Pentium IV 2.8G with memory capacity of 512 MB under Windows XP Professional Operating System.所有算法程序在Matlab 6.5和仿真运行在一台Pentium 4 2.8内存容量 512MB在Windows XP专业版操作系统. In our experiments the terminative condition is在我们的实验中的终止条件是： Where GM represents the theore
39、tical optimum of each function ,err represents the acceptable error.在改造思想的理论适合每个功能,犯错的范围是可以接受的误差之内. 4.2 Experiments and Results for Parameters Selection4.2实验结果和参数选择 To analyze the influence of the contraction ratio and contraction period to the performance of our present approach, the changing situa
40、tions of performance are studied by changing the contraction ratio within 0.20.9 range and contraction period within 10150 ranges respectively, with other parameters unchanged.分析影响的收缩率和收缩时期的表现,我们目前的做法, 转变的情况下性能的影响改变了收缩率在0.20.9射程和收缩时期,在10150射程分别同其他参数不变. To evaluate the average convergent ratio, the a
41、verage optima, the average CPU time for each 100 implementations for different contraction ratios and contraction periods respectively.评价平均收敛比率,平均极值, 平均CPU时间为每100实现不同收缩率和收缩时期. Performances for different contraction ratios are shown in Fig.1Fig.3, and those for different periods are shown in Fig.4Fig
42、.6.演出不同收缩比率列Fig.1Fig.3,而这些不同时期列于Fig.4Fig.6. Fig. 1. mean convergent ratios in various contraction ratios1 . 平均收敛比率,在不同收缩比率Fig. 2. average optima in various contraction ratios2 . 平均最优各种收缩比率 From Fig.1Fig.3, we can see, the performances of our proposed approach are best when the contraction ratio is a
43、t 0.55.从Fig.1Fig.3,我们可以看到, 演示中,我们建议的做法是最好的收缩比是0.55 . Comprehensive consideration the performance indicators shown in Fig.4Fig.6, we believe that the contraction period as 130 are appropriate.综合考虑性能指标列Fig.4Fig.6,我们认为收缩时期为130是否合适. Through these figures we also know, both parameters influence the indic
44、ators for Rosenbrock function greatly.透过这些数字,我们也知道,这两个指标的影响程度为指标的Rosenbrock函数极大. 3. average CPU time in various contraction ratios3 . 平均CPU时间,在不同收缩比率 FIG.4. mean convergence ratios in various contraction periodsFIG.4 . 平均收敛比率在各时期收缩 5. average optima in various contraction periods5 . 平均最优解在各个时期收缩 6.
45、mean convergence ratios in various contraction periods6 . 平均收敛比率在各时期收缩 4.3 Comparison of Performance Indicators4.3性能的比较指标 The average convergent ratio, average optima and total CPU time for each test are listed in Table 1 and Table 2, from which we can see that the overall performance of our algorit
46、hm is apparently superior to other 3 algorithms taken from the literature in terms of average convergent ratio, average optima and total CPU time as well.平均收敛比率, 平均最优,总CPU时间每次试验列于表1 ,表2 由此我们可以看到,整体表现的算法明显优于其它3算法采取 从文学的平均收敛比率,平均最优,总CPU时间等. Figure 7 shows the evolution process of 30-D Rosenbrock funct
47、ion for different approaches, and figure 8 shows the situation of 2-D Schaffer F6 function, which is another representative test function (the bold line marked SC is related to our approach).图7显示的演变过程, 30至D的Rosenbrock函数进行了不同的做法, 图8显示的情况,二维schaffer F6的功能, 这是另一种代表测试功能(这线段大胆标志着SC ,是不是跟我们的做法) . SC: our proposed methodLDW: Linearly Decreasing inertia Weight method23CFM: Contraction Factor Method45OTS: Method in the literature6SC:我们提出的方法 LDW:线性递减惯性重量法2 3 CFM的:收缩因子法4 5 OTS:在文献67. evolution process for 30-D Rosenbrock function7 . 演化过程为30至D的