混合二进制差异演化算法解0-1背包问题

Hybrid binary differential evolution algorithm for 0-1 knapsack problem

为了有效求解0-1背包问题,提出一种混合二进制差异演化算法。该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题。此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解。不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性。

In order to solve the 0-1 knapsack problem effectively, hybrid binary differential evolution algorithm is proposed. Firstly, the algorithm are added to the original differential evolution based on the original differential evolution with binary coding and three new operations which are mapping operation, S transform operation and inverse mapping operation, The three new operations extend the original differential evolution from the continuous field to discrete field by successfully solving the no closure problem which the original differential evolution leads. Additionally, the greedy transform method is used to change the infeasible solution which violates the constraints into the feasible one. The results of 0-1 knapsack problems with different sizes solving by the hybrid binary differential evolution show it is effective and useful.