Behavior of Multiobjective Evolutionary Algorithms on Many-Objective Knapsack Problems

Abstract

We examine the behavior of three classes of evolutionary multiobjective optimization (EMO) algorithms on many-objective knapsack problems. They are Pareto dominance-based, scalarizing function-based, and hypervolume-based algorithms. NSGA-II, MOEA/D, SMS-EMOA, and HypE are examined using knapsack problems with 2-10 objectives. Our test problems are generated by randomly specifying coefficients (i.e., profits) in objectives. We also generate other test problems by combining two objectives to create a dependent or correlated objective. Experimental results on randomly generated many-objective knapsack problems are consistent with well-known performance deterioration of Pareto dominance-based algorithms. That is, NSGA-II is outperformed by the other algorithms. However, it is also shown that NSGA-II outperforms the other algorithms when objectives are highly correlated. MOEA/D shows totally different search behavior depending on the choice of a scalarizing function and its parameter value. Some MOEA/D variants work very well only on two-objective problems while others work well on many-objective problems with 4-10 objectives. We also obtain other interesting observations such as the performance improvement by similar parent recombination and the necessity of diversity improvement for many-objective knapsack problems.