面向异构多背包问题的多级二进制帝国竞争算法

doi:10.11772/j.issn.1001-9081.2022081189

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2855-2867.DOI: 10.11772/j.issn.1001-9081.2022081189

面向异构多背包问题的多级二进制帝国竞争算法

李斌¹^,²(), 唐志斌³

^1.福建理工大学机械与汽车工程学院, 福州 350118
^2.福建省大数据挖掘与应用技术重点实验室(福建理工大学), 福州 350118
^3.福建理工大学交通运输学院, 福州 350118

收稿日期:2022-08-15 修回日期:2022-10-31 接受日期:2022-11-25 发布日期:2023-01-11 出版日期:2023-09-10
通讯作者: 李斌
作者简介:唐志斌（1998—），男，江西抚州人，硕士研究生，主要研究方向：智能交通系统、群集智能。
基金资助:
教育部人文社会科学研究规划基金资助项目(19YJA630031)

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

Bin LI¹^,²(), Zhibin TANG³

^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)

摘要/Abstract

摘要：

在传统多背包问题的基础上，从典型物流服务场景中共性抽象出异构多背包问题（HMKP），并设计和定制了一种帝国竞争算法（ICA）对HMKP进行求解和评估。针对原始ICA易陷入局部最优以及0-1背包问题最优解往往在约束边界周围的特点，设计了双点自变异策略（TPAS）和跳出局部最优算法（JLOA）对ICA进行改进，提出面向0-1背包问题的二进制帝国竞争算法（BICA）。BICA在求解35个0-1背包问题算例时展现出了全面、高效的寻优能力，基于最佳匹配值法（BMV）的BICA在第一组测试集的20个算例上能对19个算例100%找到理想最优值，在第二组测试集的15个算例上能对12个算例100%找到理想最优值，在所有对比算法中表现最优。数值结果分析表明，BICA在寻优演化中维持多极发展策略，并依托独特的种群进化方式在解空间中高效搜索理想解。在此基础上，针对HMKP强约束性和高复杂度的特性，基于BICA设计了求解HMKP的多级二进制帝国竞争算法（MLB-ICA）。分别在多个典型0-1背包问题算例组合构建的HMKP高维测试集上进行了MLB-ICA的数值实验和性能评估，结果表明虽然MLB-ICA的求解时间比Gurobi长，但求解精度提高了28%。可见，MLB-ICA能以较低的计算代价在可接受的时间范围内高效求解高维复杂的HMKP，为ICA在超大规模组合优化问题中的求解提出了可行的算法设计方案。

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

Abstract:

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

中图分类号:

TP301.6

李斌, 唐志斌. 面向异构多背包问题的多级二进制帝国竞争算法[J]. 计算机应用, 2023, 43(9): 2855-2867.

Bin LI, Zhibin TANG. Multiple level binary imperialist competitive algorithm for solving heterogeneous multiple knapsack problem[J]. Journal of Computer Applications, 2023, 43(9): 2855-2867.

图/表 21

图1 HMKP的求解架构

Fig. 1 HMKP solution architecture

图2 双点自变异策略原理

Fig. 2 Principal of two-point automutation strategy

图3 ICA与MLB-ICA的种群结构

Fig. 3 Population structures of ICA and MLB-ICA

图4 MLB-ICA的算法框架

Fig. 4 Algorithm framework of MLB-ICA

表1 不同算法的单次迭代最大时间复杂度对比

Tab. 1 Comparison of maximum time complexity of different algorithms for a single iteration

算法	时间复杂度	算法	时间复杂度
BICA	$O ((8 a + 9) n)$	HGGA	$O ((100 + 2 n) a)$
DSCA	$O (2 a n)$	OMBO	$O (8.2 a n)$

表1 不同算法的单次迭代最大时间复杂度对比

Tab. 1 Comparison of maximum time complexity of different algorithms for a single iteration

算法	时间复杂度	算法	时间复杂度
BICA	$O ((8 a + 9) n)$	HGGA	$O ((100 + 2 n) a)$
DSCA	$O (2 a n)$	OMBO	$O (8.2 a n)$

表2 算法运行参数

Tab. 2 Parameters of algorithms

参数	符号	值
帝国主义国家（王国）的数量	$i m p_n u m (m)$	8
殖民地的数量	$c o l_n u m$	72
殖民地执行TPAS操作的概率	$p r o_c o l$	0.5
帝国主义国家（王国）循环执行TPAS的次数	$T i m e T P A S$	50
殖民地移动偏角	$θ$	$π / 4$
JLOA中连续最优解未更新的最大迭代次数	$u$	20

表2 算法运行参数

Tab. 2 Parameters of algorithms

参数	符号	值
帝国主义国家（王国）的数量	$i m p_n u m (m)$	8
殖民地的数量	$c o l_n u m$	72
殖民地执行TPAS操作的概率	$p r o_c o l$	0.5
帝国主义国家（王国）循环执行TPAS的次数	$T i m e T P A S$	50
殖民地移动偏角	$θ$	$π / 4$
JLOA中连续最优解未更新的最大迭代次数	$u$	20

表3 BICA与其他3个元启发式算法在测试集1上的测试结果比较

