Hypervolume-based multiobjective optimization: theoretical foundations and practical implications.

*(English)*Zbl 1242.90205Summary: In recent years, indicator-based evolutionary algorithms, allowing to implicitly incorporate user preferences into the search, have become widely used in practice to solve multiobjective optimization problems. When using this type of methods, the optimization goal changes from optimizing a set of objective functions simultaneously to the single-objective optimization goal of finding a set of \(\mu \) points that maximizes the underlying indicator. Understanding the difference between these two optimization goals is fundamental when applying indicator-based algorithms in practice. On the one hand, a characterization of the inherent optimization goal of different indicators allows the user to choose the indicator that meets her preferences. On the other hand, knowledge about the sets of \(\mu \) points with optimal indicator values – the so-called optimal\(\mu \)-distributions – can be used in performance assessment whenever the indicator is used as a performance criterion. However, theoretical studies on indicator-based optimization are sparse.

One of the most popular indicators is the weighted hypervolume indicator. It allows to guide the search towards user-defined objective space regions and at the same time has the property of being a refinement of the Pareto dominance relation with the result that maximizing the indicator results in Pareto-optimal solutions only. In previous work, we theoretically investigated the unweighted hypervolume indicator in terms of a characterization of optimal \(\mu \)-distributions and the influence of the hypervolume’s reference point for general bi-objective optimization problems. In this paper, we generalize those results to the case of the weighted hypervolume indicator. In particular, we present general investigations for finite \(\mu \), derive a limit result for \(\mu \) going to infinity in terms of a density of points and derive lower bounds (possibly infinite) for placing the reference point to guarantee the Pareto front’s extreme points in an optimal \(\mu \)-distribution. Furthermore, we state conditions about the slope of the front at the extremes such that there is no finite reference point that allows to include the extremes in an optimal \(\mu \)-distribution — contradicting previous belief that a reference point chosen just above the nadir point or the objective space boundary is sufficient for obtaining the extremes. However, for fronts where there exists a finite reference point allowing to obtain the extremes, we show that for \(\mu \) to infinity, a reference point that is slightly worse in all objectives than the nadir point is a sufficient choice. Last, we apply the theoretical results to problems of the ZDT, DTLZ, and WFG test problem suites.

One of the most popular indicators is the weighted hypervolume indicator. It allows to guide the search towards user-defined objective space regions and at the same time has the property of being a refinement of the Pareto dominance relation with the result that maximizing the indicator results in Pareto-optimal solutions only. In previous work, we theoretically investigated the unweighted hypervolume indicator in terms of a characterization of optimal \(\mu \)-distributions and the influence of the hypervolume’s reference point for general bi-objective optimization problems. In this paper, we generalize those results to the case of the weighted hypervolume indicator. In particular, we present general investigations for finite \(\mu \), derive a limit result for \(\mu \) going to infinity in terms of a density of points and derive lower bounds (possibly infinite) for placing the reference point to guarantee the Pareto front’s extreme points in an optimal \(\mu \)-distribution. Furthermore, we state conditions about the slope of the front at the extremes such that there is no finite reference point that allows to include the extremes in an optimal \(\mu \)-distribution — contradicting previous belief that a reference point chosen just above the nadir point or the objective space boundary is sufficient for obtaining the extremes. However, for fronts where there exists a finite reference point allowing to obtain the extremes, we show that for \(\mu \) to infinity, a reference point that is slightly worse in all objectives than the nadir point is a sufficient choice. Last, we apply the theoretical results to problems of the ZDT, DTLZ, and WFG test problem suites.

##### MSC:

90C29 | Multi-objective and goal programming |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

evolutionary algorithms; hypervolume indicator; reference point; optimal \(\mu \)-distributions
PDF
BibTeX
XML
Cite

\textit{A. Auger} et al., Theor. Comput. Sci. 425, 75--103 (2012; Zbl 1242.90205)

Full Text:
DOI

##### References:

[1] | Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences, (), 563-570 |

[2] | Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Theory of the hypervolume indicator: optimal \(\mu\)-distributions and the choice of the reference point, (), 87-102 · Zbl 1369.68293 |

[3] | Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evolutionary computation, 19, 1, 45-76, (2011) |

[4] | N. Beume, C.M. Fonseca, M. Lopez-Ibanez, L. Paquete, J. Vahrenhold, On the Complexity of Computing the Hypervolume Indicator, Tech. Rep. CI-235/07, University of Dortmund, 2007. |

[5] | Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: multiobjective selection based on dominated hypervolume, European journal of operational research, 181, 3, 1653-1669, (2007) · Zbl 1123.90064 |

