基于新修复优化算子的改进环论优化算法求解多维背包问题

doi:10.11772/j.issn.1001-9081.2024050575

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (5): 1595-1604.DOI: 10.11772/j.issn.1001-9081.2024050575

基于新修复优化算子的改进环论优化算法求解多维背包问题

张寒崧¹, 贺毅朝¹^,²(), 孙菲¹, 陈国新¹, 陈炬¹

^1.河北地质大学信息工程学院，石家庄 050031
^2.河北省光电信息与地球探测技术重点实验室（河北地质大学），石家庄 050031

收稿日期:2024-05-10 修回日期:2024-07-20 接受日期:2024-07-22 发布日期:2024-07-25 出版日期:2025-05-10
通讯作者: 贺毅朝
作者简介:张寒崧（1999—），男，河北邯郸人，硕士研究生，主要研究方向：演化算法
贺毅朝（1969—），男，河北晋州人，教授，硕士，主要研究方向：演化算法、组合优化、机器学习
孙菲（1998—），女，河北邢台人，硕士研究生，主要研究方向：演化算法
陈国新（2000—），男，河北沧州人，硕士研究生，主要研究方向：演化算法
陈炬（2001—），男，湖南湘乡人，硕士研究生，主要研究方向：演化算法。
基金资助:
河北省自然科学基金资助项目(F2020403013);河北省高等学校科学技术研究项目(ZD2021016);河北地质大学2023年国家自然科学基金预研项目(KY202307);2024年河北省在读研究生创新能力培养资助项目(CXZZSS2024109)

Improved ring theory-based evolutionary algorithm with new repair optimization operator for solving multi-dimensional knapsack problem

Hansong ZHANG¹, Yichao HE¹^,²(), Fei SUN¹, Guoxin CHEN¹, Ju CHEN¹

^1.College of Information Engineering，Hebei GEO University，Shijiazhuang Hebei 050031，China
^2.Key Laboratory of Optoelectronic Information and Geo-detection Technology of Hebei Province （Hebei GEO University），Shijiazhuang Hebei 050031，China

Received:2024-05-10 Revised:2024-07-20 Accepted:2024-07-22 Online:2024-07-25 Published:2025-05-10
Contact: Yichao HE
About author:ZHANG Hansong， born in 1999， M. S. candidate. His research interests include evolutionary algorithm.
HE Yichao， born in 1969， M. S.， professor. His research interests include evolutionary algorithm， combinatorial optimization， machine learning.
SUN Fei， born in 1998， M. S. candidate. Her research interests include evolutionary algorithm.
CHEN Guoxin， born in 2000， M. S. candidate. His research interests include evolutionary algorithm.
CHEN Ju， born in 2001， M. S. candidate. His research interests include evolutionary algorithm.
Supported by:
Natural Science Foundation of Hebei Province(F2020403013);Science and Technology Project of Hebei Higher Educational Institutes(ZD2021016);Pre-research Project of National Natural Science Foundation of Hebei GEO University in 2023(KY202307);Innovative Ability Development Funding Project for Graduate Students of Hebei Province in 2024(CXZZSS2024109)

摘要/Abstract

摘要：

为了利用环论优化算法（RTEA）高效求解多维背包问题（MKP），在分析已有修复优化算子——基于物品整体资源消耗伪效用比的修复优化算子RO1和基于物品各维度资源消耗价值密度的修复优化算子RO3不足的基础上，结合互补策略提出一种新的修复优化算子——加权修复优化算子RO4。随后，引入继承策略改进RTEA的全局进化算子，并基于Logistic模型提出适用于MKP的自适应反向变异算子，由此提出了求解MKP的算法IRTEA-RO4。为验证IRTEA-RO4的高效性，利用它求解MKP的114个国际通用基准实例，并与已有求解MKP的6个较先进算法进行比较，结果表明：对于小规模MKP实例，IRTEA-RO4的求解精度和求解速度均为最佳；对于大规模MKP实例，IRTEA-RO4求得的最好结果比6个对比算法的最好结果提高了21%～125%，而且平均性能与稳定性更优，计算速度更快。

关键词: 环论优化算法, 多维背包问题, 加权伪效用比, 继承策略, Logistic模型

Abstract:

To efficiently solve Multi-dimensional Knapsack Problem （MKP） using Ring Theory-based Evolutionary Algorithm （RTEA）， after analyzing the inadequacies of existing repair operators： RO1 （based on the pseudo-utility ratio of items’ overall resource consumption） and RO3 （based on the value density across individual resource dimensions）， a new weighted repair optimization operator named RO4 was proposed by integrating complementary strategy. Additionally， an inheritance strategy was introduced to improve the global evolutionary operator of RTEA， and a self-adaptive reverse mutation operator suitable for MKP was proposed on the basis of Logistic model， along with a new algorithm IRTEA-RO4 for solving MKP. To validate its efficiency， IRTEA-RO4 was tested on 114 internationally recognized MKP benchmark instances and compared with six state-of-the-art algorithms for solving MKP. Experimental results demonstrate that for small-scale MKP instances， IRTEA-RO4 achieves the highest solution accuracy and fastest computation speed； for large-scale MKP instances， IRTEA-RO4 outperforms the best results of the six existing algorithms by 21% to 125% in solution quality， while also exhibiting superior average performance， enhanced stability， and faster computational speed.

Key words: Ring Theory-based Evolutionary Algorithm (RTEA), Multi-dimensional Knapsack Problem (MKP), weighted pseudo-utility ratio, inheritance strategy, Logistic model

中图分类号:

TP18

张寒崧, 贺毅朝, 孙菲, 陈国新, 陈炬. 基于新修复优化算子的改进环论优化算法求解多维背包问题[J]. 计算机应用, 2025, 45(5): 1595-1604.

