0 引言

Rashedi教授于2009年提出的引力搜索算法^[1](Gravitational Search Algorithm, GSA)目前已应用到系统辨识、参数优化、模式分类、动态优化、智能决策等^[2-6]领域.文献[1]的研究表明, 与粒子群优化算法、遗传算法等其他仿生算法相比, GSA具有很强的全局搜索能力与较快的收敛速度, 但也容易发生算法早熟、算法运行效率偏低. GSA在迭代初期寻优速度较慢, 并对个体的初始位置具有一定的依赖性.分析其原因是因为每次迭代都要计算寻优个体间的引力和(惯性质量、空间距离、引力常数等)来确定个体的寻优轨迹, 导致寻优初期个体更新计算量较大; 而在寻优后期若个体视野内没有更优个体时, 则个体更新操作相当于在周围进行随机运动, 进而降低了寻优效率和收敛速度.目前已在如何保持种群多样性^[7-8]、与其他智能算法进行融合^[9]、个体更新方式^[10-11]和变异^[12-13]等方面提出了一些改进方法.文献[7-8]提出了分子群的方式改进GSA的性能; 文献[9]采用粒子群算法的思想使得个体具有记忆功能, 且在速度更新公式中引入了个体最优位置和全局最优位置, 但仍需计算原有的引力和, 并增加了一些计算量; 文献[10-11]将差分变异策略引入到个体位置更新, 所不同的是文献[10]通过阈值统计学习的方式, 在进化过程中根据两种策略在先前学习代数的成功率, 自适应地选择较优策略生成下一代群体, 保证了种群在解空间中的探索与开发能力之间的平衡, 但是算法引入的学习代数与阈值的选取对算法的性能具有一定的影响; 而文献[11]是取两种策略所获最优位置, 但不管何种策略都表明用差分变异策略可以改进GSA的寻优效果; 文献[12]以预定的概率来选择变异的个体, 并通过高斯分布来确定个体的新位置, 通过动态的改变变异概率来加快算法收敛速度; 文献[13]利用反向学习策略进行种群初始化, 并提出精英策略和边界变异策略来提高个体的探索能力和开发能力.基于上述文献的算法改进思路, 本文基于分子群、个体更新方式和变异等方面提出了一种基于动态分组的多策略引力搜索算法(Multi-Strategy Gravitational Search Algorithm Based On Dynamic Grouping, MS-GSA):首先采用佳点集算法初始个体位置, 利用动态分组策略对所有个体进行分组进化寻优, 每个分组内只更新最优个体和最差个体; 在算法寻优后期将所有个体分成优势子群和拓展子群, 利用差分变异算子进化优势子群提高寻优精度和速度, 利用Tent混沌算子进化拓展子群完成个体变异避免陷入局部最优解.

1 基本引力搜索算法(GSA)

GSA将所有优化个体当作有质量的物体能够做无阻力运动.每个个体会受到解空间中其他个体的万有引力的影响, 并产生加速度向质量更大的个体运动.个体间通过万有引力的相互作用来实现优化信息的共享.下面以最小值为例对GSA进行描述.

(1) 随机产生初始个体位置, 计算个体适应值, 依据个体适应值计算惯性质量$M_i (t)$, 计算公式为

