自适应混沌变异的万有引力搜索算法

罗　萍，刘　伟，周述波

(广东工业大学 应用数学学院，广东 广州 510520)



自适应混沌变异的万有引力搜索算法

罗萍，刘伟，周述波

(广东工业大学 应用数学学院，广东 广州 510520)

摘要:通过引入平均粒距和混沌搜索变异，提高万有引力算法的局部搜索能力,增加物质种群的多样性.并且对变异后不可行的物质采用边界变异约束处理.实验结果表明,新算法收敛精度较高,收敛速度较快,能比较有效地避免早熟收敛问题.

关键词:万有引力算法； 混沌； 平均粒距； 边界变异

万有引力算法(GSA)[1]在2009年首次由Rashedi等人提出，其思想是基于物理学中宇宙间的万有引力定律和运动规律而得出的.基于万有引力算法的优化算法得到广泛关注.受“分裂”思想的启发, S.Sarafrazi等[2]提出一种具有分裂功能的万有引力算法.徐怀祥等[3]引入一个变异算子使算法跳出局部最优，给出了一种改进的万有引力算法.谷文祥等[4]将万有引力算法运用于解决流水线的调度问题. 为解决非线性的极大极小值问题，马良等[5]提出一种新的混沌万有引力算法，对当前的最优位置利用混沌优化进行比较细密的搜索. Nihan Kazak和Alpaslan Duysak针对标准引力算法的收敛速度比较慢的缺点，提出了成员卫星算法[6]，每个物质都有各自的几个卫星，卫星和成员的同步进化，保证了此算法在当代最优值周围的更为精细的搜索. 为提高引力算法的局部收敛能力，一些学者将引力算法与其他算法结合，提出了许多的混合引力算法[7-10]. Zahir[11]提出的模糊万有引力算法 ，给出了数据挖掘的新途径.许多学者通过引入各种变异算子[12-15]，增加物质种群的多样性，提高算法的搜索效率.

上述算法都存在收敛速度慢,求解精度低等问题.针对这些问题,本文提出了一种根据平均粒距大小来判断算法收敛程度,对物质群中的最优位置和最差位置进行自适应混沌变异的万有引力算法，保持和提高函数求解精度，同时提高算法的收敛速度.该算法的主要思想是在进化的过程中引入平均粒距，如果平均粒距大于给定值，说明算法处于初期，则对最差物质的位置进行混沌变异，加快算法收敛速度.如果平均粒距小于或者等于给定值，即算法处于中后期，陷入局部最优时，则在最优物质的附近进行混沌变异，增加物质种群的多样性，跳出局部收敛.如果变异产生出来的新的物质优于当前的最优物质，则替换原有的最优物质继续进化.测试函数的实验结果表明了该算法的有效性.

1改进的引力算法

1.1标准万有引力算法

在GSA算法模型中，优化问题的每个解与搜索空间中的一个物质相对应，每个物质都有4个特点：位置、施力物、受力物、惯性质量，而物质的位置就是优化问题的解.标准GSA的算法过程如下：

首先利用式(1)和式(2)计算出每个物质的惯性质量Mi(t).

(1)

(2)

其中valuei(t)表示物质i在第t代的适应值，xbest(t)(t)，xworst(t)分别表示第t代种群中最好和最坏的适应值.

万有引力常量定义为

(3)

其中，G0是一个初始值，α为一个常数，t是当前代数，T是最大的迭代次数.对于求最小值问题xbest(t),xworst(t)的定义为

xbest(t)=minj={1,2,3,…,N}valuej(t)，

xworst(t)=maxj={1,2,3…,N}valuej(t).

(4)

其次，计算各个物质在每一维间上相互之间的引力.物质j对物质i作用的第d维万有引力定义为

(5)

其中，ε是一个极小的值，Rij(t)表示物质i和物质j之间的欧氏距离，由此可得出物质i在第d维所受到的合力为

(6)

Randj为介于0和1之间的随机数，Kbest从K0到1随着时间线性减小，使得算法到最后在搜索空间中只有最好的解的那个物质去作用于其他的物质.

然后根据牛顿运动规律，计算出在时间t时物质i在第d维的加速度为

(7)

最后物质的速度和位置更新为

(8)

其中，randi为0和1之间的随机数，它可使搜索变得随机化.

1.2群体的平均粒距

由于在标准GSA算法进程中，物质种群是根据追随种群最优位置进行更新的，所以这种算法在运行过程中，如果某物质找到了一个当前最优位置，则其他物质会迅速向这个最优位置聚集. 如果这个最优位置是一个局部最优点，万有引力算法就无法在解空间内重新搜索，出现停滞或早熟收敛现象.

试验证明，GSA中无论是全局收敛还是早熟收敛，万有引力算法中的物质都会有 “聚集”的现象，此时非常缺乏种群的多样性.种群多样性的缺乏是导致过早收敛以及停滞现象的重要原因.

(9)