[6] | Beume, N.; Naujoks, B.; Preuss, M.; Rudolph, G.; Wagner, T., Effects of 1-greedy \(\mathcal{S}\)-metric-selection on innumerably large Pareto fronts, (), 21-35 |

[7] | Bourbaki, N., Elements of mathematics: general topology, (1989), Springer, (Chapter 1-4) · Zbl 0145.19302 |

[8] | Branke, J.; Deb, K.; Dierolf, H.; Osswald, M., Finding knees in multi-objective optimization, (), 722-731 |

[9] | Bringmann, K.; Friedrich, T., The maximum hypervolume set yields near-optimal approximation, (), 511-518 |

[10] | Brockhoff, D., Optimal \(\mu\)-distributions for the hypervolume indicator for problems with linear bi-objective fronts: exact and exhaustive results, (), 24-34 |

[11] | Coello Coello, C.A.; Lamont, G.B.; Van Veldhuizen, D.A., Evolutionary algorithms for solving multi-objective problems, (2007), Springer Berlin, Germany · Zbl 1142.90029 |

[12] | Das, I., On characterizing the knee of the Pareto curve based on normal-boundary intersection, Structural and multidisciplinary optimization, 18, 2-3, 107-115, (1999) |

[13] | Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), Wiley Chichester, UK · Zbl 0970.90091 |

[14] | Deb, K.; Mohan, M.; Mishra, S., Evaluating the \(\epsilon\)-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions, Evolutionary computation, 13, 4, 501-525, (Winter 2005) |

[15] | Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multi-objective optimization, (), 105-145, (chapter 6) · Zbl 1078.90567 |

[16] | Emmerich, M.; Beume, N.; Naujoks, B., An EMO algorithm using the hypervolume measure as selection criterion, (), 62-76 · Zbl 1109.68595 |

[17] | Emmerich, M.; Deutz, A.; Beume, N., (), 140-156 |

[18] | Fleischer, M., The measure of Pareto optima. applications to multi-objective metaheuristics, (), 519-533 · Zbl 1036.90530 |

[19] | Friedrich, T.; Horoba, C.; Neumann, F., Multiplicative approximations and the hypervolume indicator, (), 571-578 |

[20] | Hansen, N.; Kern, S., Evaluating the CMA evolution strategy on multimodal test functions, (), 282-291 |

[21] | Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE transactions on evolutionary computation, 10, 5, 477-506, (2006) |

[22] | Huband, S.; Hingston, P.; White, L.; Barone, L., An evolution strategy with probabilistic mutation for multi-objective optimisation, (), 2284-2291 |

[23] | Hughes, E.J., Evolutionary many-objective optimisation: many once or one many?, (), 222-227 |

[24] | Igel, C.; Hansen, N.; Roth, S., Covariance matrix adaptation for multi-objective optimization, Evolutionary computation, 15, 1, 1-28, (2007) |

[25] | Knapp, A.W., Basic real analysis, (2005), Birkhäuser |

[26] | Knowles, J., Parego: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems, IEEE transactions on evolutionary computation, 10, 1, 50-66, (2005) |

[27] | Knowles, J.; Corne, D., On metrics for comparing non-dominated sets, (), 711-716 |

[28] | Knowles, J.; Corne, D., Properties of an adaptive archiving algorithm for storing nondominated vectors, IEEE transactions on evolutionary computation, 7, 2, 100-116, (2003) |

[29] | Knowles, J.D.; Corne, D.W.; Fleischer, M., Bounded archiving using the Lebesgue measure, (), 2490-2497 |

[30] | Lizarraga-Lizarraga, G.; Hernandez-Aguirre, A.; Botello-Rionda, S., G-metric: an M-ary quality indicator for the evaluation of non-dominated sets, (), 665-672 |

[31] | R.C. Purshouse, On the evolutionary optimisation of many objectives, Ph.D. Thesis, The University of Sheffield, 2003. |

[32] | Purshouse, R.C.; Fleming, P.J., An adaptive divide-and-conquer methodology for evolutionary multi-criterion optimisation, (), 133-147 · Zbl 1036.90549 |

[33] | Zitzler, E.; Brockhoff, D.; Thiele, L., The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration, (), 862-876 |

[34] | Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evolutionary computation, 8, 2, 173-195, (2000) |

[35] | Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (), 832-842 |

[36] | Zitzler, E.; Thiele, L., Multiobjective optimization using evolutionary algorithms—a comparative case study, (), 292-301 |

[37] | Zitzler, E.; Thiele, L.; Bader, J., On set-based multiobjective optimization, IEEE transactions on evolutionary computation, 14, 1, 58-79, (2010) |

[38] | Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C.M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE transactions on evolutionary computation, 7, 2, 117-132, (2003) |

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.