Modified genetic algorithm of global extremum search in combination with directional methods

Dmitri A. Ovsyannikov   ; Liudmila V. Vladimirova   ; Irina D. Rubtsova   ; Alexey V. Rubanik   ; Vladimir A. Ponomarev

The Bulletin of Irkutsk State University. Series Mathematics, Tome 39 (2022), pp. 17-33

Résumé

In the paper, the stochastic method of global extremum search is discussed, modified and tested. The method is based on normal distribution modeling and provides covariance matrix adaptation. The method is iterative; a genetic algorithm has been developed on its basis. The coordinates of the trial points of each generation are determined using the "best" points of the previous generation and the values of standard normal random variables. Thus, at each stage of the search, a normal distribution is simulated, and its parameters (the mean and the covariance matrix) are estimated through the positions of the "best" points of the previous generation. In this case, there is no need to calculate, store and transform the covariance matrix, which is indisputable advantage of this method. Practice has shown that the dispersion ellipsoid of normal distribution shrinks rapidly with generation number increasing, which can lead to an excessive narrowing the scanning area and obtaining a local extremum instead of a global one. The proposed modification of the method avoids this situation. The trial points are divided into two groups, which are simulated using normal random variables with different standard deviations, at least one of which is greater than 1. Thus, a kind of mutation of the population is carried out, which makes it possible to provide a sufficient number of sample points both near the “best” one and at a distance from it. The modified genetic algorithm is applied to solving the problem of estimating the parameters of nonlinear parametric regression. A successful minimization of the multiextremal function is performed. The stochastic method is used in combination with directional. The numerical results presented confirm the effectiveness of the introduced modification of the genetic algorithm and make it possible to choose from two directed methods the more efficient one for the problem under consideration.

Détail

Keywords: global extremum, genetic stochastic algorithm, nonlinear regression.
Mots-clés : covariance matrix adaptation

Bibliographie

[1] Vladimirova L. V., Zhdanova A. Y., Rubtsova I. D., “Application of the Genetic Global Search Algorithm in Beam Dynamics Optimization Problem”, VI International Conference on Laser researches and technologies - LaPlas-2020, Proceedings, v. 1, National Research Nuclear University MEPhI, M., 2020, 91–92 (in Russian)

[2] Vladimirova L. V., Ovsyannikov D. A., Rubtsova I. D., Monte-Carlo Methods in Applied Problems, VVM Publ, St. Petersburg, 2015, 167 pp. (in Russian)

[3] Ermakov S. M., Monte-Carlo Method and Related Issues, Nauka Publ, M., 1975, 472 pp. (in Russian)

[4] Ermakov S. M., Mitioglova L. V., “On Extreme Search Method Based on the Estimation of the Covariance Matrix”, Computer Engineering, 1977, no. 5, 38–41 (in Russian)

[5] Zhiglyavsky A. A., Mathematical Theory of Global Random Search, Leningrad St. Univ. Publ, L., 1985, 296 pp. (in Russian)

[6] Kotina E. D., Ovsyannikov D. A., “Mathematical model of joint optimization of programmed and perturbed motions in discrete systems”, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 17:2 (2021), 213–224 | DOI

[7] Nesterov Yu.Ye., Convex Optimization Methods, MCCME Publ, M., 2010, 281 pp. (in Russian)

[8] Ovsyannikov D. A., Mizintseva M. A., Balabanov M.Yu., Durkin A. P., Edamenko N. S., Kotina E. D., Ovsyannikov A. D., “Optimization of dynamics of trajectory bundles using smooth and nonsmooth functionals. Part 1”, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 16:1 (2020), 73–84 | DOI

[9] Rubanik A. V., “Solving an Exponential Regression Problem Using a Genetic Algorithm]”, Control Processes and Stability, 7:1 (2020), 64–68 (in Russian)

[10] Srochko V. A., Aksenyushkina E. V., “Parameterization of Some Control Problems by Linear Systems”, The Bulletin of Irkutsk State University. Series Mathematics, 30 (2019), 83–98 (in Russian) | DOI

[11] Srochko V. A., Aksenyushkina E. V., Antonik V. G., “Resolution of a Linear-quadratic Optimal Control Problem Based on Finite-dimensional Models”, The Bulletin of Irkutsk State University. Series Mathematics, 37 (2021), 3–16 (in Russian) | DOI

[12] Fominyh A. V., Karelin V. V., Polyakova L. N., Myshkov S. K., Tregubov V. P., “The codifferential descent method in the problem of finding the global minimum of a piecewise affine objective functional in linear control systems”, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 17:1 (2021), 47–58 (in Russian) | DOI

[13] Ermakov S. M., Semenchikov D. N., “Genetic global optimization algorithms”, Communications in Statistics Part B: Simulation and Computation, 2019 | DOI

[14] Hansen N., Ostermeier A., “Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation”, Proceedings of 1996 IEEE Conference on Evolutionary Computation, ICEC'96 (Berlin, Germany, 1996), 312–317

[15] Igel C., Hansen N., Roth S., “Covariance matrix adaptation for multi-objective optimization.”, Evolutionary Computation, 15:1 (2007), 1–28

[16] Nocedal J., Wright S. J., Numerical optimization. Springer Series in Operations Research and Financial Engineering, Springer, Berlin, 2006, 634 pp.

[17] Qian N., “On the momentum term in gradient descent learning algorithms”, Neural networks, 12:1 (1999), 145–151 | DOI

[18] Vladimirova L., Fatyanova I., “Construction of regression experiment optimal plan using parallel computing”, 2015 International Conference “Stability and Control Processes” in Memory of V. I. Zubov, SCP 2015, 2015, 361–363

[19] Vladimirova L. V., Ovsyannikov D. A., “Random search for global extremum of a function using Markov chains simulation”, Journal of Physics: Conference Series, 1238:1 (2019), 012073 https://iopscience.iop.org/article/10.1088/1742-6596/1238/1/012073

[20] L. V. Vladimirova, A. Y. Zhdanova, I. D. Rubtsova, N. S. Edamenko, “Genetic Stochastic Algorithm Application in Beam Dynamics Optimization Problem”, Stability and Control Processes, Proceedings of the 4th International Conference Dedicated to the Memory of Professor Vladimir Zubov, Lecture Notes in Control and Information Sciences, Springer International Publishing, 2020