2021, issue 3, p. 5-14
Received 02.07.2021; Revised 23.07.2021; Accepted 28.09.2021
Published 30.09.2021; First Online 25.10.2021
https://doi.org/10.34229/2707-451X.21.3.1
Previous | Full text (in Ukrainian) | Next
Genetic Algorithms as Computational Methods for Finite-Dimensional Optimization
Nataliya
Gulayeva 1 * 
,
Volodymyr Shylo 2, Mykola Glybovets 1
1 National University of Kyiv-Mohyla Academy
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. As early as 1744, the great Leonhard Euler noted that nothing at all took place in the universe in which some rule of maximum or minimum did not appear [12]. Great many today’s scientific and engineering problems faced by humankind are of optimization nature. There exist many different methods developed to solve optimization problems, the number of these methods is estimated to be in the hundreds and continues to grow. A number of approaches to classify optimization methods based on various criteria (e.g. the type of optimization strategy or the type of solution obtained) are proposed, narrower classifications of methods solving specific types of optimization problems (e.g. combinatorial optimization problems or nonlinear programming problems) are also in use. Total number of known optimization method classes amounts to several hundreds. At the same time, methods falling into classes far from each other may often have many common properties and can be reduced to each other by rethinking certain characteristics. In view of the above, the pressing task of the modern science is to develop a general approach to classify optimization methods based on the disclosure of the involved search strategy basic principles, and to systematize existing optimization methods.
The purpose is to show that genetic algorithms, usually classified as metaheuristic, population-based, simulation, etc., are inherently the stochastic numerical methods of direct search.
Results. Alternative statements of optimization problem are given. An overview of existing classifications of optimization problems and basic methods to solve them is provided. The heart of optimization method classification into symbolic (analytical) and numerical ones is described. It is shown that a genetic algorithm scheme can be represented as a scheme of numerical method of direct search. A method to reduce a given optimization problem to a problem solvable by a genetic algorithm is described, and the class of problems that can be solved by genetic algorithms is outlined.
Conclusions. Taking into account the existence of a great number of methods solving optimization problems and approaches to classify them it is necessary to work out a unified approach for optimization method classification and systematization. Reducing the class of genetic algorithms to numerical methods of direct search is the first step in this direction.
Keywords: mathematical programming problem, unconstrained optimization problem, constrained optimization problem, multimodal optimization problem, numerical methods, genetic algorithms, metaheuristic algorithms.
Cite as: Gulayeva N., Shylo V., Glybovets M. Genetic Algorithms as Computational Methods for Finite-Dimensional Optimization. Cybernetics and Computer Technologies. 2021. 3. P. 5–14. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.3.1
References
1. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems. In Optimization Methods and Applications. In honor of Ivan V. Sergienko's 80th birthday. Vol. 130. Butenko S., Pardalos P., Shylo V., Ed. Cham. Springer. 2017. P. 239–250. https://doi.org/10.1007/978-3-319-68640-0_11
2. Sergienko I.V., Shylo V.P. Problems of discrete optimization: challenges and main approaches to solve them. Cybernetics and Systems Analysis. 2006. 42 (4). P. 465–482. https://doi.org/10.1007/s10559-006-0086-3
3. Sergienko I.V., Hulianytskyi L.F., Sirenko S.I. Classification of applied methods of combinatorial optimization. Cybernetics and Systems Analysis. 2009. 45 (5). P. 732–741. https://doi.org/10.1007/s10559-009-9134-0
4. Zhaldak M.I., Tryus Yu.V. Fundamentals of the theory and methods of optimization: a textbook. Cherkasy. Brama-Ukraina. 2005. 608 p. (in Ukrainian)
5. Gorodetskiy S.Yu., Grishagin V.A. Nonlinear programming and multiextreme optimization: a textbook. Nizhniy Novgorod. Izd-vo Nizhegorodskogo gosun-ta. 2007. 489 p. (in Russian)
6. Glybovets M.M., Gulayeva N.M. Evolutionary algorithms: a textbook. Kyiv. NaUKMA. 2013. 828 p. (in Ukrainian)
7. Shylo V.P., Glybovets M.M., Gulayeva N.M., Nikishchikhina K.V. Genetic Algorithm of Tournament Crowding Based on Gaussian Mutation. Cybernetics and Systems Analysis. 2020. 56 (2), P. 231–242. https://doi.org/10.1007/s10559-020-00239-4
8. Birattari M., Paquete L., Stützle T., Varrentrapp K. Classification of metaheuristics and design of experiments for the analysis of components. Technical report AIDA-01-05. Darmstadt. Techn. Univ. Darmstadt. 2001. 12 p.
9. Pevneva A.G. Construction of classification of global optimization methods. Mezhdunarodnyy nauchno-issledovatelskiy zhurnal. 2012. 3. P. 14–23. (in Russian)
10. Sörensen K. Metaheuristics – the metaphor exposed. International Transactions in Operational Research. 2015. 22 (1). P. 3–18. https://doi.org/10.1111/itor.12001
11. Schmidhuber J. Deep learning in neural networks: an overview. Neural Networks. 2015. 61. P. 85–117. https://doi.org/10.1016/j.neunet.2014.09.003
12. Euler L. About elastic curves. In Metod nahozhdeniya krivyih liniy, obladayuschih svoystvami maksimuma, libo minimuma ili reshenie izoperimetricheskoy zadachi, vzyatoy v samom shirokom smyisle. N.S. Koshlyakov, Ed. M.–L. GTTI. 1934. P. 447-572. (Seriya «Klassiki estestvoznaniya»). (in Russian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next