Tab. 3 Comparison of test results of BICA and other three meta-heuristic algorithms on test set 1

算例	理想值	BLDE	DBDE	Nbin-DE	BICA
KP01	1 807	1 807	1 807	1 807	1 807
KP02	3 403	3 401	3 403	3 403	3 403
KP03	5 444	5 441	5 444	5 444	5 444
KP04	9 495	9 484	9 495	9 495	9 495
KP05	18 844	18 492	18 843	18 844	18 844
KP06	659	658	659	659	659
KP07	1 332	1 329	1 332	1 332	1 332
KP08	1 963	1 961	1 963	1 963	1 963
KP09	3 250	3 247	3 247	3 250	3 250
KP10	6 482	6 458	6 463	6 482	6 482
KP11	813	812	813	813	813
KP12	1 631	1 626	1 631	1 631	1 631
KP13	2 433	2 426	2 433	2 433	2 433
KP14	4 078	4 051	4 070	4 078	4 078
KP15	8 228	8 073	8 109	8 228	8 228
KP16	493	493	493	493	493
KP17	1 001	1 001	1 001	1 001	1 001
KP18	1 523	1 523	1 523	1 523	1 523
KP19	2 518	2 518	2 518	2 518	2 518
KP20	5 068	5 068	5 068	5 068	5 068

表4 基于BICA和3个对比算法表现的非参数Wilcoxon秩和检验测试结果

Tab. 4 Results of non-parametric Wilcoxon rank sum test based on performance of BICA and three comparison algorithms

算法对比	Better	Equal	p值
BICA vs. BLDE	14	6	0.001
BICA vs. DBDE	5	15	0.430
BICA vs. Nbin-DE	0	20	null

表5 BICA在测试集2上的测试结果

Tab. 5 Test results of BICA on test set 2

相关性	算例	物品数量	理想值	算法	最优解	最差解	均值解	中位数解	标准差	迭代次数	成功率/%
无相关	KP21	800	40 686	BICA-DisEA	40 686	40 685	40 686	40 686	0.370 3	1 327.60	84
	KP21	800	40 686	BICA-BMV	40 686	40 685	40 686	40 686	0.418 4	955.46	78
	KP22	1 000	50 592	BICA-DisEA	50 592	50 591	50 592	50 592	0.197 9	416.38	96
	KP22	1 000	50 592	BICA-BMV	50 592	50 592	50 592	50 592	0.000 0	14.16	100
	KP23	1 200	61 846	BICA-DisEA	61 846	61 845	61 845	61 845	0.504 7	1 063.50	48
	KP23	1 200	61 846	BICA-BMV	61 846	61 846	61 846	61 846	0.000 0	12.56	100
	KP24	1 500	77 033	BICA-DisEA	77 033	77 033	77 033	77 033	0.000 0	222.24	100
	KP24	1 500	77 033	BICA-BMV	77 033	77 033	77 033	77 033	0.000 0	10.80	100
	KP25	2 000	102 316	BICA-DisEA	102 316	102 316	102 316	102 316	0.000 0	468.24	100
	KP25	2 000	102 316	BICA-BMV	102 316	102 316	102 316	102 316	0.000 0	23.20	100
弱相关	KP26	800	35 069	BICA-DisEA	35 069	35 069	35 069	35 069	0.000 0	334.02	100
	KP26	800	35 069	BICA-BMV	35 069	35 069	35 069	35 069	0.000 0	71.68	100
	KP27	1 000	43 786	BICA-DisEA	43 786	43 786	43 786	43 786	0.000 0	598.38	100
	KP27	1 000	43 786	BICA-BMV	43 786	43 786	43 786	43 786	0.000 0	67.64	100
	KP28	1 200	53 553	BICA-DisEA	53 553	53 552	53 552	53 552	0.503 4	1 281.44	46
	KP28	1 200	53 553	BICA-BMV	53 553	53 553	53 553	53 553	0.000 0	299.94	100
	KP29	1 500	65 710	BICA-DisEA	65 709	65 709	65 709	65 709	0.000 0	667.86	0
	KP29	1 500	65 710	BICA-BMV	65 710	65 709	65 709	65 709	0.274 1	331.12	8
	KP30	2 000	108 200	BICA-DisEA	118 200	118 199	118 200	118 200	0.141 4	724.60	98
	KP30	2 000	108 200	BICA-BMV	118 200	118 200	118 200	118 200	0.000 0	16.76	100
强相关	KP31	800	40 167	BICA-DisEA	40 167	40 157	40 166	40 167	2.740 4	1 146.24	92
	KP31	800	40 167	BICA-BMV	40 167	40 167	40 167	40 167	0.000 0	1.42	100
	KP32	1 000	49 443	BICA-DisEA	49 442	49 432	49 432	49 432	1.414 2	175.42	0
	KP32	1 000	49 443	BICA-BMV	49 442	49 442	49 442	49 442	0.000 0	2.46	0
	KP33	1 200	60 640	BICA-DisEA	60 640	60 630	60 633	60 630	4.430 8	878.58	26
	KP33	1 200	60 640	BICA-BMV	60 640	60 640	60 640	60 640	0.000 0	1.84	100
	KP34	1 500	74 932	BICA-DisEA	74 922	74 912	74 921	74 922	3.282 6	1 580.20	0
	KP34	1 500	74 932	BICA-BMV	74 932	74 932	74 932	74 932	0.000 0	2.56	100
	KP35	2 000	99 683	BICA-DisEA	99 673	99 663	99 668	99 663	5.034 5	1 029.82	0
	KP35	2 000	99 683	BICA-BMV	99 683	99 683	99 683	99 683	0.000 0	3.76	100

