摘要
为了有效求解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.
出处
《计算机工程与设计》
CSCD
北大核心
2010年第8期1795-1798,共4页
Computer Engineering and Design
基金
国家自然科学基金项目(70771037
50705039)
江西省教育厅科技基金项目(GJJ09347)
关键词
0-1背包问题
二进制差异演化
映射操作
S型变换操作
逆映射操作
贪婪变换
0-1 knapsack problem
binary differential evolution
mapping operation
S transform operation
inverse mapping operation
greedy transform