文章快速检索 高级检索

Shuffled frog-leaping algorithm based on the general center
ZHAO Jia , LYU Li, FAN Tanghuai
School of Information Engineering, Nanchang Institute of Technology, Nanchang 330099, China
Abstract:In this paper, a shuffled frog-leaping algorithm based on general center (GC-SFLA) is proposed to solve the problem of weak information sharing between memeplexes in the shuffled frog leaping algorithm (SFLA) to enhance the learning ability and use the average center of optimal frog. The proposed GC-SFLA generates a virtual general center frog from the optimal frog of each memeplex. Firstly, the optimal frog selects the best location among the original location and general center greedily as new location of new memeplex. After that, the advantage of general center frog is applied to the frog-leaping rule, which enable the worst frog to learn from the general center frog. Experiments are conducted on a set of swarm intelligence algorithms to verify that the new approach outperforms SFLA in different dimensions. The experiment results present promising performance of the GC-SFLA on convergence velocity, precision and stability of solution.
Key words: frog-leaping algorithm     shuffled frog leaping algorithm (SFLA)     general center     frog leaping rule     swarm intelligence algorithms

1 混合蛙跳算法

2 广义中心混合蛙跳算法 2.1 广义中心策略

Pgcf可能会跳出边界[Omin,Omax]成为非可行解，此时，按照式(7)进行重置。

2.2 蛙跳规则的改进

2.3 算法流程

GC-SFLA算法的流程如图 1所示。

 图 1 GC-SFLA算法流程 Fig. 1 Flowchart of GC-SFLA

1)GC-SFLA算法参数设置，包括族群数、族群内更新次数Lmax、族群内青蛙数、混合迭代次数Gmax等的设置。

2)蛙群初始化。初始化蛙群中青蛙位置并评估其适应值，记录蛙群最优蛙为Pg

3)族群初始化。将蛙群分成族群，每个族群包含相同数量的蛙，第k个族群内的最优蛙和最差蛙分别记为PkbPkw

4)广义中心蛙的生成。利用式(6)计算Pgcf并评估其适应值，并根据式(8)更新Pg

5)族群进化。对第k个族群中的Pkw根据式(9)和(2)进行更新并计算其适应度值，若更新后的蛙优于原来的蛙，则取代原来族群中的蛙；如果没有改进，则根据式(10)和(2)进行更新并评估其适应度值，若更新后的蛙优于原来的蛙，则取代原来族群中的蛙；否则根据式(3)随机产生1个新蛙直接取代原来的Pkw；重复上述局部搜索Lmax次。

6)族群混合。将更新后的各族群内蛙重新混合，对更新后的蛙群中的蛙排序，记录更新后的蛙群最优蛙为Pg

7)检验是否满足终止条件，若满足，则停止迭代，输出全局最优粒子位置Pg及其对应的适应值，否则转到步骤2)。

3 仿真实验 3.1 测试函数

 函数序号 函数名 范围 最优值坐标 最优值 f1 Sphere [－100,100] (0,0,…,0) 0 f2 Schwefel.2.22 [－10,10] (0,0,…,0) 0 f3 Schwefel.1.2 [－100,100] (0,0,…,0) 0 f4 Quadric Noise [－1.28,1.28] (0,0,…,0) 0 f5 Rastrigin [－5.12,5.12] (0,0,…,0) 0 f6 Ackley [－32,32] (0,0,…,0) 0 f7 Griewank [－600,600] (0,0,…,0) 0 f8 Penalized.1 [－50,50] (1,1,…,1) 0
