Limiting index sort – A new non-dominated sorting algorithm and its comparison to the state-of-the-art

PDF

Authors
  1. Mazurek, M.
  2. Wesolkowski, S.
Corporate Authors
Defence R&D Canada - Centre for Operational Research and Analysis, Ottawa ON (CAN)
Abstract
An important problem in the realm of evolutionary multi-objective optimization (MOO) is that of finding all non-dominated fronts (NDFs). We specifically address the computational efficiency of the non-dominated sorting algorithm for finding the non-dominated fronts for the non-dominated sorting genetic algorithm II (NSGA-II) algorithm. We introduce the Limiting Index Sort (LIS) algorithm which improves on the existing state-of-the-art algorithm for datasets which are positively correlated or uncorrelated. LIS indexes individuals based on their scores in each objective, and intelligently iterates through the index to limit the number of comparisons required between individuals. LIS also makes use of a stopping condition, allowing it to exclude some individuals from the skyline without comparing them to any other individuals. LIS was compared to two other state-of-the-art non-dominated sorting algorithms, the Sort and Limit Skyline Algorithm (SaLSa), and the Divide-and-Conquer (D&C) approach. LIS outperformed SaLSa in all tests, and it outperformed D&C when sorting individuals with positively correlated or uncorrelated objective scores, except for sorting large, uncorrelated, datasets on many objectives. LIS outperformed D&C for sorting small, negatively correlated datasets on three or five objectives. By understanding the appropriate non-dominated sorting algorithm to use in different situations, NSGA-II can be utilized more efficiently for MOO. This will allow optimizatio

Il y a un résumé en français ici.

Keywords
Non-dominated Sorting;LIS;Limiting;Index;Sort;Multi-objective Optimization;NSGA-II;Non-dominated fronts;NDFs;Sort and Limit Skyline Algorithm;SaLSa;Divide-and-Conquer
Report Number
DRDC-CORA-TM-2010-097 — Technical Memorandum
Date of publication
01 May 2010
Number of Pages
55
DSTKIM No
CA035110
CANDIS No
534554
Format(s):
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: