×

zbMATH — the first resource for mathematics

Fast hypervolume approximation scheme based on a segmentation strategy. (English) Zbl 1456.90151
Summary: Hypervolume indicator based evolutionary algorithms have been reported to be very promising in many-objective optimization, but the high computational complexity of hypervolume calculation in high dimensions restrains its further applications and developments. In this paper, we develop a fast hypervolume approximation method with both improved speed and accuracy than the previous approximation methods via a new segmentation strategy. The proposed approach consists of two crucial process: segmentation and approximation. The segmentation process recursively finds areas easy to be measured and quantified from the original geometric figure as many as possible, and then divides the measurement of the rest areas into several subproblems. In the approximation process, an improved Monte Carlo simulation is developed to estimate these subproblems. Those two processes are mutually complementary to simultaneously improve the accuracy and the speed of hypervolume approximation. To validate its effectiveness, experimental studies on four widely-used instances are conducted and the simulation results show that the proposed method is ten times faster than other comparison algorithms with a same measurement error. Furthermore, we integrate an incremental version of this method into the framework of SMS-EMOA, and the performance of the integrated algorithm is also very competitive among the experimental algorithms.
MSC:
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bader, J.; Deb, K.; Zitzler, E., Faster hypervolume-based search using monte carlo sampling, Lect. Notes Econ. Math. Syst., 634, 32, 313-326 (2010) · Zbl 1184.90147
[2] Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[3] Beume, N., S-metric calculation by considering dominated hypervolume as Klee’s measure problem, Evol. Comput., 17, 4, 477-492 (Dec. 2009)
[4] Beume, N.; Fonseca, C. M.; Vahrenhold, J., On the complexity of computing the hypervolume indicator, IEEE Trans. Evol. Comput., 13, 5, 1075-1082 (2009)
[5] Beume, N.; Naujoks, B., SMS-EMOA: multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (Feb. 2007)
[6] Bradstreet, L.; While, L.; Barone, L., A fast incremental hypervolume algorithm, IEEE Trans. Evol. Comput., 12, 6, 714-723 (2008)
[7] Bringmann, K.; Friedrich, T., Approximating the volume of unions and intersections of high-dimensional geometric objects, Int. Symp. Algorithms Comput., 43, 6, 436-447 (2008) · Zbl 1183.68653
[8] Bringmann, K.; Friedrich, T., Parameterized average-case complexity of the hypervolume indicator, Conference on Genetic and Evolutionary Computation., 575-582 (2013)
[9] Brockhoff, D.; Bader, J.; Thiele, L.; Zitzler, E., Directed multiobjective optimization based on the weighted hypervolume indicator, J. Multi-Criteria Decis. Anal., 20, 5-6, 291-317 (2013)
[10] Brockhoff, D.; Friedrich, T.; Neumann, F., Analyzing hypervolume indicator based algorithms, International Conference on Parallel Problem Solving From Nature: PPSN X, vol. 5199, 651-660 (2008)
[11] Brockhoff, D.; Friedrich, T., On the effects of adding objectives to plateau functions, IEEE Trans. Evol. Comput., 13, 3, 591-603 (Jun. 2009)
[12] Chen, L.; Liu, H.; Tan, K.; Cheung, Y.; Wang, Y., Evolutionary many-objective algorithm using decomposition based dominance relationship, IEEE Trans. Cybern. (2017)
[13] Cheung, Y.; Gu, F.; Liu, H., Objective extraction for many-objective optimization problems: algorithm and test problems, IEEE Trans. Evol. Comput., 20, 5, 755-772 (2016)
[14] Cox, W.; While, L., Improving the IWFG algorithm for calculating incremental hypervolume, IEEE Congress on Evolutionary Computation IEEE (CEC), 3969-3976 (2016)
[15] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints, IEEE Trans. Evol. Comput., 18, 4, 577-601 (2014)
[16] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and flitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[17] Deb, K.; Thiele, L.; Laumanns, M.; E, Z., Scalable multi-objective optimization test problems, Congr. Evol. Comput. (CEC), 1, 825-830 (2002)
[18] Durillo, J. J.; Nebro, A. J., jMetal: a java framework for multi-objective optimization, Adv. Eng. Softw., 42, 10, 760-771 (2011)
[19] Fleischer, M., “The measure of pareto optima: applications to multiobjective metaheuristics”, Int. Conf. Evol. Multi-Criterion Optim., 2632, 1, 519-533 (2003) · Zbl 1036.90530
[20] Friedrich, T.; Horoba, C.; Neumann, F., Multiplicative approximations and the hypervolume indicator, Conf. Genet. Evol. Comput. ACM, 571-578 (2009)
[21] García, I. C.; Coello, C. A.C.; Arias-Montaño, A., MOPSOhv: a new hypervolume-based multi-objective particle swarm optimizer, IEEE Congress on Evolutionary Computation (CEC), 266-273 (2014)
[22] Gu, F.; Cheung, Y., Self-organizing map-based weight design for decomposition-based many-objective evolutionary algorithm, IEEE Trans. Evol. Comput., 22, 2, 211-225 (2018)
[23] Gu, F.; Liu, H.; Cheung, Y.; Xie, S., Optimizing wcdma network planning by multiobjective evolutionary algorithm with problem-specific genetic operation, Knowl. Inf. Syst. (KAIS), 45, 3, 679-703 (2015)
[24] Guerreiro, P.; Fonseca, C. M.; Emmerich, M. T., A fast dimension-sweep algorithm for the hypervolume indicator in four dimensions, Canadian Conference on Computational Geometry (CCCG 2012), 77-82 (2012)
[25] Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 5, 477-506 (2006)
[26] Igel, C.; Hansen, N.; Roth, S., Covariance matrix adaptation for multi-objective optimization, Evol. Comput., 15, 1, 1 (2007)
[27] Jiang, S.; Zhang, J.; Ong, Y. S., A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm, IEEE Trans. Cybern., 45, 10, 2202-2213 (2015)
[28] Lacour, R.; Klamroth, K.; Fonseca, C. M., A box decomposition algorithm to compute the hypervolume indicator, Comput. Oper. Res., 79, 5, 347-360 (Mar, 2017)
[29] Li, B.; Tang, K.; Li, J.; Yao, X., Stochastic ranking algorithm for many-objective optimization based on multiple indicators, IEEE Trans. Evol. Comput., 20, 924-938 (2016)
[30] Liu, H.; Gu, F.; Cheung, Y., T-MOEA/D: MOEA/D with objective transform in multi-objective problems, Proceedings of 2010 International Conference on Information Science and Management Engineering, 282-285 (2010)
[31] Liu, H.; Gu, F.; Zhang, Q., Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems, IEEE Trans. Evol. Comput., 18, 3, 450-455 (Jun. 2014)
[32] Menchaca-Mendez, A.; Coello, C. A.C., A new selection mechanism based on hypervolume and its locality property, 2013 IEEE Congress on Evolutionary Computation (CEC), 924-931 (Jul. 2013)
[33] Narukawa, K.; Rodemann, T., Examining the performance of evolutionary many-objective optimization algorithms on a real-world application, International Conference on Genetic and Evolutionary Computing IEEE, 316-319 (2013)
[34] Naujoks, B.; Beume, N.; Emmerich, M., Multi-objective optimisation using s-metric selection: application to three-dimensional solution spaces, IEEE Congress on Evolutionary Computation (CEC), vol. 2, 1282-1289 (2005)
[35] Nowak, K.; Märtens, M.; Izzo, D., “Empirical performance of the approximation of the least hypervolume contributor”, International Conference on Parallel Problem Solving From Nature, vol. 8672, 662-671 (2014)
[36] Overmars, M. H.; Yap, C. K., New upper bounds in Klee’s measure problem, Proceedings of Annual Symposium Foundations of Computer Science (FOCS), vol. 20, 550-556 (2006)
[37] Priester, C.; Narukawa, K.; Rodemann, T., A comparison of different algorithms for the calculation of dominated hypervolumes, Genetic and Evolutionary Computation Conference (GECCO), vol. 21, 655-662 (2013)
[38] Rostami, S.; Neri, F., A fast hypervolume driven selection mechanism for many-objective optimisation problems, Swarm Evol. Comput., 34, 5, 50-67 (2017)
[39] Russo, L. M.S.; Francisco, A. P., “Quick hypervolume”, IEEE Trans. Evol. Comput., 18, 4, 481-502 (2014)
[40] Russo, L. M.S.; Francisco, A. P., “Extending quick hypervolume”, J. Heuristics, 22, 3, 245-271 (2016)
[41] Schutze, O.; Lara, A.; Coello, C. A.C., On the influence of the number of objectives on the hardness of a multiobjective optimization problem, IEEE Trans. Evol. Comput., 15, 4, 444-455 (Aug. 2011)
[42] Trautmann, H.; Wagner, T.; Brockhoff, D., R2-EMOA: focused multiobjective search using R2-indicator-based selection, Learning and Intelligent Optimization, vol. 7997, 70-74 (2013), Springer Berlin Heidelberg
[43] While, L.; Bradstreet, L., Applying the WFG algorithm to calculate incremental hypervolumes, Evol. Comput. IEEE, 22, 10, 1-8 (2012)
[44] While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, IEEE Trans. Evol. Comput., 16, 1, 86-95 (2012)
[45] Yuan, Y.; Xu, H.; Wang, B.; Yao, X., A new dominance relation based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 1, 16-37 (2016)
[46] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007)
[47] Zitzler, E.; Brockhoff, D.; Thiele, L., The hypervolume indicator revisited: on the design of pareto-compliant indicators via weighted integration, International Conference on Evolutionary Multi-Criterion Optimization, 4403, 862-876 (2007)
[48] Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, Parallel Problem Solving from Nature-PPSN VIII, 832-842 (Aug. 2004)
[49] Zitzler, E.; Thiele, L., Multiobjective optimization using evolutionary algorithms-a comparative case study, Parallel Problem Solving from Nature-PPSN V, 292-301 (1998), Springer Berlin Heidelberg
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.