基于区域分割的差分进化算法求解0-1背包问题
The Differential Evolution Algorithm Based on Domain Partition for Solving 0-1 Knapsack Proble

为了更有效地求解0-1背包问题,提出了基于区域分割的差分进化算法(PDE).为保证变异算子的封闭性,对传统差分进化算法(DE)的变异算子进行了修改.引入区域分割算法以后,解空间中一些没有希望的点被移除,缩小了最优解的搜索范围,增加了找到最优解的概率.将区域分割和贪婪算法相结合,用搜索到的最好解替换了种群中目标函数值最差的个体,保证了种群的多样性.数值实验表明:该算法比文献中的DE算法更稳健,全局搜索能力更强,能以更大的概率找到背包问题的最优解.
In order to solve the 0-1 knapsack problems more effectively, a new differential evolution algorithm based on domain partition method is proposed. The mutation operator of traditional differential evolution algorithm (DE) is modified to guarantee the closure of mutation operation. With the domain partition method introduced in and some hopeless points removed off, the searching field of the optimal solution is reduced. Accordingly, the probability of finding the optimal solution is improved. To ensure the diversity of population, the solution with the least object function value is replaced by the best feasible solution found by the domain partition method combined with greedy method. Numerical experiments show that the new algorithm is of more robustness, of better global searching ability, and of greater probability to find the optimal solution of knapsack problem than those algorithms mentioned in the literatures