An evolutionary lagrangian method for the 0/1 multiple knapsack problem

摘要

We propose a new evolutionary approach to solve the 0/1 multiple knapsack problem. We approach the problem from a new viewpoint different from traditional methods. The most remarkable feature is the Lagrangian method. Lagrange multipliers transform the problem, keeping the optimality as well as decreasing the complexity. However, it is not easy to find Lagrange multipliers nearest to the constraints of the problem. We propose an evolution strategy to find the optimal Lagrange multipliers. Also, we improve the evolution strategy by adjusting its objective function properly. We show the efficiency of the proposed methods by the experiments. We make comparisons with existing general approach on well-known benchmark data.