How well do multi-objective evolutionary algorithms scale to large problems

In spite of large amount of research work in multi-objective evolutionary algorithms, most have evaluated their algorithms on problems with only two to four objectives. Little has been done to understand the performance of the multi-objective evolutionary algorithms on problems with a larger number of objectives. It is unclear whether the conclusions drawn from the experiments on problems with a small number of objectives could be generalised to those with a large number of objectives. In fact, some of our preliminary work [1] has indicated that such generalisation may not be possible. This paper first presents a comprehensive set of experimental studies, which show that the performance of multi-objective evolutionary algorithms, such as NSGA-II and SPEA2, deteriorates substantially as the number of objectives increases. NSGA-II, for example, did not even converge for problems with six or more objectives. This paper analyses why this happens and proposes several new methods to improve the convergence of NSGA-II for problems with a large number of objectives. The proposed methods categorise members of an archive into small groups (non-dominated solutions with or without domination), using dominance relationship between the new and existing members in the archive. New removal strategies are introduced. Our experimental results show that the proposed methods clearly outperform NSGA-II in terms of convergence. © 2007 IEEE.