Hansong ZHANG, Yichao HE, Fei SUN, Guoxin CHEN, Ju CHEN. Improved ring theory-based evolutionary algorithm with new repair optimization operator for solving multi-dimensional knapsack problem[J]. Journal of Computer Applications, 2025, 45(5): 1595-1604.

图/表 14

图1 Pb随t的变化曲线

Fig. 1 Curve of Pb varying with t

图2 IRTEA-RO4求解6个MKP实例的箱线图

Fig. 2 Boxplots of IRTEA-RO4 solving 6 MKP instances

表1 实验算法的参数取值

Tab. 1 Parameter values of experimental algorithms

算法	N	MIT	RT	其他参数	算法	N	MIT	RT	其他参数
IRTEA-RO4	30或50	10³或10⁴	100	$α ∈ {0.1,1}, β ∈ {0,1},$ $P b ∈ [0.001, 0.05], σ = 20 / M I T$	HBDE	30或50	10³或10⁴	100	$C R = 0.3, F S = 0.5,$ $[- A, A] = [- 5.0, 5.0]$
BAAA	100	35×10³	100	sf=2， eloss=0.3， Ap=0.5， τ=1.5	MA/PL	150	5×10³	30	AL=20， LR=0.01
TR-BDS	30或100	10⁴或5×10⁴	100	$p 1 = 0.2, p 2 = 0.3, τ = 2.5$	ABQPSO	50	50n	30	α=0.8
BGWO	20	10⁵	30	$φ (y) = t a n h (y)$

表1 实验算法的参数取值

Tab. 1 Parameter values of experimental algorithms

算法	N	MIT	RT	其他参数	算法	N	MIT	RT	其他参数
IRTEA-RO4	30或50	10³或10⁴	100	$α ∈ {0.1,1}, β ∈ {0,1},$ $P b ∈ [0.001, 0.05], σ = 20 / M I T$	HBDE	30或50	10³或10⁴	100	$C R = 0.3, F S = 0.5,$ $[- A, A] = [- 5.0, 5.0]$
BAAA	100	35×10³	100	sf=2， eloss=0.3， Ap=0.5， τ=1.5	MA/PL	150	5×10³	30	AL=20， LR=0.01
TR-BDS	30或100	10⁴或5×10⁴	100	$p 1 = 0.2, p 2 = 0.3, τ = 2.5$	ABQPSO	50	50n	30	α=0.8
BGWO	20	10⁵	30	$φ (y) = t a n h (y)$

表2 实验算法计算的实例标注

Tab. 2 Labeling of instances calculated by experimental algorithms

算法	G1	cb5.100	cb5.500	cb10. 100	cb10. 500	cb30. 100	cb30. 500	算法	G1	cb5.100	cb5.500	cb10. 100	cb10. 500	cb30. 100	cb30. 500
IRTEA-RO4	√	√	√	√	√	√	√	HBDE	√	√	×	√	×	√	×
BAAA	√	×	√	√	×	×	×	MA/PL	√	√	√	√	√	×	√
TR-BDS	√	√	×	×	√	×	×	ABQPSO	√	√	√	√	√	×	×
BGWO	×	√	×	×	×	×	√

表3 6个算法求解实例G1的计算结果

Tab. 3 Calculation results of six algorithms solving instances G1

