On the complexity of computing the hypervolume indicator
Authors
Abstract
The goal of multi-objective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multi-objective optimizers providing them, unary quality measures are usually applied. Among these,the hypervolume indicator (or S-metric) is of particular relevance due to its favorable properties. Moreover, this indicator has been successfully integrated into stochastic
optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for finding good approximations to the Pareto front. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee's Measure Problem. In general, Klee's Measure Problem can be solved with O(n log n+n^(d/2) log n) comparisons for an input instance of size n in d dimensions; as of this writing, it is unknown whether a lower bound higher than \\omega(n log n) can be proven. In this article, we derive a lower bound of O(n log n) for the complexity of computing the hypervolume indicator in any number of dimensions d > 1 by reducing the so-called
UNIFORMGAP problem to it. For the three dimensional case, we also present a matching upper bound of O(n log n) comparisons that is obtained by extending an algorithm
for finding the maxima of a point set.
Journal
IEEE Transactions on Evolutionary Computation, Vol. 13, #5, pp. 1075-1082, October 2009DOI
Cited by
Year 2015 : 28 citations
Sen Bong Gee; Kay Chen Tan; Vui Ann Shim; Pal, N.R., "Online Diversity Assessment in Evolutionary Multiobjective Optimization: A Geometrical Perspective," in Evolutionary Computation, IEEE Transactions on , vol.19, no.4, pp.542-559, Aug. 2015
doi: 10.1109/TEVC.2014.2353672
Ran Cheng; Yaochu Jin; Narukawa, K.; Sendhoff, B., "A Multiobjective Evolutionary Algorithm Using Gaussian Process-Based Inverse Modeling," in Evolutionary Computation, IEEE Transactions on , vol.19, no.6, pp.838-856, Dec. 2015
doi: 10.1109/TEVC.2015.2395073
Dimo Brockhoff, Tobias Wagner, and Heike Trautmann, "2 Indicator-Based Multiobjective Search", Evolutionary Computation 2015 23:3, 369-395
Leonardo C. T. Bezerra , Manuel López-Ibáñez, Thomas Stützle, "Comparing Decomposition-Based and Automatically Component-Wise Designed Multi-Objective Evolutionary Algorithms," Evolutionary Multi-Criterion Optimization2015,
Volume 9018 of the series Lecture Notes in Computer Science pp 396-410.
T. Barthélémy, S. N. Parragh and F. Tricoire, Beam search for integer multi-objective
optimization, Working paper, 2015. http://www.optimization-online.org/DB_FILE/2015/04/4879.pdf
JS Angelo, HS Bernardino, HJC Barbosa, Ant colony approaches for multiobjective structural optimization problems with a cardinality constraint, Advances in Engineering Software Volume 80, February 2015, Pages 101–115
A Bayesian Approach to Portfolio Selection in Multicriteria Group Decision Making
MTM Emmerich, AH Deutz, I Yevseyeva
Procedia Computer Science, 2015
Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm
M Rajabi-Bahaabadi, A Shariat-Mohaymany,
Expert Systems with Applications, 2015
Cost to Evaluate Versus Cost to Learn? Performance of Selective Evaluation Strategies in Multiobjective Optimization
KS Bhattacharjee, T Ray
AI 2015: Advances in Artificial Intelligence, 2015
Faster exact algorithms for computing expected hypervolume improvement
I Hupkens, A Deutz, K Yang, M Emmerich
Evolutionary Multi-Criterion Optimization, 2015
Performance of a steady state quantum genetic algorithm for multi/many-objective engineering optimization problems
Asafuddoula, M. ; Ray, T. ; Isaacs, A. ; Singh, H.K.
Evolutionary Computation (CEC),
Selective evaluation in multiobjective optimization: A less explored avenue
KS Bhattacharjee, T Ray -
Evolutionary Computation (CEC), 2015
A new uniform evolutionary algorithm based on decomposition and CDAS for many-objective optimization
D Cai, W Yuping
Knowledge-Based Systems 2015
Performance metrics in multi-objective optimization
Riquelme, Nery; von Lucken, Christian ; Baran, Benjamin
Computing Conference (CLEI), 2015 Latin American
General subpopulation framework and taming the conflict inside populations
DV Vargas, J Murata, H Takano, ACB Delbem
Evolutionary computation, 2015
A new decomposition based evolutionary algorithm with uniform designs for many-objective optimization
C Dai, Y Wang
Applied Soft Computing, 2015
Ant colony approaches for multiobjective structural optimization problems with a cardinality constraint
JS Angelo, HS Bernardino, HJC Barbosa
Advances in Engineering Software, 2015
S-metric based multi-objective fireworks algorithm
L Liu, S Zheng, Y Tan
Evolutionary Computation (CEC), 2015
S-Metric-Based Multi-objective Fireworks Algorithm
Y Tan
Fireworks Algorithm, 2015
Hybrid Algorithm for Multi-Objective Optimization by Greedy Hypervolume Maximization
CS Miranda, FJ Von Zuben
arXiv, 2015
Multi-Objective Optimization for Self-Adjusting Weighted Gradient in Machine Learning Tasks
CS Miranda, FJ Von Zuben
arXiv 2015
An improved {\ alpha}-dominance strategy for many-objective optimization problems
C Dai, Y Wang, L Hu
Soft Computing, 2015
Decomposition-based chemical reaction optimization (CRO) and an extended CRO algorithms for multiobjective optimization
H Li, L Wang, X Hei
Journal of Computational Science, 2015
Solving the multi-objective path planning problem in mobile robotics with a firefly-based approach
A Hidalgo-Paniagua, MA Vega-Rodríguez, J Ferruz
Soft Computing, 2015
Learning to Anticipate Flexible Choices in Multiple Criteria Decision-Making Under Uncertainty
CRB Azevedo, FJ Von Zuben
Cybernetics, IEEE Transactions on, 2015
Adaptive Computation of the Klee's Measure in High Dimensions
J Barbay, P Pérez-Lantero
arXiv, 2015
Optimizacion de enjambre de particulas para problemas de muchos objetivos
M Torres, B Baran
Computing Conference (CLEI), 2015 Latin America, 2015
Cai Dai, Yuping Wang, Lijuan Hu, "An improved alpha-dominance strategy for many-objective optimization problems", Soft Computing, doi:10.1007/s00500-014-1570-8, published online 01 January 2015.
Year 2014 : 12 citations
M. Emmerich and A. Deutz, “Time complexity and zeros of the hypervolume indicator gradient field,” in EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation III (O. Schuetze, C. A. Coello Coello, A.-A. Tantar, E. Tantar, P. Bouvry, P. Del Moral, P. Legrand, eds.), vol. 500 of Studies in Computational Intelligence, pp 169-193, Berlin: Springer, 2014.
Rui Wang, Peter J. Fleming and Robin C. Purshouse, "General framework for localised multi-objective evolutionary algorithms," Information Sciences, Vol. 258, Pages 29–53, 2014.
K Bringmann, T Friedrich, Two-dimensional Subset Selection for Hypervolume and Epsilon-Indicator, GECCO 2014
F Gu, HL Liu, KC Tan, A hybrid evolutionary multiobjective optimization algorithm with adaptive multi-fitness assignment, Soft Computing, 2014
T Tušar, B Filipic, Visualizing Exact and Approximated 3D Empirical Attainment Functions, Mathematical Problems in Engineering, 2014
W Wang, Multi-objective sequential decision making, PhD thesis, 2014
MTM Emmerich, AH Deutz, I Yevseyeva, On Reference Point Free Weighted Hypervolume Indicators based on Desirability Functions and their Probabilistic Interpretation, Procedia Technology, 2014
S Jiang, YS Ong, J Zhang, L Feng, Consistencies and Contradictions of Performance Metrics in Multiobjective Optimization,IEEE Transactions on Cybernetics, 44(12), 2391 - 2404 , 2014
I Hupkens, M Emmerich, A Deutz, Faster Computation of Expected Hypervolume Improvement, arXiv preprint arXiv:1408.7114, 2014
K Nowak, M Märtens, D Izzo, Empirical Performance of the Approximation of the Least Hypervolume Contributor,
Parallel Problem Solving from Nature – PPSN XIII, Lecture Notes in Computer Science Volume 8672, 2014, pp 662-671
N Boland, H Charkhgard, M Savelsbergh, The L-Shape Search Method for Triobjective Integer Programming, Publication/NA, 2014
I Tsoukalas, C Makropoulos, Multiobjective optimisation on a budget: Exploring surrogate modelling for robust multi-reservoir rules generation under hydrological uncertainty, Environmental Modelling & Software, 2014
Year 2013 : 22 citations
Iris Hupkens, “Complexity Reduction and Validation of Computing the Expected Hypervolume Improvement,” Master's thesis, Universiteit Leiden, Opleiding Informatica. Internal Report 2013–12, August 2013.
Rui Wang, “Preference-inspired Co-evolutionary Algorithms,” PhD thesis, University of Sheffield, 2013.
Koji Shimoyama, Koma Sato, Shinkyu Jeong and Shigeru Obayashi, "Updating Kriging Surrogate Models Based on the Hypervolume Indicator in Multi-Objective Optimization," J. Mech. Des. 135(9), 094503, 2013.
Heike Trautmann, Tobias Wagner, Dirk Biermann, Claus Weihs, Indicator-based Selection in Evolutionary Multiobjective Optimization Algorithms Based On the Desirability Index, Journal of Multicriteria Decision Analysis, 20(5-6), 319,337, 2013
I Couckuyt, D Deschrijver, T Dhaene, Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization, Journal of Global Optimization, 2013
R Wang, RC Purshouse, Preference-Inspired Coevolutionary Algorithms for Many-Objective Optimization, IEEE Transactions on Evolutionary Computation, 17(4) 2013
P Esling, C Agon, Multiobjective time series matching for audio classification and retrieval, IEEE transaction on Audio, Speech, and Language Processing, 2013
W Wang, M Sebag, Hypervolume indicator and dominance reward based multi-objective Monte-Carlo Tree Search, Machine learning, 2013
I Couckuyt, D Deschrijver, T Dhaene, Fast calculation of multiobjective probability of improvement and expected improvement criteria for pareto optimization, Journal of Global Optimization, 2013
K Shimoyama, S Jeong, Kriging-surrogate-based optimization considering expected hypervolume improvement in non-constrained many-objective test problems, CEC 2013.
R Wang, Preference-inspired co-evolutionary algorithms, PhD Thesis, 2013
AA BAKHSH, A POSTERIORI AND INTERACTIVE APPROACHES FOR DECISION-MAKING WITH MULTIPLE STOCHASTIC OBJECTIVES, Publication/NA, 2013
Shimoyama, Koji , Jeong, Shinkyu, Obayashi, Shigeru, Kriging-surrogate-based optimization considering expected hypervolume improvement in non-constrained many-objective test problems, 2013 IEEE Congress on Evolutionary Computation (CEC), 658 - 665, 2013.
Iris Hupkens, Michael Emmerich, Logarithmic-Time Updates in SMS-EMOA and Hypervolume-Based Archiving, EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV, Advances in Intelligent Systems and Computing Volume 227, 2013, pp 155-169
Ray, Tapabrata , Asafuddoula, Md, Isaacs, Amitay, A steady state decomposition based quantum genetic algorithm for many objective optimization, , 2013 IEEE Congress on Evolutionary Computation (CEC), 2817 - 2824, 2013.
Weijia Wang, Michèle Sebag, Hypervolume indicator and dominance reward based multi-objective Monte-Carlo Tree Search, Machine Learning September 2013, Volume 92, Issue 2-3, pp 403-429
D. H. Phan and J. Suzuki, "R2-IBEA: R2 Indicator Based Evolutionary Algorithm for Multiobjective Optimization," In Proc. of IEEE Congress on Evolutionary Computation (CEC), Cancun, Mexico, June 2013.
Hans J. F. Moen, Nikolai B. Hansen, Harald Hovland, Jim Tørresen , Many-Objective Optimization Using Taxi-Cab Surface Evolutionary Algorithm, Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science Volume 7811, pp 128-142, 2013
Michael Emmerich, André Deutz, Johannes Kruisselbrink, Pradyumn Kumar Shukla, Cone-Based Hypervolume Indicators: Construction, Properties, and Efficient Computation, Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science Volume 7811, pp 111-127, 2013
K. Bringmann, “Bringing Order to Special Cases of Klee’s Measure Problem,” in Mathematical Foundations of Computer Science 2013 (K. Chatterjee and J. Sgall, eds.), vol. 8087 of Lecture Notes in Computer Science, pp 207-218, Berlin: Springer, 2013.
MG Villarreal-Marroquín, JD Svenson, A comparison of two metamodel-based methodologies for multiple criteria simulation optimization using an injection molding case study, Journal of Polymer Engineering, 2013
K. Bringmann, T. Friedrich, Parameterized Average-Case Complexity of the Hypervolume Indicator, Proc. of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO 2013), Amsterdam, The Netherlands, ACM, 2012.
Year 2012 : 12 citations
M Helbig, Solving dynamic multi-objective optimisation problems using vector evaluated particle swarm optimisation, PhD thesis, 2012
P CARDOSO,M.Jesus, P. Guerreiro, P. Ribeiro, A. Marquez, J. Porillo, Two multi-criteria evolutionary algorithms for a multi-path evacuation problem, The 6th WSEAS Conference, 2012
L. While, L. Bradstreet, L. Barone, A Fast Way of Calculating Exact Hypervolumes, IEEE Transactions on Evolutionary Computation, 2012.
Karl Bringmann, Tobias Friedrich, Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, Theoretical Computer Science, 2012
A Auger, J Bader, D Brockhoff, E Zitzler, Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications, Theoretical Computer Science, 2012
M Díez-Fernández, S Teleña, D Gorse, Construction of Emerging Markets Exchange Traded Funds Using Multiobjective Particle Swarm Optimisation, Artificial Neural Networks and Machine Learning – ICANN 2012, LNCS 7553, 2012, pp 140-147
MM Drugan, D Thierens, Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies, Journal of Heuristics, 2012
L While, L Bradstreet, Applying the WFG algorithm to calculate incremental hypervolumes, Evolutionary Computation Conference, 2012
W Wang, M Sebag, Multi-objective Monte-Carlo Tree Search, Asian Conference on Machine Learning, 2012
K Shimoyama, K Sato, S Jeong, Comparison of the criteria for updating Kriging response surface models in multi-objective optimization, Evolutionary Computation Conference, 2012
I Couckuyt, D Deschrijver, Towards Efficient Multiobjective Optimization: Multiobjective statistical criterions, Evolutionary Computation Conference, 2012
D Brockhoff, T Wagner, H Trautmann, On the Properties of the R2 Indicator, Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, 2012
Year 2011 : 10 citations
MTM Emmerich, CM Fonseca, Computing hypervolume contributions in low dimensions: Asymptotically optimal algorithm and complexity results, Evolutionary Multi-Criterion Optimization, 2011
W Zhu, A Yaseen, Y Li, DEMCMC-GPU: an efficient multi-objective optimization method with GPU acceleration on the fermi architecture, New Generation Computing, 2011
L Bradstreet, The Hypervolume Indicator for Multi-objective Optimisation: Calculation and Use, PHD thesis, 2011
Z He, Performance metrics ensemble for multiobjective evolutionary algorithms, PhD thesis, 2011
Johannes Bader, Eckart Zitzler, HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization, Evolutionary Computation, Vol. 19, No. 1, 45-76, 2011.
B Naujoks, Design and tuning of an evolutionary multiobjective optimisation algorithm, PhD thesis, TU Dortmund, Germany, 2011
Weihang Zhu, Ashraf Yaseen and Yaohang Li, DEMCMC-GPU: An Efficient Multi-Objective Optimization Method with GPU Acceleration on the Fermi Architecture, New Generation Computing, Volume 29, Number 2, 163-184, 2011
D. Brockhoff, Theoretical Aspects of Evolutionary Multiobjective Optimization, A. Auger, B. Doerr (eds), Theory of Randomized Algorithms, World Scientific, 2011
J. P. Arun, A radius based guide selection technique in multi-objective particle swarm optimization, IEEE International Conference on Recent Trends in Information Technology, pp. 1169-1174, 2011
A. P. Guerreiro, Efficient Algorithms for the Assessment of Stochastic Multiobjective Optimizers, Master's thesis, Instituto Superior Técnico, 2011.
Year 2010 : 12 citations
T Lust, New metaheuristics for solving MOCO problems: application to the knapsack problem, the traveling salesman problem and IMRT optimization, PhD thesi, 2010
T Meinl, Maximum-score diversity selection., PhD thesis, 2010
H Ishibuchi, Y Sakane, Y Nojima, Use of Multiple Grids with Different Scalarizing Functions in MOEA/D, SCIS & ISIS, 2010
T. Wagner, H. Trautmann, Integration of Preferences in Hypervolume-Based Multiobjective Evolutionary Algorithms by Means of Desirability Functions, IEEE Transactions on Evolutionary Computation, 14 (5), pp. 688 - 701, 2010
J. Bader, E. Zitzler, HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization, Evolutionary Computation, Vol. 19, No. 1, Pages 45-76, 2010
K. Bringmann, T. Friedrich, Approximating the volume of unions and intersections of high-dimensional geometric objects, Computational Geometry Volume 43, Issues 6-7, Pages 601-610, 2010
A. Auger, J. Bader, D. Brockhoff, Theoretically investigating optimal µ-distributions for the hypervolume indicator: first results for three objectives, Proceedings of the 11th international conference on Parallel problem solving from nature,volume 6238 of LNCS, pages 586–596. Springer, 2010.
J. Bader and E. Zitzler. A Hypervolume-Based Optimizer for High-Dimensional Objective Spaces, In Multiple Objective and Goal Programming (MOPGP 2008), volume 638 of Lecture Notes in Economics and Mathematical Systems, pages 35-54. Springer, 2010
K. Bringmann, T. Friedrich, An Efficient Algorithm for Computing Hypervolume Contributions, Evolutionary Computation, Vol. 18, No. 3, Pages 383-402, 2010
H. Ishibuchi, N. Tsukamoto, Y. Sakane, Y. Nojima, Indicator-based evolutionary algorithm with hypervolume approximation by achievement scalarizing functions, Proceedings of the 12th annual conference on Genetic and evolutionary computation,527-534, 2010
D. Brockhoff, Optimal μ-Distributions for the Hypervolume Indicator for Problems with Linear Bi-objective Fronts: Exact and Exhaustive Results, Proc. Simulated Evolution and Learning, LNCS 6457, 23-34, 2010
Edgar Reehuis, Multiobjective Optimization of Water Distribution Networks, MSc thesis, Technical Report 2010-04, Universiteit Leiden, Opleiding Informatica, 2008
Year 2009 : 8 citations
N Beume, S-metric calculation by considering dominated hypervolume as klee's measure problem, Evolutionary Computation, 2009
N Beume, B Naujoks, M Preuss, G Rudolph, Effects of 1-Greedy\ S-Metric-Selection on Innumerably Large Pareto Fronts, Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science Volume 5467, 2009, pp 21-35
A. Auger, J. Bader, D. Brockhoff, and E. Zitzler, Theory of the Hypervolume Indicator: Optimal μ-Distributions and the Choice of the Reference Point, In Foundations of Genetic Algorithms (FOGA 2009), pages 87–102, New York, NY, USA, 2009. ACM.
K. Bringmann, T. Friedrich, Approximating the Least Hypervolume Contributor: NP-Hard in General, But Fast in Practice, Proc. of the 5th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2009), Vol. 5467 of LNCS, pages 6-20, Springer-Verlag, 2009
K. Bringmann and T. Friedrich. Don't be greedy when calculating hypervolume contributions,Proceedings of the 10th Foundations of Genetic Algorithms Workshop (FOGA X), Orlando, Florida, pp. 103-112, 2009
D Brockhoff, Theoretical Aspects of Evolutionary Multiobjective Optimization---A Review, INRIA technical report 7030, 2009
T. Lust,: New metaheuristics for solving MOCO problems: application to the knapsack, traveling salesman problems and IMRT optimization. PhD Thesis, University of Mons, Belgium, 2009.
C.A.C.Coello, A Tutorial on multiobjective optimization using metaheuristics. MonografÃas del Seminario Matemático GarcÃa de Galdeano, 1–20, 2009
Year 2008 : 2 citations
K Bringmann, T Friedrich, Approximating the volume of unions and intersections of high-dimensional geometric objects, Algorithms and Computation, 2008
E Reehuis, N Bohrweg, Opleiding Informatica, Publication/NA, 2008
Year 1999 : 1 citations
CAC Coello, List of references on evolutionary multiobjective optimization, Laboratorio Nacional de Informática Avanzada, …, 1999