一类0-1背包问题的分枝定界DAPSO启发式算法

Branch and bound-DAPSO heuristic algorithm for solving a class of 0-1 knapsack problems

目的更好地求解一类非线性0-1背包问题,给出计算性能较好的分枝定界-DAPSO启发式算法。方法通过求解线性规划松弛问题来确定最优值的下界,用改进的粒子群优化算法(DAPSO)确定最优值的上界和好的可行解,分枝过程是简单的0-1变量分枝。结果与结论数值结果表明分枝定界-DAPSO启发式算法更好于分枝定界算法,并且它克服了粒子群优化算法(PSO)收敛性的困难。

Purposes-To propose a branch and bound-DAPSO heuristic algorithm for solving a class of nonlinear 0-1knapsack problems.Methods-In aforesaid algorithm,the lower bound of the optimal value was determined by solving linear programming relaxation.Meanwhile,the upper bound of the optimal value and good feasible solutions were determined with a new particle swarm optimization( DAPSO),and the branching was the one of simple 0-1variables.Result and Conclusion-The numerical results show that the branch and bound-DAPSO heuristic algorithm is not only better than the branch and bound algorithm but also overcomes the convergent difficulty of particle swarm optimization( PSO).