Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (9): 2855-2867.DOI: 10.11772/j.issn.1001-9081.2022081189

• Advanced computing • Previous Articles     Next Articles

Multiple level binary imperialist competitive algorithm for solving heterogeneous multiple knapsack problem

Bin LI1,2(), Zhibin TANG3   

  1. 1.School of Mechanical and Automotive Engineering,Fujian University of Technology,Fuzhou Fujian 350118,China
    2.Fujian Provincial Key Laboratory of Big Data Mining and Applications (Fujian University of Technology),Fuzhou Fujian 350118,China
    3.School of Transportation,Fujian University of Technology,Fuzhou Fujian 350118,China
  • Received:2022-08-15 Revised:2022-10-31 Accepted:2022-11-25 Online:2023-01-11 Published:2023-09-10
  • Contact: Bin LI
  • About author:TANG Zhibin, born in 1998, M. S. candidate. His research interests include intelligent transportation system, swarm intelligence.
  • Supported by:
    Research Programming Foundation of Humanities and Social Sciences of Ministry of Education(19YJA630031)


李斌1,2(), 唐志斌3   

  1. 1.福建理工大学 机械与汽车工程学院, 福州 350118
    2.福建省大数据挖掘与应用技术重点实验室(福建理工大学), 福州 350118
    3.福建理工大学 交通运输学院, 福州 350118
  • 通讯作者: 李斌
  • 作者简介:唐志斌(1998—),男,江西抚州人,硕士研究生,主要研究方向:智能交通系统、群集智能。
  • 基金资助:


On the basis of the classical multiple knapsack problem, the Heterogeneous Multiple Knapsack Problem (HMKP) was proposed, which was abstracted from the commonalities of typical logistics service scenarios. And, an Imperialist Competitive Algorithm (ICA) was designed and customized to solve HMKP. As the origin ICA is easy to fall into the local optimum and the optimal solution of the 0-1 knapsack problem is usually near the constraint boundary, Two-Point Automutation Strategy (TPAS) and Jump out of Local Optimum Algorithm (JLOA) were designed to improve ICA, and a Binary Imperialist Competitive Algorithm (BICA) for 0-1 knapsack problem was presented. BICA showed comprehensive and efficient optimization ability in solving 35 numerical examples of 0-1 knapsack problem. BICA based on Best-Matched Value (BMV) was able to find the ideal optimal solutions of 19 out of 20 examples with 100% success rate in the first test set, and the ideal optimal solutions of 12 out of 15 examples were found by the above algorithm with 100% success rate in the second test set, achieving the best performance of all the comparison algorithms. The numerical analysis results show that BICA maintains the multipolar development strategy in the optimization evolution and relies on the unique population evolution method to search the ideal solution in the solution space efficiently. Subsequently, aiming at the strong constraint and high complexity of HMKP, a Multiple Level Binary Imperialist Competitive Algorithm (MLB-ICA) for solving HMKP was put forward based on BICA. Finally, the numerical experiments and performance evaluation of MLB-ICA were carried out on a high dimensional HMKP test set constructed by combining multiple typical numerical examples of 0-1 knapsack problems. The results showed that the solving time of MLB-ICA is longer than that of Gurobi solver, but the solving accuracy of MLB-ICA is 28% higher than that of Gurobi solver. It can be seen that MLB-ICA can solve high-dimensional complicated HMKP efficiently with low computational cost within acceptable time, and provides a feasible algorithm design scheme for ICA to solve super-large scale combinatorial optimization problems.

Key words: 0-1 knapsack problem, Heterogeneous Multiple Knapsack Problem (HMKP), Imperialist Competitive Algorithm (ICA), local search strategy, Jump out of Local Optimum Algorithm (JLOA), multiple level computing architecture



关键词: 0-1背包问题, 异构多背包问题, 帝国竞争算法, 局部搜索策略, 跳出局部最优机制, 多级计算架构

CLC Number: