Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (5): 1378-1385.DOI: 10.11772/j.issn.1001-9081.2024010113

Special Issue: 进化计算专题(2024年第5期“进化计算专题”导读,全文已上线)

• Special issue on evolutionary calculation • Previous Articles     Next Articles

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

Xuanfeng LI1,2, Shengcai LIU1(), Ke TANG1,2   

  1. 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)

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

李炫锋1,2, 刘晟材1(), 唐珂1,2   

  1. 1.南方科技大学 计算机科学与工程系,广东 深圳 518055
    2.南方科技大学 斯发基斯可信自主系统研究院,广东 深圳 518055
  • 通讯作者: 刘晟材
  • 作者简介:李炫锋(1995—),男,广西钦州人,博士研究生,主要研究方向:机会约束优化
    唐珂(1981—),男,湖北武汉人,教授,博士,主要研究方向:演化计算、机器学习。
    第一联系人:刘晟材(1992—),男,重庆人,副教授,博士,主要研究方向:组合优化、自动算法配置
  • 基金资助:
    国家重点研发计划项目(2022YFA1004102)

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

摘要:

机会约束的多选择背包问题(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可作为基准对比方法,而实验工作中所构建的测试样例集可作为该问题的标准测试集。

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

CLC Number: