Handling of overlapping objective vectors in evolutionary multiobjective optimization

Article from - International Journal of Computational Intelligence Research Year : 2005, Volume : 1, Issue : 1

Ishibuchi Hisao*, Narukawa Kaname†, Nojima Yusuke‡
Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Sakai, Osaka 599-8531, Japan

Recently a number of evolutionary multiobjective optimization (EMO) algorithms have been proposed to find a variety of well-distributed Pareto-optimal or near Pareto-optimal solutions with a wide range of objective values. We focus on the handling of overlapping objective vectors in the objective space.

First we show that there exist a large number of overlapping objective vectors in each population when EMO algorithms are applied to multiobjective combinatorial optimization problems with only a few objectives. We discuss the number of overlapping objective vectors from a viewpoint of the diversity-convergence balance in the objective space.

Next we implement two strategies to handle overlapping objective vectors. One strategy is the removal of overlapping objective vectors (i.e., overlapping solutions in the objective space). In this strategy, overlapping objective vectors are removed during the generation update phase except for only a single solution among them. As a result, each solution in the next population has a different location in the objective space. The other strategy is the removal of overlapping decision vectors (i.e., overlapping solutions in the decision space) so that each solution in the next population has a different location in the decision space.

In this strategy, the next population may include overlapping objective vectors because different solutions in the decision space are not necessarily different in the objective space. Finally we examine the effect of each strategy on the performance of EMO algorithms through computational experiments on multiobjective 0/1 knapsack problems.