表5 BICA在测试集2上的测试结果

Tab. 5 Test results of BICA on test set 2

相关性	算例	物品数量	理想值	算法	最优解	最差解	均值解	中位数解	标准差	迭代次数	成功率/%
无相关	KP21	800	40 686	BICA-DisEA	40 686	40 685	40 686	40 686	0.370 3	1 327.60	84
	KP21	800	40 686	BICA-BMV	40 686	40 685	40 686	40 686	0.418 4	955.46	78
	KP22	1 000	50 592	BICA-DisEA	50 592	50 591	50 592	50 592	0.197 9	416.38	96
	KP22	1 000	50 592	BICA-BMV	50 592	50 592	50 592	50 592	0.000 0	14.16	100
	KP23	1 200	61 846	BICA-DisEA	61 846	61 845	61 845	61 845	0.504 7	1 063.50	48
	KP23	1 200	61 846	BICA-BMV	61 846	61 846	61 846	61 846	0.000 0	12.56	100
	KP24	1 500	77 033	BICA-DisEA	77 033	77 033	77 033	77 033	0.000 0	222.24	100
	KP24	1 500	77 033	BICA-BMV	77 033	77 033	77 033	77 033	0.000 0	10.80	100
	KP25	2 000	102 316	BICA-DisEA	102 316	102 316	102 316	102 316	0.000 0	468.24	100
	KP25	2 000	102 316	BICA-BMV	102 316	102 316	102 316	102 316	0.000 0	23.20	100
弱相关	KP26	800	35 069	BICA-DisEA	35 069	35 069	35 069	35 069	0.000 0	334.02	100
	KP26	800	35 069	BICA-BMV	35 069	35 069	35 069	35 069	0.000 0	71.68	100
	KP27	1 000	43 786	BICA-DisEA	43 786	43 786	43 786	43 786	0.000 0	598.38	100
	KP27	1 000	43 786	BICA-BMV	43 786	43 786	43 786	43 786	0.000 0	67.64	100
	KP28	1 200	53 553	BICA-DisEA	53 553	53 552	53 552	53 552	0.503 4	1 281.44	46
	KP28	1 200	53 553	BICA-BMV	53 553	53 553	53 553	53 553	0.000 0	299.94	100
	KP29	1 500	65 710	BICA-DisEA	65 709	65 709	65 709	65 709	0.000 0	667.86	0
	KP29	1 500	65 710	BICA-BMV	65 710	65 709	65 709	65 709	0.274 1	331.12	8
	KP30	2 000	108 200	BICA-DisEA	118 200	118 199	118 200	118 200	0.141 4	724.60	98
	KP30	2 000	108 200	BICA-BMV	118 200	118 200	118 200	118 200	0.000 0	16.76	100
强相关	KP31	800	40 167	BICA-DisEA	40 167	40 157	40 166	40 167	2.740 4	1 146.24	92
	KP31	800	40 167	BICA-BMV	40 167	40 167	40 167	40 167	0.000 0	1.42	100
	KP32	1 000	49 443	BICA-DisEA	49 442	49 432	49 432	49 432	1.414 2	175.42	0
	KP32	1 000	49 443	BICA-BMV	49 442	49 442	49 442	49 442	0.000 0	2.46	0
	KP33	1 200	60 640	BICA-DisEA	60 640	60 630	60 633	60 630	4.430 8	878.58	26
	KP33	1 200	60 640	BICA-BMV	60 640	60 640	60 640	60 640	0.000 0	1.84	100
	KP34	1 500	74 932	BICA-DisEA	74 922	74 912	74 921	74 922	3.282 6	1 580.20	0
	KP34	1 500	74 932	BICA-BMV	74 932	74 932	74 932	74 932	0.000 0	2.56	100
	KP35	2 000	99 683	BICA-DisEA	99 673	99 663	99 668	99 663	5.034 5	1 029.82	0
	KP35	2 000	99 683	BICA-BMV	99 683	99 683	99 683	99 683	0.000 0	3.76	100

表6 对比算法在大规模算例上的平均排名

Tab. 6 Average ranking of comparison algorithms on large-scale numerical examples

算法	无相关算例排名	弱相关算例排名	强相关算例排名
CMBO	4.97	4.33	4.20
OMBO	4.90	3.93	3.13
GMBO	7.00	6.07	6.73
BICA-BMV	2.37	2.70	3.07
HGGA	2.77	2.97	2.67
BICA-DisEA	2.70	3.40	5.53
NM	3.17	3.30	2.67

表7 基于BICA和5个对比算法表现的非参数Wilcoxon秩和检验测试结果

Tab. 7 Results of non-parametric Wilcoxon rank sum test based on performance of BICA and 5 comparison algorithms

