对较好和较差个体双向更新的混合蛙跳算法

庞凯立，梁昔明

(北京建筑大学 理学院，北京 100044)

对较好和较差个体双向更新的混合蛙跳算法

庞凯立，梁昔明

(北京建筑大学 理学院，北京 100044)

针对基本蛙跳算法在处理复杂函数优化问题时求解精度低且易陷入局部最优的缺点，将共轭梯度法引入基本蛙跳算法，对排名靠前的p个模因组中的精英个体和排名靠后的q个模因组中的落后个体同时使用共轭梯度法进行更新，一方面增强对较差青蛙的指导能力，另一方面使最差的青蛙直接更新，提高了算法的收敛精度. 所得混合蛙跳算法有效结合了基本蛙跳算法较强的全局搜索能力和共轭梯度法快速精确的局部搜索能力. 将所得的混合蛙跳算法与其他智能优化算法进行对比，数值试验结果表明，无论从收敛精度还是进化代数而言，所得混合蛙跳算法较其他算法均有较大的改进，具有更高的收敛精度，能有效避免陷入局部最优，且优化结果更加稳定.

混合蛙跳算法； 共轭梯度法； 数值试验； 适应度函数

基本蛙跳算法[1]是一种新的基于群体智能的启发式算法，该算法是在2003年由Eusuff和Lansey受青蛙进食行为的启发进行建模和仿真研究的结果，该算法结合了粒子群算法和模因算法两者的优点，具有结构简单、收敛速度快和全局寻优能力强等特点.

基本蛙跳算法与其他群体迭代算法一样，虽然具有较强的全局搜索能力，但是易陷入局部最优，且收敛精度不高. 为此，学者们进行了深入的研究，提出了一些改进算法，也都取得了不错的效果. 文献[2]对子群中每只青蛙个体引入了随机扰动，并让子群内每只青蛙个体都参与产生新个体，充分利用每只青蛙个体的信息，增加了种群多样性. 文献[3]引入全局共享因子和局部共享因子，由于共享因子随着迭代次数的增加而增大，使得在局部搜索初期，较小的共享因子初值能减弱最优个体对最差个体的指导，避免了青蛙个体更新步长过大而跳过局部最优；在进化后期，共享因子增大，增强了最优个体对最差个体的指导，使得个体跳过局部最优实现全局收敛，该算法动态改变最优个体对最差个体的指导能力，使得青蛙个体更容易跳出局部最优实现全局收敛. 文献[4]基于量子理论提出一种量子混合蛙跳算法，该算法采用量子位的Bloch球面坐标编码个体，利用量子位在Bloch球面上绕轴旋转的方法更新个体，通过自适应混沌旋转角度算子提高子群内部局部搜索能力，采用Hadamard门实现个体变异避免早熟，有效扩展了空间的搜索范围. 文献[5]定义了新的粒子分类标准，将所有青蛙按此标准进行分类，青蛙个体在迭代过程中根据自身状态动态调整惯性权重，并以停滞代数判断是否对最优个体进行优化，避免了陷入局部最优.

以上文献中的改进算法都较好地改善了基本SFLA算法，在克服种群陷入局部最优缺陷的基础上增加了种群多样性. 考虑到传统优化算法—共轭梯度法具有较强的局部搜索能力，而现代智能优化算法—基本蛙跳算法收敛精度不高，寻找一种方法将蛙跳算法与共轭梯度法结合起来从而凸显各自的优点显得尤为重要，且历来很少有学者将传统优化方法与基本蛙跳算法结合起来研究. 本文提出的对较好和较差个体进行更新的混合蛙跳算法(SFLA_HH)，充分利用了SFLA算法和共轭梯度法两者的优点，弥补了两者的不足，将SFLA_HH算法与其他智能优化算法进行对比，对五个测试问题的试验结果表明，SFLA_HH算法收敛精度更高.

1 基本蛙跳算法与共轭梯度法分析

对无约束连续优化问题：

minf(x)，x∈Rd

(1)

若x*∈Rd满足：

f(x*)≤f(x)，∀x∈Rd

(2)

则称x*为f(x)在全空间Rd上的全局最小点或整体极小点.

1.1 SFLA原理

SFLA算法将每个个体看做池塘中的一只青蛙[6]，搜索区间即为整个池塘.SFLA算法首先在寻优区间内随机初始化一组向量来组成青蛙的初始种群[7]P={X1,X2,…,Xi,…,XF}(i=1,2,…,F)，第i只青蛙为Xi=(xi1,xi2,…,xid)，每一只青蛙代表一个待选解，xij为第i只青蛙第j维的分量. 对于每个青蛙个体，计算适应度函数值fit(Xi)，本文中适应度函数取为目标函数，然后将所有青蛙个体按照它们的适应度值进行升序排列，并分别放入m个模因组中. 设Mk为第k个模因组青蛙的集合(k=1,2,…,m)，表达式如下：

