Fast Implementation of the Steady-State NSGA-II Algorithm for Two Dimensions Based on Incremental Non-Dominated Sorting

Maxim Buzdalov, Ilya Yakupov, Andrey Stankevich

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

Abstract

Genetic algorithms (GAs) are widely used in multi-objective optimization for solving complex problems. There are two distinct approaches for GA design: generational and steady-state algorithms. Most of the current state-of-the-art GAs are generational, although there is an increasing interest to steady-state algorithms as well. However, for algorithms based on non-dominated sorting, most of steady-state implementations have higher computation complexity than their generational counterparts, which limits their applicability. We present a fast implementation of a steady-state version of the NSGA-II algorithm for two dimensions. This implementation is based on a data structure which has O(N) complexity for single solution insertion and deletion in the worst case. The experimental results show that our implementation works noticeably faster than steady-state NSGA-II implementations which use fast non-dominated sorting.
Original languageEnglish
Title of host publicationGECCO '15
Subtitle of host publicationProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
EditorsSara Silva
PublisherAssociation for Computing Machinery
Pages647-654
Number of pages8
ISBN (Print)978-1-4503-3472-3
DOIs
Publication statusPublished - 11 Jul 2015
Externally publishedYes
Event16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain
Duration: 11 Jul 201515 Jul 2015

Conference

Conference16th Genetic and Evolutionary Computation Conference, GECCO 2015
Country/TerritorySpain
CityMadrid
Period11 Jul 201515 Jul 2015

Keywords

  • incremental updates
  • multi-objective
  • non-dominated sorting
  • nsga-ii
  • steady-state

Fingerprint

Dive into the research topics of 'Fast Implementation of the Steady-State NSGA-II Algorithm for Two Dimensions Based on Incremental Non-Dominated Sorting'. Together they form a unique fingerprint.

Cite this