机会约束的多选择背包问题的遗传算法求解

doi:10.11772/j.issn.1001-9081.2024010113

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1378-1385.DOI: 10.11772/j.issn.1001-9081.2024010113

所属专题：进化计算专题（2024年第5期“进化计算专题”导读，全文已上线）

机会约束的多选择背包问题的遗传算法求解

李炫锋¹^,², 刘晟材¹(), 唐珂¹^,²

^1.南方科技大学计算机科学与工程系，广东深圳 518055
^2.南方科技大学斯发基斯可信自主系统研究院，广东深圳 518055

收稿日期:2024-01-31 接受日期:2024-02-21 发布日期:2024-04-26 出版日期:2024-05-10
通讯作者: 刘晟材
作者简介:李炫锋（1995—），男，广西钦州人，博士研究生，主要研究方向：机会约束优化
唐珂（1981—），男，湖北武汉人，教授，博士，主要研究方向：演化计算、机器学习。
第一联系人：刘晟材（1992—），男，重庆人，副教授，博士，主要研究方向：组合优化、自动算法配置
基金资助:
国家重点研发计划项目(2022YFA1004102)

Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems

Xuanfeng LI¹^,², Shengcai LIU¹(), Ke TANG¹^,²

^1.Department of Computer Science and Engineering，Southern University of Science and Technology，Shenzhen Guangdong 518055，China
^2.Research Institute of Trustworthy Autonomous Systems，Southern University of Science and Technology，Shenzhen Guangdong 518055，China

Received:2024-01-31 Accepted:2024-02-21 Online:2024-04-26 Published:2024-05-10
Contact: Shengcai LIU
About author:LI Xuanfeng， born in 1995， Ph. D. candidate. His research interests include chance-constrained optimization.
TANG Ke， born in 1981， Ph. D.， professor. His research interests include evolutionary computation， machine learning.
Supported by:
National Key Research and Development Program of China(2022YFA1004102)

摘要/Abstract

摘要：

机会约束的多选择背包问题（CCMCKP）是一类具有重要应用价值的NP难组合优化问题，但目前还缺乏关于该问题求解方法的专门研究。为此，提出首个CCMCKP的求解框架，并基于该框架构建了两种求解方法：基于动态规划的RA-DP和基于遗传算法的RA-IGA。RA-DP是精确求解方法，具有最优性保证，但是在可接受的时间（1 h）内仅能求解小规模问题样例；相较而言，RA-IGA是近似求解方法，具有更好的可扩放性。仿真实验结果验证了所提求解方法的性能：在小规模问题样例上，RA-DP和RA-IGA都可以找到最优解；在中大规模问题样例上，RA-IGA表现出了比RA-DP显著更高的求解效率，它总是可以在给定时间（1 h）内快速获得可行解。在CCMCKP的后续研究中，RA?DP和RA-IGA可作为基准对比方法，而实验工作中所构建的测试样例集可作为该问题的标准测试集。

关键词: 组合优化问题, 机会约束的多选择背包问题, 遗传算法, 动态规划, 精确算法, 近似算法

Abstract:

Chance-Constrained Multi-Choice Knapsack Problem （CCMCKP） is a class of NP-hard combinatorial optimization problems with important practical applications. However， there is a lack of research on the solution methods for this problem. The first framework for solving CCMCKP was proposed for this problem， and two solution methods were established based on this framework， including the dynamic programming-based method RA-DP and the genetic algorithm-based method RA-IGA. RA-DP is an exact method with optimality guarantee， but it can only solve small-scale problem instances within a time budget of 1 hour. In contrast， RA-IGA is an approximation method with better scalability. Simulation experimental results verify the performance of the proposed methods. On small-scale problem instances， both RA-DP and RA-IGA can find the optimal solutions. On the medium- and large-scale problem instances， RA-IGA exhibits significantly higher efficiency than RA-DP， always obtaining feasible solutions quickly within 1 hour. In future research on CCMCKP， RA-DP and RA-IGA can be considered as baseline methods， and the benchmark set considered in this work can also be used as a standard benchmark test set.

