摘要
针对0-1背包问题的数学特征,设计了相应离散算法进行求解。算法在基本正弦余弦算法的框架内,首先采用实数编码进行个体初始化,并设计非线性指数递减函数根据迭代深度调节个体更新步长,借用贪婪修复算子对不可行解进行修复及优化。算法性能采用2组大规模的0-1背包问题进行测试,并通过与同类新兴算法的对比表明,本算法高效、简洁,不仅为0-1背包问题提供了高效率的解决方案,还拓展了正弦余弦算法的应用领域。
According to the mathematical characteristics of the 0-1 knapsack problem(0-1 KP),this paper redesigns a discrete version of SCA(DSCA)for 0-1 KP.Within the framework of basic SCA,DSCA uses the real code to generate initial individuals,a new nonlinear exponential decreasing function is applied to adjust the individual update step size.A greedy-based repair operator is included to fix and optimize the infeasible solution.The performance of the improved algorithm was tested on two sets of large-scale 0-1 KP.The comparison with some state-of-arts algorithms confirms that DSCA is efficient and concise,not only can it provide an effective solution for 0-1 KP,but also it expands the application fields of SCA.
作者
郑健
ZHENG Jian(Meizhouwan Vocational Technology College,Putian 351119,Fujian,China)
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2020年第11期87-95,共9页
Journal of Shandong University(Natural Science)
基金
福建省莆田市科技计划项目(2019GM003)。
关键词
0-1背包问题
正弦余弦算法
群智能
组合优化
0-1 knapsack problem
sine cosine algorithm
swarm intelligence
combination optimization