算法	CMBO	OMBO	GMBO	HGGA	NM
BICA-BMV	0.022	0.213	0.001	0.900	0.900
BICA-DisEA	0.879	0.900	0.004	0.606	0.804

表8 HGGA和BICA-BMV的迭代次数对比

Tab. 8 Comparison of ierations between HGGA and BICA-BMV

算例	HGGA	BICA-BMV	算例	HGGA	BICA-BMV
KP22	15 603	14	KP31	4 297	1
KP24	18 507	11	KP33	7 281	2
KP26	8 671	72	KP34	10 549	3
KP27	12 050	68	KP35	17 054	4
KP30	22 551	17

表9 ICA、BICA-A、BICA-B和BICA的测试结果

Tab. 9 Test results of ICA，BICA-A，BICA-B and BICA

算例	算法	最优解	最差解	均值解	标准差
KP03	ICA	5 444	5 443	5 443.28	0.45
	BICA-A	5 444	5 443	5 443.86	0.35
	BICA-B	5 444	5 443	5 443.80	0.40
	BICA	5 444	5 443	5 443.92	0.27
KP21	ICA	40 685	40 683	40 684.86	0.40
	BICA-A	40 686	40 685	40 685.38	0.49
	BICA-B	40 686	40 685	40 685.36	0.48
	BICA	40 686	40 685	40 685.78	0.41
KP22	ICA	50 592	50 590	50 591.80	0.53
	BICA-A	50 592	50 592	50 592.00	0.00
	BICA-B	50 592	50 592	50 592.00	0.00
	BICA	50 592	50 592	50 592.00	0.00
KP23	ICA	61 846	61 844	61 845.84	0.42
	BICA-A	61 846	61 846	61 846.00	0.00
	BICA-B	61 846	61 846	61 846.00	0.00
	BICA	61 846	61 846	61 846.00	0.00
KP24	ICA	77 033	77 029	77 032.64	1.00
	BICA-A	77 033	77 033	77 033.00	0.00
	BICA-B	77 033	77 033	77 033.00	0.00
	BICA	77 033	77 033	77 033.00	0.00
KP25	ICA	102 316	102 309	102 315.28	1.37
	BICA-A	102 316	102 316	102 316.00	0.00
	BICA-B	102 316	102 316	102 316.00	0.00
	BICA	102 316	102 316	102 316.00	0.00
KP29	ICA	65 709	65 705	65 708.40	0.94
	BICA-A	65 710	65 709	65 709.04	0.20
	BICA-B	65 710	65 709	65 709.08	0.27
	BICA	65 710	65 709	65 709.08	0.27

图5 ICA、BICA-A、BICA-B和BICA的收敛曲线

Fig. 5 Convergence curves of ICA， BICA-A， BICA-B and BICA

图6 BICA-BMV在KP03和KP21上的国家数量配置参数分析

Fig. 6 Country number configuration parameter analysis of BICA-BMV on KP03 and KP21

图7 BICA-BMV在KP03、KP21和KP29上的局部搜索深度参数分析

Fig. 7 Local search depth parameter analysis of BICA-BMV on KP03， KP21 and KP29

图8 不同u值条件下帝国数量的变化

Fig. 8 Change of empire number under different u values

表10 BICA在不同u值条件下的测试结果

Tab. 10 Test results of BICA-BMV under different u values

算例	$u$	最优解	最差解	均值解	标准差
KP03	20	5 444	5 443	5 443.92	0.27
	40	5 444	5 443	5 443.82	0.38
	60	5 444	5 443	5 443.94	0.24
	80	5 444	5 443	5 443.92	0.27
	100	5 444	5 443	5 443.94	0.24
KP21	20	40 686	40 685	40 685.78	0.41
	40	40 686	40 685	40 685.46	0.50
	60	40 686	40 685	40 685.54	0.50
	80	40 686	40 685	40 685.62	0.49
	100	40 686	40 685	40 685.52	0.50
KP29	20	65 710	65 709	65 709.08	0.27
	40	65 709	65 709	65 709.00	0.00
	60	65 710	65 709	65 709.06	0.24
	80	65 710	65 709	65 709.08	0.27
	100	65 710	65 709	65 709.02	0.14
KP32	20	49 442	49 442	49 442.00	0.00
	40	49 442	49 442	49 442.00	0.00
	60	49 442	49 442	49 442.00	0.00
	80	49 442	49 442	49 442.00	0.00
	100	49 442	49 442	49 442.00	0.00

表10 BICA在不同u值条件下的测试结果

Tab. 10 Test results of BICA-BMV under different u values

算例	$u$	最优解	最差解	均值解	标准差
KP03	20	5 444	5 443	5 443.92	0.27
	40	5 444	5 443	5 443.82	0.38
	60	5 444	5 443	5 443.94	0.24
	80	5 444	5 443	5 443.92	0.27
	100	5 444	5 443	5 443.94	0.24
KP21	20	40 686	40 685	40 685.78	0.41
	40	40 686	40 685	40 685.46	0.50
	60	40 686	40 685	40 685.54	0.50
	80	40 686	40 685	40 685.62	0.49
	100	40 686	40 685	40 685.52	0.50
KP29	20	65 710	65 709	65 709.08	0.27
	40	65 709	65 709	65 709.00	0.00
	60	65 710	65 709	65 709.06	0.24
	80	65 710	65 709	65 709.08	0.27
	100	65 710	65 709	65 709.02	0.14
