Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem

doi:10.11772/j.issn.1001-9081.2019091638

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (5): 1291-1294.DOI: 10.11772/j.issn.1001-9081.2019091638

• Artificial intelligence • Previous Articles Next Articles

Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem

YANG Yan¹, LIU Shengjian¹, ZHOU Yongquan²

1.South China Institute of Software Engineering. GU, Guangzhou Guangdong 510990, China
2.School of Information Science and Engineering, Guangxi University for Nationalities, NanningGuangxi 530006, China

Received:2019-09-25 Revised:2019-10-28 Online:2020-05-10 Published:2020-05-15
Contact: YANG Yan, born in 1985, M. S., lecturer. Her research interests include computation intelligence, swarm intelligence algorithm.
About author:YANG Yan, born in 1985, M. S., lecturer. Her research interests include computation intelligence, swarm intelligence algorithm.LIU Shengjian, born in 1972, M. S., lecturer. His research interests include swarm intelligence algorithm, deep learning.ZHOU Yongquan, born in 1962, Ph. D., professor. His research interests include computation intelligence, neural networks.
Supported by:
This work is partially supported by the Key Platform and Major Program of Higher Education Institutions of Guangdong (2018KQNCX392), the Scientific Research Project of South China Institute of Software Engineering. GU (ky201823).

贪心二进制狮群优化算法求解多维背包问题

杨艳¹, 刘生建¹, 周永权²

1.广州大学华软软件学院，广州 510990
2.广西民族大学信息科学与工程学院，南宁 530006

通讯作者: 杨艳(1985—)
作者简介:杨艳(1985—)，女，湖北襄阳人，讲师，硕士，主要研究方向：计算智能、群智能算法；刘生建(1972—)，男，贵州遵义人，讲师，硕士，主要研究方向：群智能算法、深度学习；周永权(1962—)，男，陕西旬邑人，教授，博士，主要研究方向：计算智能、神经网络。
基金资助:
广东省普通高校重点科研平台和科研项目(2018KQNCX392);广州大学华软软件学院科研项目(ky201823)。

Abstract

Abstract:

The Multidimensional Knapsack Problem (MKP) is a kind of typical multi-constraint combinatorial optimization problems. In order to solve this problem, a Greedy Binary Lion Swarm Optimization (GBLSO) algorithm was proposed. Firstly, with the help of binary code transform formula, the locations of lion individuals were discretized to obtain the binary lion swarm algorithm. Secondly, the inverse moving operator was introduced to update the location of lion king and redefine the locations of the lionesses and lion cubs. Thirdly, the greedy algorithm was fully utilized to make the solution feasible, so as to enhance the local search ability and speed up the convergence. Finally, Simulations on 10 typical MKP examples were carried out to compare GBLSO algorithm with Discrete binary Particle Swarm Optimization (DPSO) algorithm and Binary Bat Algorithm (BBA). The experimental results show that GBLSO algorithm is an effective new method for solving MKP and has good convergence efficiency, high optimization accuracy and good robustness in solving MKP.

Key words: intelligent algorithm, greedy algorithm, Greedy Binary Lion Swarm Optimization (GBLSO) algorithm, Multidimensional Knapsack Problem (MKP), combinatorial optimization

摘要：

针对经典的多约束组合优化问题——多维背包问题(MKP)，提出了一种贪心二进制狮群优化(GBLSO)算法。首先，采用二进制代码转换公式将狮群个体位置离散化，得到二进制的狮群算法；其次，引入反置移动算子对狮王位置进行更新，同时对母狮和幼狮位置重新定义；然后，充分利用贪心算法进行解的可行化处理，增强搜索能力并进一步提高收敛速度；最后，对10个MKP典型算例进行仿真实验，并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明，GBLSO算法是一种有效的求解MKP的新方法，在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。

关键词: 智能算法, 贪心算法, 贪心二进制狮群优化算法, 多维背包问题, 组合优化

CLC Number:

TP18

YANG Yan, LIU Shengjian, ZHOU Yongquan. Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem[J]. Journal of Computer Applications, 2020, 40(5): 1291-1294.

杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.

References

1 张晓霞,刘哲 . 一种新的求解多维背包问题的分散算法[J]. 计算机应用研究, 2012, 29(5): 1716-1719. (ZHANG X X, LIU Z. New scatter search algorithm for multidimensional knapsack problem[J]. Application Research of Computers, 2012, 29(5): 1716-1719.)
2 MIRJALILI S , LEWISA . S-shaped versus V-shaped transfer function for binary particle swarm optimization[J]. Swarm and Evolutionary Computation, 2013, 9:1-14.
3 CHIL M , LIN C J , CHEERN M S , et al . Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem[J]. Applied Mathematical Modelling, 2014, 38(4):1338-1350.
4 钟培华，吴志远，缪建群 . 区域分割粒子群算法及多维背包问题求解[J].计算机工程与应用，2011，47（36）：73-75.（ ZHONG P H,WU Z Y, MIAO J Q. Partition particle optimization for multi-dimensional knapsack problem[J]. Computer Engineering and Applications, 2011,47(36):73-75.）
5 王会颖，倪志伟，吴昊 .求解多维背包问题的MapReduce蚁群优化算法[J]. 计算机工程，2013，39（4）：248-253. （WANG H Y，NI Z W，WU H. MapReduce-based ant colony optimization algrithm for multi-dimensional knapsack problem[J]. Computer Engineering, 2013,39(4):248-253.）
6 薛俊杰,王瑛,孟祥飞,等 . 二进制反向学习烟花算法求解多维背包问题[J]. 系统工程与电子技术, 2017, 39(2):451-458. XUE J J , WANG Y , MENG X F , et al . Binary opposite backward learning fireworks algorithm for multidimensional knapsack problem[J]. Systems Engineering and Electronics, 2017, 39(2): 451-458.
7 吴虎胜,张凤鸣,战仁军,等 . 利用改进的二进制狼群算法求解多维背包问题[J]. 系统工程与电子技术, 2015, 37(5):1084-1091． WU H S , ZHANG F M , ZHAN R J , et al . Improved binary wolf pack algorithm for solving multidimensional knapsack problem[J]. Systems Engineering and Electronics, 2015, 37(5):1084-1091.
8 张晶,吴虎胜 . 改进二进制布谷鸟搜索算法求解多维背包问题[J]. 计算机应用, 2015, 35(1):183-188．(ZHANG J, WU H S. Modified binary cuckoo search algorithm for multidimensional knapsack problem[J]. Journal of Computer Applications, 2015, 35(1):183-188．)
9 王小彤,侯立刚,苏成利 . 一种改进的蚁群算法求解多维背包问题[J]. 辽宁石油化工大学学报, 2015, 35(4):53-57. (WANG X T, HOU L G, SU C L. An improved ant colony algorithm solving multi-dimension knapsack problem[J]. Journal of Liaoning Shihua University, 2015, 35(4):53-57.
10 刘生建,杨艳,周永权．一种群体智能算法——狮群算法[J]. 模式识别与人工智能, 2018, 31(5): 431-441. (LIU S J, YANG Y, ZHOU Y Q. A swarm intelligence algorithm-lion swarm optimization[J]. Pattern Recognition and Artificial Intelligence, 2018, 31(5):431-441.)
11 KENNEDY J , EBERHART R C . A discrete binary version of the particle swarm algorithm[C]// Proceedings of the 1997 IEEE International Conference on Systemics, Man, and Cybernetics: Computational Cybernetics and Simulation. Piscataway: IEEE, 1997:4104-4109.
12 MIRJALILI S , MIRJALILI S M , YANG X S . Binary bat algorithm[J]. Neural Computing and Applications, 2014, 25(3/4):663-681.
13 WU H , ZHANG F , ZHAN R , et al . A binary wolf pack algorithm for solving 0-1 knapsack problem[J]. Systems Engineering and Electronics, 2014, 36(8):1660-1667.

[1]	WANG Yu, LIU Yanli, CHEN Shaowu. Maximum common induced subgraph algorithm based on vertex conflict learning [J]. Journal of Computer Applications, 2021, 41(6): 1756-1760.
[2]	ZHANG Shuyao, LI Yonghua, FAN Jiajia. Bulk storage assignment algorithm in bulk port based on game theory [J]. Journal of Computer Applications, 2021, 41(3): 867-874.
[3]	WANG Zekun, HE Yichao, LI Huanzhe, ZHANG Fazhan. Binary particle swarm optimization algorithm based on novel S-shape transfer function for knapsack problem with a single continuous variable [J]. Journal of Computer Applications, 2021, 41(2): 461-469.
[4]	LI Zhanghong, LIANG Xiaolei, TIAN Mengdan, ZHOU Wenfeng. Solution space dynamic compression strategy for permutation and combination problems [J]. Journal of Computer Applications, 2020, 40(7): 2016-2020.
[5]	CAI Hao, YUAN Zhengdao. Greedy algorithm optimization based virtual machine selection strategy in cloud data center [J]. Journal of Computer Applications, 2020, 40(6): 1707-1713.
[6]	YANG Yunting, WANG Peng. Multi-scale quantum free particle optimization algorithm for solving travelling salesman problem [J]. Journal of Computer Applications, 2020, 40(5): 1278-1283.
[7]	ZHANG Xianli, TANG Jianxin, CAO Laicheng. Influence maximization algorithm based on reverse PageRank [J]. Journal of Computer Applications, 2020, 40(1): 96-102.
[8]	LI He, JIANG Dengying, HUANG Zhangcan, WANG Zhanzhan. Method for solving color images quantization problem of color images [J]. Journal of Computer Applications, 2019, 39(9): 2646-2651.
[9]	YUAN Peiyan, CAI Yunyun. Content offloading scheme of greedy strategy in mobile edge computing system [J]. Journal of Computer Applications, 2019, 39(9): 2664-2668.
[10]	LIU Xiao, WANG Xiaoguo. Dense subgraph based telecommunication fraud detection approach in bank [J]. Journal of Computer Applications, 2019, 39(4): 1214-1219.
[11]	LIU Kainan. Greedy algorithm-based virtual machine migration strategies in cloud data center [J]. Journal of Computer Applications, 2019, 39(11): 3333-3338.
[12]	TANG Haibo, LIN Yuming, LI You, CAI Guoyong. Balanced clustering based on simulated annealing and greedy strategy [J]. Journal of Computer Applications, 2018, 38(11): 3132-3138.
[13]	FAN Zifu, YAO Jie, YANG Xianhui. Controller deployment strategy based on delay optimization in software defined network [J]. Journal of Computer Applications, 2018, 38(1): 207-211.
[14]	GUO Houqian, WANG Weiwei, SHANG Ying, ZHAO Ruilian. Weak mutation test case set generation based on dynamic set evolutionary algorithm [J]. Journal of Computer Applications, 2017, 37(9): 2659-2664.
[15]	LI Weipeng, ZENG Jing, ZHANG Guoliang. Intelligent algorithm acceleration strategy for nonlinear 0-1 programming based on improved Markov neighborhood [J]. Journal of Computer Applications, 2016, 36(9): 2416-2421.

Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem

贪心二进制狮群优化算法求解多维背包问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics