MOEA/D with Uniform Design for the Multiobjective 0/1 Knapsack Problem

摘要

The 0/1 knapsack problem is a well known problem occurring in many real world problems. The problem is NP-complete. The multiobjective 0/1 knapsack problem is a generalization of the 0/1 knapsack problem in which multiple knapsacks are considered. A new version of MOEA/D for solving multiobjective 0/1 knapsack problem is proposed in this paper. This algorithm adopts the uniform design method to generate the aggregation coefficient vectors so that the decomposed scalar optimization sub problems are uniformly scattered, and therefore the algorithm could explore uniformly the region of interest from the initial iteration. Experimental results demonstrate that the proposed algorithm outperforms NSGA-II, SPEA2 and PESA significantly for the 2-objective, 3-objective and 4-objective benchmark knapsack problems.