实例	n×m	Opt	IRTEA-RO4		BAAA		TR-BDS		HBDE		MA/PL		ABQPSO
实例	n×m	Opt	SR	AT	SR	AT	SR	AT	SR	AT	SR	AT	SR	AT
SENTO1	60×30	7 772	1.00	0.28	1.00	—	0.8	21.71	1.00	0.54	1.00	10.34	1.00	0.14
SENTO2	60×31	8 722	1.00	0.28	1.00	—	0.73	21.69	0.91	0.40	1.00	10.64	1.00	0.04
HP1	28×4	3 418	1.00	0.07	0.93	—	0.40	16.33	1.00	0.07	1.00	3.73	1.00	0.06
HP2	28×5	3 186	1.00	0.08	0.27	—	0.97	16.57	1.00	0.08	1.00	4.68	1.00	0.17
PB1	27×4	3 090	1.00	0.07	1.00	—	0.50	16.16	1.00	0.06	1.00	3.68	1.00	0.03
PB2	34×4	3 186	1.00	0.08	1.00	—	0.97	16.52	1.00	0.08	1.00	4.47	1.00	0.19
PB4	29×2	95 168	1.00	0.07	1.00	—	1.00	15.84	1.00	0.07	1.00	3.74	1.00	0.01
PB5	20×10	2 139	1.00	0.06	1.00	—	0.80	16.49	1.00	0.07	1.00	2.71	1.00	0.04
PB6	40×30	776	1.00	0.19	1.00	—	0.57	20.16	1.00	0.41	1.00	6.42	1.00	0.10
PB7	37×30	1 035	1.00	0.18	1.00	—	0.80	20.14	1.00	0.30	1.00	6.39	1.00	0.01
PET2	10×10	87 061	1.00	0.03	—	—	—	—	—	—	1.00	1.37	—	—
PET3	15×10	4 015	1.00	0.05	—	—	—	—	—	—	1.00	2.09	—	—
PET4	20×10	6 120	1.00	0.06	—	—	—	—	—	—	1.00	2.77	—	—
PET5	28×10	12 400	1.00	0.08	—	—	—	—	—	—	1.00	3.96	—	—
PET6	39×5	10 618	1.00	0.10	—	—	—	—	—	—	0.83	6.04	—	—
PET7	50×5	16 537	1.00	0.12	—	—	—	—	—	—	1.00	7.98	—	—
WEING1	28×2	141 278	1.00	0.06	1.00	—	1.00	15.65	1.00	0.06	1.00	4.15	1.00	0.02
WEING2	28×2	130 883	1.00	0.06	1.00	—	1.00	15.74	1.00	0.07	1.00	4.27	1.00	0.04
WEING3	28×2	95 677	1.00	0.06	1.00	—	0.00	15.61	1.00	0.07	1.00	4.27	1.00	0.60
WEING4	28×2	119 337	1.00	0.06	1.00	—	1.00	15.65	1.00	0.07	1.00	4.33	1.00	0.01
WEING5	28×2	98 796	1.00	0.06	1.00	—	0.70	16.97	1.00	0.07	1.00	4.20	1.00	0.01
WEING6	28×2	130 623	1.00	0.06	1.00	—	1.00	16.75	1.00	0.06	1.00	4.13	1.00	0.02
WEING7	105×2	1 095 445	1.00	0.23	0.58	—	0.00	21.70	1.00	0.21	0.23	16.30	<1.00	5.67
WEING8	105×2	624 319	1.00	0.23	0.93	—	0.50	20.05	1.00	0.26	1.00	18.12	1.00	0.10
WEISH01	30×5	4 554	1.00	0.07	1.00	—	1.00	15.27	1.00	0.08	1.00	4.67	1.00	0.01
WEISH02	30×5	4 536	1.00	0.07	1.00	—	1.00	15.27	1.00	0.08	1.00	4.65	1.00	0.01
WEISH03	30×5	4 115	1.00	0.07	1.00	—	1.00	15.22	1.00	0.09	1.00	4.70	1.00	0.01
WEISH04	30×5	4 561	1.00	0.07	1.00	—	1.00	15.13	1.00	0.08	1.00	4.62	1.00	0.01
WEISH05	30×5	4 514	1.00	0.08	1.00	—	1.00	15.12	1.00	0.09	1.00	4.76	1.00	0.01
WEISH06	40×5	5 557	1.00	0.10	1.00	—	1.00	15.82	0.91	0.11	1.00	6.45	1.00	0.03
WEISH07	40×5	5 567	1.00	0.10	1.00	—	0.98	15.81	1.00	0.10	1.00	6 .41	1.00	0.01
WEISH08	40×5	5 605	1.00	0.10	1.00	—	0.98	15.86	1.00	0.11	1.00	6.46	1.00	0.06
WEISH09	40×5	5 246	1.00	0.10	1.00	—	1.00	15.77	1.00	0.12	1.00	6.43	1.00	0.01
WEISH10	50×5	6 339	1.00	0.13	1.00	—	1.00	16.30	1.00	0.15	1.00	8.26	1.00	0.02
WEISH11	50×5	5 643	1.00	0.13	1.00	—	0.92	16.18	1.00	0.15	1.00	7.82	1.00	0.01
WEISH12	50×5	6 339	1.00	0.12	1.00	—	0.96	16.24	1.00	0.15	1.00	7.73	1.00	0.02
WEISH13	50×5	6 159	1.00	0.13	1.00	—	0.98	16.20	1.00	0.15	1.00	7.80	1.00	0.01
WEISH14	60×5	6 954	1.00	0.15	1.00	—	0.92	16.84	1.00	0.18	1.00	9.38	1.00	0.01
WEISH15	60×5	7 486	1.00	0.15	1.00	—	0.96	16.83	1.00	0.17	1.00	9.41	1.00	0.03
WEISH16	60×5	7 289	1.00	0.15	1.00	—	1.00	16.88	1.00	0.17	1.00	9.29	1.00	0.11
WEISH17	60×5	8 633	1.00	0.14	1.00	—	1.00	17.17	1.00	0.14	1.00	9.17	1.00	0.03
WEISH18	70×5	9 580	1.00	0.17	1.00	—	0.98	17.71	1.00	0.19	1.00	10.86	1.00	0.23
WEISH19	70×5	7 698	1.00	0.18	1.00	—	0.96	17.42	1.00	0.23	1.00	13.56	1.00	0.02
WEISH20	70×5	9 450	1.00	0.17	1.00	—	0.96	17.64	1.00	0.19	1.00	10.96	1.00	0.17
WEISH21	70×5	9 074	1.00	0.17	1.00	—	0.96	17.59	1.00	0.20	1.00	12.08	1.00	0.08
WEISH22	80×5	8 947	1.00	0.20	1.00	—	0.98	17.88	1.00	0.24	1.00	12.72	1.00	0.12
WEISH23	80×5	8 344	1.00	0.20	0.45	—	0.92	17.81	1.00	0.25	1.00	12.83	1.00	0.25
WEISH24	80×5	10 220	1.00	0.19	0.54	—	0.68	18.16	1.00	0.20	1.00	12.61	1.00	0.26
WEISH25	80×5	9 939	1.00	0.19	1.00	—	0.84	18.02	1.00	0.23	1.00	12.67	1.00	0.23
WEISH26	90×5	9 584	1.00	0.23	1.00	—	0.94	18.39	1.00	0.28	1.00	14.39	1.00	0.16
WEISH27	90×5	9 819	1.00	0.23	1.00	—	0.98	18.27	1.00	0.27	1.00	14.40	1.00	0.03
WEISH28	90×5	9 492	1.00	0.23	1.00	—	0.94	18.28	1.00	0.28	1.00	14.59	1.00	0.03
WEISH29	90×5	9 410	1.00	0.23	1.00	—	0.92	18.30	1.00	0.30	1.00	14.47	1.00	0.03
WEISH30	90×5	11 191	1.00	0.22	1.00	—	0.32	18.67	1.00	0.24	1.00	14.31	1.00	0.13
SUM-SR			54		45.7		40.8		47.8		53.1		<48
AVG-AT				0.13		—		17.20		0.17		8.11		0.20

表3 6个算法求解实例G1的计算结果

Tab. 3 Calculation results of six algorithms solving instances G1