KP32	20	49 442	49 442	49 442.00	0.00
	40	49 442	49 442	49 442.00	0.00
	60	49 442	49 442	49 442.00	0.00
	80	49 442	49 442	49 442.00	0.00
	100	49 442	49 442	49 442.00	0.00

图9 KP28和KP29的收敛情况和种群交换地位次数情况

Fig. 9 Conditions of convergence and times of population status exchange for KP28 and KP29

表11 MLB-ICA在测试集3上的测试结果

Tab. 11 Test results of MLB-ICA on test set 3

算例	参数	最优解	最差解	均值解	中位数解	标准差	迭代次数	成功率/%
KP36	$G A P$	0.00	1.00	0.48	0.00	0.50	127.72	52
KP36	$g a p i$	0.00、0.00	1.00、0.00	0.48	0.00、0.00	0.50	127.72	52
KP37	$G A P$	0.00	2.00	0.96	1.00	0.28	101.76	6
KP37	$g a p i$	0.00、0.00	1.00、1.00	0.96	0.00、1.00	0.28	101.76	6
KP38	$G A P$	0.00	3.00	0.94	1.00	0.47	162.14	12
KP38	$g a p i$	0.00、0.00、0.00	0.00、2.00、1.00	0.94	0.00、1.00、0.00	0.47	162.14	12
KP39	$G A P$	0.00	0.00	0.00	0.00	0.00	10.58	100
KP39	$g a p i$	0.00、0.00、0.00	0.00、0.00、0.00	0.00	0.00、0.00、0.00	0.00	10.58	100
KP40	$G A P$	0.00	2.00	1.46	1.00	0.57	222.32	4
KP40	$g a p i$	0.00、0.00、0.00 0.00	1.00、0.00、0.00 1.00	1.46	0.00、0.00、0.00 1.00	0.57	222.32	4
KP41	$G A P$	0.00	0.00	0.00	0.00	0.00	4.10	100
KP41	$g a p i$	0.00、0.00、0.00 0.00	0.00、0.00、0.00 0.00	0.00	0.00、0.00、0.00 0.00	0.00	4.10	100
KP42	$G A P$	0.00	1.00	0.02	0.00	0.14	65.36	98
KP42	$g a p i$	0.00、0.00、0.00 0.00、0.00	0.00、0.00、0.00 0.00、1.00	0.02	0.00、0.00、0.00 0.00、0.00	0.14	65.36	98
KP43	$G A P$	0.00	1.00	0.34	0.00	0.47	161.70	66
KP43	$g a p i$	0.00、0.00、0.00 0.00、0.00	0.00、0.00、1.00 0.00、0.00	0.34	0.00、0.00、0.00 0.00、0.00	0.47	161.70	66
KP44	$G A P$	0.00	2.00	0.94	1.00	0.31	142.46	8
KP44	$g a p i$	0.00、0.00、0.00 0.00、0.00、0.00	0.00、0.00、0.00 0.00、2.00、0.00	0.94	0.00、0.00、0.00 0.00、1.00、0.00	0.31	142.46	8
KP45	$G A P$	0.00	2.00	1.38	1.00	0.52	266.62	2
KP45	$g a p i$	0.00、0.00、0.00 0.00、0.00、0.00	1.00、0.00、0.00 0.00、1.00、0.00	1.38	0.00、0.00、0.00 0.00、1.00、0.00	0.52	266.62	2

表11 MLB-ICA在测试集3上的测试结果

Tab. 11 Test results of MLB-ICA on test set 3

算例	参数	最优解	最差解	均值解	中位数解	标准差	迭代次数	成功率/%
KP36	$G A P$	0.00	1.00	0.48	0.00	0.50	127.72	52
KP36	$g a p i$	0.00、0.00	1.00、0.00	0.48	0.00、0.00	0.50	127.72	52
KP37	$G A P$	0.00	2.00	0.96	1.00	0.28	101.76	6
KP37	$g a p i$	0.00、0.00	1.00、1.00	0.96	0.00、1.00	0.28	101.76	6
KP38	$G A P$	0.00	3.00	0.94	1.00	0.47	162.14	12
KP38	$g a p i$	0.00、0.00、0.00	0.00、2.00、1.00	0.94	0.00、1.00、0.00	0.47	162.14	12
KP39	$G A P$	0.00	0.00	0.00	0.00	0.00	10.58	100
KP39	$g a p i$	0.00、0.00、0.00	0.00、0.00、0.00	0.00	0.00、0.00、0.00	0.00	10.58	100
KP40	$G A P$	0.00	2.00	1.46	1.00	0.57	222.32	4
KP40	$g a p i$	0.00、0.00、0.00 0.00	1.00、0.00、0.00 1.00	1.46	0.00、0.00、0.00 1.00	0.57	222.32	4
KP41	$G A P$	0.00	0.00	0.00	0.00	0.00	4.10	100
KP41	$g a p i$	0.00、0.00、0.00 0.00	0.00、0.00、0.00 0.00	0.00	0.00、0.00、0.00 0.00	0.00	4.10	100
KP42	$G A P$	0.00	1.00	0.02	0.00	0.14	65.36	98
KP42	$g a p i$	0.00、0.00、0.00 0.00、0.00	0.00、0.00、0.00 0.00、1.00	0.02	0.00、0.00、0.00 0.00、0.00	0.14	65.36	98
KP43	$G A P$	0.00	1.00	0.34	0.00	0.47	161.70	66
KP43	$g a p i$	0.00、0.00、0.00 0.00、0.00	0.00、0.00、1.00 0.00、0.00	0.34	0.00、0.00、0.00 0.00、0.00	0.47	161.70	66
KP44	$G A P$	0.00	2.00	0.94	1.00	0.31	142.46	8
KP44	$g a p i$	0.00、0.00、0.00 0.00、0.00、0.00	0.00、0.00、0.00 0.00、2.00、0.00	0.94	0.00、0.00、0.00 0.00、1.00、0.00	0.31	142.46	8
KP45	$G A P$	0.00	2.00	1.38	1.00	0.52	266.62	2
KP45	$g a p i$	0.00、0.00、0.00 0.00、0.00、0.00	1.00、0.00、0.00 0.00、1.00、0.00	1.38	0.00、0.00、0.00 0.00、1.00、0.00	0.52	266.62	2

