Towards Large-Scale Multiobjective Optimisation with a Hybrid Algorithm for Non-dominated Sorting

Margarita Markina, Maxim Buzdalov

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

Abstract

We present an algorithm for non-dominated sorting that is suitable for large-scale multiobjective optimisation. This algorithm is a hybrid of two previously known algorithms: the divide-and-conquer algorithm initially proposed by Jensen, and the non-dominated tree algorithm proposed by Gustavsson and Syberfeldt. While possessing the good worst-case asymptotic behaviour of the divide-and-conquer algorithm, the proposed algorithm is also very efficient in practice. In our experimental study it is shown to outperform both of its parents on the majority of problem instances, both sampled uniformly from a hypercube and having a single front, with as large as 10^6 points and up to 15 objectives
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XV
Subtitle of host publication15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
EditorsAnne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luís Paquete, Darrell Whitley
PublisherSpringer Nature
Pages347-358
Number of pages12
ISBN (Electronic)978-3-319-99253-2, 3319992538
ISBN (Print)331999252X, 978-3319992525
DOIs
Publication statusPublished - 22 Aug 2018
Externally publishedYes
Event15th International Conference - Parallel Problem Solving from Nature - PPSN XV - Coimbra, Portugal
Duration: 08 Sept 201812 Sept 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume11101
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference - Parallel Problem Solving from Nature - PPSN XV
Country/TerritoryPortugal
CityCoimbra
Period08 Sept 201812 Sept 2018

Keywords

  • multiobjective optimisation
  • non-dominated sorting
  • large-scale optimisation

Fingerprint

Dive into the research topics of 'Towards Large-Scale Multiobjective Optimisation with a Hybrid Algorithm for Non-dominated Sorting'. Together they form a unique fingerprint.

Cite this