平均粒距说明了在单位搜索空间上物质的分布情况，描述了种群中各个物质间彼此相互分布的离散程度，D(t)越小，表示种群越集中.即可能陷入局部收敛.

1.3混沌变异

混沌指在一个确定的系统中发生的不规则的运动，行为主要表现为随机性、规律性、 遍历性.由于执行简单并且能够有效避免陷入局部极值，因此混沌搜索已成为一种新的局部搜索技术.

本文引入Logistic混沌方程，其表达式为

xi+1=αxi(1-xi)，i=1,2…N，α=4.0.

(10)

由于GSA算法本身的局限性使得标准的引力算法比较容易陷入局部最优，而混沌的遍历性、不重复性，可以在一定的搜索空间内跳出局部收敛，因此在GSA算法中引入混沌搜索，获得全局最优解就成为可能.自适应混沌变异GSA算法的主要思想是在标准GSA算法的基础上，引入平均粒矩，当平均粒距小于或等于给定值时，算法陷入早熟收敛状态,对最优物质进行混沌搜索，引导物质快速跳出局部最优，避免陷入早熟收敛.当物质的平均粒距大于给定值时，对最差物质进行混沌搜索，产生一个优于最差物质的位置,来替换最差物质，加快算法收敛速度.

当算法的平均粒距大于给定值d0时，即在算法初期,对最差物质的位置由下式变异更新.

xi(t)=αxworst(t)(1-xworst(t)),

(11)

当算法的平均粒距小于或等于给定值d0时，此时算法出现早熟收敛，对最优物质的位置由下式变异更新.

xj(t)=αxbest(t)(1-xbest(t)),

(12)

1.4越界处理

考虑到本文中的变异方法可能产生一些越界的物质，对越界物质采用边界变异的方式进行处理.

ifx(p)

x(p)=x_min

endif

ifx(p)>x_max

x(p)=x_max

endif

其中x_max和x_min为物质在第p维位置的上下界，x(p)为变异后物质第p维的位置.

1.5算法步骤

本文算法主要步骤如下.

步骤1：设定算法参数,包括种群平均粒距给定值d0等,在解空间随机初始化N个物质的位置和速度.

步骤2：计算物质的函数适应值valuei(t).

步骤3：利用式(3)～(4)计算更新每个物质的xworst(t)和xbest(t).

步骤4：利用式(9)计算群体的平均粒距D(t).

步骤7：利用式(1)、(2)计算每个物质的质量Mi(t).

步骤9：根据式(7)、(8)计算物质的加速度，速度以及更新种群中物质的位置.

步骤10：如果达到了结束的条件,最大迭代次数或者更新的位置足够好，则迭代结束，否则返回步骤2.

2数值实验结果及分析

2.1测试函数与条件

为验证改进后算法的有效性，本文选择了5个标准的测试函数与标准万有引力算法(SGSA)和混沌万有引力算法(CGSA)作比较，如表1所示.本文改进后的算法简称ACGSA.5个测试函数中f1～f3为单模测试函数,f4～f5为多模测试函数.在实验中,种群规模N=30,最大迭代次数T=50,平均粒距给定值d0=0.003,万有引力常量初值G0=100,最大速度v_max=[3,3,3],最小速度v_min=[-3,-3,-3],K0=100.表2为3种算法独立运行50次,得到的最优值(BSF),最优值的平均值(ABSF)以及最优值的标准方差(STDBSF)的比较结果.

表1　测试函数

表2　计算结果

2.2实验结果分析

对于单峰函数f1～f3,由图1可以发现在这3种算法中ACGSA均能准确且快速地找到函数的最优解.同时从表2的数据结果来看,ACGSA算法搜索到的最优值精度都比SGSA和CGSA高.由标准方差来看,ACGSA算法的稳定性也是最好的.

图1　f1～f5的进化曲线

对于多峰函数f4～f5,其他两种算法都快速地陷入局部最优,出现停滞现象，而ACGSA由于引入混沌搜索,算法的局部和全局搜索能力的调整更为灵活，提高了搜索过程的效率，又增加了种群的多样性,使算法继续在解空间搜索，逐步收敛到精度更高的全局最优值.同时表2中3种算法的标准方差的比较结果也反映出该算法在处理多峰问题时具有较好的稳定性.这说明随着问题复杂程度的增加,ACGSA的优化效果没有减弱.

3结语

本文给出一种自适应的混沌变异万有引力优化算法(ACGSA算法).该算法在运行的前期可以经过变异，加快算法收敛速度；在算法运行的后期可以跳出局部收敛，增加种群的多样性，并在全局最优区域进行较为细密的搜索.本文算法搜索速度和收敛精度比标准 GSA 算法及CGSA算法有较大提高，并且能够以更快的速度找到全局最优解.

参考文献：

[1]RASHEDI E,NEZAMABADI-POUR H, SARYAZDI S.GSA:a gravitational search algoritm[J].Information Sciences, 2009, 179(13):2232-2248.

[2] SARAFRAZI S, NEZAMABADI-POUR H, SARYAZDI S.Disruption: a new operator in gravitational search algorithm[J].Scientia Iranica D, 2011, 18(3):539-548.

