基于改进PSO算法的Rosenbrock函数优化问题的研究

摘要/Abstract

摘要： Rosenbrock函数优化属于无约束函数优化问题,其全局极小值位于一条平滑而狭长的抛物线形状的山谷底部,且为优化算法提供的信息很少,因此找到其全局极小值就显得很困难。根据Rosenbrock函数的这种特性,专门提出了一种改进的PSO算法(PSO-R),该算法引入三角函数因子,利用三角函数具有的周期振荡性,使每个粒子获得较强的振荡性,扩大每个粒子的搜索空间,引导粒子向全局极小值附近靠近,避免算法过早地收敛,陷入局部最优,从而找到Rosenbrock函数的全局极小值。大量实验结果表明,该算法具有很好的优化性能,为某些领域某些特定的类似于Rosenbrock函数的优化问题提供了一种新的思路。

关键词: 无约束优化,Rosenbrock函数,粒子群算法,三角函数因子中图法分类号TP18文献标识码A

Abstract: Rosenbrock function optimization belongs to unconstrained optimization problems,and its global minimum value is located in the bottom of a smooth and narrow valley of the parabolic shape．It is very difficult to find the global minimum value because of little information the function optimization algorithm provided．According to the characteristics of the Rosenbrock function,this paper specifically proposed an improved particle swarm optimization(PSO)algorithm(PSO-R)which introduces trigonometric factor with periodic oscillations of trigonometric functions so that each particle gets strong oscillation to expand the search space of each particle and guide particles to close nearly the optimal value and avoid converging prematurely and local optimum,and find the global minimum of the Rosenbrock function．A large number of experimental results show that the algorithm has good performance of function optimization,and provides a new idea for optimization problems similar with the Rosenbrock function for some problems of special fields.

Key words: Unconstrained optimization,Rosenbrock function,PSO algorithm,Trigonometric factor

邵鹏,吴志健. 基于改进PSO算法的Rosenbrock函数优化问题的研究[J]. 计算机科学, 2013, 40(9): 194-197. https://doi.org/

SHAO Peng and WU Zhi-jian. Rosenbrock Function Optimization Based on Improved Particle Swarm Optimization Algorithm[J]. Computer Science, 2013, 40(9): 194-197. https://doi.org/

参考文献