Mk={Xk+m(l-1)∈P|1≤k≤m;1≤l≤n}

(3)

式中，n为每个模因组中的青蛙的个数.

青蛙移动的距离向量：

(4)

更新最差青蛙位置：

(5)

(6)

(7)

1.2 共轭梯度法

共轭梯度法[8]是由Hestenes和Stiefel( 1952)提出来的，是一种介于最速下降法和牛顿法之间的经典非线性无约束优化算法，它的基本思想是根据迭代点处的负梯度方向构造出一组共轭方向，再沿着这组方向搜索目标函数极值，共轭梯度法的机制保证了所得到的这组共轭方向就是函数值的下降方向. 共轭梯度法最大的优势在于同时解决了最速下降法收敛慢和牛顿法对目标函数要求较高且计算量大的不足，具有较好的局部搜索能力，是求解大型非线性无约束最优化问题的有效算法之一，其求解流程如下：

步骤4令Xk+1=Xk+tkPk；

步骤6计算共轭方向Pk+1，令k=k+1并转步骤3.

2 嵌入共轭梯度法的混合蛙跳算法

考虑到基本蛙跳算法中精英个体更新效率较低、较差个体更新效果不明显等缺陷导致的进化后期易陷入局部最优这一缺点，本文提出在基本蛙跳算法中引入共轭梯度法，对前p个模因组中的精英个体和后q个模因组中的落后个体直接进行更新，一方面增强了对较差个体的指导能力，另一方面提高了最差个体的更新效率. SFLA_HH算法首先对种群和参数进行初始化，各青蛙的初始位置在给定搜索区间内随机生成；然后计算每只青蛙的适应度函数值，对函数值进行升值排序. 本文中适应度函数取为目标函数，故函数值越小代表点的位置越好，由此得到Xg；然后将排完序后的青蛙按照式(3)划分模因组，找到每个模因组中的Xb和Xw，对模因组中的前p组和后q组与共轭梯度法进行结合，具体更新规则为：前p组以Xb为初始点，即X0=Xb，初始搜索方向P0取为-g(Xb)，根据X1=X0+tP0对Xb进行更新，其中步长t根据：

(8)

求解. 如果X1满足给定的精度要求，则跳出共轭梯度法循环，否则，按下式：

Xk+1=Xk+tPk

(9)

(10)

进行下一点的迭代，重复计算直至达到给定的精度要求或次数，更新Xb，再按照式(4)、式(5)指导更新Xw；将排列在中间的的(m-p-q)个模因组按照式(5)、式(7)进行更新；将排列在最后的q个模因组与共轭梯度法结合，以Xw为初始点，初始搜索方向P0取为-g(Xw)，再按照上面的式(8)、式(9)、式(10)对Xw进行更新. 从整体效率来考虑，可以适当放低共轭梯度法的精度要求[9]，并且同时使用精度和循环代数一起作为判断共轭梯度法停止的条件. 当所有模因组的局部更新操作都完成后，判断是否达到全局搜索次数，若满足，则输出当前最好解，即为全局最优解；否则，将全部青蛙混合，重复进行下一轮搜索. SFLA_HH算法流程如下：

步骤1随机初始化F只青蛙，最大蛙跳步长为Smax，模因组数为m，每个模因组中的青蛙数为n，局部迭代次数为L，整体迭代次数为G；

步骤2计算所有青蛙适应度函数值；

步骤3将青蛙按照适应度函数值从小到大排序，适应度函数值最小的青蛙记为Xg；

步骤4青蛙种群根据分组规则按照(3)式划分为m个模因组；分别记下每个模因组中的Xb和Xw；

步骤5对前p个模因组结合共轭梯度法，以模因组中Xb为初始点进行循环迭代r次或达到精度要求，更新Xb，再按照式(4)、式(5)指导更新Xw；对中间的(m-p-q)个模因组按照式(5)、式(7)进行局部搜索L次，更新Xw；对剩余的q个模因组以Xw为初始点行进行循环迭代r次或达到精度要求，更新Xw；

步骤6当局部搜索全部完成后，判断是否达到全局混合迭代次数G，若满足，则输出当前最好解，即为全局最优解；否则，将全部青蛙混合，返回步骤3进行下一轮搜索.

