基于动态分组的多策略引力搜索算法

张强 王梅

摘要：给出了一种基于动态分组的多策略引力搜索算法.算法迭代初期利用自适应分组策略对种群进行分组寻优，每个分组内只更新最差个体，采用云模型理论来改进最优个体的进化行为;迭代后期将种群分为优势子群和拓展子群，采用差分变异算子更新优势子群提高寻优精度和速度，利用Tent混沌理论进化拓展子群完成个体变异.典型复杂函数测试表明，该算法具有很好的收敛精度和计算速度.

关键词：引力搜索算法;云模型;佳点集;混沌;连续空间优化

中图分类号：TP 301.6 文献标志码：A DOI：10.3969/j.issn.1000-5641.2019.01.08

0引言

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

1基本引力搜索算法（GSA）

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

（1）随机产生初始个体位置，计算个体适应值，依据个体适应值计算惯性质量Mi（t），计算公式为

2动态分组多策略引力搜索算法原理

2.1基于佳点集理论的种群初始化

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

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

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

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

步骤（1）：针对每个分组内的最优个体，以其作为期望Ex代表子个体的搜索中心.

步骤（2）：计算每个分组的适应度方差作为熵En来改变搜索范围.

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

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

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

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

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

2.5算法流程步骤1：设定种群规模、分组个数m、最大迭代数T、分组内迭代数和最小收敛精度，

采用第2.1节的方法初始寻优个体.

步骤2：根据第2.2节对种群里的个体进行分组，根据第2.3节对个体进行更新.

步骤3：如果未满足结束条件，且分组内的迭代次数达到指定次数和分组个数m不为2，则执行步骤2.

步骤4：若m等于2，采用第2.4节的方法进化后期的双子群个体寻优行为.

步驟5：若满足收敛精度或达到最大迭代数则退出，否则执行步骤4.

从分析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所示，将本文所提算法fMS-GSA）与文献的引力搜索算法（GSA）、文献的差分进化算法（Differential Evolution Algorithm，DE）、文献的DE-GSA（Hybrid Differential Evolution and Gravitation Search Algo—rithm）和文献的QGSA（Gravitational Search Algorithm Based on Gaussian Mutation）进行寻优性能对比.本文的多种策略主要涉及动态分组、优势种群的差分变异和拓展子群的Tent混沌映射;文献将差分变异和GSA改进的进化方式进行混合寻优，在一定程度上可与本文无动态分组策略的算法相对比;而文献主要采用高斯变异策略改进，可以与本文的Tent混沌映射相对比.从众多的变异改进算法结果可知，单一的不同变异策略对改进算法的性能差距各有优劣.故本文算法与文献的算法和文献的算法进行对比，可以认为这3种主要策略的协作使得本文算法的寻优效果具有一定的优越性，故它们之间的对比可以等价于这些策略具体功用的实验证明.

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

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

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

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

4结论

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