[3] Kennedy J,Eberhart R C.Particle swarm optimization [C]∥Proc of the IEEE Int Conf on Neural Networks．Piscataway,1995:1942-1948
[4] Wang Hui,Wu Zhi-jian,Rahnamayan S,et al．Enhancing particle swarm optimization using generalized opposition-based learning [J]．Information Sciences,2011,181(20):4699-4714
[5] Yang X-S,Deb S.Engineering optimization by cuckoo search[J].Int．J．Math．Modelling Num,Optimization,2010,1(4):330-343
[6] Dixon L C W,Mills D J．Effect of rounding errors on the Variable Metric Method [J].Journal of Optimization Theory and Applications,1994,80(1):175-179
[7] 崔志化,曾建潮.微粒群优化算法[M].北京:科学出版社,2004
[8] 陈入云.高振荡函数积分的高效数值算法及实现研究[D].长沙:中南大学,2009
[9] 中的设置一样,后3种算法参数设置如下:c₁=c₂=1.49618,惯性权重w=0.72984,最大速度V_max=2.0；r₁和r₂为[0,1]之间服从均匀分布的随机数；所有算法中种群大小为40,最大迭代次数为200000,运行次数为30,维数为30；本算法中参数h初始范围为(－∏,∏)(不包括0),其中∏为圆周率,初始值为3.141592653；误差精度为1.27e－7。 4.2 实验结果与性能分析 4.2.1 参数h取值范围为(－∏,∏)的实验 本次实验中,参数的设置如前文所述。PSO-R算法对Rosenbrock函数的优化以及其它5种算法对Rosenbrock函数的优化结果如表1所列。表中最好结果加粗并用下划线标记。表1 6种函数对Rosenbrock函数的优化结果算法平均值标准方差 PSO-W2.93e+0012.51e+001 UPSO1.51e+0018.14e－001 CLPSO2.01e+0012.98e+000 OPSO9.78e+0016.33e+000 GOPSO1.48e+0019.57e－001 PSO-R2.55e－0034.78e－003 参考文献[4,9-12]表明对应的算法对大部分函数的优化性能都很好,但对Rosenbrock函数的优化存在问题,从表1中可以看出,无论是从平均值的角度还是从标准方差的角度来分析,PSO-R算法对Rosenbrock函数的优化性能明显优于其它5种函数对该函数的优化性能。 同时,大量实验表明PSO-R算法的鲁棒性弱,但对于类似于Rosenbrock函数的优化性能相对较好。为了验证该结论,实验中选择两个结构上类似Rosenbrock函数的函数,它们分别为Extended Tridiagonal-1函数和Extended White & Holst函数,其函数形式如式(7)和式(8)所示。 f(x_i)=∑n/2i=1[(x2i－1+x_2i－3)²⁺(x2i－1－x_2i+1)⁴](7) f(x_i)=∑n2i=1[100(x_2i－x³2i－1)²⁺(1－x2i－1)²](8) 式(7)的函数的极值点为(1,2,1,2,…,1,2)T,极小值为0；式(8)的函数的极值点为(1,1,…,1)T,极值点为0。 实验中选择两个代表性的算法(PSO-w算法和GOPSO算法)以及PSO-R算法分别对上述两个函数进行测试,结果如表2所列。表2 不同函数的实验结果函数Extended Tridiagonal-1Extended White & Holst算法平均值标准方差平均值标准方差 PSO-W8.29e+000 3.53e+0007.72e+0003.85e+000 GOPSO9.88e+000 3.77e+0007.51e+0003.81e+000 PSO-R4.27e+000 1．46e+000 5.25e－0026.88e－002 从表2中可以看出,PSO-R算法对两个函数的优化相对来说均好于其它两种算法,且对Extended White & Holst函数的优化性能明显好于Extended Tridiagonal-1函数,这是因为Extended White & Holst函数的结构更类似于Rosenbrock函数。实验结果表明,PSO-R算法虽然鲁棒性弱但对于结构类似于Rosenbrock函数的函数具有较好的优化性能。 4.2.2 参数h的实验分析 在测试函数性能的大量实验中发现,参数h的不同取值对算法的性能有很大的影响。因此,为了测试参数的不同取值对PSO-R算法性能的影响,在(－∏,∏)范围内取9个点,分别为－1.0,1.0,1.5,1.8,2.0,2.5,3.0,3.14,3.141592653。每个h值对应的PSO-R算法对Rosenbrock函数进行优化,运行30次,实验结果如表3所列。表3 不同h值下PSO-R算法的实验结果参数h取值平均值标准方差最好适应值－1.01.81e+0033.31e+0021.18e+003 1.01.87e+0032.39e+0021.41e+003 1.51.08e+0031.66e+0027.22e+002 1.89.34e+0021.68e+0027.08e+002 2.01.00e+0032.78e+0024.96e+002 2.51.80e+0023.13e+0018.59e+001 3.02.90e－0018.71e－0032.64e－001 3.144.58e－0099.13e－0114.33e－009 3.14159260.00.0 从表3中可以看到,随着h取值的不断增大,平均值、标准方差和最好适应值都在不断减小,平均值从1810减至0,标准方差从3310减至0,最好适应值也从1180减至0。实验结果表明,参数h的取值对PSO-R算法的性能有很大的影响。为了使PSO-R算法具有更好的优化性能,分别取h的范围为[3.0,∏)、[3.14,∏)。 在h的取值范围为[3.0,∏)、[3.14,∏)的情况下,分别再次采用PSO-R算法对Rosenbrock函数进行优化,实验结果如表4所列。表4 h在不同取值范围下PSO-R算法的实验结果 h取值范围平均值标准方差最好适应值 (－∏,∏)2.55e－0034.78e－0032.07e－011[3.0,∏)6.90e－0101.20e－0093.28e－016[3.14,∏)8.53e－0221.05e－0211.84e－027 从表4中看到,当h的取值范围从(－∏,∏)压缩到[3.0,∏)时,平均值数量级从10－3到10－10、标准方差从10－3到10－9、最好适应值从10－11到10－16等3个性能评价指标均有大幅提高。进一步压缩范围到[3.14,∏),平均值数量级从10－10到10－22、标准方差从10－9到10－21、最好适应值从10－16到10－27等3个性能评价指标均再次大幅提高,从而表明参数h的范围较精确的定位能够较大幅度提高PSO-R算法的性能。 结合表3和表4还可以看到,当h=3.1415926,却在范围[3.0,∏)内,平均值、标准方差、最好适应值都达到全局极小值0,取得了较好的优化性能,PSO-R算法已经找到了全局极小值。为了不失一般性,PSO-R算法中h取值范围为[3.14,∏)。 另外,从实验中还可以看到,h的取值范围的缩小引导粒子向全局极小值靠近,同时证明了所设计算法的正确性。 结束语鉴于Rosenbrock函数全局极小值位于一条狭长的山谷底部致使许多优化算法很难找到其全局极小值,专门提出了一种改进的PSO算法(PSO-R)。实验研究表明,该改进算法对Rosenbrock函数的优化具有非常好的性能,且为解决类似于该函数的优化问题提供了一种新的思路。该算法对Rosenbrock函数具有很好的优化性能,同时,Rosenbrock函数也证明该算法是一种性能很好的优化算法。然而,该算法也存在不足,即振荡性强度过大可能会导致收敛速度变慢；该算法对于Rosenbrock函数具有很好的优化性能,但鲁棒性弱,对于其它函数的优化性能相对差些,原因是该算法是针对Rosenbrock函数的特性设计的；下一步的研究工作是如何控制算法的振荡强度以及按照算法思想将其推广到所有优化问题。 Rosenbrock H H．An automatic method for finding the greatest or least value of a function [J].Computer Journal,1960,3(3):175-184[3]Kennedy J,Eberhart R C.Particle swarm optimization [C]∥Proc of the IEEE Int Conf on Neural Networks．Piscataway,1995:1942-1948[4]Wang Hui,Wu Zhi-jian,Rahnamayan S,et al．Enhancing particle swarm optimization using generalized opposition-based learning [J]．Information Sciences,2011,181(20):4699-4714[5]Yang X-S,Deb S.Engineering optimization by cuckoo search[J].Int．J．Math．Modelling Num,Optimization,2010,1(4):330-343[6]Dixon L C W,Mills D J．Effect of rounding errors on the Variable Metric Method [J].Journal of Optimization Theory and Applications,1994,80(1):175-179[7]崔志化,曾建潮.微粒群优化算法[M].北京:科学出版社,2004[8]陈入云.高振荡函数积分的高效数值算法及实现研究[D].长沙:中南大学,2009[9]Shi Y,Eberhart R C.A modified particle swarm optimizer [C]∥Proc．Congr．Evol．Comput．1998:69-73
[10] Parsopoulos K E,Vrahatis M N.UPSO-A unified particleswarm optimization scheme [Z].Lect．Ser．Comput．Sci．,2004:868-873
[11] Liang J J,Qin A K,Suganthan P N,et al.Comprehensive lear-ning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Trans．Evolut．Comput,2006,10:281-295
[12] Wang Hui,Liu Yong,Zeng San-you,et al．Opposition-based particle swarm algorithm with Cauchy mutation[C]∥Proc．Congr．Evol．Comput．2007:4750-4756

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed