离散正弦余弦算法求解大规模0-1背包问题

Discrete sine cosine algorithm for solving large-scale 0-1 knapsack problems

针对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.