Key words: combinatorial optimization problem, Chance-Constrained Multi-Choice Knapsack Problem (CCMCKP), Genetic Algorithm (GA), dynamic programming, exact algorithm, approximation algorithm

中图分类号:

TP301.6

李炫锋, 刘晟材, 唐珂. 机会约束的多选择背包问题的遗传算法求解[J]. 计算机应用, 2024, 44(5): 1378-1385.

Xuanfeng LI, Shengcai LIU, Ke TANG. Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems[J]. Journal of Computer Applications, 2024, 44(5): 1378-1385.

图/表 9

参考文献 26

1	KELLERER H， PFERSCHY U， PISINGER D. The multiple-choice knapsack problem［M］// Knapsack Problems. Berlin： Springer， 2004： 317-347. 10.1007/978-3-540-24777-7_11
2	SHARKEY T C， ROMEIJN H E， GEUNES J. A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems［J］. Mathematical Programming， 2011， 126（1）： 69-96. 10.1007/s10107-009-0274-9
3	TAAFFE K， GEUNES J， ROMEIJN H E. Target market selection and marketing effort under uncertainty： the selective newsvendor［J］. European Journal of Operational Research， 2008， 189（3）： 987-1003. 10.1016/j.ejor.2006.11.049
4	NAUSS R M. The 0-1 knapsack problem with multiple choice constraints［J］. European Journal of Operational Research， 1978， 2（2）： 125-131. 10.1016/0377-2217(78)90108-x
5	KWONG C K， MU L F， TANG J F， et al. Optimization of software components selection for component-based software system development［J］. Computers & Industrial Engineering， 2010， 58（4）： 618-624. 10.1016/j.cie.2010.01.003
6	SINHA A， ZOLTNERS A A. The multiple-choice knapsack problem［J］. Operations Research， 1979， 27（3）： 503-515. 10.1287/opre.27.3.503
7	KOZANIDIS G， MELACHRINOUDIS E， SOLOMON M M. The linear multiple choice Knapsack problem［J］. Operations Research Letters， 1979， 8（2）： 95-100.
8	DYER M E， KAYAL N， WALKER J. A branch and bound algorithm for solving the multiple-choice knapsack problem［J］. Journal of Computational & Applied Mathematics， 1984， 11（2）：231-249. 10.1016/0377-0427(84)90023-2
9	KRZYSZTOF DUDZIŃSKI， WALUKIEWICZ S. Exact methods for the knapsack problem and its generalizations［J］. European Journal of Operational Research， 1987， 28（1）： 3-21. 10.1016/0377-2217(87)90165-2
10	GENS G， LEVNER E V. An approximate binary search algorithm for the multiple-choice knapsack problem［J］. Information Processing Letters， 1998， 67（5）： 261-265. 10.1016/s0020-0190(98)00115-x
11	HIFI M， MICHRAFY M， SBIHI A. A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem［J］. Computational Optimization & Applications， 2006， 33（2）： 271-285. 10.1007/s10589-005-3057-0
12	NASRALLAH A， THYAGATURU A S， ALHARBI Z， et al. Ultra-Low Latency （ULL） networks： the IEEE TSN and IETF DetNet standards and related 5G ULL research［J］. IEEE Communications Surveys & Tutorials， 2018， 21（1）： 88-145. 10.1109/comst.2018.2869350
13	DELAGE E， MANNOR S. Percentile optimization for Markov decision processes with parameter uncertainty［J］. Operations Research， 2010， 58（1）： 203-213. 10.1287/opre.1080.0685
14	DOERR B， DOERR C， NEUMANN A， et al. Optimization of chance-constrained submodular functions［C］// Proceedings of the 34th AAAI Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2020：1460-1467. 10.1609/aaai.v34i02.5504
15	SHAPIRO A， DENTCHEVA D， RUSZCZYЙSKI A. Lectures on Stochastic Programming： Modeling and Theory［M/OL］. ［S.l.］： SIAM， 2009 ［2023-11-09］. . 10.1137/1.9780898718751
16	KLEINBERG J， RABANI Y， TARDOS É. Allocating bandwidth for bursty connections［J］. SIAM Journal Computing， 2000， 30（1）： 191-217. 10.1137/s0097539797329142
17	GOEL A， INDYK P. Stochastic load balancing and related problems［C］// Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Washington， DC： IEEE Computer Society， 1999： 579-586.
18	GOYAL V， RAVI R. A PTAS for the chance-constrained knapsack problem with random item sizes［J］. Operations Research Letters， 2010， 38（3）： 161-164. 10.1016/j.orl.2010.01.003
19	CHAI R， SAVVARIS A， TSOURDOS A， et al. Solving trajectory optimization problems in the presence of probabilistic constraints［J］. IEEE Transactions on Cybernetics， 2020， 50（10）： 4332-4345. 10.1109/tcyb.2019.2895305
20	ZHANG X， MA J， CHENG Z， et al. Trajectory generation by chance-constrained nonlinear MPC with probabilistic prediction［J］. IEEE Transactions on Cybernetics， 2021， 51（7）： 3616-3629. 10.1109/tcyb.2020.3032711
21	YANG F， CHAKRABORTY N. Algorithm for optimal chance constrained knapsack problem with applications to multi-robot teaming［C］// Proceedings of the 2018 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2018： 1043-1049. 10.1109/icra.2018.8461040
22	LI X， LIU S， WANG J， et al. Chance-constrained multiple-choice knapsack problem： model， algorithms， and applications［EB/OL］. ［2023-11-15］. .
23	TANG K， LIU S， YANG P， et al. Few-shots parallel algorithm portfolio construction via co-evolution［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（3）： 595-607. 10.1109/tevc.2021.3059661
24	LIU S， TANG K， YAO X. Memetic search for vehicle routing with simultaneous pickup-delivery and time windows［J］. Swarm and Evolutionary Computation， 2021， 66： 100927. 10.1016/j.swevo.2021.100927
25	LIU S， ZHANG Y， TANG K， et al. How good is neural combinatorial optimization？ A systematic evaluation on the traveling salesman problem［J］. IEEE Computational Intelligence Magazine， 2023， 18（3）： 14-28. 10.1109/mci.2023.3277768
26	刘晟材，杨鹏，唐珂.近似最优并行算法组智能汇聚构造［J］.中国科学：技术科学，2023，53：280-290. 10.1360/sst-2021-0372
	LIU S C， YANG P， TANG K. Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence［J］. SCIENTIA SINICA Technologica， 2023， 53： 280-290. 10.1360/sst-2021-0372