表12 MLB-ICA和Gurobi在测试集3上的均值解和求解时间

Tab. 12 Mean solutions and solving time of MLB-ICA and Gurobi on test set 3

算例	MLB-ICA		Gurobi
算例	均值解	求解时间/s	均值解	求解时间/s
Avg	0.65	801.18	0.90	0.70
KP36	0.48	791.95	0.00	1.09
KP37	0.96	599.44	1.00	0.56
KP38	0.94	723.89	2.00	0.97
KP39	0.00	590.58	0.00	0.25
KP40	1.46	634.88	1.00	0.52
KP41	0.00	397.36	0.00	0.09
KP42	0.02	870.09	1.00	0.61
KP43	0.34	1 069.07	1.00	0.66
KP44	0.94	1 016.85	1.00	0.83
KP45	1.38	1 317.73	2.00	1.37

参考文献 36

1	DANTZIG G B. Discrete-variable extremum problems［J］. Operations Research， 1957， 5（2）： 266-288. 10.1287/opre.5.2.266
2	HAN K H， KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problem［C］// Proceedings of the 2000 Congress on Evolutionary Computation - Volume 2. Piscataway： IEEE， 2000： 1354-1360.
3	杨艳，刘生建，周永权. 贪心二进制狮群优化算法求解多维背包问题［J］. 计算机应用， 2020， 40（5）： 1291-1294.
	YANG Y， LIU S J， ZHOU Y Q. Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem［J］. Journal of Computer Applications， 2020， 40（5）： 1291-1294.
4	张清勇，钱浩，雷德明. 基于核问题的果蝇优化算法求解多维背包问题［J］. 华中科技大学学报（自然科学版）， 2019， 47（2）： 92-97.
	ZHANG Q Y， QIAN H， LEI D M. Core-based fruit fly optimization algorithm for solving multidimensional knapsack problem［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2019， 47（2）： 92-97.
5	崔建双，王憧憬. 求解多重背包问题的限速粒子群算法［J］. 计算机工程与应用， 2015， 51（9）： 244-247. 10.3778/j.issn.1002-8331.1305-0531
	CUI J S， WANG C J. Solving multiple knapsack problem with speed limit particle swarm algorithm［J］. Computer Engineering and Applications， 2015， 51（9）： 244-247. 10.3778/j.issn.1002-8331.1305-0531
6	贺毅朝，王熙照，李文斌，等. 基于遗传算法求解折扣｛0-1｝背包问题的研究［J］. 计算机学报， 2016， 39（12）： 2614-2630. 10.11897/SP.J.1016.2016.02614
	HE Y C， WANG X Z， LI W B， et al. Research on genetic algorithms for the discounted ｛0-1｝ knapsack problem［J］. Chinese Journal of Computers， 2016， 39（12）： 2614-2630. 10.11897/SP.J.1016.2016.02614
7	杨洋. 改进帕累托算法求解超大规模多选择背包问题［J］. 电子学报， 2020， 48（6）： 1205-1212. 10.3969/j.issn.0372-2112.2020.06.023
	YANG Y. Improved Pareto algorithm for solving very large scale multiple-choice knapsack problem［J］. Acta Electronica Sinica， 2020， 48（6）： 1205-1212. 10.3969/j.issn.0372-2112.2020.06.023
8	贺毅朝，田海燕，张新禄，等. 基于动态规划法求解动态0-1背包问题［J］. 计算机科学， 2012， 39（7）： 237-241. 10.3969/j.issn.1002-137X.2012.07.054
	HE Y C， TIAN H Y， ZHANG X L， et al. Solving dynamic 0-1 knapsack problems based on dynamic programming algorithm［J］. Computer Science， 2012， 39（7）： 237-241. 10.3969/j.issn.1002-137X.2012.07.054
9	苗世清，高岳林. 求解0/1背包问题的离散差分进化算法［J］. 小型微型计算机系统， 2009， 30（9）： 1828-1830.
	MIAO S Q， GAO Y L. Discrete differential evolution algorithm for solving 0/1 knapsack problem［J］. Journal of Chinese Computer Systems， 2009， 30（9）： 1828-1830.