3.2 与标准混合蛙跳算法在不同维度下的比较

 函数序号 Mean±Std.Dev D=10 D=30 D=50 SFLA GC-SFLA SFLA GC-SFLA SFLA GC-SFLA f1 6.655 0e-007±8.774 4e-006 0.000 0e+000±0.000 0e+000 6.130 5e+000±7.965 1e+001 0.000 0e+000±0.000 0e+000 9.609 3e+001±5.304 9e+001 0.000 0e+000±0.000 0e+000 f5 5.12e+000±1.256 1e-014 0.000 0e+000±0.000 0e+000 5.12e+000±1.256 1e-014 0.000 0e+000±0.000 0e+000 5.12e+000±1.256 1e-014 0.000 0e+000±0.000 0e+000 f6 6.154 9e-005±5.719 5e-004 5.887 2e-016±0.000 0e+000 7.759 0e-001±3.912 7e+000 5.887 2e-016±0.000 0e+000 2.082 8e+000±2.640 8e+000 9.428 1e-002±1.278 1e-001 f7 5.480 9e-002±1.712 0e-001 0.000 0e+000±0.000 0e+000 1.611 5e-001±5.920 5e-001 0.000 0e+000±0.000 0e+000 9.167 3e-001±9.664 5e-001 6.505 6e-012±2.277 8e-011

 图 2 4种测试函数的进化曲线 Fig. 2 The evolution curves of four benchmark functions
3.3 与新近提出的知名群智能算法进行比较

 测试函数 指标 SFLA APSO DCPSO GABC MEABC GC-SFLA f1 Mean 5.41e-1 1.45e-150 7.31e-230 4.70e-16 1.55e-56 1.99e-277 Std.Dev 6.40e-1 5.73e-150 0 2.57e-15 3.67e-55 0 f2 Mean 7.84e0 5.15e-84 1.94e-85 1.26e-15 1.08e-29 1.21e-111 Std.Dev 2.37e1 1.44e-83 3.07e-84 6.90e-15 2.21e-28 1.24e-110 f3 Mean 1.00e2 1.0e-10 2.22e-22 5.49e3 8.31e3 5.81e-86 Std.Dev 1.03e2 2.13e-10 6.50e-21 3.00e4 7.54e3 7.62e-85 f4 Mean 2.17e3 4.66e-3 3.34e-4 5.00e-2 2.18e-2 2.20e-4 Std.Dev 4.19e-3 1.7e-3 1.01e-3 2.74e-1 3.77e-3 2.15e-4 f5 Mean 5.12e0 5.8e-15 0 0 0 0 Std.Dev 1.25e-14 1.01e-14 0 0 0 0 f6 Mean 7.80e-3 1.11e-14 2.96e-15 2.91e-14 4.13e-14 5.88e-16 Std.Dev 3.81e-2 3.55e-15 0 1.59e-13 2.17e-15 0 f7 Mean 1.45e-1 1.67e-2 0 3.70e-17 0 0 Std.Dev 5.67e-1 2.41e-2 0 2.08e-16 0 0 f8 Mean 3.03e-2 3.76e-31 1.42e-1 4.75e-16 3.02e-17 1.31e-2 Std.Dev 2.77e-1 1.2e-30 1.88e-1 2.60e-15 0 2.15e-2

 测试函数 SFLA APSO DCPSO GABC MEABC f1 + = + = = f2 + + = = = f3 + + = = + f4 + + = = + f5 + + + + + f6 = + + = + f7 = + + = + f8 = - + - - w/t/l 5/3/0 6/1/1 5/3/0 6/1/1 5/2/1

 算法 秩均值 GC-SFLA 2.44 DCPSO 2.81 APSO 3.13 GABC 3.44 MEABC 3.56 SFLA 5.63

 图 3 8种测试函数的进化曲线 Fig. 3 The evolutionary curve of eight benchmark functions