样例		W	Brute-force	RA-DP			RA-IGA
样例		W	Cost	Cost	Runtime	RA times	Cost	Runtime	RA times
小规模	m=3， N=3	6 210.8	252.944 3	252.944 3（0）	0.011 921（0）	3（0）	252.944 3（0）	4.440 889（0）	3.0（0）
	m=3， N=5	4 919.9	285.937 8	285.937 8（0）	0.013 110（0.001）	3（0）	285.937 8（0）	4.601 127（0）	3.0（0）
	m=3， N=10	3 646.8	211.918 6	211.918 6（0）	0.009 135（0）	1（0）	211.918 6（0）	1.831 504（0）	1.0（0）
	m=3， N=20	3 812.9	281.236 6	281.236 6（0）	0.026 805（0.001）	3（0）	281.236 6（0）	7.465 148（0）	3.0（0）
	m=5， N=3	8 315.3	572.689 9	572.689 9（0）	0.016 865（0.001）	4（0）	572.689 9（0）	7.188 246（0）	4.0（0）
	m=5， N=5	7 629.6	408.884 2	408.884 2（0）	0.031 710（0.001）	7（0）	408.884 2（5.7）	12.540 500（0）	7.0（0）
	m=5， N=10	6 743.0	380.126 0	380.126 0（0）	0.025 071（0.001）	3（0）	380.126 0（0）	6.170 371（0）	3.0（0）
	m=5， N=20	6 070.4	311.030 7	311.030 7（0）	0.038 182（0.002）	3（0）	311.030 7（0）	9.147 092（0）	3.0（0）
中规模	m=10， N=3	19 094.4	936.723 5	936.723 5（0）	0.022 837（0.001）	3（0）	936.723 5（0）	15.158 180（0）	3.0（0）
	m=10， N=5	16 431.4	749.652 8	749.652 8（0）	0.081 501（0.009）	3（0）	749.652 8（0）	15.840 780（0）	3.0（0）
	m=10， N=10	13 278.5	—	778.559 2（0）	0.606 485（0.012）	3（0）	778.559 2（0）	20.257 980（0）	3.0（0）
	m=10， N=20	11 807.6	—	648.779 7（0）	1.796 385（0.052）	8（0）	653.021 4（0.079）	64.724 050（0）	7.0（1.55）
	m=20， N=3	33 404.2	—	1 560.820 0（0）	0.598 593（0.016）	3（0）	1 560.820 0（0）	19.851 520（0）	3.0（0）
	m=20， N=5	30 608.0	—	1 647.302 0（0）	22.490 890（0.267）	3（0）	1 647.302 0（0）	30.879 680（0）	3.8（0.4）
	m=20， N=10	26 362.0	—	1 400.262 0（0）	927.749 000（1.227）	4（0）	1 400.250 0（2.81）	25.725 420（0）	3.0（0）
	m=20， N=20	24 027.1	—	—	—	—	1 249.669 0（4.33）	35.472 280（0）	3.0（0）
	m=30， N=10	37 851.2	—	—	—	—	2 205.289 0（2.98）	36.073 440（0）	3.2（0.4）
	m=30， N=20	36 520.4	—	—	—	—	1 755.243 0（1.47）	50.546 630（0）	3.2（0.4）
	m=50， N=10	63 168.1	—	—	—	—	3 276.099 0（1.56）	222.494 000（0）	5.0（0.49）
	m=50， N=20	58 517.1	—	—	—	—	3 138.925 0（1.72）	237.129 000（0）	3.6（0.49）
大规模	m=100， N=10	122 523.6	—	—	—	—	6 908.194 0（2.53）	356.178 500（0）	4.6（1.02）
	m=100， N=20	114 579.3	—	—	—	—	6 458.782 0（9.67）	470.785 900（0）	3.6（0.5）
	m=100， N=50	110 990.4	—	—	—	—	5 566.828 0（5.35）	860.830 500（0）	3.2（0.4）

样例		W	Brute-force	RA-DP			RA-IGA
样例		W	Cost	Cost	Runtime	RA times	Cost	Runtime	RA times
小规模	m=3， N=3	6 210.8	252.944 3	252.944 3（0）	0.011 921（0）	3（0）	252.944 3（0）	4.440 889（0）	3.0（0）
	m=3， N=5	4 919.9	285.937 8	285.937 8（0）	0.013 110（0.001）	3（0）	285.937 8（0）	4.601 127（0）	3.0（0）
	m=3， N=10	3 646.8	211.918 6	211.918 6（0）	0.009 135（0）	1（0）	211.918 6（0）	1.831 504（0）	1.0（0）
	m=3， N=20	3 812.9	281.236 6	281.236 6（0）	0.026 805（0.001）	3（0）	281.236 6（0）	7.465 148（0）	3.0（0）
	m=5， N=3	8 315.3	572.689 9	572.689 9（0）	0.016 865（0.001）	4（0）	572.689 9（0）	7.188 246（0）	4.0（0）
	m=5， N=5	7 629.6	408.884 2	408.884 2（0）	0.031 710（0.001）	7（0）	408.884 2（5.7）	12.540 500（0）	7.0（0）
	m=5， N=10	6 743.0	380.126 0	380.126 0（0）	0.025 071（0.001）	3（0）	380.126 0（0）	6.170 371（0）	3.0（0）
	m=5， N=20	6 070.4	311.030 7	311.030 7（0）	0.038 182（0.002）	3（0）	311.030 7（0）	9.147 092（0）	3.0（0）
