南方科技大学知识苑(SUSTech KC): 机会约束的多选择背包问题的遗传算法求解

题名	机会约束的多选择背包问题的遗传算法求解
其他题名	Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems
作者	李炫锋1 ; 刘晟材 ; 唐珂1
发表日期	2024
DOI	10.11772/j.issn.1001-9081.2024010113
发表期刊	计算机应用影响因子和分区
ISSN	1001-9081
卷号	44 期号:5页码:1378-1385
摘要	机会约束的多选择背包问题(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可作为基准对比方法,而实验工作中所构建的测试样例集可作为该问题的标准测试集.
关键词	组合优化问题机会约束的多选择背包问题遗传算法动态规划精确算法近似算法
相关链接	[万方记录]
语种	中文
学校署名	第一
来源库	WanFang
万方记录号	jsjyy202405008
引用统计
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/788214
专题	工学院_计算机科学与工程系南方科技大学
作者单位	1.南方科技大学计算机科学与工程系,广东深圳 518055;南方科技大学斯发基斯可信自主系统研究院,广东深圳 518055 2.南方科技大学计算机科学与工程系,广东深圳 518055
第一作者单位	计算机科学与工程系
第一作者的第一单位	计算机科学与工程系
推荐引用方式 GB/T 7714	李炫锋,刘晟材,唐珂. 机会约束的多选择背包问题的遗传算法求解[J]. 计算机应用,2024,44(5):1378-1385.
APA	李炫锋,刘晟材,&唐珂.(2024).机会约束的多选择背包问题的遗传算法求解.计算机应用,44(5),1378-1385.
MLA	李炫锋,et al."机会约束的多选择背包问题的遗传算法求解".计算机应用 44.5(2024):1378-1385.