10	吴聪聪，贺毅朝，赵建立. 求解折扣｛0-1｝背包问题的新遗传算法［J］. 计算机工程与应用， 2020， 56（7）： 57-66.
	WU C C， HE Y C， ZHAO J L. New Genetic algorithm for discounted ｛0-1｝ knapsack problem［J］. Computer Engineering and Applications， 2020， 56（7）： 57-66.
11	赵新超，杨婷婷.求解背包问题的更贪心粒子群算法［J］.计算机工程与应用， 2009， 45（36）： 32-34. 10.3778/j.issn.1002-8331.2009.36.010
	ZHAO X C， YANG T T. Very greedy particle swarm optimization algorithm for knapsack problem［J］. Computer Engineering and Applications， 2009， 45（36）： 32-34. 10.3778/j.issn.1002-8331.2009.36.010
12	吴虎胜，张凤鸣，战仁军，等. 求解0-1背包问题的二进制狼群算法［J］. 系统工程与电子技术， 2014， 36（8）： 1660-1667.
	WU H S， ZHANG F M， ZHAN R J， et al. A binary wolf pack algorithm for solving 0-1 knapsack problem［J］. Systems Engineering and Electronics， 2014， 36（8）： 1660-1667.
13	刘生建，杨艳，周永权. 求解0-1背包问题的二进制狮群算法［J］. 计算机工程与科学， 2019， 41（11）： 2079-2087. 10.3969/j.issn.1007-130X.2019.11.024
	LIU S J， YANG Y， ZHOU Y Q. A binary lion swarm algorithm for solving 0-1 knapsack problem［J］. Computer Engineering and Science， 2019， 41（11）： 2079-2087. 10.3969/j.issn.1007-130X.2019.11.024
14	LI Y， HE Y C， LIU X J， et al. A novel discrete whale optimization algorithm for solving knapsack problems［J］. Applied Intelligence， 2020， 50（10）： 3350-3366. 10.1007/s10489-020-01722-3
15	ATASHPAZ-GARGARI E， LUCAS C. Imperialist competitive algorithm： an algorithm for optimization inspired by imperialistic competition［C］// Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2007： 4661-4667. 10.1109/cec.2007.4425083
16	TRUONG T K， LI K L， XU Y M. Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem［J］. Applied Soft Computing， 2013， 13（4）： 1774-1780. 10.1016/j.asoc.2012.11.048
17	高思齐，邢玉轩，肖侬，等. 求解01背包问题的贪婪蛙跳算法［J］. 计算机科学， 2018， 45（7）： 73-77.
	GAO S Q， XING Y X， XIAO N， et al. Greedy frog leaping algorithm for 01 knapsack problem［J］. Computer Science， 2018， 45（7）： 73-77.
18	陈桢，钟一文，林娟. 求解0-1背包问题的混合贪婪遗传算法［J］. 计算机应用， 2021， 41（1）： 87-94.
	CHEN Z， ZHONG Y W， LIN J. Hybrid greedy genetic algorithm for solving 0-1 knapsack problem［J］. Journal of Computer Applications， 2021， 41（1）： 87-94.
19	郑健. 离散正弦余弦算法求解大规模0-1背包问题［J］. 山东大学学报（理学版）， 2020， 55（11）： 87-95.
	ZHENG J. Discrete sine cosine algorithm for solving large-scale 0-1 knapsack problems［J］. Journal of Shandong University （Natural Science）， 2020， 55（11）： 87-95.
20	朱颢东，李红婵. 求解0-1背包问题的基于双禁忌对象的TS算法［J］. 微电子学与计算机， 2011， 28（5）： 148-151.
	ZHU H D， LI H C. TS to solve 0-1 knapsack problem based on double-tabu objects［J］. Microelectronics and Computer， 2011， 28（5）： 148-151.
21	ALI I M， ESSAM D， KASMARIK K. Novel binary differential evolution algorithm for knapsack problems［J］. Information Sciences， 2021， 542： 177-194. 10.1016/j.ins.2020.07.013
22	李迎，张璟，刘庆，等. 求解大规模多背包问题的高级人工鱼群算法［J］. 系统工程与电子技术， 2018， 40（3）： 710-716. 10.3969/j.issn.1001-506X.2018.03.34
	LI Y， ZHANG J， LIU Q， et al. Advanced artificial fish swarm algorithm for large scale multiple knapsack problem［J］. Systems Engineering and Electronics， 2018， 40（3）： 710-716. 10.3969/j.issn.1001-506X.2018.03.34
23	贺毅朝，寇应展，陈致明. 求解多选择背包问题的改进差分演化算法［J］. 小型微型计算机系统， 2007， 28（9）：1682-1685. 10.3969/j.issn.1000-1220.2007.09.027
	HE Y C， KOU Y Z， CHEN Z M. A modified differential evolution algorithm for multiple-choice knapsack problem［J］. Journal of Chinese Computer Systems， 2007， 28（9）：1682-1685. 10.3969/j.issn.1000-1220.2007.09.027