中规模	m=10， N=3	19 094.4	936.723 5	936.723 5（0）	0.022 837（0.001）	3（0）	936.723 5（0）	15.158 180（0）	3.0（0）
	m=10， N=5	16 431.4	749.652 8	749.652 8（0）	0.081 501（0.009）	3（0）	749.652 8（0）	15.840 780（0）	3.0（0）
	m=10， N=10	13 278.5	—	778.559 2（0）	0.606 485（0.012）	3（0）	778.559 2（0）	20.257 980（0）	3.0（0）
	m=10， N=20	11 807.6	—	648.779 7（0）	1.796 385（0.052）	8（0）	653.021 4（0.079）	64.724 050（0）	7.0（1.55）
	m=20， N=3	33 404.2	—	1 560.820 0（0）	0.598 593（0.016）	3（0）	1 560.820 0（0）	19.851 520（0）	3.0（0）
	m=20， N=5	30 608.0	—	1 647.302 0（0）	22.490 890（0.267）	3（0）	1 647.302 0（0）	30.879 680（0）	3.8（0.4）
	m=20， N=10	26 362.0	—	1 400.262 0（0）	927.749 000（1.227）	4（0）	1 400.250 0（2.81）	25.725 420（0）	3.0（0）
	m=20， N=20	24 027.1	—	—	—	—	1 249.669 0（4.33）	35.472 280（0）	3.0（0）
	m=30， N=10	37 851.2	—	—	—	—	2 205.289 0（2.98）	36.073 440（0）	3.2（0.4）
	m=30， N=20	36 520.4	—	—	—	—	1 755.243 0（1.47）	50.546 630（0）	3.2（0.4）
	m=50， N=10	63 168.1	—	—	—	—	3 276.099 0（1.56）	222.494 000（0）	5.0（0.49）
	m=50， N=20	58 517.1	—	—	—	—	3 138.925 0（1.72）	237.129 000（0）	3.6（0.49）
大规模	m=100， N=10	122 523.6	—	—	—	—	6 908.194 0（2.53）	356.178 500（0）	4.6（1.02）
	m=100， N=20	114 579.3	—	—	—	—	6 458.782 0（9.67）	470.785 900（0）	3.6（0.5）
	m=100， N=50	110 990.4	—	—	—	—	5 566.828 0（5.35）	860.830 500（0）	3.2（0.4）

样例		W	Brute-force	RA-DP			RA-IGA
样例		W	Cost	Cost	Runtime	RA times	Cost	Runtime	RA times
小规模	m=3， N=3	6 511.6	225.402 4	225.402 4（0）	0.006 805（0）	1（0）	225.402 4（0）	1.496 704（0.003）	1.0（0）
	m=3， N=5	5 404.8	244.009 6	244.009 6（0）	0.013 297（0.001）	3（0）	244.009 6（0）	4.404 947（0.03）	3.0（0）
	m=3， N=10	4 255.6	211.918 6	211.918 6（0）	0.017 788（0.001）	3（0）	211.918 6（0）	5.281 897（0.117）	3.0（0）
	m=3， N=20	4 457.0	232.910 2	232.910 2（0）	0.026 463（0.001）	3（0）	232.910 2（0）	6.587 724（0.012）	3.0（0）
	m=5， N=3	8 875.6	488.236 7	488.236 7（0）	0.013 904（0.001）	3（0）	488.236 7（0）	4.960 898（0.09）	3.0（0）
	m=5， N=5	8 455.2	367.126 9	367.126 9（0）	0.020 507（0.001）	4（0）	367.126 9（0）	6.508 796（0.09）	4.0（0）
	m=5， N=10	7 742.4	316.725 9	316.725 9（0）	0.024 883（0.001）	3（0）	316.725 9（0）	5.719 294（0.115）	3.0（0）
	m=5， N=20	7 137.8	300.920 7	300.920 7（0）	0.041 647（0.002）	3（0）	300.920 7（0）	7.764 045（0.078）	3.0（0）
