GUIDED HYBRID GENETIC ALGORITHM FOR SOLVING GLOBAL OPTIMIZATION PROBLEMS

Authors

  • S. E. Avramenko Dnipro University of Technology. COMPARUS.UA, Dnipro, Ukraine.
  • T. A. Zheldak Dnipro University of Technology
  • L. S. Koriashkina Dnipro University of Technology

DOI:

https://doi.org/10.15588/1607-3274-2021-2-18

Keywords:

nonlinear optimization, global minimum, randomized search heuristics, hybrid approach, genetic algorithm, deflation operator, guided local search.

Abstract

Context. One of the leading problems in the world of artificial intelligence is the optimization of complex systems, which is often represented as a nonlinear function that needs to be minimized. Such functions can be multimodal, non-differentiable, and even set as a black box. Building effective methods for solving global optimization problems raises great interest among scientists.

Objective. Development of a new hybrid genetic algorithm for solving global optimization problems, which is faster than existing analogues.

Methods. One of the crucial challenges for hybrid methods in solving nonlinear global optimization problems is the rational use of local search, as its application is accompanied by quite expensive computational costs. This paper proposes a new GBOHGA hybrid genetic algorithm that reproduces guided local search and combines two successful modifications of genetic algorithms. The first one is BOHGA that establishes a qualitative balance between local and global search. The second one is HGDN that prevents reexploration of the previously explored areas of a search space. In addition, a modified bump-function and an adaptive scheme for determining one of its parameters – the radius of the “deflation” of the objective function in the vicinity of the already found local minimum – were presented to accelerate the algorithm.

Results. GBOHGA performance compared to other known stochastic search heuristics on a set of 33 test functions in 5 and 25dimensional spaces. The results of computational experiments indicate the competitiveness of GBOHGA, especially in problems with multimodal functions and a large number of variables.

Conclusions. The new GBOHGA hybrid algorithm, developed on the basis of the integration of guided local search ideas and BOHGA and HGDN algorithms, allows to save significant computing resources and speed up the solution process of the global optimization problem. It should be used to solve global optimization problems that arise in engineering design, solving organizational and management problems, especially when the mathematical model of the problem is complex and multidimensional.

Author Biographies

S. E. Avramenko, Dnipro University of Technology. COMPARUS.UA, Dnipro, Ukraine.

Ms. Sc., Department of System Analysis and Control. Machine Learning Engineer.

T. A. Zheldak, Dnipro University of Technology

PhD, Head of the Department of System Analysis and Control.

L. S. Koriashkina, Dnipro University of Technology

PhD, Associate Professor of the Department of System Analysis and Control.

References

Locatelli M., Schoen F. Global optimization: theory, algorithms, and applications, Society for Industrial and Applied Mathematics, 2013, 432 p. DOI: 10.1137/1.9781611972672

Floudas C. A., Gounaris C. E. A review of recent advances in global optimization, Journal of Global Optimization, 2009, Vol. 45, No. 3, pp. 3–38. DOI 10.1007/s10898-0089332-8

Fasano G., Pinter J. D. Space engineering: modeling and optimization with case studies. Switzerland, Springer, 2016, 492 p. DOI 10.1007/978-3-319-41508-6_18

Rao S. S. Engineering optimization: theory and practice. Hoboken, New Jersey, John Wiley & Sons, 2009, 813 p.

Siddique N., Adeli H. Nature inspired computing: an overview and some future directions, Cognitive Computation, 2015, Vol. 7, No. 6, pp. 706–714.

Wan W., Birch J. B. An improved hybrid genetic algorithm with a new local search procedure, Journal of Applied Mathematics, 2013, Vol. 2013, Article ID 103591, 10 p. DOI: 10.1155/2013/103591

Noack M. M., Funke S. W. Hybrid genetic deflated newton method for global optimisation, Journal of Computational and Applied Mathematics, 2017, Vol. 325, pp. 97–112. DOI: 10.1016/j.cam.2017.04.047

Voudouris C., Tsang E.P., Alsheddy A. Guided local search, Handbook of Metaheuristics. International Series in Operations Research & Management Science Eds.: M. Gendreau, JY. Potvin. Boston, Springer, 2010, Vol. 146, pp. 321–361. DOI: 10.1007/978-1-4419-1665-5_11

Pintér J. D. Global Eds.: P. M. Pardalos, H. E. Romeijn Optimization: Software, Test Problems, and Applications, Handbook of Global Optimization. Nonconvex Optimization and Its Applications. Boston, Springer, 2002, Vol. 62, pp. 515–569. DOI: 10.1007/978-1-4757-5362-2_15

Pardalos P. M., Zhigljavsky A. A., Žilinskas J. Advances in Stochastic and Deterministic Global Optimization. New York, Springer, 2016, 296 p. DOI: 10.1007/978-3-31929975-4

Paulaviˇcius R., Zilinskas J. Simplicial Global Optimization, Journal of Global Optimization, 2014, Vol. 60, No. 4, pp. 61–86. DOI: 10.1007/978-1-4614-9093-7_3