24	DELL’AMICO M， DELORME M， IORI M， et al. Mathematical models and decomposition methods for the multiple knapsack problem［J］. European Journal of Operational Research， 2019， 274（3）： 886-899. 10.1016/j.ejor.2018.10.043
25	李斌，李文锋. 基于MAS的集装箱码头物流系统协同生产调度体系［J］. 计算机集成制造系统， 2011， 17（11）： 2502-2513.
	LI B， LI W F. Container terminal logistics systems collaborative scheduling based on multi-agent systems［J］. Computer Integrated Manufacturing Systems， 2011， 17（11）： 2502-2513.
26	贺毅朝，王熙照，赵书良，等. 基于编码转换的离散演化算法设计与应用［J］. 软件学报， 2018， 29（9）： 2580-2594.
	HE Y C， WANG X Z， ZHAO S L， et al. Design and applications of discrete evolutionary algorithm based on encoding transformation［J］. Journal of Software， 2018， 29（9）： 2580-2594.
27	LI B， TANG Z B. Double-assimilation of prosperity and destruction oriented improved imperialist competitive algorithm with computational thinking［C］// Proceedings of the 2022 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2022：1-8. 10.1109/cec55065.2022.9870296
28	FENG Y H， WANG G G， DONG J Y， et al. Opposition-based learning monarch butterfly optimization with Gaussian perturbation for large-scale 0-1 knapsack problem［J］. Computers and Electrical Engineering， 2018， 67： 454-468. 10.1016/j.compeleceng.2017.12.014
29	FENG Y H， WANG G G， GAO X Z. A novel hybrid cuckoo search algorithm with global harmony search for 0-1 knapsack problems［J］. International Journal of Computational Intelligence Systems， 2016， 9（6）： 1174-1190. 10.1080/18756891.2016.1256577
30	李斌，李文锋. 基于仿真的优化的粒子群算法参数选取研究［J］. 计算机工程与应用， 2011， 47（33）： 30-35. 10.3778/j.issn.1002-8331.2011.33.009
	LI B， LI W F. Simulation based optimization for parameter selection in PSO［J］. Computer Engineering and Applications， 2011， 47（33）： 30-35. 10.3778/j.issn.1002-8331.2011.33.009
31	CHEN Y， XIE W C， ZOU X F. A binary differential evolution algorithm learning from explored solutions［J］. Neurocomputing， 2015， 149（Pt B）： 1038-1047. 10.1016/j.neucom.2014.07.030
32	PENG H， WU Z J， SHAO P， et al. Dichotomous binary differential evolution for knapsack problems［J］. Mathematical Problems in Engineering， 2016， 2016： No.5732489. 10.1155/2016/5732489
33	FENG Y H， YANG J， WU C C， et al. Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with Gaussian mutation［J］. Memetic Computing， 2018， 10（2）： 135-150. 10.1007/s12293-016-0211-4
34	FENG Y H， YU X， WANG G G. A novel monarch butterfly optimization with global position updating operator for large-scale 0-1 knapsack problems［J］. Mathematics， 2019， 7（11）： No.1056. 10.3390/math7111056
35	ZHAN S H， WANG L J， ZHANG Z J， et al. Noising methods with hybrid greedy repair operator for 0-1 knapsack problem［J］. Memetic Computing， 2020， 12（1）： 37-50. 10.1007/s12293-019-00288-z
36	XU S H， WANG Y， LU P C. Improved imperialist competitive algorithm with mutation operator for continuous optimization problems［J］. Neural Computing and Applications， 2017， 28（7）： 1667-1682. 10.1007/s00521-015-2138-y

[1]	张国辉, 陆熙熙, 胡一凡, 孙靖贺. 基于改进帝国竞争算法的柔性作业车间机器故障重调度[J]. 计算机应用, 2021, 41(8): 2242-2248.
[2]	王贵林, 李斌. 受春秋战国史实启发的帝国竞争改进算法[J]. 计算机应用, 2021, 41(2): 470-478.
[3]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.
[4]	刘帅, 刘长良, 甄成刚. 风电机组齿轮箱的多变量时间序列故障预警[J]. 计算机应用, 2019, 39(4): 1229-1233.
[5]	陈孟辉, 刘俊麟, 徐健锋, 李向军. 求解旅行商问题的多样化搜索帝国竞争算法[J]. 计算机应用, 2019, 39(10): 2992-2996.
[6]	吕聪, 魏康林. 柔性车间调度问题的协作混合帝国算法[J]. 计算机应用, 2018, 38(7): 1882-1887.
[7]	宋潇潇, 王军. 改进膜蜂群算法求解0-1背包问题[J]. 计算机应用, 2015, 35(7): 2088-2092.
[8]	张良徐成田峥李涛. 基于贪心算法和模拟退火算法的软硬件划分[J]. 计算机应用, 2013, 33(07): 1898-1902.
[9]	刘磊熊小鹏. 最小驻留价值缓存替换算法[J]. 计算机应用, 2013, 33(04): 1018-1022.
[10]	李宁刘建芹贺毅朝. 基于和声搜索算法求解组合优化问题[J]. 计算机应用, 2012, 32(04): 1041-1044.

面向异构多背包问题的多级二进制帝国竞争算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 21

参考文献 36

相关文章 10

编辑推荐

Metrics