中规模	m=10， N=3	20 135.8	866.683 9	866.683 9（0）	0.023 867（0.003）	3（0）	866.683 9（0）	13.909 810（0.157）	3.0（0）
	m=10， N=5	17 953.8	716.727 4	716.727 4（0）	0.112 159（0.01）	3（0）	716.727 4（3.36）	14.131 290（0.167）	3.0（0）
	m=10， N=10	15 133.0	—	698.237 5（0）	3.125 697（0.064）	3（0）	698.237 5（0）	18.484 650（0.265）	3.0（0）
	m=10， N=20	14 023.2	—	581.904 3（0）	3.338 666（0.057）	3（0）	581.904 3（0）	21.694 380（0.369）	3.0（0）
	m=20， N=3	35 975.4	—	1 474.784 0（0）	1.989 371（0.075）	4（0）	1 478.826 0（0）	20.743 580（2.802）	3.4（0）
	m=20， N=5	33 709.0	—	1 480.981 0（0）	121.308 200（1.19）	3（0）	1 487.644 0（3.642）	25.387 000（4.776）	3.4（0.49）
	m=20， N=10	30 172.0	—	—	—	—	1 251.546 0（0）	23.164 330（0.683）	3.0（0）
	m=20， N=20	28 366.2	—	—	—	—	1 163.822 0（0）	30.721 970（0.845）	3.0（0）
	m=30， N=10	43 617.4	—	—	—	—	1 993.904 0（1.048）	35.150 780（3.684）	3.8（0.4）
	m=30， N=20	42 890.8	—	—	—	—	1 667.808 0（0.996）	35.517 990（0.401）	3.0（0）
	m=50， N=10	72 851.2	—	—	—	—	3 045.043 0（1.872）	122.939 200（17.901）	3.4（0.49）
	m=50， N=20	69 339.2	—	—	—	—	2 917.159 0（2.487）	189.324 600（28.74）	3.4（0.49）
大规模	m=100， N=10	141 964.2	—	—	—	—	6 241.125 0（6.52）	217.603 400（28.87）	3.2（0.4）
	m=100， N=20	136 463.6	—	—	—	—	5 881.865 0（17.86）	302.502 800（5.134）	3.0（0）
	m=100， N=50	133 984.8	—	—	—	—	5 363.524 0（5.97）	569.733 500（14.88）	3.0（0）

样例		W	Brute-force	RA-DP			RA-IGA
样例		W	Cost	Cost	Runtime	RA times	Cost	Runtime	RA times
小规模	m=3， N=3	6 511.6	225.402 4	225.402 4（0）	0.006 805（0）	1（0）	225.402 4（0）	1.496 704（0.003）	1.0（0）
	m=3， N=5	5 404.8	244.009 6	244.009 6（0）	0.013 297（0.001）	3（0）	244.009 6（0）	4.404 947（0.03）	3.0（0）
	m=3， N=10	4 255.6	211.918 6	211.918 6（0）	0.017 788（0.001）	3（0）	211.918 6（0）	5.281 897（0.117）	3.0（0）
	m=3， N=20	4 457.0	232.910 2	232.910 2（0）	0.026 463（0.001）	3（0）	232.910 2（0）	6.587 724（0.012）	3.0（0）
	m=5， N=3	8 875.6	488.236 7	488.236 7（0）	0.013 904（0.001）	3（0）	488.236 7（0）	4.960 898（0.09）	3.0（0）
	m=5， N=5	8 455.2	367.126 9	367.126 9（0）	0.020 507（0.001）	4（0）	367.126 9（0）	6.508 796（0.09）	4.0（0）
	m=5， N=10	7 742.4	316.725 9	316.725 9（0）	0.024 883（0.001）	3（0）	316.725 9（0）	5.719 294（0.115）	3.0（0）
	m=5， N=20	7 137.8	300.920 7	300.920 7（0）	0.041 647（0.002）	3（0）	300.920 7（0）	7.764 045（0.078）	3.0（0）
