A fast dimension-sweep algorithm for the hypervolume indicator in four dimensions
Authors
Abstract
The Hypervolume Indicator is one of the most widely used quality indicators in Evolutionary Multiobjective Optimization. Its computation is a special case of Klee’s Measure Problem (KMP) where the upper end of all rectangular ranges coincides with a given referencepoint (assuming minimization, without loss of generality). Although the time complexity of the hypervolume indicator in two and three dimensions is known to be ?(n log n), improving upon the O(n^(d/2) log n) complexity of Overmars and Yap’s algorithm for the general KMP in higher dimensions has been a challenge. In this paper, a new dimension-sweep algorithm to compute the hypervolume indicator in four dimensions is proposed, and its complexity is shown to be O(n²).
Conference
24th Canadian Conference on Computational Geometry (CCCG 2012), August 2012Cited by
Year 2015 : 2 citations
Yang, Zhiwei, et al. "Multicriteria Inventory Routing by Cooperative Swarms and Evolutionary Algorithms." Bioinspired Computation in Artificial Systems. Springer International Publishing, 2015. 127-137.
Siwei Jiang; Jie Zhang; Yew-Soon Ong; Zhang, A.N.; Puay Siew Tan, "A Simple and Fast Hypervolume Indicator-Based Multiobjective Evolutionary Algorithm," in Cybernetics, IEEE Transactions on , vol.45, no.10, pp.2202-2213, Oct. 2015
doi: 10.1109/TCYB.2014.2367526
Year 2014 : 5 citations
Russo, L.M.S.and; Francisco, A.P., "Quick Hypervolume," IEEE Transactions on Evolutionary Computation, Volume 18, Issue 4, pp. 481 - 502, 2014. http://dx.doi.org/10.1109/TEVC.2013.2281525
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.
Siwei Jiang, Jie Zhang, Yew-Soon Ong, Allan N. Zhang, and Puay Siew Tan, "A Simple and Fast Hypervolume Indicator-Based Multiobjective Evolutionary Algorithm", IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2014.2367526, Published online 2 December 2014.
Michael T.M. Emmerich, André H. Deutz, Iryna Yevseyeva, "On Reference Point Free Weighted Hypervolume Indicators based on Desirability Functions and their Probabilistic Interpretation", Procedia Technology, Volume 16, Pages 532–541, 2014.
Krzysztof Nowak, Marcus Märtens, Dario 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, pp 662-671, 2014.
Year 2013 : 6 citations
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.
I. Hupkens and M. Emmerich , “Logarithmic-time updates in SMS-EMOA and hypervolume-based archiving,” in EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV ( M. Emmerich, A. Deutz, O. Schuetze, T. Bäck, E. Tantar, A.-A. Tantar, P. Del Moral, P. Legrand, P. Bouvry, C. A. Coello, eds.), vol. 227 of Advances in Intelligent Systems and Computing, pp 155-169 Berlin: Springer, 2013.
A. Zhou, Q. Zhang, and G. Zhang, “Approximation Model Guided Selection for Evolutionary Multiobjective Optimization,” in Evolutionary Multi-Criterion Optimization. 7th International Conference, EMO 2013 (R. C. Purshouse, P. J. Fleming, C. M. Fonseca, S. Greco, and J. Shaw, eds.), vol. 7811 of Lecture Notes in Computer Science, pp 398-412, Berlin: Springer, 2013.
M. Emmerich, A. Deutz, J. Kruisselbrink, and P. K. Shukla , “Cone-Based Hypervolume Indicators: Construction, Properties, and Efficient Computation,” in Evolutionary Multi-Criterion Optimization. 7th International Conference, EMO 2013 (R. C. Purshouse, P. J. Fleming, C. M. Fonseca, S. Greco, and J. Shaw, eds.), vol. 7811 of Lecture Notes in Computer Science, pp 111-127, Berlin: Springer, 2013.
P. K. Shukla and M. A. Braun, “Indicator Based Search in Variable Orderings: Theory and Algorithms,” in Evolutionary Multi-Criterion Optimization. 7th International Conference, EMO 2013 (R. C. Purshouse, P. J. Fleming, C. M. Fonseca, S. Greco, and J. Shaw, eds.), vol. 7811 of Lecture Notes in Computer Science, pp 66-80, Berlin: Springer, 2013.
João A. Duro, Machine learning based decision support for a class of many-objective optimisation problems, Ph.D. Thesis, Cranfield University, 2013.