Accelerating MOEA Non-dominated Sorting by Preserving Archival Relationships.

摘要

Non-dominated sorting is an important part of many multi-objective evolutionary algorithms (MOEAs). It is used to determine which individuals to keep in the archive of best individuals between generations and to evaluate fitness for breeding. Because this sorting is performed after every generation, it can contribute significantly to the running time of an MOEA. If the population size is sufficiently large, the time spent sorting the population can come to dominate an MOEA's running time.;The non-dominated sorting algorithms in the literature propose optimizations that focus on skipping unnecessary comparisons among individuals. While these algorithms provide different means for skipping these comparisons, none of them have considered adding mechanisms to preserve knowledge of relationships among the individuals from the archive that was sorted in an MOEA's previous generation. Considering that the primary use for nondominated sorting algorithms is in MOEAs, this seems a gross oversight.;In this thesis, I propose three new algorithms can accept partially, internally sorted populations: the Non-dominated Insertion Sort (NIS), the Non-dominated Merge Sort (NMS), and the Modified Dominance Tree Sort (MDTS). The strengths and weaknesses against each other and the algorithms in the literature are explored by testing how they impact the running time of the well-known MOEA NSGA-II [1] on several multi-objective problems (MOPs) and constrained optimization problems (COPs).