实例	n×m	Opt	IRTEA-RO4		BAAA		TR-BDS		HBDE		MA/PL		ABQPSO
实例	n×m	Opt	SR	AT	SR	AT	SR	AT	SR	AT	SR	AT	SR	AT
SENTO1	60×30	7 772	1.00	0.28	1.00	—	0.8	21.71	1.00	0.54	1.00	10.34	1.00	0.14
SENTO2	60×31	8 722	1.00	0.28	1.00	—	0.73	21.69	0.91	0.40	1.00	10.64	1.00	0.04
HP1	28×4	3 418	1.00	0.07	0.93	—	0.40	16.33	1.00	0.07	1.00	3.73	1.00	0.06
HP2	28×5	3 186	1.00	0.08	0.27	—	0.97	16.57	1.00	0.08	1.00	4.68	1.00	0.17
PB1	27×4	3 090	1.00	0.07	1.00	—	0.50	16.16	1.00	0.06	1.00	3.68	1.00	0.03
PB2	34×4	3 186	1.00	0.08	1.00	—	0.97	16.52	1.00	0.08	1.00	4.47	1.00	0.19
PB4	29×2	95 168	1.00	0.07	1.00	—	1.00	15.84	1.00	0.07	1.00	3.74	1.00	0.01
PB5	20×10	2 139	1.00	0.06	1.00	—	0.80	16.49	1.00	0.07	1.00	2.71	1.00	0.04
PB6	40×30	776	1.00	0.19	1.00	—	0.57	20.16	1.00	0.41	1.00	6.42	1.00	0.10
PB7	37×30	1 035	1.00	0.18	1.00	—	0.80	20.14	1.00	0.30	1.00	6.39	1.00	0.01
PET2	10×10	87 061	1.00	0.03	—	—	—	—	—	—	1.00	1.37	—	—
PET3	15×10	4 015	1.00	0.05	—	—	—	—	—	—	1.00	2.09	—	—
PET4	20×10	6 120	1.00	0.06	—	—	—	—	—	—	1.00	2.77	—	—
PET5	28×10	12 400	1.00	0.08	—	—	—	—	—	—	1.00	3.96	—	—
PET6	39×5	10 618	1.00	0.10	—	—	—	—	—	—	0.83	6.04	—	—
PET7	50×5	16 537	1.00	0.12	—	—	—	—	—	—	1.00	7.98	—	—
WEING1	28×2	141 278	1.00	0.06	1.00	—	1.00	15.65	1.00	0.06	1.00	4.15	1.00	0.02
WEING2	28×2	130 883	1.00	0.06	1.00	—	1.00	15.74	1.00	0.07	1.00	4.27	1.00	0.04
WEING3	28×2	95 677	1.00	0.06	1.00	—	0.00	15.61	1.00	0.07	1.00	4.27	1.00	0.60
WEING4	28×2	119 337	1.00	0.06	1.00	—	1.00	15.65	1.00	0.07	1.00	4.33	1.00	0.01
WEING5	28×2	98 796	1.00	0.06	1.00	—	0.70	16.97	1.00	0.07	1.00	4.20	1.00	0.01
WEING6	28×2	130 623	1.00	0.06	1.00	—	1.00	16.75	1.00	0.06	1.00	4.13	1.00	0.02
WEING7	105×2	1 095 445	1.00	0.23	0.58	—	0.00	21.70	1.00	0.21	0.23	16.30	<1.00	5.67
WEING8	105×2	624 319	1.00	0.23	0.93	—	0.50	20.05	1.00	0.26	1.00	18.12	1.00	0.10
WEISH01	30×5	4 554	1.00	0.07	1.00	—	1.00	15.27	1.00	0.08	1.00	4.67	1.00	0.01
WEISH02	30×5	4 536	1.00	0.07	1.00	—	1.00	15.27	1.00	0.08	1.00	4.65	1.00	0.01
WEISH03	30×5	4 115	1.00	0.07	1.00	—	1.00	15.22	1.00	0.09	1.00	4.70	1.00	0.01
WEISH04	30×5	4 561	1.00	0.07	1.00	—	1.00	15.13	1.00	0.08	1.00	4.62	1.00	0.01
WEISH05	30×5	4 514	1.00	0.08	1.00	—	1.00	15.12	1.00	0.09	1.00	4.76	1.00	0.01
WEISH06	40×5	5 557	1.00	0.10	1.00	—	1.00	15.82	0.91	0.11	1.00	6.45	1.00	0.03
WEISH07	40×5	5 567	1.00	0.10	1.00	—	0.98	15.81	1.00	0.10	1.00	6 .41	1.00	0.01
WEISH08	40×5	5 605	1.00	0.10	1.00	—	0.98	15.86	1.00	0.11	1.00	6.46	1.00	0.06
WEISH09	40×5	5 246	1.00	0.10	1.00	—	1.00	15.77	1.00	0.12	1.00	6.43	1.00	0.01
WEISH10	50×5	6 339	1.00	0.13	1.00	—	1.00	16.30	1.00	0.15	1.00	8.26	1.00	0.02
WEISH11	50×5	5 643	1.00	0.13	1.00	—	0.92	16.18	1.00	0.15	1.00	7.82	1.00	0.01
WEISH12	50×5	6 339	1.00	0.12	1.00	—	0.96	16.24	1.00	0.15	1.00	7.73	1.00	0.02
WEISH13	50×5	6 159	1.00	0.13	1.00	—	0.98	16.20	1.00	0.15	1.00	7.80	1.00	0.01
WEISH14	60×5	6 954	1.00	0.15	1.00	—	0.92	16.84	1.00	0.18	1.00	9.38	1.00	0.01
WEISH15	60×5	7 486	1.00	0.15	1.00	—	0.96	16.83	1.00	0.17	1.00	9.41	1.00	0.03
WEISH16	60×5	7 289	1.00	0.15	1.00	—	1.00	16.88	1.00	0.17	1.00	9.29	1.00	0.11
WEISH17	60×5	8 633	1.00	0.14	1.00	—	1.00	17.17	1.00	0.14	1.00	9.17	1.00	0.03
WEISH18	70×5	9 580	1.00	0.17	1.00	—	0.98	17.71	1.00	0.19	1.00	10.86	1.00	0.23
WEISH19	70×5	7 698	1.00	0.18	1.00	—	0.96	17.42	1.00	0.23	1.00	13.56	1.00	0.02
WEISH20	70×5	9 450	1.00	0.17	1.00	—	0.96	17.64	1.00	0.19	1.00	10.96	1.00	0.17
WEISH21	70×5	9 074	1.00	0.17	1.00	—	0.96	17.59	1.00	0.20	1.00	12.08	1.00	0.08
WEISH22	80×5	8 947	1.00	0.20	1.00	—	0.98	17.88	1.00	0.24	1.00	12.72	1.00	0.12
WEISH23	80×5	8 344	1.00	0.20	0.45	—	0.92	17.81	1.00	0.25	1.00	12.83	1.00	0.25
WEISH24	80×5	10 220	1.00	0.19	0.54	—	0.68	18.16	1.00	0.20	1.00	12.61	1.00	0.26
WEISH25	80×5	9 939	1.00	0.19	1.00	—	0.84	18.02	1.00	0.23	1.00	12.67	1.00	0.23
WEISH26	90×5	9 584	1.00	0.23	1.00	—	0.94	18.39	1.00	0.28	1.00	14.39	1.00	0.16
WEISH27	90×5	9 819	1.00	0.23	1.00	—	0.98	18.27	1.00	0.27	1.00	14.40	1.00	0.03
WEISH28	90×5	9 492	1.00	0.23	1.00	—	0.94	18.28	1.00	0.28	1.00	14.59	1.00	0.03
WEISH29	90×5	9 410	1.00	0.23	1.00	—	0.92	18.30	1.00	0.30	1.00	14.47	1.00	0.03
WEISH30	90×5	11 191	1.00	0.22	1.00	—	0.32	18.67	1.00	0.24	1.00	14.31	1.00	0.13
SUM-SR			54		45.7		40.8		47.8		53.1		<48
AVG-AT				0.13		—		17.20		0.17		8.11		0.20

