基于信息熵的改进狮群算法及其在组合优化中的应用

doi:10.12263/DZXB.20200143

摘要/Abstract

摘要：

狮群算法是一种具有较强寻优能力的群智能算法.为了克服基本狮群算法中因狮王替换的长周期性导致收敛速度较慢，幼狮选择策略较盲目导致的前期遍历性不足，幼狮步长扰动因子受解空间影响过大和算法后期局部收敛速度慢等缺陷；本文在原始狮群算法的基础上改良了狮王的替换策略和幼狮选择的概率，引入信息熵分别控制不同幼狮的步长，引入狮王稳定因子解决幼狮后期选择的盲目性，并适当调整狮群整体构成方式.由信息熵的值来度量狮群算法中幼狮选择的不确定性，通过设置不同的扰动因子达到控制算法中不同幼狮的移动范围，实现算法的自适应调节并增大算法的鲁棒性.仿真实验、桁架优化算例和TSP问题求解对比验证了改进算法的有效性.该研究为组合优化问题的求解提供了一种新的思路和方法.

关键词: 群智能, 狮群算法, 信息熵, 组合优化

Abstract:

Lion swarm algorithm is a kind of group intelligent algorithm with strong optimization ability. In order to overcome the slow convergence speed caused by the long periodicity of Lion King replacement in the basic lion group algorithm, the insufficient earlier ergodicity due to the blind selection strategy of young lion, and the slow local convergence speed in the later stage of the algorithm, the replacement strategy of Lion King and the selection probability of lion cubs were improved based on the original lion swarm algorithm. The information entropy was introduced to control the step length of different lion cubs, the Lion King Stabilizer factor was introduced to solve the blindness of lion cubs' later selection, and the overall composition of lion group was adjusted appropriately. The value of information entropy was used to measure the uncertainty of young lion selection in the lion group algorithm. Different disturbance factors were set to achieve the moving range of different young lions in the control algorithm, so as to realize the adaptive adjustment of the algorithm and increase the robustness of the algorithm. The effectiveness of the improved algorithm was verified by simulation, TSP and truss optimization. This study provides a new idea and method for solving structural optimization problems.

Key words: swarm intelligence, lion swarm optimization, information entropy, combinational optimization

中图分类号:

TP301.6

李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585.

LI Yan-cang, GONG Xiang-yu. An Improved Lion Swarm Algorithm Based on Information Entropy and Its Application in Combinatorial Optimization[J]. Acta Electronica Sinica, 2021, 49(8): 1577-1585.

图/表 15

参考文献 15

1	KarabogaD, BasturkB. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3): 459－471.
2	吴虎胜, 张凤鸣, 吴庐山. 一种新的群体智能算法: 狼群算法[J]. 系统工程与电子技术, 2013, 35(11): 2430－2438.
	WuH S, ZhangF M, WuL S. New swarm intelligence algorithm—wolf pack algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430－2438. (in Chinese)
3	褚鼎立, 陈红, 王旭光. 基于自适应权重和模拟退火的鲸鱼优化算法[J]. 电子学报, 2019, 47(5): 992－999.
	ChuD L, ChenH, WangX G. Whale optimization algorithm based on adaptive weight and simulated annealing[J]. Acta Electronica Sinica, 2019, 47(5): 992－999. (in Chinese)
4	龙文, 蔡绍洪, 焦建军, 等. 一种改进的灰狼优化算法[J]. 电子学报, 2019, 47(1): 169－175.
	LongW, CaiS H, JiaoJ J, et al. An improved grey wolf optimization algorithm[J]. Acta Electronica Sinica, 2019, 47(1): 169－175. (in Chinese)
5	马卫, 孙正兴. 采用搜索趋化策略的布谷鸟全局优化算法[J]. 电子学报, 2015, 43(12): 2429－2439.
	MaW, SunZ X. A global cuckoo optimization algorithm using coarse-to-fine search[J]. Acta Electronica Sinica, 2015, 43(12): 2429－2439. (in Chinese)
6	RajakumarB R. The Lion's algorithm: A new nature-inspired search algorithm[J]. Procedia Technology, 2012, 6: 126－135.
7	YazdaniM, JolaiF. Lion optimization algorithm (LOA): A nature-inspired metaheuristic algorithm[J]. Journal of Computational Design and Engineering, 2016, 3(1): 24－36.
8	刘生建, 杨艳, 周永权. 一种群体智能算法: 狮群算法[J]. 模式识别与人工智能, 2018, 31(5): 431－441.
	LiuS J, YangY, ZhouY Q. A swarm intelligence algorithm-lion swarm optimization[J]. Pattern Recognition and Artificial Intelligence, 2018, 31(5): 431－441. (in Chinese)