4 结束语

 [1] EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225. [2] MOSCATO P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms, Technical report C3P 826[R]. Pasadena, USA: California Institute of Technology, 1989. [3] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia, 1995: 1942-1948. [4] RAHIMI-VAHED A, MIRZAEI A H. A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem[J]. Computers & Industrial Engineering, 2007, 53(4): 642-666. [5] 崔文华, 刘晓冰, 王伟, 等. 混合蛙跳算法研究综述[J]. 控制与决策, 2012, 27(4): 481-486, 493.CUI Wenhua, LIU Xiaobing, WANG Wei, et al. Survey on shuffled frog leaping algorithm[J]. Control and Decision, 2012, 27(4): 481-486, 193. [6] FAN Tanghuai, LU Li, ZHAO Jia. Improved shuffled frog leaping algorithm and its application in node localization of wireless sensor networks[J]. Intelligent Automation & Soft Computing, 2012, 18(7): 807-818. [7] XIA Li, LUO Jianping, CHEN Minrong, et al. An improved shuffled frog-leaping algorithm with extremal optimisation for continuous optimisation[J]. Information Sciences, 2012, 192: 143-151. [8] ROY P, ROY P, CHAKRABARTI A. Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect[J]. Applied Soft Computing, 2013, 13(11): 4244-4252. [9] VAISAKH K, REDDY A S. MSFLA/GHS/SFLA-GHS/SDE algorithms for economic dispatch problem considering multiple fuels and valve point loadings[J]. Applied Soft Computing, 2013, 13(11): 4281-4291. [10] 罗雪晖, 杨烨, 李霞. 改进混合蛙跳算法求解旅行商问题[J]. 通信学报, 2009, 30(7): 130-135. LUO Xuehui, YANG Ye, LI Xia. Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J]. Journal on Communications, 2009, 30(7): 130-135. [11] NIKNAM T, FIROUZI B B, MOJARRAD H D. A new evolutionary algorithm for non-linear economic dispatch[J]. Expert Systems with Applications, 2011, 38(10): 13301-13309. [12] 张潇丹, 胡峰, 赵力, 等. 基于分子动力学模拟的改进混合蛙跳算法[J]. 数据采集与处理, 2012, 27(3): 327-332. ZHANG Xiaodan, HU Feng, ZHAO Li, et al. Improved shuffled frog leaping algorithm based on molecular dynamics simulations[J]. Journal of Data Acquisition & Processing, 2012, 27(3): 327-332. [13] SUN Hui, ZHAO Jia. Application of particle sharing based particle swarm frog leaping hybrid optimization algorithm in wireless sensor network coverage optimization[J]. Journal of Information and Computational Science, 2011, 8(14): 3181-3188. [14] 汤可宗. 遗传算法与粒子群优化算法的改进及应用研究[D]. 南京: 南京理工大学, 2011: 1-100. TANG Kezong. Modifications and application research on genetic algorithm and particle swarm optimization algorithm[D]. Nanjing, China: Nanjing University of Science & Technology, 2011: 1-100. [15] LIU Yu, QIN Zheng, SHI Zhewen, et al. Center particle swarm optimization[J]. Neurocomputing, 2007, 70(4/5/6): 672-679. [16] 汤可宗, 柳炳祥, 杨静宇, 等. 双中心粒子群优化算法[J]. 计算机研究与发展, 2012, 49(5): 1086-1094.TANG Kezong, LIU Bingxiang, YANG Jingyu, et al. Double center particle swarm optimization algorithm[J]. Journal of Computer Research and Development, 2012, 49(5): 1086-1094. [17] YAO Xin, LIU Yong, LIN Guangming. Evolutionary programming made faster[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102. [18] 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. [19] ZHU Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173. [20] WANG Hui, WU Zhijian, RAHNAMAYAN S, et al. Multi-strategy ensemble artificial bee colony algorithm[J]. Information Sciences, 2014, 279: 587-603.
DOI: 10.3969/j.issn.1673-4785.201405070

0

#### 文章信息

ZHAO Jia, LYU Li, FAN Tanghuai

Shuffled frog-leaping algorithm based on the general center

CAAI Transactions on Intelligent Systems, 2015, 10(03): 414-421.
DOI: 10.3969/j.issn.1673-4785.201405070