表4 6个算法求解实例cb5.100.0~cb5.100.9的计算结果

Tab. 4 Calculation results of six algorithms solving instances cb5.100.0 - cb5.100.9

算法	指标	q
算法	指标	0	1	2	3	4	5	6	7	8	9
IRTEA-RO4	Best	*24 381*	*24 274*	*23 551*	*23 534*	*23 991*	*24 613*	*25 591*	*23 410*	*24 216*	*24 411*
	Mean	24 380.6	24 274.0	23 533.9	23 492.2	23 966.1	24 608.7	25 561.6	23 409.6	24 216.0	24 391.6
	Std	1.74	0.00	6.68	8.94	2.78	6.46	34.55	4.48	0.00	23.43
	AT	2.69	2.64	2.70	2.73	2.71	2.73	2.70	2.70	2.69	2.72
TR-BDS	Best	*24 381*	*24 274*	*23 551*	*23 534*	*23 966*	*24 613*	*25 591*	*23 410*	*24 216*	*24 411*
	Mean	24 319.0	24 214.3	23 535.9	23 534.0	23 944.6	24 539.5	25 523.8	23 356.8	24 198.2	24 311.6
	Std	—	—	—	—	—	—	—	—	—	—
	AT	—	—	—	—	—	—	—	—	—	—
BGWO	Best	*24 381*	*24 274*	<23 538	*23 534*	*23 991*	*24 613*	*25 591*	*23 410*	*24 216*	*24 411*
	Mean	24 381.0	24 270.7	23 525.5	23 494.2	23 970.1	24 608.7	25 591.0	23 369.4	24 206.8	24 406.6
	Std	—	—	—	—	—	—	—	—	—	—
	AT	—	—	—	—	—	—	—	—	—	—
HBDE	Best	*24 381*	*24 274*	<23 538	<23 534	<23 991	*24 613*	*25 591*	*23 410*	*24 216*	*24 411*
	Mean	24 378.1	24 250.4	23 490.7	23 465.0	23 953.4	24 597.9	25 522.4	23 410.0	24 187.2	24 297.0
	Std	7.66	61.01	33.44	30.54	17.50	8.97	9.80	0.00	16.63	26.88
	AT	4.53	4.47	4.78	4.85	4.67	4.56	4.61	4.64	4.71	4.86
MA/PL	Best	*24 381*	*24 274*	*23 538*	*23 534*	*23 991*	*24 613*	*25 591*	*23 410*	*24 216*	*24 411*
	Mean	24 380.7	24 274.0	23 520.0	23 486.0	23 962.4	24 588.9	25 558.3	23 376.2	24 208.4	24 371.4
	Std	1.45	0.00	14.50	16.32	7.54	31.36	34.92	35.55	5.78	45.19
	AT	16.95	16.66	16.78	17.44	16.78	16.85	16.76	17.04	16.36	17.18
ABQPSO	Best	*24 381*	*24 274*	*23 551*	*23 534*	*23 991*	*24 613*	*25 591*	*23 410*	*24 216*	*24 411*
	Mean	24 381.0	24 273.5	23 536.4	23 501.0	23 968.7	24 602.9	25 586.3	23 405.2	24 205.9	24 409.3
	Std	0.00	2.92	5.86	21.91	18.43	13.56	17.76	12.45	7.63	7.38
	AT	0.65	1.86	6.30	7.28	6.71	6.00	2.38	3.62	6.53	2.78
Opt		24 381	24 274	23 551	23 534	23 991	24 613	25 591	23 410	24 216	24 411

表5 4个算法求解实例cb5.500.0~cb5.500.9的计算结果

Tab. 5 Calculation results of four algorithms solving instances cb5.500.0 - cb5.500.9

