×

Particle swarm metaheuristics for robust optimisation with implementation uncertainty. (English) Zbl 1458.90523

Summary: We consider global non-convex optimisation problems under uncertainty. In this setting, it is not possible to implement a desired solution exactly. Instead, any other solution within some distance to the intended solution may be implemented. The aim is to find a robust solution, i.e., one where the worst possible solution nearby still performs as well as possible.
Problems of this type exhibit another maximisation layer to find the worst case solution within the minimisation level of finding a robust solution, which makes them harder to solve than classic global optimisation problems. So far, only few methods have been provided that can be applied to black-box problems with implementation uncertainty. We improve upon existing techniques by introducing a novel particle swarm based framework which adapts elements of previous methods, combining them with new features in order to generate a more effective approach. In computational experiments, we find that our new method outperforms state of the art comparator heuristics in almost 80% of cases.

MSC:

90C26 Nonconvex programming, global optimization
90C47 Minimax problems in mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 3, 464-501 (2011) · Zbl 1233.90259
[2] Bertsimas, D.; Nohadani, O., Robust optimization with simulated annealing, J. Global Optim., 48, 2, 323-334 (2010) · Zbl 1198.90402
[3] Bertsimas, D.; Nohadani, O.; Teo, K. M., Robust optimization in electromagnetic scattering problems, J. Appl. Phys., 101, 7, Article 074507 pp. (2007)
[4] Bertsimas, D.; Nohadani, O.; Teo, K. M., Nonconvex robust optimization for problems with constraints, INFORMS J. Comput., 22, 1, 44-58 (2010) · Zbl 1243.90176
[5] Bertsimas, D.; Nohadani, O.; Teo, K. M., Robust optimization for unconstrained simulation-based problems, Oper. Res., 58, 1, 161-178 (2010) · Zbl 1226.90074
[6] Branke, J., 1998. Creating robust solutions by means of evolutionary algorithms. In Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P., (Eds.). Parallel Problem Solving from Nature — PPSN V. Springer, Berlin Heidelberg, Berlin, Heidelberg. pp. 119-128
[7] Beyer, H.-G.; Sendhoff, B., Robust optimization – a comprehensive survey, Comput. Methods Appl. Mech. Eng., 196, 33, 3190-3218 (2007) · Zbl 1173.74376
[8] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton University Press: Princeton University Press Princeton and Oxford · Zbl 1221.90001
[9] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math. Oper. Res., 23, 4, 769-805 (1998) · Zbl 0977.90052
[10] Chen, R.; Lucier, B.; Singer, Y.; Syrgkanis, V., Robust optimization for non-convex objectives, (Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17 (2017), Curran Associates Inc.: Curran Associates Inc. USA), 4708-4717
[11] Cramer, A. M.; Sudhoff, S. D.; Zivi, E. L., Evolutionary algorithms for minimax problems in robust design, IEEE Trans. Evol. Comput., 13, 2, 444-453 (2009)
[12] Esteban Diaz, J.; Handl, J.; Xu, D.-L., Evolutionary robust optimization in production planning – interactions between number of objectives, sample size and choice of robustness measure, Comput. Oper. Res., 79, 266-278 (2017) · Zbl 1391.90652
[13] Dinno, A., 2017. dunn.test: Dunn’s Test of Multiple Comparisons Using Rank Sums. R package version 1.3.5.
[14] Dippel, C. J., Using particle swarm optimization for finding robust optima (2010), Natural Computing Group, Universiteit Leiden, (Technical report)
[15] Homem de Mello, T.; Bayraksan, G., Monte carlo sampling-based methods for stochastic optimization, Surveys Oper. Res. Manage. Sci., 19, 1, 56-85 (2014)
[16] Engelbrecht, A., 2012. Particle swarm optimization: velocity initialization. In: 2012 IEEE Congress on Evolutionary Computation. pp. 1-8.
[17] Eiben, A. E.; Smit, S. K., Evolutionary algorithm parameters and methods to tune them, (Hamadi, Y.; Monfroy, E.; Saubion, F., Autonomous Search (2012), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 15-36
[18] Gabrel, V.; Murat, C.; Thiele, A., Recent advances in robust optimization: an overview, Eur. J. Oper. Res., 235, 3, 471-483 (2014) · Zbl 1305.90390
[19] Goerigk, M.; Schöbel, A., Algorithm engineering in robust optimization, (Kliemann, L.; Sanders, P., Algorithm Engineering: Selected Results and Surveys. Algorithm Engineering: Selected Results and Surveys, Volume 9220 of LNCS State of the Art of Lecture Notes in Computer Science (2016), Springer: Springer Berlin/ Heidelberg), 245-279
[20] Herrmann, J. W., A genetic algorithm for minimax optimization problems, (Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, vol. 2 (1999), IEEE), 1099-1103
[21] Hughes, M.; Goerigk, M.; Wright, M., A largest empty hypersphere metaheuristic for robust optimisation with implementation uncertainty, Comput. Oper. Res., 103, 64-80 (2019) · Zbl 1458.90524
[22] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2009), Springer Series in Statistics. Springer: Springer Series in Statistics. Springer New York · Zbl 1273.62005
[23] Jensen, M. T.; New, A., Look at Solving Minimax Problems with Coevolutionary Genetic Algorithms, 369-384 (2004), Springer US: Springer US Boston, MA
[24] Jamil, M.; Yang, X.-S., A literature survey of benchmark functions for global optimization problems, Int. J. Math. Modell. Numer. Optim., 4, 2, 150-194 (2013) · Zbl 1280.65053
[25] Kameyama, K., 2009. Particle swarm optimization – a survey. IEICE Trans. Inf. Syst. E92.D(7), 1354-1361.
[26] Kennedy, J.; Eberhart, R. C., Particle swarm optimization, (Proceedings of the 1995 IEEE International Conference on Neural Networks, vol. 4 (1995)), 1942-1948, Perth, Australia
[27] Kruisselbrink, J., Emmerich, M., Bäck, T., 2010. An archive maintenance scheme for finding robust solutions. In Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G., (Eds.). Parallel Problem Solving from Nature, PPSN XI. Springer, Berlin Heidelberg, Berlin, Heidelberg. pp. 214-223.
[28] Kennedy, J.; Eberhart, R. C.; Shi, Y., Swarm Intelligence (2001), Morgan Kaufmann
[29] Kruisselbrink, J. W.; Reehuis, E.; Deutz, A.; Bäck, T.; Emmerich, M., Using the uncertainty handling cma-es for finding robust optima, (Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO ’11 (2011), ACM: ACM New York, NY, USA), 877-884
[30] Kruisselbrink, J. W., Evolution strategies for robust optimization (2012), Leiden Institute of Advanced Computer Science (LIACS), Faculty of Science, Leiden University, (PhD thesis)
[31] Kouvelis, P.; Yu, G., Robust Discrete Optimization and Its Applications (1997), Kluwer Academic Publishers · Zbl 0873.90071
[32] Masuda, K.; Kurihara, K.; Aiyoshi, E., A novel method for solving min-max problems by using a modified particle swarm optimization In Systems, Man, and Cybernetics (SMC), (2011 IEEE International Conference on (2011), IEEE), 2113-2120
[33] Mirjalili, S.; Lewis, A.; Mostaghim, S., Confidence measure: a novel metric for robust meta-heuristic optimisation algorithms, Inf. Sci., 317, 114-142 (2015)
[34] Marzat, J.; Walter, E.; Piet-Lahanier, H., Worst-case global optimization of black-box functions through kriging and relaxation, J. Global Optim., 55, 4, 707-727 (Apr 2013) · Zbl 1268.90054
[35] Marzat, J.; Walter, E.; Piet-Lahanier, H., A new expected-improvement algorithm for continuous minimax optimization, J. Global Optim., 64, 4, 785-802 (2016) · Zbl 1345.90105
[36] Ong, Y.-S.; Nair, P. B.; Lum, K. Y., Max-min surrogate-assisted evolutionary algorithm for robust design, IEEE Trans. Evol. Comput., 10, 4, 392-404 (2006)
[37] Paenke, I.; Branke, J.; Jin, Y., Efficient search for robust solutions by means of evolutionary algorithms and fitness approximation, IEEE Trans. Evol. Comput., 10, 4, 405-420 (2006)
[38] R Core Team, 2019. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria.
[39] Robinson, J.; Rahmat-Samii, Y., Particle swarm optimization in electromagnetics, IEEE Trans. Antennas Propag., 52, 2, 397-407 (2004) · Zbl 1368.78192
[40] Sengupta, S.; Basak, S.; Peters, R., Particle swarm optimization: a survey of historical and recent developments with hybridization perspectives, Mach. Learn. Knowl. Extraction, 1, 1, 157-191 (2018)
[41] Shi, Y., Eberhart, R., 1998. A modified particle swarm optimizer. In: 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360). pp. 69-73.
[42] Sanders, N.D., Everson, R.M., Fieldsend, J.E., Rahat, A.A.M., 2019. A Bayesian Approach for the Robust Optimisation of Expensive-To-Evaluate Functions. arXiv e-prints, page arXiv:1904.11416.
[43] Shi, Y.; Krohling, R., Co-evolutionary particle swarm optimization to solve min-max problems, (Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002 Congress on, vol. 2 (2002), IEEE), 1682-1687
[44] Talbi, E.-G., Metaheuristics: From Design to Implementation (2009), Wiley Publishing · Zbl 1190.90293
[45] Tsutsui, S.; Ghosh, A., Genetic algorithms with a robust solution searching scheme, IEEE Trans. Evol. Comput., 1, 3, 201-208 (1997)
[46] ur Rehman, S.; Langelaar, M., Expected improvement based infill sampling for global robust optimization of constrained problems, Optim. Eng., 18, 3, 723-753 (2017) · Zbl 1390.90457
[47] ur Rehman, S.; Langelaar, M.; van Keulen, F., Efficient kriging-based robust optimization of unconstrained problems, J. Comput. Sci., 5, 6, 872-881 (2014)
[48] Khac Vu, K.; D’Ambrosio, C.; Hamadi, Y.; Liberti, L., Surrogate-based methods for black-box optimization, Int. Trans. Oper. Res., 24, 3, 393-424 (2016) · Zbl 1366.90196
[49] Zhang, Y.; Wang, S.; Ji, G., A comprehensive survey on particle swarm optimization algorithm and its applications, Math. Prob. Eng., 2015 (2015) · Zbl 1394.90588
[50] Zhou, A., Zhang, Q., 2010. A surrogate-assisted evolutionary algorithm for minimax optimization. In: IEEE Congress on Evolutionary Computation. pp. 1-7.
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.