$ \begin{equation} \label{eq1} \left\{ {\begin{array}{l} m_i (t)=\dfrac{{\rm {fit}}_i (t)-{\rm {worst}}(t)}{{\rm {best}}(t)-{\rm {worst}(t)}}, \\[4mm] M_i (t)=\dfrac{m_i (t)}{\sum\limits_{j=1}^N {m_j (t)} }, i=1, 2, \cdots, N, \\ \end{array}} \right. \end{equation} $

(1)

其中, fit$_i (t)$表示个体$x_i $第$t$次迭代的适应值, best$(t)$表示第$t$次迭代的最佳解, worst$(t)$表示第$t$次迭代的最差解.

(2) 计算引力常数$G(t)$和计算空间距离$R_{ij} (t)$, 计算公式分别为

$ \begin{equation} \label{eq2} G(t)=G_0 {\rm {e}}^{-\alpha \frac{t}{T}}, \end{equation} $

(2)

$ \begin{equation} \label{eq3} R_{ij} (t)=\left\| {x_i (t), x_j (t)} \right\|_2, \end{equation} $

(3)

其中, $G_0 $、$\alpha $为常数, $T$为最大迭代次数, $R_{ij} (t)$表示个体$i$和个体$j$的欧氏距离.

(3) 计算在第$t$次迭代, 个体$i$在第$d$维与个体$j$之间的引力, 计算公式为

$ \begin{equation} \label{eq4} F_{ij}^d (t)=G(t)\times \frac{M_j (t)\times M_i (t)}{R_{ij} (t)+\varepsilon }(x_j^d (t)-x_i^d (t)), \end{equation} $

(4)

其中, $M_i (t)$和$M_j (t)$为个体$i$和个体$j$的惯性质量, $\varepsilon $为一个很小的常量, $G(t)$表示第$t$次迭代的引力常数, $R_{ij} (t)$为个体$i$和个体$j$间的空间距离.

(4) 在第$t$次迭代, 第$d$维上作用于个体$x_i $的作用力总和等于其他所有个体对其作用力之和, 当个体$x_i $受到其他个体的引力作用后就会产生加速度.计算个体$i$在第$d$维所受的合力$F_i^d (t)$和加速度$a_i^d (t)$, 计算公式为

$ \left\{ \begin{array}{l} F_i^d(t) = \sum\limits_{j = 1,j \ne i}^N {{\rm{rand}}() \times F_{ij}^d(t)} ,\\ a_i^d(t) = \frac{{F_i^d(t)}}{{{M_i}(t)}}, \end{array} \right. $

(5)

其中, rand$()$为$[0, 1]$上的随机数.

(5) 最后在第$t$次迭代, 个体$i$根据计算得到的加速度更新速度和位置, 更新公式为

$ \left\{ \begin{array}{l} V_i^d (t+1)={\rm {rand}}()\times V_i^d (t)+a_i^d (t), \\ X_i^d (t+1)=X_i^d (t)+V_i^d (t+1). \end{array} \right. $

(6)

GSA的标准版本算法如下所示.

2 动态分组多策略引力搜索算法原理 2.1 基于佳点集理论的种群初始化

寻优个体的初始位置在一定程度上影响着寻优性能.个体多样性越多则找到最优解的几率也越大, 若有某些个体就在最优解周围, 则有利于加速算法收敛和提高寻优性能.故本文算法的个体采用佳点集算法进行初始化.佳点集理论^[14-16]已证明近似计算函数在$s$维欧氏空间单位立方体上的积分时, 用$n$个佳点构成的加权和比采用任何其他$n$个点所得到的误差都要小.具体定义如下.

设$G_s $是$s$维欧氏空间中的单位立方体, 如果$r\in G_s $, 形为$p_n (k)=\big\{ (\{ {r_1 ^{(n)}\times k} \}, $ $\{ {r_2 ^{(n)}\times k} \}, \cdots, \{ {r_s ^{(n)}\times k} \}), 1\le k\le n \big\}$, 其偏差$\varphi (n)$满足$\varphi (n)=C(r, \varepsilon )n^{-1+\varepsilon }$, 其中$C(r, \varepsilon )$是只与$r$和$\varepsilon (\varepsilon >0)$相关的常数, 则称$p_n (k)$为佳点集.佳点$r=\left\{ {2\cos (2{\pi }k/p), 1\le k\le s} \right\}$, 其中, $p$是满足$(p-s)/2\ge s$的最小素数.

2.2 算法进化初期自适应分组策略

从GSA的运行原理和部分函数极值优化结果可知, 虽然算法在进化初期寻优速度较慢, 但在后期具有较强的开发能力.故为了发挥GSA的优势, 提升迭代初期的寻优速度, 本文提出了一种动态分组策略来增加种群多样性和提高寻优速度, 动态分组原理如下.

(1) 对所有个体按适应度降序排列, 并划分成$m$个子群, 每个子群包含$n$个个体.

(2) 将前面第1到第$m$个个体依次分到$m$个子群, 则第$m+1$个个体分到第1个子群.

(3) 令$\alpha _i^t (x)={\rm {e}}_i^t (x)/\sum\limits_{i=1}^m {{\rm {e}}_i^t (x)}, i\in (1, \cdots, m)$, 其中${\rm {e}}_i^t (x)$为第$t$次迭代后的方差, ${\rm {e}}_i^t (x)$越小表明子群内个体离散度越小.若存在$\alpha _i^t (x)$相对其他子群的$\alpha _k^t (x), k\in (1, \cdots, i-1, i+1, \cdots, m)$较小, 则表明该子群内的个体或已发现最优解, 或已陷入局部最优, 则$m=m-1$, 将该子群的个体分配到其他子群.

(4) 若各个子群内的$a_t^t(x)$相差不大, 则说明动态分组寻优效果不明显, 此时将所有个体分为两个子群:一个以当代最优个体为中心的优势种群来提高寻优精度和速度; 一个以当代最差个体为中心的拓展子群来避免陷入局部最优.两个子群在完成内部迭代进化后再重新分组交换信息.

(5) 考虑到GSA每次迭代都要计算个体间的距离$R_{ij} (t)$, 所以可以利用$R_{ij} (t)$来把优化个体分为两个子群:距离最优个体近的个体划分到优势子群; 距离最差个体近的个体划分到拓展子群.

(6) 考虑到会存在总的进化周期较短, 造成后期进化策略还未运行的可能性, 所以需设置一个迭代比例因子$\lambda $, 用于控制超过预设迭代次数后划分为两个子群, 进而完成后期的进化策略.

2.3 自适应分组内最优个体的进化方式

GSA的个体更新计算量决定着算法的寻优速度, 可以借鉴混洗蛙跳算法的个体更新方式.在分组内只更新最差个体, 仍采用GSA的更新方式.而最优个体由于所受合力相对较小, 实际上等价于随机移动位置.根据GSA进化原理可知, 每个个体都要计算惯性质量、与其他个体的距离和引力, 进而指导个体更新轨迹.如果将这个计算复杂度用另一种计算方式替代, 产生最优解周围的若干个体, 则既可以保持个体的多样性, 也可以增加获取更优解的概率.社会学研究表明在较优个体周围往往更容易找到更优个体, 可以理解为局部最优解周围往往更易发现更优解.云模型^[17-18]在知识表达时具有不确定中带有确定性、稳定之中又有变化的特点, 体现了自然界物种进化的基本原理.以局部最优个体为中心按云模型理论生成$h$个子个体.生成步骤如下.

步骤(1):针对每个分组内的最优个体, 以其作为期望$Ex$代表子个体的搜索中心.

步骤(2):计算每个分组的适应度方差作为熵$En$来改变搜索范围.

步骤(3):用超熵$He$来控制生成个体的离散度.令$He=En/\lambda $, 动态改变$\lambda =\lambda _{\max } -(\lambda _{\max } -\lambda _{\min } )\times \frac{t}{T}$, 使得在进化初期加大随机性, 在进化后期加强稳定性, 其中$\lambda _{\max } $和$\lambda _{\min } $为$\lambda $的取值区间($\lambda \in [3, 10])$, $t$为当前子群内迭代数, $T$为子群内总迭代数.

步骤(4):利用正态云模型算法根据步骤(1)到步骤(3)确定的$C(Ex, En, He)$生成$h$个云滴(子个体), 若发现比分组内最优个体更好的子个体则代替.

2.4 进化后期双子群进化原理

智能进化算法在寻优后期既要增加收敛速度和求解精度, 又要尽量避免陷入局部最优解, GSA也不例外.算法在寻优后期要么已在全局最优解附近, 要么陷入局部最优解.故本文算法利用优势子群来加速寻优效率, 利用拓展子群来避免陷入局部最优, 两个子群在各自经过指定次数的迭代后再重新分成两个子群.

2.4.1 优势子群内个体更新方式

差分进化算法是一种简单且高效的智能优化算法, 算法中的变异操作在很大程度上影响着寻优性能^[19-21].采用差分进化算法的变异操作来更新优势子群内的个体, 公式为

$ \begin{equation} \label{eq7} X_i^d (t+1)=X_i^d (t)+F_i \times (X_b^d (t)-X_r^d (t)), \end{equation} $

(7)

其中, 选择最优个体作为$X_b $和随机个体$X_r (r$是不同于被更新个体的随机整数), $F_i $表示缩放因子.如果$X_b $与$X_r $的适应度相差较小, 则说明它们位置很近, 此时为防止扰动量过小$F_i $应选择较大值; 反之, 如果$X_b $与$X_r $的适应度相差较大, 为限制扰动量过大则应选择较小值.确定公式

$ \begin{equation} \label{eq8} F_i =F_u -(F_u -F_l )\times \frac{f_b }{f_r }, \end{equation} $

(8)

其中, $F_u $、$F_l $分别为$F_i $的上限和下限, $f_r$、$f_b $分别为个体$X_r $和$X_b $的适应度.

2.4.2 拓展子群的个体进化方式

对于拓展子群的个体先采用GSA的原有个体更新策略生成新个体, 发挥GSA较强的开发能力.如果新个体没有产生更好的适应度, 则采用混沌映射完成个体变异操作. Tent混沌映射^[22-23]所产生的混沌序列具有对初值不敏感、全局遍历性, 且分布较为均匀, 其数学表达式为

$ \begin{equation} \label{eq9} X_{i+1}^d =\left\{ {\begin{array}{l} 2\times X_i^d, \;\;\;0\le X_i^d \le \dfrac {1}{2}, \\ 2\times (1-X_i^d ), \;\;\;\dfrac {1}{2}\le X_i^d \le 1. \\ \end{array}} \right. \end{equation} $

(9)

对于[0, 1]之间的浮点数, Tent映射经过Bernoulli移位变换后, 在计算机中进行映射时只需要将小数部分的二进制数进行无符号左移, 这种特性更适合计算机进行大数量级数据序列的运算处理.

2.5 算法流程

从分析MS-GSA的算法原理可知, 在不考虑种群初始化的时间复杂度情况下, MS-GSA在自适应分组策略、双子群分组及进化方式上增加了计算量.但由于经典GSA在实现过程中已完成适应度的排序和个体间距离的计算, 所以进化初期的动态分组和后期的双子群分组的复杂度并没有增加.故MS-GSA实际的计算开销主要增加在第2.3节和公式(7)、公式(9).针对第2.3节的复杂度, 其本质是利用云模型进行启发式计算, 在云滴个数确定的情况下相当于增加若干个个体, 这些计算量相对于GSA的最优个体计算与其他个体间的距离、引力合力和加速度及最后的位置更新的计算量要小很多, 实际上是减少了GSA最优个体的计算量, 同时每个分组里只更新最差个体.所以总体上自适应分组策略的计算量要远远少于经典GSA.而公式(7)只针对优势子群的个体之间利用子群内个体的位置进行更新, 公式(9)的变异操作也只是极小部分个体, 相对于其GSA原有的个体更新方式计算量要少.故依据算法复杂性渐进性理论可知本文的MS-GSA没有增加GSA的复杂度, 而且还减少了原有算法的计算量.

3 实验仿真

实验仿真环境为: Windows 7操作系统; Intel酷睿i5处理器; 主频2.5 Hz, 4 G内存; 开发工具为Matlab.针对8个函数极值求解问题如表 1所示, 将本文所提算法(MS-GSA)与文献[1]的引力搜索算法(GSA)、文献[19]的差分进化算法(Differential Evolution Algorithm, DE)、文献[11]的DE-GSA(Hybrid Differential Evolution and Gravitation Search Algorithm)和文献[12]的QGSA(Gravitational Search Algorithm Based on Gaussian Mutation)进行寻优性能对比.本文的多种策略主要涉及动态分组、优势种群的差分变异和拓展子群的Tent混沌映射; 文献[11]将差分变异和GSA改进的进化方式进行混合寻优, 在一定程度上可与本文无动态分组策略的算法相对比; 而文献[12]主要采用高斯变异策略改进, 可以与本文的Tent混沌映射相对比.从众多的变异改进算法结果可知, 单一的不同变异策略对改进算法的性能差距各有优劣.故本文算法与文献[11]的算法和文献[12]的算法进行对比, 可以认为这3种主要策略的协作使得本文算法的寻优效果具有一定的优越性, 故它们之间的对比可以等价于这些策略具体功用的实验证明.

3.1 固定迭代次数和精度的性能测试

种群规模全都设定为50, 8个函数的维数为$n=30$, 5种算法分别独立运行20次, 收敛精度为10E-12. DE参数设置参照文献[19], 交叉概率$CR=0.9$, 缩放因子$F=0.5$; GSA参数设置参照文献[1], $G_0 =100, \alpha =20$; DE-GSA参数设置参照文献[11]; QGSA参数设置参照文献[12], 最大迭代次数设置为1 000; MS-GSA的参数设置为$G_0 ={1}00, \alpha =20$.分组个数为5, 分组内迭代次数为10、分组合并系数$\lambda =1/4$, 算法总迭代次数为100.针对每一个优化函数, 5种进化算法的优化结果对比如表 2至表 9所示.

从本节的仿真结果可知, 本文的动态分组多策略引力搜索算法具有很好的寻优精度和速度.这是由于GSA的进化原理计算相对复杂, 其中每个个体要计算与其他个体间的距离和引力和, 故其运行时间较多.本文的MS-GSA减少了原有算法的计算量, 同时利用小生镜的方式进行寻优可以保持群体中个体的多样性, 并且本文的分组策略主要基于适应值的排序结果, 故不增加算法的额外计算量, 同时在迭代过程中利用分组内个体的方差来判定离散程度, 进而在进化过程中不断减少分组个数, 这样既有利于前期进行全局寻优, 又可以在后期进行局部精细挖掘和增加收敛速度, 并且在分组内只更新最优个体和最差个体进而减少了算法的计算量, 加快了收敛速度; 同时MS-GSA采用佳点集理论初始化个体增加了个体靠近最优解的几率, 在进化过程中云模型的稳定倾向性和随机性既利于使个体向周围更优个体自适应定位, 又利于保护个体的多样性, 所以采用云模型更新最优个体加强了最优个体进化的确定性并保持了随机多样性, 进而提高了算法的寻优速率和性能, 有效地改善了GSA在求解一些高维复杂函数时求解精度不高、收敛速率慢的缺点.

3.2 高维函数上的优化性能测试

对于函数$f_1, f_2, f_3, f_4 $进行维度为$N=100$, $N=200$来对比MS-GSA与DE、GSA的性能.各类算法的运行参数设置见第3.1节, 收敛精度为10E-6, 函数在每个算法中独立运行20次, 对比结果如表 10所示.

从高维函数测试的优化效果可知, 随着维度的增加, GSA的运行时间增加幅度较大, 主要是由于维数的增加需要计算的个体质量、个体间的距离、个体间的引力合力和加速度也大大增加, 造成求解速度和精度下降, 而MS-GSA利用小生镜技术和差分变异算子的优势大大改进了经典GSA的不足, 同时加速了寻优速度和精度, 尤其是在高维函数寻优性能的稳定性上得到了很大的改进.由于实验设定迭代次数为1 000, 造成DE和GSA的表现性能不是很好, 通过进一步增加迭代次数发现, 这两种算法的寻优结果也会得到改善, 这也说明本文所提算法在较短的迭代周期内能获得较好的寻优速度和精度.

4 结论

本文给出了基于动态分组的多策略引力搜索算法(MS-GSA).该算法基于动态分组技术将云模型算法、差分变异算法和混沌算法引入到个体更新过程中, 有效地改进了GSA迭代初期较大的计算量, 加速了迭代初期寻优速度, 加强了算法后期的逃逸能力, 使其快速定位到最优解区域.研究结果表明将各种算法的优势有机地融合在一起, 有利于拓宽算法的研究范围和应用领域, 也为智能进化算法的研究进行了新的探索和尝试.由于本文算法在求解高维优化问题的较好性能, 可尝试将其用于去解决工业控制、机器学习、神经网络等领域的一些高维优化问题.