算法	指标	q
算法	指标	0	1	2	3	4	5	6	7	8	9
IRTEA-RO4	Best	*120 148*	*117 879*	*121 131*	120 799	*122 319*	122 006	119 126	120 551	121 575	120 707
	Mean	120 099.8	117 826.0	121 100.5	120 751.3	122 286.5	121 975.5	119 084.4	120 512.7	121 541.2	120 663.9
	Std	16.64	17.87	12.86	17.83	15.81	9.97	16.75	13.62	28.24	13.63
	AT	14.23	14.06	14.10	14.09	13.96	13.95	14.02	13.95	14.02	14.08
BAAA	Best	120 066	117 702	120 951	120 572	122 231	121 957	119 070	120 472	121 052	120 499
	Mean	120 013.7	117 560.5	120 782.9	120 340.6	122 101.8	121 741.8	118 913.4	120 331.2	120 683.6	120 296.3
	Std	21.57	111.40	87.96	106.01	56.95	84.33	63.01	69.09	834.88	110.06
	AT	—	—	—	—	—	—	—	—	—	—
MA/PL	Best	—	—	—	—	—	—	—	—	—	—
	Mean	120 009.7	117 744.3	121 004.3	120 688.9	122 194.5	121 903.0	119 007.8	120 467.5	121 464.1	120 584.6
	Std	41.35	43.51	31.09	38.05	37.21	46.72	34.11	32.07	28.55	42.81
	AT	152.05	138.48	131.03	156.01	142.95	145.91	139.73	153.41	165.24	161.92
ABQPSO	Best	120 099	117 864	121 104	120 778	*122 319*	*122 024*	119 102	120 536	121 537	120 678
	Mean	120 061.1	117 790.2	121 055.9	120 711.3	122 294.3	121 958.2	119 065.7	120 496.5	121 494.9	120 645.0
	Std	21.44	26.17	26.29	25.85	17.88	24.28	24.32	24.96	24.59	19.27
	AT	324.44	386.58	441.31	491.86	376.70	390.30	427.78	457.06	456.18	393.83
Opt		120 148	117 879	121 131	120 804	122 319	122 024	119 127	120 568	121 586	120 717

表6 5个算法求解实例cb10.100.0~cb10.100.9的计算结果

Tab. 6 Calculation results of five algorithms solving instances cb10.100.0 - cb10.100.9

算法	指标	q
算法	指标	0	1	2	3	4	5	6	7	8	9
IRTEA-RO4	Best	*23 064*	*22 801*	*22 131*	*22 772*	*22 751*	22 725	*21 875*	*22 635*	*22 511*	*22 702*
	Mean	23 057.2	22 752.7	22 131.0	22 753.4	22 739.6	22 705.3	21 824.3	22 555.7	22 456.6	22 702.0
	Std	3.95	20.06	0.00	22.91	35.50	13.09	22.03	23.66	43.84	0.00
	AT	3.14	3.14	3.15	3.15	3.12	3.18	3.15	3.14	3.14	3.11
BAAA	Best	<23 064	*22 801*	*22 131*	*22 772*	*22 751*	<22 777	*21 875*	*22 635*	*22 511*	*22 702*
	Mean	23 043.3	22 750.2	22 091.1	22 645.7	22 635.3	22 711.0	21 822.2	22 530.7	22 412.9	22 650.5
	Std	—	—	—	—	—	—	—	—	—	—
	AT	17.50	17.02	13.48	17.81	14.18	17.41	13.07	17.99	19.16	15.58
HBDE	Best	<23 064	*22 801*	*22 131*	<22 772	*22 751*	<22 725	<21 875	*22 635*	*22 511*	<22 702
	Mean	23 053.9	22 735.4	22 098.2	22 693.2	22 748.4	22 593.6	21 734.5	22 550.1	22 436.9	22 471.4
	Std	7.56	51.55	32.76	43.87	17.92	45.86	63.11	20.47	46.40	37.54
	AT	6.98	6.64	6.85	6.74	6.71	6.74	6.96	6.70	6.96	6.85
MA/PL	Best	23 057	*22 801*	*22 131*	22 763	*22 751*	*22 777*	21 856	*22 635*	*22 511*	22 561
	Mean	23 046.8	22 750.7	22 105.1	22 714.0	22 726.7	22 653.9	21 804.0	22 536.7	22 508.1	22 558.2
	Std	15.82	28.17	28.10	12.44	39.59	43.92	54.43	39.08	15.80	14.90
	AT	18.04	18.63	18.97	17.01	15.86	17.29	16.00	16.28	15.43	15.84
ABQPSO	Best	23 057	*22 801*	*22 131*	*22 772*	22 697	22 725	*21 875*	22 551	*22 511*	*22 702*
	Mean	23 050.47	22 730.27	22 127.67	22 713.63	22 618	22 664.2	21 802.6	22 549.8	22 422.47	22 691.87
	Std	1.78	25.36	12.69	21.38	36.52	20.15	27.74	3.11	19.23	31.1
	AT	8.82	7.15	3.5	15.21	8.87	11.88	9.17	14.46	9.24	5.92
Opt		23 064	22 801	22 131	22 772	22 751	22 777	21 875	22 635	22 511	22 702

表7 4个算法求解实例cb10.500.0~cb10.500.9的计算结果

Tab. 7 Calculation results of four algorithms solving instances cb10.500.0 - cb10.500.9

算法	指标	q
算法	指标	0	1	2	3	4	5	6	7	8	9
IRTEA-RO4	Best	117 779	119 189	119 141	118 813	116 489	119 448	119 764	118 288	117 776	119 180
	Mean	117 711.0	119 093.7	119 071.7	118 725.9	116 405.7	119 372.0	119 711.9	118 225.3	117 692.4	119 115.4
	Std	24.33	33.15	29.26	31.39	47.70	35.18	32.93	17.54	40.77	37.26
	AT	16.66	16.41	16.64	16.45	16.89	16.52	16.58	16.70	16.71	16.63
