Dynamic algorithm selection for Pareto optimal set approximation. (English) Zbl 1359.90133
Summary: This paper presents a meta-algorithm for approximating the Pareto optimal set of costly black-box multiobjective optimization problems given a limited number of objective function evaluations. The key idea is to switch among different algorithms during the optimization search based on the predicted performance of each algorithm at the time. Algorithm performance is modeled using a machine learning technique based on the available information. The predicted best algorithm is then selected to run for a limited number of evaluations. The proposed approach is tested on several benchmark problems and the results are compared against those obtained using any one of the candidate algorithms alone.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
multiobjective optimization; expensive black-box function; machine learning; classification; algorithm selection; hypervolume metric; featuresReferences:
| [1] | Bader, J., Zitzler, E.: Hype: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1), 45-76 (2011) · doi:10.1162/EVCO_a_00009 |
| [2] | Borrett, J.E., Tsang, E.P.: Adaptive constraint satisfaction: the quickest first principle. In: Computational Intelligence, pp. 203-230. Springer (2009) · Zbl 1184.68470 |
| [3] | Breiman, L.: Random forests. Mach. Learn. 45(1), 5-32 (2001) · Zbl 1007.68152 · doi:10.1023/A:1010933404324 |
| [4] | Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms, vol. 16. Wiley, New York (2001) · Zbl 0970.90091 |
| [5] | Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182-197 (2002) · doi:10.1109/4235.996017 |
| [6] | Durillo, J.J., Nebro, A.J.: jMetal: a java framework for multi-objective optimization. Adv. Eng. Softw. 42(10), 760-771 (2011) · doi:10.1016/j.advengsoft.2011.05.014 |
| [7] | Feng, Z., Zhang, Q., Zhang, Q., Tang, Q., Yang, T., Ma, Y.: A multiobjective optimization based framework to balance the global exploration and local exploitation in expensive optimization. J. Glob. Optim. 61, 677-694 (2014) · Zbl 1323.90045 |
| [8] | Forrester, A.I., Keane, A.J.: Recent advances in surrogate-based optimization. Prog. Aerosp. Sci. 45(1-3), 50-79 (2009) · doi:10.1016/j.paerosci.2008.11.001 |
| [9] | Gao, F., Han, L.: Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Comput. Optim. Appl. 51(1), 259-277 (2012) · Zbl 1245.90121 · doi:10.1007/s10589-010-9329-3 |
| [10] | Garrett, D., Dasgupta, D.: Multiobjective landscape analysis and the generalized assignment problem. In: Learning and Intelligent Optimization, pp. 110-124. Springer (2008) |
| [11] | Han, L., Neumann, M.: Effect of dimensionality on the Nelder-Mead simplex method. Optim. Methods Softw. 21(1), 1-16 (2006) · Zbl 1181.90290 · doi:10.1080/10556780512331318290 |
| [12] | Jiang, S., Ong, Y.S., Zhang, J., Feng, L.: Consistencies and contradictions of performance metrics in multiobjective optimization. IEEE Trans. Cybern. 44(12), 2391-2404 (2014) · doi:10.1109/TCYB.2014.2307319 |
| [13] | Jin, R., Chen, W., Simpson, T.: Comparative studies of metamodelling techniques under multiple modelling criteria. Struct. Multidiscip. Optim. 23(1), 1-13 (2001) · doi:10.1007/s00158-001-0160-4 |
| [14] | Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455-492 (1998) · Zbl 0917.90270 · doi:10.1023/A:1008306431147 |
| [15] | Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: a survey. J. Artif. Intell. Res. 4, 237-285 (1996) · Zbl 0229.65053 |
| [16] | Knowles, J.: Parego: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comput. 10(1), 50-66 (2006) · doi:10.1109/TEVC.2005.851274 |
| [17] | Koduru, P., Dong, Z., Das, S., Welch, S.M., Roe, J.L., Charbit, E.: A multiobjective evolutionary-simplex hybrid approach for the optimization of differential equation models of gene networks. IEEE Trans. Evol. Comput. 12(5), 572-590 (2008) · doi:10.1109/TEVC.2008.917202 |
| [18] | Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385-482 (2003) · Zbl 1059.90146 · doi:10.1137/S003614450242889 |
| [19] | Kursawe, F.; Schwefel, HP (ed.); Mnner, R. (ed.), A variant of evolution strategies for vector optimization, No. 496, 193-197 (1991), Berlin · doi:10.1007/BFb0029752 |
| [20] | Lagarias, J.C., Reeds, J.A., Wright, M.H., Wright, P.E.: Convergence properties of the Nelder-Mead simplex method in low dimensions. SIAM J. Optim. 9(1), 112-147 (1998) · Zbl 1005.90056 · doi:10.1137/S1052623496303470 |
| [21] | Lagoudakis, M.G., Littman, M.L.: Algorithm selection using reinforcement learning. In: ICML, pp. 511-518. Citeseer (2000) · Zbl 1059.90146 |
| [22] | Luersen, M.A., Le Riche, R.: Globalized Nelder-Mead method for engineering optimization. Comput. Struct. 82(23), 2251-2260 (2004) · doi:10.1016/j.compstruc.2004.03.072 |
| [23] | Marler, R.T., Arora, J.S.: Survey of multi-objective optimization methods for engineering. Struct. Multidiscip. Optim. 26(6), 369-395 (2004) · Zbl 1243.90199 · doi:10.1007/s00158-003-0368-6 |
| [24] | Miettinen, K.: Nonlinear Multiobjective Optimization, vol. 12. Springer Science & Business Media, Berlin (1999) · Zbl 0949.90082 |
| [25] | Mockus, J.: Bayesian Approach to Global Optimization. Kluwer Academic Publishers, Dordrecht (1989) · Zbl 0693.49001 · doi:10.1007/978-94-009-0909-0 |
| [26] | Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7(4), 308-313 (1965) · Zbl 0229.65053 · doi:10.1093/comjnl/7.4.308 |
| [27] | Okabe, T.; Jin, Y.; Sendhoff, MOB; Yao, X. (ed.); Burke, E. (ed.); Lozano, J. (ed.); Smith, J. (ed.); Merelo-Guervs, J. (ed.); Bullinaria, J. (ed.); Rowe, J. (ed.); Tio, P. (ed.); Kabn, A. (ed.); Schwefel, HP (ed.), On test functions for evolutionary multi-objective optimization, No. 3242, 792-802 (2011), Berlin · doi:10.1007/978-3-540-30217-9_80 |
| [28] | Pham, N., Wilamowski, B.M.: Improved Nelder Meads simplex method and applications. J. Comput. 3(3), 55-63 (2011) |
| [29] | Ponweiser, W.; Wagner, T.; Biermann, D.; Vincze, M.; Rudolph, G. (ed.); Jansen, T. (ed.); Beume, N. (ed.); Lucas, S. (ed.); Poloni, C. (ed.), Multiobjective optimization on a limited budget of evaluations using model-assisted \[\cal{S}S\]-metric selection, No. 5199, 784-794 (2008), Berlin · doi:10.1007/978-3-540-87700-4_78 |
| [30] | Rice, J.R.: The algorithm selection problem. Comput. Sci. Tech. Rep. (1975). http://docs.lib.purdue.edu/cstech/99 |
| [31] | Santana-Quintero, L.; Montaño, A.; Coello, CC; Tenne, Y. (ed.); Goh, CK (ed.), A review of techniques for handling expensive functions in evolutionary multi-objective optimization, No. 2, 29-59 (2010), Berlin · doi:10.1007/978-3-642-10701-6_2 |
| [32] | Steponavičė, I., Hyndman, R.J., Smith-Miles, K., Villanova, L.: Efficient identification of the Pareto optimal set. In: Learning and Intelligent Optimization, pp. 341-352. Springer International Publishing (2014) · Zbl 1359.90133 |
| [33] | Torczon, V.J.: Multi-directional search: a direct search algorithm for parallel machines. Ph.D. thesis, Citeseer (1989) |
| [34] | Törn, A., Žilinskas, A.: Global Optimization. Springer, New York, NY (1989) · Zbl 0752.90075 |
| [35] | Van Veldhuizen, D.A., Lamont, G.B.: Multiobjective evolutionary algorithm test suites. In: Proceedings of the 1999 ACM Symposium on Applied Computing, pp. 351-357. ACM (1999) |
| [36] | Viennet, R., Fonteix, C., Marc, I.: New multicriteria optimization method based on the use of a diploid genetic algorithm: example of an industrial problem. In: Selected Papers from the European Conference on Artificial Evolution, pp. 120-127. Springer, London (1996) · Zbl 0917.90270 |
| [37] | Wagner, T.: Planning and Multi-objective Optimization of Manufacturing Processes by Means of Empirical Surrogate Models. Vulkan, Essen (2013) |
| [38] | Wu, J., Azarm, S.: Metrics for quality assessment of a multiobjective design optimization solution set. J. Mech. Des. 123(1), 18-25 (2001) · doi:10.1115/1.1329875 |
| [39] | Zahara, E., Kao, Y.T.: Hybrid Nelder-Mead simplex search and particle swarm optimization for constrained engineering design problems. Expert Syst. Appl. 36(2), 3880-3886 (2009) · doi:10.1016/j.eswa.2008.02.039 |
| [40] | Zapotecas-Martínez, S., Coello, C.A.C.: Monss: a multi-objective nonlinear simplex search approach. Eng. Optim. 48, 16-38 (2016) |
| [41] | Zhang, Q., Liu, W., Tsang, E., Virginas, B.: Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Trans. Evol. Comput. 14(3), 456-474 (2010) · doi:10.1109/TEVC.2009.2033671 |
| [42] | Zitzler, E., Brockhoff, D., Thiele, L.: The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration. In: Evolutionary Multi-criterion Optimization, pp. 862-876. Springer (2007) |
| [43] | Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173-195 (2000) · doi:10.1162/106365600568202 |
| [44] | Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Parallel Problem Solving from Nature—PPSN-V, pp. 292-301. Springer (1998) |
| [45] | Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117-132 (2003) · doi:10.1109/TEVC.2003.810758 |
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.
