A faster algorithm for the binary epsilon indicator based on orthant minimum search

Andrey Vasin, Maxim Buzdalov

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

Abstract

The binary ε-indicator is often used to assess the quality of solutions in multiobjective optimization, and to perform optimization as well. It is normally evaluated using a straightforward θ(nmk) algorithm, where n and m are the number of solutions in the arguments, and k is the number of objectives. This is considered to be fast compared to, for example, the hypervolume indicator, which is #P-hard. However, there are efficient algorithms for the latter, especially for small values of k, while the ε-indicator evaluation is too slow already for n,m > 104 and for any k.

We present an efficient algorithm to compute the value of the binary ε-indicator. It reduces the problem to a series of orthant minimum searches, which are solved by an appropriate algorithm. For the latter, we consider two implementations: the one based on a dynamic tree data structure, and the one based on the divide-and-conquer technique. In both cases, evaluation of the binary ε-indicator takes O((n+m)k(log(n+m))max(1, k-2)) time. Empirical evaluation shows that the second implementation has a better performance than the first one, and both of them outperform the naive algorithm for large enough values of n.

Original languageEnglish
Title of host publicationGECCO 2016
Subtitle of host publicationProceedings of the 2016 Genetic and Evolutionary Computation Conference
EditorsTobias Friedrich, Frank Neumann, Andrew M. Sutton
PublisherAssociation for Computing Machinery, Inc
Pages613-620
Number of pages8
ISBN (Electronic)9781450342063
DOIs
Publication statusPublished - 20 Jul 2016
Externally publishedYes
Event2016 Genetic and Evolutionary Computation Conference, GECCO 2016 - Denver, United States of America
Duration: 20 Jul 201624 Jul 2016

Publication series

NameGECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

Conference

Conference2016 Genetic and Evolutionary Computation Conference, GECCO 2016
Country/TerritoryUnited States of America
CityDenver
Period20 Jul 201624 Jul 2016

Keywords

  • Divide-and-conquer
  • E-indicator
  • Multiobjective optimization
  • Orthant search
  • Performance evaluation
  • Range search

Fingerprint

Dive into the research topics of 'A faster algorithm for the binary epsilon indicator based on orthant minimum search'. Together they form a unique fingerprint.

Cite this