mk:emo07

Summary

Substitute Distance Assignments in NSGA-II for Handling Many-Objective Optimization Problems. Mario Köppen and Kaori Yoshida. In Evolutionary Multi-Criterion Optimization, 4th International Conference, EMO 2007, Matsushima, Japan, March 2007. Proceedings, pages 727-741, 2007.

Abstract

Many-objective optimization refers to optimization problems with a number of objectives considerably larger than two or three. In this paper, a study on the performance of the Fast Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) for handling such many-objective optimization problems is presented. In its basic form, the algorithm is not well suited for the handling of a larger number of objectives. The main reason for this is the decreasing probability of having Pareto-dominated solutions in the initial external population. To overcome this problem, substitute distance assignment schemes are proposed that can replace the crowding distance assignment, which is normally used in NSGA-II. These distances are based on measurement procedures for the highest degree, to which a solution is nearly Pareto-dominated by any other solution: like the number of smaller objectives, the magnitude of all smaller or larger objectives, or a multi-criterion derived from the former ones. For a number of many-objective test problems, all proposed substitute distance assignments resulted into a strongly improved performance of the NSGA-II.

Bibtex entry

@INPROCEEDINGS { mk:emo07,
    ABSTRACT = { Many-objective optimization refers to optimization problems with a number of objectives considerably larger than two or three. In this paper, a study on the performance of the Fast Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) for handling such many-objective optimization problems is presented. In its basic form, the algorithm is not well suited for the handling of a larger number of objectives. The main reason for this is the decreasing probability of having Pareto-dominated solutions in the initial external population. To overcome this problem, substitute distance assignment schemes are proposed that can replace the crowding distance assignment, which is normally used in NSGA-II. These distances are based on measurement procedures for the highest degree, to which a solution is nearly Pareto-dominated by any other solution: like the number of smaller objectives, the magnitude of all smaller or larger objectives, or a multi-criterion derived from the former ones. For a number of many-objective test problems, all proposed substitute distance assignments resulted into a strongly improved performance of the NSGA-II. },
    AUTHOR = { Mario Köppen and Kaori Yoshida },
    BOOKTITLE = { Evolutionary Multi-Criterion Optimization, 4th International Conference, EMO 2007, Matsushima, Japan, March 2007. Proceedings },
    ADDED = { 2007-04-06 14:05:35 +0900 },
    MODIFIED = { 2008-02-28 11:16:27 +0900 },
    EDITOR = { Shigeru Obayashi and Kalyanmoy Deb and Carlo Poloni and Tomoyuki Hiroyasu and Tadahiko Murata },
    HASABSTRACT = { Yes },
    PAGES = { 727-741 },
    PDF = { emo07.pdf },
    PUBLISHER = { Springer Berlin, Heidelberg },
    SERIES = { LNCS 4403 },
    TITLE = { Substitute Distance Assignments in NSGA-II for Handling Many-Objective Optimization Problems },
    YEAR = { 2007 },
}