因为共轭梯度法对于一个n元正定二次目标函数最多n次就可以寻得最优解，可见共轭梯度法的寻优效率之高. 由于共轭梯度法的运算涉及到梯度计算，运算过程中调用共轭梯度法的次数越多，耗时越久，在本文中共轭梯度法的运算次数与两个因素有关，一是结合共轭梯度法的组数，二是共轭梯度法的内部终止迭代次数r. 为了整体寻优速度，本试验调用共轭梯度法的次数不宜太多，故只选取前两组和后两组，即p=q=2.

共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题，因此混合蛙跳算法SFLA_HH对较高维数的函数优化具有较大的优势.

3 实验结果与分析

为验证混合蛙跳算法SFLA_HH的寻优效果和稳定性，将SFLA_HH算法与基本SFLA算法在不同维度下进行试验. 为了进一步验证文中所提出的混合蛙跳算法的优越性，将SFLA_HH与SFLA、文献[2]中提出的内嵌扰动变异的混合蛙跳算法(DVSFLA)、文献[10]中提出的自适应粒子群优化算法(APSO)以及文献[11]中提出的强化学习的人工蜂群算法(GABC)分别在30维时固定全局迭代次数情况下进行对比分析. 又将SFLA_HH与文献[5]中基于新搜索策略的混合蛙跳算法(NSSFLA)在固定精度情况下进行对比分析. 三种情况对比均使用表1中5个典型的无约束优化问题进行数值试验，各问题的目标函数表达式、搜索范围和理论最优值如表1所示[12]，其中D为问题的维度.

函数f1为Sphere单峰函数，全局最小点是(0,0,…,0)；函数f2为Rastrigin函数，函数f3为Griewank函数，函数f4为Ackley函数，都是多峰函数，有很多局部极小点，全局最小点是(0,0,…,0)；函数f5为Rosenbrock函数，是非凸的病态函数，在极小值附近有陡峭的峡谷，用SFLA求解时很容易陷入局部极值，它的全局最小点是(1,1,…,1). 为了进一步比较各种算法的性能，并减少偶然性的影响，本文采用Matlab R2014b试验平台进行数值试验，并对每个测试问题进行30次独立试验，取试验所得的平均最优值、标准差进行对比. 其中，平均最优值为30次试验中每次求得的全局最优解相加除以30；标准差即为30次试验中全局最优解的标准差.

本文所选取的试验参数如下，其余对比算法参数设置见对应文献：

青蛙个体数F=200;

族群数m=20;

族群内青蛙个数n=10;

局部循环迭代次数L=10;

全局循环迭代次数G=200;

青蛙最大移动步长设置规则根据文献[13]，即：

Smax=可行域的界×45%；

p=2；q=2；r=5；eps=1e-2.

表2为将SFLA_HH算法与基本SFLA算法在不同维度下进行试验的结果对比.

表2 两种算法在不同维度下对比

由表2中对比结果可以看出，在不同试验维度下，无论是解的质量还是算法的稳定性，SFLA_HH算法较SFLA算法均有较大提高. 对于五个测试问题，SFLA算法均未找到最优解，且随着维数增高，SFLA寻优效果也越来越差，而SFLA_HH算法都找到了最优解，并且解的精度在维数变化较大的情况下保持一定的稳定性. 对于问题f1，f2，f3，SFLA_HH算法在三种维度下都找到了理论最优解，

SFLA求解精度较差，且未找到最优解；对于问题f4，f5，SFLA_HH算法也都找到了最优解，SFLA算法求解效果较差，且未找到最优解.

表3为30维时SFLA_HH与其他现代智能优化算法在固定全局迭代次数情况下结果对比.

表4为SFLA_HH与基本蛙跳算法及文献[5]中NSSFLA算法在固定精度情况下结果对比.

表3 SFLA_HH与新近知名智能优化算法寻优结果对比

从表3对比结果中可以看出，SFLA_HH算法与其他算法相比有明显的优势，对于五个测试问题都找到了最优解，其中对于f1，f2，f3都找到了理论最优解；SFLA算法对于所有的问题均未找到最优解；DVSFLA只对f1找到了最优解；APSO和GABC对于f1，f2和f4均找到了最优解，但求解精度都不如SFLA_HH，可见SFLA_HH的寻优精度之高.

从表4可以看出，SFLA对于所有问题都没能达到指定的精度，NSSFLA和SFLA_HH都达到了指定精度；对于f2，NSSFLA和SFLA_HH进化代数没有太大差异；对于f3，SFLA_HH比NSSFLA效果略差；但对于f1和f5，SFLA_HH只需一次就可以达到指定精度，比NSSFLA所需次数少，对于f4，NSSFLA最少需要17次才可以达到指定精度，而SFLA_HH最少只需11次就可以达到指定精度，且平均次数也比NSSFLA少.