9	刘生建, 杨艳, 周永权. 求解0-1背包问题的二进制狮群算法[J]. 计算机工程与科学, 2019, 41(11): 2079－2087.
	LiuS J, YangY, ZhouY Q. A binary lion swarm algorithm for solving 0-1 knapsack problem[J]. Computer Engineering & Science, 2019, 41(11): 2079－2087. (in Chinese)
10	张聪明, 刘立群, 马立群. 一种新的群智能算法: 狮群算法[J]. 计算机科学, 2018, 45(S1): 114－116.
	ZhangC M, LiuL Q, MaL Q. New swarm intelligent algorithms: Lions algorithm[J]. Computer Science, 2018, 45(S1): 114－116. (in Chinese)
11	刘振, 郭恒光, 任建存. 一种局部搜索能力增强的狮群算法[J]. 河南师范大学学报(自然科学版), 2019, 47(3): 35－41.
	LiuZ, GuoH G, RenJ C. An enhanced local search lion optimization algorithm[J]. Journal of Henan Normal University (Natural Science Edition), 2019, 47(3): 35－41. (in Chinese)
12	甘福宝, 黄友锐, 韩涛, 等. 基于狮群优化二维Otsu算法的输送带撕裂检测方法[J]. 工矿自动化, 2019, 45(10): 55－60, 79.
	GanF B, HuangY R, HanT, et al. Conveyor belt tear detection method based on lion group optimization two-dimensional Otsu algorithm[J]. Industry and Mine Automation, 2019, 45(10): 55－60, 79. (in Chinese)
13	李晓东. 遗传狮群算法的分布式电源定容选址[J]. 重庆工商大学学报(自然科学版), 2019, 36(6): 106－110.
	LiX D. Distributed power supply location with constant capacity based on genetic lion swarm algorithm[J]. Journal of Chongqing Technology and Business University (Natural Science Edition), 2019, 36(6): 106－110. (in Chinese)
14	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291－1294.
	YangY, LiuS J, ZhouY Q. Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem[J]. Journal of Computer Applications, 2020, 40(5): 1291－1294. (in Chinese)
15	周新宇, 吴志健, 王晖, 等. 一种精英反向学习的粒子群优化算法[J]. 电子学报, 2013, 41(8): 1647－1652.
	ZhouX Y, WuZ J, WangH, et al. Elite opposition-based particle swarm optimization[J]. Acta Electronica Sinica, 2013, 41(8): 1647－1652. (in Chinese)

算法种类	最优值	最差值	成功次数	早熟次数	寻优平均值
狮群算法	3.0054	1.6275	75	25	2.9108
改进狮群算法	3.0054	3.0054	100	0	3.0054
粒子群算法	3.0054	3.0053	100	0	3.0054
狼群算法	3.0054	3.0048	100	0	3.0053

算法种类	最优值	最差值	成功次数	早熟次数	寻优平均值
狮群算法	3.0054	1.6275	75	25	2.9108
改进狮群算法	3.0054	3.0054	100	0	3.0054
粒子群算法	3.0054	3.0053	100	0	3.0054
狼群算法	3.0054	3.0048	100	0	3.0053

算法种类	最优值	最差值	成功次数	寻优平均值
狮群算法	1.0000	0.9954	100	0.9994
改进狮群算法	1.0000	0.9991	100	0.9999
粒子群算法	1.0000	1.0000	100	1.0000
狼群算法	1.0000	1.0000	100	1.0000

算法种类	最优值	最差值	成功次数	寻优平均值
狮群算法	1.0000	0.9954	100	0.9994
改进狮群算法	1.0000	0.9991	100	0.9999
粒子群算法	1.0000	1.0000	100	1.0000
狼群算法	1.0000	1.0000	100	1.0000

算法种类	最优值	最差值	成功次数	早熟次数	寻优平均值
狮群算法	96.2898	96.2890	100	0	96.2898
改进狮群算法	96.2898	96.2895	100	0	96.2898
粒子群算法	96.2898	75.5587	91	9	94.0109
狼群算法	96.2898	96.1363	100	0	96.2839