×

Speeding up many-objective optimization by Monte Carlo approximations. (English) Zbl 1334.68199

Summary: Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

SHARK; HypE; SMS-EMOA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Auger, A.; Hansen, N., Performance evaluation of an advanced local search evolutionary algorithm, (Proceedings of the IEEE Congress on Evolutionary Computation (CEC) (2005), IEEE Press), 1777-1784
[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 (2009)
[4] Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: Multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[5] Beyer, H.-G., Evolution strategies, Scholarpedia, 2, 8, 1965 (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., An improved algorithm for Kleeʼs measure problem on fat boxes, Comput. Geom., 45, 5-6, 225-233 (2012) · Zbl 1375.52006
[8] Bringmann, K.; Friedrich, T., Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, (Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization (EMO). Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization (EMO), LNCS, vol. 5467 (2009), Springer), 6-20
[9] Bringmann, K.; Friedrich, T., Approximating the volume of unions and intersections of high-dimensional geometric objects, Comput. Geom., 43, 601-610 (2010) · Zbl 1206.65072
[10] Bringmann, K.; Friedrich, T., An efficient algorithm for computing hypervolume contributions, Evol. Comput., 18, 3, 383-402 (2010)
[11] Bringmann, K.; Friedrich, T., Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, Theor. Comput. Sci., 425, 104-116 (2012) · Zbl 1237.68085
[12] Bringmann, K.; Friedrich, T., Parameterized average-case complexity of the hypervolume indicator, (Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO) (2013), ACM Press), 575-582
[13] Bringmann, K.; Friedrich, T., Approximation quality of the hypervolume indicator, Artif. Intell., 195, 265-290 (2013) · Zbl 1270.68238
[14] Brockhoff, D., Theoretical aspects of evolutionary multiobjective optimization, (Auger, A.; Doerr, B., Theory of Randomized Search Heuristics: Foundations and Recent Developments (2011), World Scientific Publishing), 101-139 · Zbl 1235.90184
[15] Coello Coello, C.; Lamont, G. B.; van Veldhuizen, D. A., Evolutionary Algorithms for Solving Multi-Objective Problems (2007), Springer · Zbl 1142.90029
[16] Deb, K., Multi-Objective Optimization using Evolutionary Algorithms (2001), Wiley · Zbl 0970.90091
[17] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 182-197 (2002)
[18] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable multi-objective optimization test problems, (Proceedings of the Congress on Evolutionary Computation (CEC) (2002), IEEE Press), 825-830
[19] Ehrgott, M., Multicriteria Optimization (2010), Springer
[20] Eiben, A. E.; Smith, J. E., Introduction to Evolutionary Computing. Natural Computing (2008), Springer · Zbl 1028.68022
[21] Emmerich, M. T.M.; Fonseca, C. M., Computing hypervolume contributions in low dimensions: Asymptotically optimal algorithm and complexity results, (Proceedings of the Evolutionary Multi-Criterion Optimization (EMO). Proceedings of the Evolutionary Multi-Criterion Optimization (EMO), LNCS, vol. 6576 (2011), Springer), 121-135
[22] (Figueira, J.; Greco, S.; Ehrgott, M., Multiple Criteria Decision Analysis: State of the Art Surveys. Multiple Criteria Decision Analysis: State of the Art Surveys, International Series in Operations Research & Management Science, vol. 78 (2004), Springer) · Zbl 1060.90002
[23] Friedrich, T.; Bringmann, K.; Voß, T.; Igel, C., The logarithmic hypervolume indicator, (Beyer, H.; Langdon, W. B., Proceedings of the 11th International Workshop on Foundations of Genetic Algorithms (FOGA) (2011), ACM Press), 81-92 · Zbl 1369.90157
[24] Hansen, N.; Ostermeier, A., Completely derandomized self-adaptation in evolution strategies, Evol. Comput., 9, 2, 159-195 (2001)
[25] Hansen, N.; Auger, A.; Ros, R.; Finck, S.; Pošík, P., Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009, (Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO) (2010), ACM), 1689-1696
[26] Huband, S.; Hingston, P.; While, L.; Barone, L., An evolution strategy with probabilistic mutation for multi-objective optimisation, (Proceedings of the IEEE Congress on Evolutionary Computation (CEC), vol. 4 (2003)), 2284-2291
[27] Igel, C.; Hansen, N.; Roth, S., Covariance matrix adaptation for multi-objective optimization, Evol. Comput., 15, 1, 1-28 (2007)
[28] Igel, C.; Suttorp, T.; Hansen, N., Steady-state selection and efficient covariance matrix update in the multi-objective CMA-ES, (Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO). Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO), LNCS, vol. 4403 (2007), Springer), 171-185
[29] Igel, C.; Glasmachers, T.; Heidrich-Meisner, V., Shark, J. Mach. Learn. Res., 9, 993-996 (2008) · Zbl 1225.68188
[30] Impagliazzo, R.; Paturi, R., The complexity of \(k\)-SAT, (Proceedings of the 14th IEEE Conference on Computational Complexity (CCC) (1999)), 237-240
[31] Kern, S.; Müller, S.; Hansen, N.; Büche, D.; Ocenasek, J.; Koumoutsakos, P., Learning probability distributions in continuous evolutionary algorithms - A comparative review, Nat. Comput., 3, 77-112 (2004) · Zbl 1074.68063
[32] Miettinen, K., Nonlinear Multiobjective Optimization, Kluwerʼs International Series in Operations Research & Management Science, vol. 12 (1999), Kluwer Academic Publishers · Zbl 0949.90082
[33] Sawaragi, Y.; Nakayama, H.; Tanino, T., Theory of Multiobjective Optimization, Mathematics in Science and Engineering, vol. 176 (1985), Academic Press · Zbl 0566.90053
[34] Suttorp, T.; Hansen, N.; Igel, C., Efficient covariance matrix update for variable metric evolution strategies, Mach. Learn., 75, 2, 167-197 (2009) · Zbl 1470.68183
[35] Ursem, R. K., Centrifugal pump design: Three benchmark problems for many-objective optimization (2010), Grundfos Management A/S, Technical Report 2010-01
[36] Voß, T.; Friedrich, T.; Bringmann, K.; Igel, C., Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: A preliminary study, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO): Workshop on Theoretical Aspects of Evolutionary Multiobjective Optimization (2010), ACM Press), 1975-1978
[37] Voß, T.; Hansen, N.; Igel, C., Improved step size adaptation for the MO-CMA-ES, (Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO) (2010), ACM Press), 487-494
[38] While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, IEEE Trans. Evol. Comput., 16, 1, 86-95 (2012)
[39] Wickramasinghe, U. K.; Carrese, R.; Li, X., Designing airfoils using a reference point based evolutionary many-objective particle swarm optimization, (Proceedings of the IEEE Congress on Evolutionary Computation (2010), IEEE Press), 1857-1864
[40] Yıldız, H.; Suri, S., On Kleeʼs measure problem for grounded boxes, (Proceedings of the ACM Symposium on Computational Geometry (SoCG) (2012)), 111-120 · Zbl 1293.68302
[41] Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN). Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN), LNCS, vol. 3242 (2004), Springer), 832-842
[42] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271 (1999)
[43] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: An analysis and review, IEEE Trans. Evol. Comput., 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. 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.