Abstract
When optimization is applied in real-world applications, optimal solutions that do not take into account uncertainty are of limited value, since changes or disturbances in the input data may reduce the quality of the solution. One way to find a robust solution and consider uncertainty is to formulate the problem as a min-max optimization problem. Min-max optimization aims to identify solutions which remain feasible and of good quality under even the worst possible scenarios, i.e., realizations of the uncertain data, formulating a nested problem. Employing hierarchical evolutionary algorithms to solve the problem requires numerous function evaluations. Nevertheless, Evolutionary Algorithms can be easily parallelized. This work investigates a parallel model for differential evolution using SciPy, to solve general unconstrained min-max problems. A differential evolution is applied for both the design and scenario space optimization. To reduce the computational cost, the design level optimization is parallelized. The performance of the algorithm is evaluated for a different number of cores and different dimensionality of four benchmark test functions. The results show that, when the right parameters of the algorithm are selected, the parallelization can be of high benefit to a nested differential evolution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
- 2.
The specific model uses the traditional synchronous parallelization of the DE, where also the operators are applied in parallel to produce the population.
References
Adamidis, P.: Parallel evolutionary algorithms: a review. In: Proceedings of the 4th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA 1998), Athens, Greece. Citeseer (1998)
Aissi, H., Bazgan, C., Vanderpooten, D.: Min-max and min-max regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197(2), 427–438 (2009)
Alba, E.: Parallel evolutionary algorithms can achieve super-linear performance. Inf. Process. Lett. 82(1), 7–13 (2002)
Antoniou, M. (2022). https://github.com/MargAnt0/ParallelMinMax_Scipy
Antoniou, M., Papa, G.: Differential evolution with estimation of distribution for worst-case scenario optimization. Mathematics 9(17), 2137 (2021)
Barbosa, H.J.: A genetic algorithm for min-max problems. In: Goodman, E.D. (ed.) Proceedings of the First International Conference on Evolutionary Computation and Its Applications, pp. 99–109 (1996)
Barbosa, H.J.: A coevolutionary genetic algorithm for constrained optimization. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), vol. 3, pp. 1605–1611. IEEE (1999)
Beyer, H.G., Sendhoff, B.: Robust optimization-a comprehensive survey. Comput. Methods Appl. Mech. Eng. 196(33–34), 3190–3218 (2007)
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 (2008)
Fabris, F., Krohling, R.A.: A co-evolutionary differential evolution algorithm for solving min-max optimization problems implemented on GPU using C-CUDA. Expert Syst. Appl. 39(12), 10324–10333 (2012)
Jensen, M.T.: A new look at solving minimax problems with coevolutionary genetic algorithms. In: Metaheuristics: Computer Decision-Making, pp. 369–384. Springer, Boston (2003). https://doi.org/10.1007/978-1-4757-4137-7_17
Kozlov, K., Samsonov, A.: New migration scheme for parallel differential evolution. In: Proceedings of the International Conference on Bioinformatics of Genome Regulation and Structure, pp. 141–144 (2006)
Laskari, E.C., Parsopoulos, K.E., Vrahatis, M.N.: Particle swarm optimization for minimax problems. In: Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002 (Cat. No. 02TH8600), vol. 2, pp. 1576–1581. IEEE (2002)
Luong, T.V., Melab, N., Talbi, E.G.: GPU-based island model for evolutionary algorithms. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO 2010, pp. 1089–1096. Association for Computing Machinery, New York (2010). https://doi.org/10.1145/1830483.1830685
Magalhães, T., Krempser, E., Barbosa, H.: Parallel models of differential evolution for bilevel programming. In: Proceedings of the 2018 International Conference on Artificial Intelligence (2018)
Montemanni, R., Gambardella, L.M., Donati, A.V.: A branch and bound algorithm for the robust shortest path problem with interval data. Oper. Res. Lett. 32(3), 225–232 (2004)
Pedroso, D.M., Bonyadi, M.R., Gallagher, M.: Parallel evolutionary algorithm for single and multi-objective optimisation: differential evolution and constraints handling. Appl. Soft Comput. 61, 995–1012 (2017)
Qiu, X., Xu, J.X., Xu, Y., Tan, K.C.: A new differential evolution algorithm for minimax optimization in robust design. IEEE Trans. Cybern. 48(5), 1355–1368 (2017)
Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997)
Sudholt, D.: Parallel evolutionary algorithms. In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 929–959. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-43505-2_46
Tasoulis, D.K., Pavlidis, N.G., Plagianakos, V.P., Vrahatis, M.N.: Parallel differential evolution. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), vol. 2, pp. 2023–2029. IEEE (2004)
Virtanen, P., et al.: SciPy 1.0 contributors: SciPy 1.0: fundamental algorithms for scientific computing in Python. Nat. Methods 17, 261–272 (2020). https://doi.org/10.1038/s41592-019-0686-2
Wang, H., Feng, L., Jin, Y., Doherty, J.: Surrogate-assisted evolutionary multitasking for expensive minimax optimization in multiple scenarios. IEEE Comput. Intell. Mag. 16(1), 34–48 (2021)
Zhou, A., Zhang, Q.: A surrogate-assisted evolutionary algorithm for minimax optimization. In: IEEE Congress on Evolutionary Computation, pp. 1–7. IEEE (2010)
Acknowledgements
This work was supported by the European Commission’s H2020 program under the Marie Skłodowska-Curie grant agreement No. 722734 (UTOPIAE) and by the Slovenian Research Agency (research core funding No. P2-0098). The authors would like to thank Peter Korošec and Gašper Petelin for interesting discussions regarding this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Antoniou, M., Papa, G. (2022). Evaluation of Parallel Hierarchical Differential Evolution for Min-Max Optimization Problems Using SciPy. In: Mernik, M., Eftimov, T., Črepinšek, M. (eds) Bioinspired Optimization Methods and Their Applications. BIOMA 2022. Lecture Notes in Computer Science, vol 13627. Springer, Cham. https://doi.org/10.1007/978-3-031-21094-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-21094-5_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21093-8
Online ISBN: 978-3-031-21094-5
eBook Packages: Computer ScienceComputer Science (R0)