TR-BDS	Best	114 716	119 232	*119 215*	118 813	114 687	*119 504*	116 094	116 642	114 654	114 016
	Mean	114 425.4	119 223.0	117 625.6	117 625.8	114 312.4	112 503.7	115 629.1	115 531.9	114 204.0	113 622.8
	Std	—	—	—	—	—	—	—	—	—	—
	AT	5 650.00	5 652.00	5 637.00	5 645.00	5 674.00	5 655.00	5 746.00	5 654.00	5 596.00	5 500.00
MA/PL	Best	117 628	118 974	119 055	118 680	116 289	119 318	119 658	118 121	117 634	119 086
	Mean	117 571.2	118 928.9	118 950.4	118 614.6	116 229.6	119 248.2	119 566.1	118 036.5	117 546.6	118 981.1
	Std	—	—	—	—	—	—	—	—	—	—
	AT	159.11	153.88	166.51	154.94	158.44	148.38	163.87	157.29	162.53	150.97
ABQPSO	Best	117 699	119 188	119 086	118 785	116 423	119 448	119 721	118 223	117 724	119 127
	Mean	117 638.5	119 090.6	119 004.7	118 694.3	116 349.1	119 361.9	119 668.4	118 216.4	117 667.0	119 057.6
	Std	48.42	39.43	47.69	44.52	44.55	46.51	36.00	26.17	47.63	31.54
	AT	483.72	526.51	571.64	488.35	515.56	424.14	532	500.09	394.67	504.29
Opt		117 821	119 249	119 215	118 829	116 530	119 504	119 827	118 344	117 815	119 251

表8 2个算法求解实例cb30.100.0~cb30.100.9的计算结果

Tab. 8 Calculation results of two algorithms solving instances cb30.100.0 - cb30.100.9

算法	指标	q
算法	指标	0	1	2	3	4	5	6	7	8	9
IRTEA-RO4	Best	*21 946*	*21 716*	*20 754*	*21 464*	*21 814*	*22 176*	*21 799*	21 327	22 471	*20 983*
	Mean	21 946.0	21 583.7	20 682.9	21 420.9	21 786.4	22 176.0	21 746.5	21 220.2	22 430.7	20 982.6
	Std	0.00	24.99	23.70	20.53	28.12	0.00	44.24	70.83	50.52	3.88
	AT	4.74	5.60	4.82	4.84	4.85	4.90	4.88	4.86	4.85	4.73
HBDE	Best	*21 946*	*21 716*	*20 754*	*21 464*	*21 844*	*22 176*	<21 799	<21 397	*22 493*	*20 983*
	Mean	21 910.1	21 615.1	20 689.2	21 410.6	21 754.1	22 170.4	21 746.5	21 188.2	22 415.1	20 983.0
	Std	72.07	63.60	101.19	39.10	46.01	6.86	35.31	43.80	54.37	0.00
	AT	14.12	14.08	14.79	14.29	14.68	13.85	14.11	13.76	13.95	14.17
Opt		21 946	21 716	20 754	21 464	21 844	22 176	21 799	21 397	22 493	20 983

表9 3个算法求解实例cb30.500.0~cb30.500.9的计算结果

Tab. 9 Calculation results of three algorithms solving instances cb30.500.0 - cb30.500.9

算法	指标	q
算法	指标	0	1	2	3	4	5	6	7	8	9
IRTEA-RO4	Best	115 894	114 667	116 591	115 225	116 413	115 639	113 899	114 230	115 319	116 955
	Mean	115 820.2	114 568.1	116 498.8	115 085.0	116 323.0	115 543.1	113 834.8	114 068.8	115 136.1	116 869.1
	Std	41.71	42.85	40.46	60.53	54.55	52.72	17.63	52.28	43.80	55.29
	AT	24.93	24.74	25.48	25.26	25.00	24.8	24.60	25.90	25.53	25.23
BGWO	Best	115 814	114 701	116 531	115 125	116 312	115 586	113 939	114 118	115 153	116 939
	Mean	—	—	—	—	—	—	—	—	—	—
	Std	—	—	—	—	—	—	—	—	—	—
	AT	—	—	—	—	—	—	—	—	—	—
MA/PL	Best	115 609	114 426	116 357	114 933	116 146	115 331	113 621	113 850	115 049	116 724
	Mean	115 480.7	114 299.9	116 231.3	14 815.9	116 027.4	115 150.6	113 524.5	113 683.7	114 889.3	116 595.7
	Std	—	—	—	—	—	—	—	—	—	—
	AT	214.65	214.96	215.11	199.56	215.82	216.66	209.25	195.16	199.12	160.12
Opt		116 056	114 810	116 741	115 354	116 525	115 741	114 181	114 348	115 419	117 116

表10 7个算法求得的最好Best数量

Tab. 10 Numbers of best Best values obtained by seven algorithms

算法	cb5.100	cb5.500	cb10.100	cb10.500	cb30.100	cb30.500	NB₁ vs NB₂	算法	cb5.100	cb5.500	cb10.100	cb10.500	cb30.100	cb30.500	NB₁ vs NB₂
IRTEA-RO4	10	9	9	7	8	8		HBDE	7	—	5	—	8	—	27 vs 20
BAAA	—	0	8	—	—	—	18 vs 8	MA/PL	10	—	6	0	—	—	26 vs 16
TR-BDS	10	—	—	4	—	—	17 vs 14	ABQPSO	10	2	6	0	—	—	35 vs 18
BGWO	9	—	—	—	—	2	18 vs 11

图3 7个算法求解实例G2的Friedman检验

Fig. 3 Friedman test of seven algorithms solving instances G2

表11 5个算法求得的最好Std数量

Tab. 11 Numbers of best Std values obtained by five algorithms

