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

针对0-1背包问题的数学特征,设计了相应离散算法进行求解。算法在基本正弦余弦算法的框架内,首先采用实数编码进行个体初始化,并设计非线性指数递减函数根据迭代深度调节个体更新步长,借用贪婪修复算子对不可行解进行修复及优化。算法性能采用2组大规模的0-1背包问题进行测试,并通过与同类新兴算法的对比表明,本算法高效、简洁,不仅为0-1背包问题提供了高效率的解决方案,还拓展了正弦余弦算法的应用领域。

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

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.