UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2022; 2: 5-11
http://dx.doi.org/10.17213/1560-3644-2022-2-5-11
USING THE MODIFIED GOLDBERG MODEL FOR SOLVING AN INHOMOGENEOUS MINIMAX PROBLEM WITH REPEATS AND STRONG MUTATIONS
Kobak Valeriy G. – Doctor of Technical Sciences, Professor, Department «The Software of Computer Facilities and Automated Systems», valera33305@mail.ru
Tsemenko Oleg I. – Student, Department «The Software of Computer Facilities and Automated Systems».
Abstract
The influence of strong mutations on the formation of initial generations during repetitions is considered in order to obtain improved results, in comparison with the random formation of the initial generation. The minimax scheduling problem itself belongs to the category of NP-complete ones, for which no exact algorithm for solving in polynomial time for large dimensions has yet been found. There are various ways to solve a problem, such as heuristic methods, genetic approach, dynamic programming, exact solutions or hybrid algorithms. This paper analyzes the widely used genetic approach, namely the modified Goldberg model, which uses the principle of crossing each individual, as well as the mutation of offspring and the principle of tournament selection. To solve the problem, a software tool has been developed that allows you to specify the dimension of the problem, set the number of repetitions and the percentage of strong mutation. Also in this paper, the results obtained are presented in the form of tables for a more visual perception of the results of the program, and it is concluded how strong mutations affect the results obtained.
Keywords: heterogeneous problem, scheduling theory, NP-complete problem, genetic algorithm, modified Goldberg mod-el, minimax criterion, classical crossover, main ancestor, classical mutation, strong mutation, repetitions, tournament selection
Full text: [in elibrary.ru]
References
- Conway R.V., Maxwell V.L., Miller L.V. Schedule theory. Moscow: Nauka; 1975. 359 р.
- Alekseev O.T. Complex application of discrete optimization methods. Moscow: Nauka;1987. 250 р.
- Kashirina I.L. Introduction to evolutionary modeling. Voronezh; 2007. 40 p.
- Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning. USA: Addison-Wesley Publishing Company, Inc. 1989. Pp. 28-33.
- Kobak, V.G. et al. Improving the efficiency of a genetic algorithm based on the Goldenberg model through the use of the elite. Izv. vuzov. Sev.-Kavk. region. Techn. nauki= Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2014(3): 12-15. (In Russ.).
- Kobak V.G., Zhukovsky A.G., Kuzin A.P. Study of the use of a single-point crossover in solving an inhomogeneous minimax problem. Engineering Bulletin of the Don. 2018; (1). Accessed at: ivdon.ru/ru/magazine/archive/n1y2018/4714 (In Russ.).
- Kobak V.G., Porksheyan V.M., Kuzin A.P. The use of different variants of mutation in solving a non-homogeneous minimax problem with a modified Goldberg model. Scientific and practical journal “Aspirant”. 2017; (10): 26-29. (In Russ.).
- Kobak V.G., Zhukovsky A.G., Kuzin A.P. Investigation of tournament selection modifications in solving an inhomogeneous minimax problem with a modified Goldberg model. Engineering Bulletin of the Don. 2018; (2). Accessed at: ivdon.ru/ru/magazine/archive/N2y2018/496 (In Russ.).
- Panchenko T.V. Genetic algorithms. Astrakhan: Astrakhan University; 2007.
- Kobak V.G., Zhukovsky A.G., Kuzin A.P. The use of a hybrid algorithm in solving a non-homogeneous minimax problem using strong mutations. Engineering Bulletin of the Don. 2018; (4). Accessed at: ivdon.ru/ru/magazine/archive/n4y2018/5396 (In Russ.).