×

On using the hypervolume indicator to compare Pareto fronts: applications to multi-criteria optimal experimental design. (English) Zbl 1311.62115

Summary: The Pareto approach to optimal experimental design simultaneously considers multiple objectives by constructing a set of Pareto optimal designs while explicitly considering trade-offs between opposing criteria. Various algorithms have been proposed to populate Pareto fronts of designs, and evaluating and comparing these fronts-and by extension the algorithms that produce them-is crucial. In this paper, we first propose a framework for comparing algorithm-generated Pareto fronts based on a refined hypervolume indicator. We then theoretically address how the choice of the reference point affects comparisons of Pareto fronts, and demonstrate that our approach is Pareto compliant. Based on our theoretical investigation, we provide rules for choosing reference points when two-dimensional Pareto fronts are compared. Because theoretical results for three-dimensional fronts are difficult to obtain, we propose an empirical rule for the three-dimensional case by making an analogy to the rules for two dimensions. We also consider the use of our procedure in evaluating the progress of a front-constructing algorithm, and illustrate our work with two examples from the literature.

MSC:

62K05 Optimal statistical designs
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Auger, A.; Bader, J.; Brockhoff, D., Theoretical investigation optimal distributions for the hypervolume indicator: first results for three objectives, (Parallel Problem Solving from Nature, PPSN XI 586-596 (2010), Springer: Springer Berlin Heidelberg)
[2] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Theory of the hypervolume indicator: optimal distributions and the choice of the reference point, (Foundations of Genetic Algorithms (FOGA 2009) (2009), ACM: ACM New York, NY, USA), 87-102 · Zbl 1369.68293
[3] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Hypervolume-based multiobjective optimization: theoretical foundations and practical implications, Theoret. Comput. Sci., 425, 75-103 (2012) · Zbl 1242.90205
[4] Bader, J.; Zitzler, E., HypE: An algorithm for fast hypervolume-based many-objective optimization, Evolutionary Computation, 19, 1, 45-76 (2011)
[5] Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: multiobjective selection based on dominated hypervolume, European J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[6] Brockhoff, D., Optimal \(\mu \)-distributions for the hypervolume indicator for problems with linear bi-objective fronts: exact and exhaustive Results, (Simulated Evolution and Learning (2010), Springer: Springer Berlin Heidelberg), 24-34
[7] Coello Coello, C. A.; Lamont, G. B.; Van Veldhuizen, D. A., (Evolutionary algorithms for solving multi-objective problems (2007), Springer) · Zbl 1142.90029
[8] Cook, R. D.; Nachtsheim, C. J., A comparison of algorithms for constructing exact D-optimal designs, Technometrics, 22, 315-324 (1980) · Zbl 0459.62061
[9] Cook, R. D.; Wong, W. K., On the equivalence of constrained and compound optimal design, J. Amer. Statist. Assoc., 89, 687-692 (1994) · Zbl 0799.62081
[10] Das, I.; Dennis, J. E., A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, Struct. Optim., 14, 63-69 (1997)
[11] Emmerich, M.; Beume, N.; Naujoks, B., An EMO algorithm using the hypervolume measure as selection criterion, (In Evolutionary Multi-Criterion Optimization (2005), Springer: Springer Berlin Heidelberg), 62-76 · Zbl 1109.68595
[12] Fedorov, V. V., Theory of Optimal Exeriments (1972), Academic Press: Academic Press New York, NY
[13] Fonseca, C. M.; Paquete, L.; López-Ibánez, M., An improved dimension-sweep algorithm for the hypervolume indicator, (IEEE Congress on Evolutionary Computation, 2006. CEC 2006 (2006), IEEE), 1157-1163
[15] Gilmour, S. G.; Trinca, L. A., Optimum design of experiments for statistical inference, J. R. Stat. Soc.: Ser. C Appl. Stat., 61, 3, 345-401 (2012)
[16] Judt, L.; Mersmann, O.; Naujoks, B., Non-monotonicity of obtained hypervolume in 1-greedy S-metric selection, J. Multi-Criteria Decis. Anal., 20, 5-6, 277-290 (2013)
[17] Judt, L.; Mersmann, O.; Naujoks, B., Do hypervolume regressions hinder EMOA performance? surprise and relief, (Evolutionary Multi-Criterion Optimization (2013), Springer: Springer Berlin Heidelberg), 96-110
[18] Knowles, J. D.; Corne, D. W.; Fleischer, M., Bounded archiving using the Lebesgue measure, (The 2003 Congress on Evolutionary Computation, 2003. CEC ’03, vol. 4 (2003), IEEE), 2490-2497
[19] Lu, L.; Anderson-Cook, C. M., Adapting the hypervolume quality indicator to quantify trade-offs and search efficiency for multiple criteria decision making using Pareto fronts, Qual. Reliab. Eng. Int., 29, 8, 1117-1133 (2012)
[20] Lu, L.; Anderson-Cook, C. M.; Robinson, T. J., Optimization of designed experiments based on multiple criteria utilizing a Pareto frontier, Technometrics, 61, 353-365 (2011)
[21] Park, Y.-J., Multi-optimal designs for second-order response surface model, Commun. Korean Statist. Soc., 16, 1, 195-208 (2009)
[22] Sambo, F.; Borrotti, M.; Mylona, K., A coordinate-exchange two-phase local search algorithm for the D- and I-optimal designs of split-plot experiments, Comput. Statist. Data Anal., 71, 1193-1207 (2014) · Zbl 1471.62179
[23] While, L.; Hingston, P.; Barone, L.; Huband, S., A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Comput., 10, 1, 29-38 (2006)
[24] Zio, E.; Bazzo, R., A comparison of methods for selecting preferred solutions in multiobjective decision making, (Computational Intelligence Systems in Industrial Engineering (2012), Atlantis Press), 23-43
[25] Zitzler, E.; Brockhoff, D.; Thiele, L., The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration, (Evolutionary Multi-Criterion Optimization (2007), Spring: Spring Berlin Heidelberg), 862-876
[26] Zitzler, E.; Knowles, J.; Thiele, L., Quality assessment of Pareto set approximations, (Multiobjective Optimization (2008), Springer Berlin Heidelberg), 373-404
[27] Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (Parallel Problem Solving from Nature-PPSN VIII (2004), Springer: Springer Berlin Heidelberg), 832-842
[28] Zitzler, E.; Thiele, L., Multiobjective optimization using evolutionary algorithms—a comparative case study, (Parallel problem solving from Nature—PPSN V (1998), Spring: Spring Berlin Heidelberg), 292-301
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.