Beliakov G. Cutting angle method – A tool for constrained global optimization, Optimization Methods and Software, 2004, Vol. 19, № 2, pp. 137–151.

Kvasov D. E., Sergeyev Y. D. Univariate geometric Lipschitz global optimization algorithms, Numerical Algebra, Control and optimization, 2012, Vol. 2, No. 1, pp. 69– 90.

Malherbe C., Vayatis N. Global optimization of Lipschitz functions, Machine Learning : 34th International Conference, Sydney, 6–11 August 2017 : proceedings. Australia, PMLR, 2017, Vol. 70, pp. 2314–2323.

Rios L. M., Sahinidis N. V. Derivative-free optimization: a review of algorithms and comparison of software implementations, Journal of Global Optimization, 2013, Vol. 56, pp. 1247–1293. DOI 10.1007/s10898-012-9951-y

Sergeyev Y. Mukhametzhanov M., Kvasov D. et al. Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization, Journal of Optimization Theory and Applications, 2017, Vol. 171, pp. 186–208. DOI: 10.1007/s10957-016-0947-5

Ye P., Pan G., Dong Z. Ensemble of surrogate based global optimization methods using hierarchical design space reduction, Structural and Multidisciplinary Optimization, 2018, Vol. 58, pp. 537–554. DOI: 10.1007/s00158-018-1906-6

Pengcheng Ye. A Review on Surrogate-Based Global Optimization Methods for Computationally Expensive Functions, Software Engineering, 2019, Vol. 7, No. 4, pp. 68–84. DOI: 10.11648/j.se.20190704.11

Li Z., Ruan Sh., Gu J. et al. Investigation on parallel algorithms in efficient global optimization based on multiple points infill criterion and domain decomposition, Structural and Multidisciplinary Optimization, 2016, Vol. 54, No. 4, pp. 747–773. DOI: 10.1007/s00158-016-1441-2

Wang Z., Gehring C., Kohli P. et al. Batched large-scale Bayesian optimization in high-dimensional spaces, Artificial Intelligence and Statistics : Twenty-First International Conference, Lanzarote, 9–11 April 2018 : proceedings. Spain, PMLR, 2018, Vol. 84, pp. 745–754.

Eriksson D., Pearce M., Gardner J. R. et al. Scalable Global Optimization via Local Bayesian Optimization, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8–14, 2019, Vancouver. Canada, BC, 2019, pp. 5497–5508.

Mitchell M. An introduction to genetic algorithms. Cambridge, Mass., MIT Press, 1998, 221 p.

Farrell P. E., Birkisson Á., S. W. Funke Deflation techniques for finding distinct solutions of nonlinear partial differential equations, Society for Industrial and Applied Mathematics. Journal on Scientific Computing, 2015, Vol. 37, No. 4, pp. A2026–A2045.

Nieto-Fuentes R., Segura C., Valdez S. I. A Guided Local Search Approach for the Travelling Thief Problem, IEEE Congress on Evolutionary Computation, Rio de Janeiro, 8– 13 July 2018. Brazil, 2018, pp. 1–8. DOI: 10.1109/CEC.2018.8477821

Touat M. Tayeb F. B., Benhamou B. et al. An Integrated Guided Local Search considering Human Resource Constraints for the Single-machine Scheduling problem with Preventive Maintenance, IEEE International Conference on Systems, Man and Cybernetics, Bari, 6–9 October 2019. Italy, 2019, pp. 3799–3804. DOI: 10.1109/SMC.2019.8914261

Peh S. C. W., Hong J. L. Eds.: Gervasi O. et al. GLSDock – Drug Design Using Guided Local Search, Computational Science and Its Applications. Lecture Notes in Computer Science: 16th International Conference, Beijing, July 4–7 2016 : proceedings. China, Springer, 2016, Vol. 9788, pp. 11–21. DOI: 10.1007/978-3-319-42111-7_2

Jamil M., Yang X. S. A literature survey of benchmark functions for global optimisation problems, International Journal of Mathematical Modelling and Numerical Optimisation, 2013, Vol. 4, No. 2, pp. 150–194. DOI: 10.1504/IJMMNO.2013.055204

Dall’Igna Júnior A., Silva R. S., Mundim K. C. et al. Performance and parameterization of the algorithm simplified generalized simulated annealing, Genetics and Molecular Biology, 2004, Vol. 27, № 4, pp. 616–622.

Khabarlak K., Koriashkina L. Fast Facial Landmark Detection and Applications: A Survey, arXiv: 2101.10808, 2021, 20 p.

Downloads

Published

2021-07-10

How to Cite

Avramenko, S. E., Zheldak, T. A., & Koriashkina, L. S. (2021). GUIDED HYBRID GENETIC ALGORITHM FOR SOLVING GLOBAL OPTIMIZATION PROBLEMS . Radio Electronics, Computer Science, Control, (2), 174–188. https://doi.org/10.15588/1607-3274-2021-2-18

Issue

Section

Control in technical systems