算法	cb5.100	cb5.500	cb10.100	cb10.500	cb30.100	cb30.500	NS₁ vs NS₂	算法	cb5.100	cb5.500	cb10.100	cb10.500	cb30.100	cb30.500	NS₁ vs NS₂
IRTEA-RO4	5	9	5	8	7	10		MA/PL	1	0	2	—	—	—	20 vs 3
BAAA	—	0	—	—	—	—	9 vs 0	ABQPSO	3	1	1	9	—	—	27 vs 14
HBDE	2	—	2	—	3	—	18 vs 7

参考文献 24

1	KELLERER H， PFERSCHY U， PISINGER D. Knapsack problems［M］. Berlin： Springer， 2004.
2	NAWROCKI J R， COMPLAK W， BŁAŻEWICZ J， et al. The knapsack-lightening problem and its application to scheduling HRT tasks［J］. Bulletin of the Polish Academy of Sciences： Technical Sciences， 2009， 57（1）： 71-77.
3	BEAUJON G J， MARIN S P， McDONALD G C. Balancing and optimizing a portfolio of R&D projects［J］. Naval Research Logistics， 2001， 48（1）： 18-40.
4	WU C， WANG X， LIN J. Optimizations in project scheduling： a state-of-art survey［M］// XU H， WANG X. Optimization and control methods in industrial engineering and construction， ISCA 72. Dordrecht： Springer， 2014： 161-177.
5	BALEV S， YANEV N， FRÉVILLE A， et al. A dynamic programming based reduction procedure for the multidimensional 0‑1 knapsack problem［J］. European Journal of Operational Research， 2008， 186（1）： 63-76.
6	SHIH W. A branch and bound method for the multiconstraint zero-one knapsack problem［J］. Journal of the Operational Research Society， 1979， 30（4）： 369-378.
7	HANAFI S， FREVILLE A. An efficient tabu search approach for the 0-1 multidimensional knapsack problem［J］. European Journal of Operational Research， 1998， 106（2/3）： 659-675.
8	VASQUEZ M， HAO J K. A hybrid approach for the 0-1 multidimensional knapsack problem［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers Inc.， 2001： 328-333.
9	LAI X， HAO J K， GLOVER F， et al. A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem［J］. Information Sciences， 2018， 436/437： 282-301.
10	LAI X， HAO J K， FU Z H， et al. Diversity-preserving quantum particle swarm optimization for the multidimensional knapsack problem［J］. Expert Systems with Applications， 2020， 149： No.113310.
11	ZHANG X， WU C， LI J， et al. Binary artificial algae algorithm for multidimensional knapsack problems［J］. Applied Soft Computing， 2016， 43： 583-595.
12	LIU J， WU C， CAO J， et al. A binary differential search algorithm for the 0-1 multidimensional knapsack problem［J］. Applied Mathematical Modelling， 2016， 40（23/24）： 9788-9805.
13	LUO K， ZHAO Q. A binary grey wolf optimizer for the multidimensional knapsack problem［J］. Applied Soft Computing， 2019， 83： No.105645.
14	HE Y C， ZHANG X L， LI W B， et al. An efficient binary differential evolution algorithm for the multidimensional knapsack problem［J］. Engineering with Computers， 2021， 37： 745-761.
15	LI Z， TANG L， LIU J. A memetic algorithm based on probability learning for solving the multidimensional knapsack problem［J］. IEEE Transactions on Cybernetics， 2020， 52（4）： 2284-2299.
16	LI X， FANG W， ZHU S， et al. An adaptive binary quantum-behaved particle swarm optimization algorithm for the multidimensional knapsack problem［J］. Swarm and Evolutionary Computation， 2024， 86： No.101494.
17	HE Y， WANG X， GAO S. Ring Theory-Based Evolutionary Algorithm and its application to D｛0-1｝KP［J］. Applied Soft Computing， 2019， 77： 714-722.
18	耿素云，屈婉玲，王捍贫. 离散数学教程［M］. 北京：北京大学出版社， 2002： 285.
	GENG S Y， QU W L， WANG H P. Discrete mathematics course［M］. Beijing： Peking University Press， 2002： 285.
19	CHU P C， BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem［J］. Journal of Heuristics， 1998， 4： 63-86.
20	ZHANG B， PAN Q K， ZHANG X L， et al. An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems［J］. Applied Soft Computing， 2015， 29： 288-297.
21	王凌，王圣尧，方晨. 一种求解多维背包问题的混合分布估计算法［J］. 控制与决策， 2011， 26（8）： 1121-1125.
	WANG L， WANG S Y， FANG C. A hybrid distribution estimation algorithm for solving multidimensional knapsack problem［J］. Control and Decision， 2011， 26（8）： 1121-1125.
22	WANG L， WANG S Y， XU Y. An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem［J］. Expert Systems with Applications， 2012， 39（5）： 5593-5599.
23	张寒崧，贺毅朝，王静红，等. 增强型群论优化算法求解折扣｛0-1｝背包问题［J］. 计算机科学与探索， 2024， 18（6）： 1526-1542.
	ZHANG H S， HE Y C， WANG J H， et al. Enhanced group theory-based optimization algorithm for solving discounted ｛0-1｝ knapsack problem［J］. Journal of Frontiers of Computer Science and Technology， 2024， 18（6）： 1526-1542.
24	DERRAC J， GARCÍA S， MOLINA D， et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］. Swarm and Evolutionary Computation， 2011， 1（1）： 3-18.

[1]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[2]	张晶, 吴虎胜. 改进二进制布谷鸟搜索算法求解多维背包问题[J]. 计算机应用, 2015, 35(1): 183-188.
[3]	倪晚成刘连臣吴澄. 网格工作流中基于商品市场的服务选择[J]. 计算机应用, 2007, (12): 2973-2975.

基于新修复优化算子的改进环论优化算法求解多维背包问题

Improved ring theory-based evolutionary algorithm with new repair optimization operator for solving multi-dimensional knapsack problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 24

相关文章 3

编辑推荐

Metrics