Empirical Analysis of Using Weighted Sum Fitness Functions in NSGA-II for Many-Objective 0/1 Knapsack Problems

摘要

Handling of many-objective problems is a hot issue in the evolutionary multiobjective optimization (EMO) community. It is well-known that frequently-used EMO algorithms such as NSGA-II and SPEA do not work well on many-objective problems whereas they have been successfully applied to a large number of test problems and real-world application tasks with two or three objectives. The main difficulty in the handling of many-objective problems is that almost all solutions in the current population of an EMO algorithm are non-dominated with each other. This means that Pareto dominance relation cannot generate enough selection pressure toward the Pareto front. As a result, Pareto dominance-based EMO algorithms such as NSGA-II and SPEA cannot drive the current population toward the Pareto front efficiently in a high-dimensional objective space of a many-objective problem. A simple idea for introducing additional selection pressure toward the Pareto front is the use of scalarizing fitness functions. In this paper, we examine the effect of using weighted sum fitness functions for parent selection and generation update on the performance of NSGA-II for many-objective 0/1 knapsack problems.