[3] 徐怀祥，刘伟.基于最优变异的万有引力算法[J].广东工业大学学报, 2014, 31(1):46-50.

XU H X, LIU W.The gravitational algorithm based on the optimal mutation[J].Journal of Guangdong University of Technology, 2014, 31(1):46-50.

[4] 谷文祥，李向涛，朱磊，等.求解求解流水线调度问题的万有引力收索算法[J].智能系统学报,2010,5(5):411-418.

GU W X,LI X T,ZHU L,et al.A gravitationnal search algorithm for slow shop scheduling[J].CAAI Transactions on Intelligent System,2010,5(5):411-418.

[5] 刘勇,马良.非线性极大极小问题的混沌万有引力搜索算法求解[J].计算机应用研究,2012, 29(1):47-48.

LIU Y, MA L.Solving nonlinear minimax problems based on chaos gravitional search algorithm[J].Application Research of Computers, 2012, 29(1):47-48.

[6] KAZAK N, DUYSAK A.Modified gravitational search algorithm[C]∥ Innovations in Intelligent Systems and Applications, International Symposium on. Turkey:IEEE,2012:1589-1597.

[7] MIRJALILI S,HASHIM S Z M.A New Hybrid PSOGSA Algorithm for Function Optimization[C]∥ Computer and Information Application (ICCIA), 2010 International Conference on.Tianjin:IEEE,2010:374-377.

[8] 蒋悦,沈冬梅,赵彦,等.基于引力搜索和分布估计的混合离散优化算法[J].计算机应用.2014,34(7):2074-2079.

JIANG Y,SHEN D M,ZHAO Y,et al.Hybrid discrete optimization algorithm based on gravity search and estimate of distribution[J].Journal of Computer Application，2014,34(7):2074-2079.

[9] 徐耀群,王长举.一种万有引力算法及其收敛性分析[J].哈尔滨商业大学学报(自然版).2013,29(1):63-67.

XU Y Q,WANG C J.Universal gravitation optimization and its convergence analysis[J].Journal of Harbin University of Commerce(Natural Sciences Edition)，2013,29(1):63-67.

[10]谷文祥,郭丽萍,殷明浩.模糊c-均值算法和万有引力算法求解模糊聚类问题[J].智能系统学报，2011,6(6):520-524.

GU W X,GUO L P,YIN M H.A solution for a fuzzy clustering problem by applying fuzzy c-means algorithm and gravitational search algorithm[J].CAAI Transactions on Intelligent Systems,2011,6(6):520-524.

[11] ZAHIRI S H.Fuzzy gravitational search algorithm an approch for data mining[J].Iranian Journal of Fuzzy Systems,2012,9(1),21-37.

[12] 徐遥,安亚静,王士同.基于三角范数的引力搜索算法分析[J].计算机科学,2011,38(11):225-229.

Xu Y, AN Y J,WANG S T.Analyzing of gravitational search algorithm based on triangular norms[J].Computer Science,2011,38(11):225-229.

[13] SOLEIMANPOUR-MOGHADAM M, NEZAMABADI-POUR H.An improved quantum behaved gravitational search algorithm[C]∥ Electrical Engineering (ICEE), 2012 20th Iranian Conference on. Tehran:IEEE,2012:711-714.

[14] 张维平,任雪飞,李国强,等.改进的万有引力搜索算法在函数优化中的应用[J].计算机应用,2013,33(5):1317-1320.

ZHANG W P, REN X F,LI G Q,et al.Improved gravitation search algorithm and its application to function optimization[J].Journal of Computer Application,2013,33(5):1317-1320.

[15] 袁建涛,周慧,郭陈江,等.基于改进引力搜索算法的阵列天线波束赋形[J].微波学报,2014,30(3):50-53.

YUAN J T,ZHOU H,GUO C J,et al.Beam shaping for antenna based on improved gravitational search algorithm[J].Journal of Microwaves,2014,30(3):50-53.

Gravitational Search Algorithm of Adaptive Chaos Mutation

Luo Ping, Liu Wei, Zhou Shu-bo

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:This paper proposes a gravitational search algorithm of adaptive chaos mutation. By introducing the average distance and the chaotic search variation, this paper improves local search ability of gravity algorithm, increases the diversity of substance population and treats the unfeasible materials after mutation by boundary variation constraint. The results show that the new algorithm has the advantages of high precision and fast rate in convergence which can effectively avoid premature convergence. And the variation of the material after not feasible material treated by boundary variationconstraint.

Key words:gravitational search algorithm; chaos; average particle distance; boundary mutation

中图分类号:TP301.6

文献标志码:A

文章编号:1007-7162(2016)01- 0057- 05

doi:10.3969/j.issn.1007- 7162.2016.01.011

作者简介:罗萍(1987-)，女，硕士研究生，主要研究方向为智能计算及其应用.

基金项目:国家自然科学基金资助项目(60974077)

收稿日期:2014- 09- 23