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

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

作　　者：李炫锋 刘晟材 唐珂 LI Xuanfeng;LIU Shengcai;TANG Ke(Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen Guangdong 518055,China;Research Institute of Trustworthy Autonomous Systems,Southern University of Science and Technology,Shenzhen Guangdong 518055,China)

机构地区：[1]南方科技大学计算机科学与工程系,广东深圳518055 [2]南方科技大学斯发基斯可信自主系统研究院,广东深圳518055

出　　处：《计算机应用》2024年第5期1378-1385,共8页journal of Computer Applications

基　　金：国家重点研发计划项目(2022YFA1004102)。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]