中规模	m=10， N=3	20 135.8	866.683 9	866.683 9（0）	0.023 867（0.003）	3（0）	866.683 9（0）	13.909 810（0.157）	3.0（0）
	m=10， N=5	17 953.8	716.727 4	716.727 4（0）	0.112 159（0.01）	3（0）	716.727 4（3.36）	14.131 290（0.167）	3.0（0）
	m=10， N=10	15 133.0	—	698.237 5（0）	3.125 697（0.064）	3（0）	698.237 5（0）	18.484 650（0.265）	3.0（0）
	m=10， N=20	14 023.2	—	581.904 3（0）	3.338 666（0.057）	3（0）	581.904 3（0）	21.694 380（0.369）	3.0（0）
	m=20， N=3	35 975.4	—	1 474.784 0（0）	1.989 371（0.075）	4（0）	1 478.826 0（0）	20.743 580（2.802）	3.4（0）
	m=20， N=5	33 709.0	—	1 480.981 0（0）	121.308 200（1.19）	3（0）	1 487.644 0（3.642）	25.387 000（4.776）	3.4（0.49）
	m=20， N=10	30 172.0	—	—	—	—	1 251.546 0（0）	23.164 330（0.683）	3.0（0）
	m=20， N=20	28 366.2	—	—	—	—	1 163.822 0（0）	30.721 970（0.845）	3.0（0）
	m=30， N=10	43 617.4	—	—	—	—	1 993.904 0（1.048）	35.150 780（3.684）	3.8（0.4）
	m=30， N=20	42 890.8	—	—	—	—	1 667.808 0（0.996）	35.517 990（0.401）	3.0（0）
	m=50， N=10	72 851.2	—	—	—	—	3 045.043 0（1.872）	122.939 200（17.901）	3.4（0.49）
	m=50， N=20	69 339.2	—	—	—	—	2 917.159 0（2.487）	189.324 600（28.74）	3.4（0.49）
大规模	m=100， N=10	141 964.2	—	—	—	—	6 241.125 0（6.52）	217.603 400（28.87）	3.2（0.4）
	m=100， N=20	136 463.6	—	—	—	—	5 881.865 0（17.86）	302.502 800（5.134）	3.0（0）
	m=100， N=50	133 984.8	—	—	—	—	5 363.524 0（5.97）	569.733 500（14.88）	3.0（0）

样例		W	Brute-force	RA-DP			RA-IGA
样例		W	Cost	Cost	Runtime	RA times	Cost	Runtime	RA times
小规模	m=3，N=3	6 210.8	225.402 361	225.402 4（0）	0.011 504（0.001）	3（0）	225.402 4（0）	4.061 699（0.12）	3（0）
	m=3，N=5	4 919.9	213.812 352	213.812 4（0）	0.007 470（0）	1（0）	213.812 4（0）	1.334 633（0.01）	1（0）
	m=3， N=10	3 646.8	167.374 351	167.374 4（0）	0.018 105（0.001）	3（0）	167.374 4（0）	4.388 657（0.197）	3（0）
	m=3，N=20	3 812.9	197.276 079	197.276 1（0）	0.026 889（0.001）	3（0）	197.276 1（0）	4.097 674（0.04）	3（0）
	m=5，N=3	8 315.3	337.421 212	337.421 2（0）	0.013 903（0.001）	3（0）	337.421 2（0）	3.957 431（0.049）	3（0）
	m=5， N=5	7 629.6	325.310 233	325.310 2（0）	0.008 587（0）	1（0）	325.310 2（0）	1.350 837（0.051）	1（0）
	m=5，N=10	6 743.0	304.449 708	304.449 7（0）	0.011 846（0）	1（0）	304.449 7（0）	1.400 598（0.055）	1（0）
	m=5，N=20	6 070.4	289.356 396	289.356 4（0）	0.017 734（0.001）	1（0）	289.356 4（0）	1.524 389（0.044）	1（0）
中规模	m=10，N=3	19 094.4	768.379 257	768.379 3（0）	0.054 093（0.004）	3（0）	768.379 3（0）	12.853 330（0.446）	3（0）
	m=10，N=5	16 431.4	626.774 623	626.774 6（0）	0.181 477（0.011）	3（0）	626.774 6（0）	12.707 540（1.095）	3（0）
	m=10，N=10	13 278.5	—	615.346 8（0）	9.177 558（0.136）	3（0）	615.346 8（0）	13.945 870（0.39）	3（0）
	m=10，N=20	11 807.6	—	537.386 5（0）	2.250 868（0.063）	1（0）	537.386 5（0）	4.520 560（0.077）	1（0）
	m=20，N=3	33 404.2	—	1 362.727 0（0）	0.485 046（0.017）	1（0）	1 362.727 0（0）	4.632 803（0.06）	1（0）
	m=20，N=5	30 608.0	—	1 293.604 0（0）	647.675 000（19.89）	3（0）	1 293.604 0（0）	14.596 230（0.119）	3（0）
	m=20，N=10	26 362.0	—	—	—	—	1 139.965 0（2.78）	17.903 570（0.36）	3（0）
	m=20，N=20	24 027.1	—	—	—	—	1 098.458 0（0）	5.443 564（0.049）	1（0）
	m=30，N=10	37 851.2	—	—	—	—	1 793.509 0（0.75）	18.670 320（0.317）	3（0）
	m=30，N=20	36 520.4	—	—	—	—	1 620.478 0（1.63）	20.122 130（0.22）	3（0）
	m=50，N=10	63 168.1	—	—	—	—	2 871.462 0（0）	24.468 380（0.27）	1（0）
	m=50，N=20	58 517.1	—	—	—	—	2 718.846 0（0.407）	97.803 120（1.85）	3（0）
大规模	m=100，N=10	122 523.6	—	—	—	—	5 768.800 0（0）	36.257 020（0.327）	1（0）
	m=100，N=20	114 579.3	—	—	—	—	5 448.920 0（0.33）	134.249 200（3.00）	3（0）
	m=100，N=50	110 990.4	—	—	—	—	5 205.552 0（2.689）	55.963 040（0.48）	1（0）

机会约束的多选择背包问题的遗传算法求解

Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 26

相关文章 15

编辑推荐

Metrics

样例	W	Repair	Without repair
m=10， N=5	17 920	715.58	716.73
m=20， N=20	24 027	1 249.02	1 253.33
m=100， N=10	122 523	6 909.72	6 912.81
m=100， N=50	110 990	5 574.68	5 599.71

[1]	刘栋, 李晨航, 吴长茂, 茹法鑫, 夏媛媛. 基于可校正强化搜索遗传算法的光学系统自动设计[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2838-2847.
[2]	高麟, 周宇, 邝得互. 进化双层自适应局部特征选择[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1408-1414.
[3]	佘维, 李阳, 钟李红, 孔德锋, 田钊. 基于改进实数编码遗传算法的神经网络超参数优化[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 671-676.
[4]	徐兰天, 李荣华, 戴永恒, 王国仁. 面向超图的极大团搜索算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2319-2324.
[5]	梁军, 洪泽泓, 余松森. 基于改进粒子群优化算法和遗传变异的图像分割模型[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1743-1749.
[6]	王彬, 向甜, 吕艺东, 王晓帆. 基于NSGA‑Ⅱ的自适应多尺度特征通道分组优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1401-1408.
[7]	张敏, 韩晓龙. 多目标模糊机会约束规划的低碳多式联运路径优化[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 636-644.
[8]	薛海蓉, 韩晓龙. 基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3848-3855.
[9]	邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3833-3839.
[10]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[11]	刘延飞, 彭征, 王艺辉, 王忠. 基于改进的遗传算法的有刷直流电机PID参数整定[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1634-1641.
[12]	李晓寒, 贾华丁, 程雪, 李太勇. 基于改进遗传算法和图神经网络的股市波动预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1624-1633.
[13]	陈浩杰, 范江亭, 刘勇. 深度强化学习解决动态旅行商问题[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1194-1200.
[14]	陈权, 李莉, 陈永乐, 段跃兴. 面向深度学习可解释性的对抗攻击算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 510-518.
[15]	刘忠慧, 王梓宥, 闵帆. 近似概念的遗传生成算法及其推荐应用[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 412-418.