GUIDED HYBRID GENETIC ALGORITHM FOR SOLVING GLOBAL OPTIMIZATION PROBLEMS
DOI:
https://doi.org/10.15588/1607-3274-2021-2-18Keywords:
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.
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
How to Cite
Issue
Section
License
Copyright (c) 2021 S. E. Avramenko, T. A. Zheldak, L. S. Koriashkina
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
