[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2908812.2908951acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article
Open access

A Faster Algorithm for the Binary Epsilon Indicator Based on Orthant Minimum Search

Published: 20 July 2016 Publication History

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.

References

[1]
A. Auger, J. Bader, D. Brockhoff, and E. Zitzler. Theory of the hypervolume indicator: Optimal μ-distributions and the choice of the reference point. In Proceedings of Foundations of Genetic Algorithms, pages 87--102. ACM, 2009.
[2]
A. Auger, J. Bader, D. Brockhoff, and E. Zitzler. Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications. Theoretical Computer Science, 425:75--103, 2012.
[3]
J. Bader and E. Zitzler. HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 19(1):45--76, 2011.
[4]
K. Bringmann and T. Friedrich. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. In Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization, pages 6--20, 2009.
[5]
M. Buzdalov and A. Shalyto. A provably asymptotically fast version of the generalized Jensen algorithm for non-dominated sorting. In Parallel Problem Solving from Nature -- PPSN XIII, number 8672 in Lecture Notes in Computer Science, pages 528--537. Springer, 2014.
[6]
P. M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3):327--336, 1994.
[7]
F.-A. Fortin, S. Grenier, and M. Parizeau. Generalizing the improved run-time complexity algorithm for non-dominated sorting. In Proceedings of Genetic and Evolutionary Computation Conference, pages 615--622. ACM, 2013.
[8]
H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 135--143, 1984.
[9]
M. T. Jensen. Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms. Transactions on Evolutionary Computation, 7(5):503--515, 2003.
[10]
R. Lacour, K. Klamroth, and C. M. Fonseca. A box decomposition algorithm to compute the hypervolume indicator. http://arxiv.org/abs/1510.01963, 2015.
[11]
A. J. Nebro and J. J. Durillo. On the effect of applying a steady-state selection scheme in the multi-objective genetic algorithm NSGA-II. In Nature-Inspired Algorithms for Optimisation, number 193 in Studies in Computational Intelligence, pages 435--456. Springer Berlin Heidelberg, 2009.
[12]
Y. Nekrich. A fast algorithm for three-dimensional layers of maxima problem. In Algorithms and Data Structures, number 6844 in Lecture Notes in Computer Science, pages 607--618. 2011.
[13]
L. Russo and A. Francisco. Quick hypervolume. IEEE Transactions on Evolutionary Computation, 18(4), 2014.
[14]
P. Van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99--127, 1976.
[15]
E. Zitzler and S. Künzli. Indicator-based selection in multiobjective search. In Parallel Problem Solving from Nature -- PPSN VIII, number 3242 in Lecture Notes in Computer Science, pages 832--842. 2004.
[16]
E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: A comparative case study and the Strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257--271, 1999.
[17]
E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. Grunert da Fonseca. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117--132, 2003.

Cited By

View all
  • (2019)Generalized incremental orthant searchProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326880(1357-1365)Online publication date: 13-Jul-2019
  • (2018)Generalized offline orthant searchProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205469(593-600)Online publication date: 2-Jul-2018

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016
July 2016
1196 pages
ISBN:9781450342063
DOI:10.1145/2908812
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. divide-and-conquer
  2. epsilon indicator
  3. multiobjective optimization
  4. orthant search
  5. performance evaluation
  6. range search

Qualifiers

  • Research-article

Funding Sources

  • Government of Russian Federation

Conference

GECCO '16
Sponsor:
GECCO '16: Genetic and Evolutionary Computation Conference
July 20 - 24, 2016
Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)37
  • Downloads (Last 6 weeks)4
Reflects downloads up to 01 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Generalized incremental orthant searchProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326880(1357-1365)Online publication date: 13-Jul-2019
  • (2018)Generalized offline orthant searchProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205469(593-600)Online publication date: 2-Jul-2018

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media