表4 固定目标精度下30次试验结果对比

综上，SFLA_HH收敛精度和平均进化代数均优于基本蛙跳算法和其他几种智能优化算法.

4 结论

共轭梯度法是经典无约束优化算法，由于采用梯度信息，因此可以较快的收敛到函数极小值；基本蛙跳算法在搜索区间广泛随机采点，然后从各点出发，依据青蛙觅食原理搜寻全局最小点，因而具有较好的全局搜索能力. 本文所提出的SFLA_HH算法正是结合了两者的优点，对于排列在前面位置较好的模因组和后面位置较差的模因组均引入共轭梯度法，不仅加强了对最差青蛙个体的指导能力，更提高了最差青蛙的更新效率，进而提高了算法的收敛精度. 改进算法无论从收敛精度、进化代数还是稳定性方面都有较大的优越性，但仍存在一些问题，由于共轭梯度法每次循环都需要计算梯度信息，故对于有些复杂问题，或者非凸问题无法很好地解决，这也是需要改进的地方.

[1] 崔文华，刘晓冰，王伟,等.混合蛙跳算法研究综述[J]. 控制与决策，2012，4(3)：481-486

[2] 季骏，戴月明，吴定会.内嵌扰动变异的混合蛙跳算法[J].计算机工程与应用，2015，51(12)：27-30

[3] 刘立群，王联国，韩俊英,等.基于全局共享因子的混合蛙跳算法[J].计算机工程，2013，39(10)：162-166

[4] 张强，李盼池.量子混合蛙跳算法求解连续空间优化问题[J].吉林大学学报：理学版，2013，51(3)：471-477

[5] 赵芳，张桂珠.基于新搜索策略的混合蛙跳算法[J].计算机应用与软件，2015，32(8)：224-228

[6] 杨淑莹，张桦.群体智能与仿生计算—Matlab技术实现[M].北京：电子工业出版社，2012：167-176

[7] 马鲁，陈国初，王海群.蛙跳算法及其在函数优化中的应用[J].上海电机学院学报，2014，17(2)：68-75

[8] 孙文瑜，徐成贤，朱德通.最优化方法[M].北京：高等教育出版社，2010：125-137

[9] 梁昔明，李德生.嵌入共轭梯度法的混合粒子群优化算法[J].小型微型计算机系统，2014，35(4)：835-839

[10] Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man, and Cybernetics—Part B: Cybernetics, 2009,39(6): 1362-1381

[11] Zhu Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173

[12] Meng Jia-na, Lin Hong-fei. Transfer learning based on graph ranking[C]∥Proc. Of the 9th International Conference on Fuzzy Systems and Knowledge Discovery. [S.1.]: IEEE Press, 2012

[13] Eusuff M, Lansey K, Pasha F. Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization [J]. Engineering Optimization, 2006, 38(2): 129-154

[责任编辑：佟启巾]

Hybrid SFLA Algorithm with the Bidirectional Updates of Elite and Behind Individuals

Pang Kaili，Liang Ximing

(School of Science, Beijing University of Civil Engineering and Architecture, Beijing 100044)

A kind of hybrid Shuffled Frog Leaping Algorithm (SFLA) coupling with conjugate gradient method is proposed to solve the problem of low solution precision and easy to fall into local optimal solutions under basic SFLA. The elite individuals in the frontpmeme groups and the behind individuals in the lastqmeme groups are selected to search the solution with conjugate gradient method, which enhance the ability to guide the poor frogs in one hand, and in another hand update the worst frogs directly, and improve the convergence accuracy. The proposed hybrid SFLA algorithm combines the strongly global searing ability of SFLA with the fast local searching ability of conjugate gradient method. Comparisons among the hybrid SFLA and other well-known intelligent algorithms are made and the numerical experiment results show that, in terms of convergence or evolutionary generation, the improvements have been achieved greatly in the hybrid SFLA. The improved algorithm has a higher convergent precision, more stable optimal results, and better ability to jump out local optimal solution than other well-known intelligent algorithms.

shuffled frog leaping algorithm; conjugate gradient method; numerical experiment; fitness function

2016-07-09

国家自然科学基金(61463009)；北京市自然科学基金项目(4122022)；中央支持地方科研创新团队项目(PXM2013- 014210- 000173).

庞凯立(1990—)，女，硕士研究生，研究方向； 智能优化算法.

1004-6011(2016)04-0052-06

TP301.6

A