Hisao Ishibuchi
ABSTRACT
Hypervolume has been frequently used as a performance indicator for comparing evolutionary multiobjective optimization (EMO) algorithms. Hypervolume has been also used in indicator-based algorithms. Whereas a reference point is needed for hypervolume calculation, its specification has not been discussed in detail from a viewpoint of fair comparison. This may be because a slightly worse reference point than the nadir point seems to work well. In this paper, we tackle this issue: How to specify a reference point for fair comparison. First we discuss an appropriate specification of a reference point for multiobjective problems. Our discussions are based on the well-known theoretical results about the optimal solution distribution for hypervolume maximization. Next we examine various specifications by computational experiments. Experimental results show that a slightly worse reference point than the nadir point works well only for test problems with triangular Pareto fronts. Then we explain why this specification is not always appropriate for test problems with inverted triangular Pareto fronts. We also report a number of solution sets obtained by SMS-EMOA with various specifications of a reference point.
- A. Auger, J. Bader, D. Brockhoff, and E. Zitzler. 2012. Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications. Theoretical Computer Science 425 (2012), 75--103. Google Scholar
Digital Library
- J. Bader and E. Zitzler. 2011. HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation 19, 1 (2011), 45--76. Google ScholarDigital Library
- M. Basseur, B. Derbel, A. Goëffon, and A. Liefooghe. 2016. Experiments on greedy and local search heuristics for d-dimensional hypervolume subset selection. In Proceedings of 2016 Genetic and Evolutionary Computation Conference (GECCO 2016), ACM, Denver, USA, 541--548. Google ScholarDigital Library
- N. Beume, B. Naujoks, and M. Emmerich. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 180, 3 (2007), 1653--1669.Google ScholarCross Ref
- K. Bringmann, T. Friedrich, and P. Klitzke. 2014. Two-dimensional subset selection for hypervolume and epsilon-indicator. In Proceedings of 2014 Genetic and Evolutionary Computation Conference (GECCO 2014), ACM, Vancouver, Canada, 589--596. Google ScholarDigital Library
- D. Brockhoff. 2010. Optimal μ-distributions for the hypervolume indicator for problems with linear bi-objective fronts: Exact and exhaustive results. In Proceedings of the 8th International Conference on Simulated Evolution and Learning (SEAL 2010), Springer, Kanpur, India, 24--34. Google ScholarDigital Library
- K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. 2002. Scalable multi-objective optimization test problems. In Proceedings of 2002 Congress on Evolutionary Computation (CEC 2002), IEEE, Honolulu, USA, 825--830.Google Scholar
- T. Friedrich, F. Neumann, and C. Thyssen. 2015. Multiplicative approximations, optimal hypervolume distributions, and the choice of the reference point. Evolutionary Computation 23, 1 (2015), 131--159. Google ScholarDigital Library
- A. P. Guerreiro, C. M. Fonseca, and L. Paquete. 2015. Greedy hypervolume subset selection in the three-objective case. In Proceedings of 2015 Genetic and Evolutionary Computation Conference (GECCO 2015), Madrid, Spain, 671--678. Google ScholarDigital Library
- A. P. Guerreiro, C. M. Fonseca, and L. Paquete. 2016. Greedy hypervolume subset selection in low dimensions. Evolutionary Computation 24, 3 (2016), 521--544. Google ScholarDigital Library
- S. Huband, P. Hingston, L. Barone, and L. While. 2006. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation 10, 5 (2006), 477--506. Google ScholarDigital Library
- H. Ishibuchi, N. Akedo, and Y. Nojima. 2015. Behavior of multi-objective evolutionary algorithms on many-objective knapsack problems. IEEE Trans. on Evolutionary Computation 19, 2 (2015), 264--283.Google ScholarDigital Library
- H. Ishibuchi, R. Imada, Y. Setoguchi, and Y. Nojima. 2017. Hypervolume subset selection for triangular and inverted triangular Pareto fronts of three-objective problems. In Proceeding of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2017), ACM, Copenhagen, Denmark, 95--110. Google ScholarDigital Library
- H. Ishibuchi, H. Masuda, and Y. Nojima. 2014. Selecting a small number of non-dominated solutions to be presented to the decision maker. In Proceedings of 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2014), IEEE, San Diego, USA, 3850--3855.Google ScholarCross Ref
- H. Ishibuchi, Y. Setoguchi, H. Masuda, and Y. Nojima. 2017. Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Trans. on Evolutionary Computation 21, 2 (2017) 169--190. Google ScholarDigital Library
- H. Jain and K. Deb. 2014. An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, Part II: Handling constraints and extending to an adaptive approach. IEEE Trans. on Evolutionary Computation 18, 4 (2014), 602--622.Google ScholarCross Ref
- T. Kuhn, C. M. Fonseca, L. Paquete, S. Ruzika, M. M. Duarte, and J. R. Figueira. 2016. Hypervolume subset selection in two dimensions: Formulations and algorithms. Evolutionary Computation 24, 3 (2016), 411--425. Google ScholarDigital Library
- K. Li, K. Deb, Q. Zhang, and S. Kwong. 2015. An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans. on Evolutionary Computation 19, 5 (2015), 694--716.Google ScholarDigital Library
- H. Seada and K. Deb. 2016. A unified evolutionary optimization procedure for single, multiple, and many objectives. IEEE Trans. on Evolutionary Computation 20, 3 (2016), 358--369.Google ScholarCross Ref
- P. K. Shukla, N. Doll, and H. Schmeck. 2014. A theoretical analysis of volume based Pareto front approximations. In Proceedings of 2014 Genetic and Evolutionary Computation Conference (GECCO 2014), ACM, Vancouver, Canada, 1415--1422. Google ScholarDigital Library
- T. Wagner, N. Beume, and B. Naujoks. 2007. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), Springer, Matsushima, Japan, 742--756. Google ScholarDigital Library
- Y. Yuan, H. Xu, B. Wang, and X. Yao. 2016. A new dominance relation based evolutionary algorithm for many-objective optimization. IEEE Trans. on Evolutionary Computation 20, 1 (2016), 16--37.Google ScholarDigital Library
- Y. Yuan, H. Xu, B. Wang, B. Zhang, and X. Yao. 2016. Balancing convergence and diversity in decomposition-based many-objective optimizers. IEEE Trans. on Evolutionary Computation 20, 2 (2016), 180--198.Google ScholarCross Ref
- Q. Zhang and H. Li. 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation 11, 6 (2007), 712--731. Google ScholarDigital Library
- E. Zitzler, D. Brockhoff, and L. Thiele. 2007. The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), Springer, Matsushima, Japan, 862--876. Google ScholarDigital Library
- E. Zitzler and L. Thiele. 1998. Multiobjective optimization using evolutionary algorithms - A comparative case study. In Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V), Amsterdam, Netherlands, 292--301. Google ScholarDigital Library
- E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. da Fonseca. 2003. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. on Evolutionary Computation 7, 2 (2003), 117--132. Google ScholarDigital Library
Index Terms
- Reference point specification in hypervolume calculation for fair comparison and efficient search
Recommendations
How to specify a reference point in hypervolume calculation for fair performance comparison
The hypervolume indicator has frequently been used for comparing evolutionary multi-objective optimization EMO algorithms. A reference point is needed for hypervolume calculation. However, its specification has not been discussed in detail from a ...
Dynamic Specification of a Reference Point for Hypervolume Calculation in SMS-EMOA
2018 IEEE Congress on Evolutionary Computation (CEC)The hypervolume has been frequently used as an indicator to compare the performance of evolutionary multi-objective optimization (EMO) algorithms. It has also been used in indicator-based algorithms (e.g., SMS-EMOA and HypE). In such an EMO algorithm, a ...
Meta-level multi-objective formulations of set optimization for multi-objective optimization problems: multi-reference point approach to hypervolume maximization
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary ComputationHypervolume has been frequently used as an indicator to evaluate a solution set in indicator-based evolutionary algorithms (IBEAs). One important issue in such an IBEA is the choice of a reference point. A different solution set is often obtained from a ...
Comments