UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2016; 4: 3-10
http://dx.doi.org/10.17213/0321-2653-2016-4-3-10
RESEARCH OF GENERATIONAL STRATEGIES FOR SOLVING HOMOGENEOUS AND HETEROGENEOUS MINIMAX PROBLEM BY VARIOUS MODIFICATIONS OF GENETIC ALGORITHM
Shcherbinina Natalya Igorevna – postgraduate student, department «Computer Systems and Information Security», Don State Technical University, Rostov-on-Don, Russia. E-mail: TrotsyukNaTa@yandex.ru
Kobak Valerij Grigorevich – professor, department «Computer Systems and Information Security», department «Software Computer Technology and Automated Systems», Don State Technical University, Rostov-on-Don, Russia. E-mail: valera33305@mail.ru
Zhukovskiy Aleksandr Georgievich – Candidate of Technical Sciences, professor, department «Software Computer Technology and Automated Systems», Don State Technical University, Rostov-on-Don, Russia. E-mail: zhykovskij@mail.ru
Abstract
This article discusses the homogeneous and heterogeneous scheduling problems related to the class of NP-complete problems. To solve the problems was considered a genetic algorithm - Goldberg model and its modification using the principle of the participation of each individual in a crossover. To improve the results has been used the island model with and without migration, as well as generational strategy. Computational experiment was carried out for the analysis of the algorithms, based on which conclusions about the modifications.
Keywords: scheduling theory; NP-complete problems; genetic algorithms; the Goldberg model; the island model; circular migration; random migration; generational strategy.
Full text: [in elibrary.ru]
References
1. Kononov A.V. Aktual'nye zadachi teorii raspisanij: vychislitel'naja slozhnost' i priblizhennye algoritmy. Diss. dokt. fiz.-mat. nauk [Urgent tasks of the theory of schedules: computing complexity and approximate algorithms. Dr. phys. and math. sci. diss.]. Novosibirsk, 2014, 196 p.
2. Kobak V.G., Trocjuk N.I. [Comparative analysis of algorithms: genetic with elite and Krone with genetic initial distribution]. Matematicheskie metody v tehnike i tehnologijah: sbornik trudov mezhdunar. nauch. konf. [Mathematical methods in the equipment and technologies: collection of works of the international scientific conference]. Saratov, 2013, pp. 62–64. [In Russ.]
3. Trocjuk N.I., Kobak V.G. [The solution of a non-uniform minimax task Goldberg's model with use of generational strategy]. Innovacii, jekologija i resursosberegajushhie tehnologii (InJeRT-2014): trudy XI mezhdunarodnogo nauchno-tehnicheskogo foruma [Innovation, ecology and resource-saving technologies (INERT-2014): works XI of the international scientific and technical forum]. Rostov-on-Don, 2014, pp. 1497 – 1500. [In Russ.]
4. Holland J. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence.— USA: University of Michigan, 1975, 227 p.
5. Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning. – USA: Addison-Wesley Publishing Company, Inc., 1989, 403 p.
6. Kobak V.G., Titov D.V. [Research of tournament selection in a genetic algorithm for the solution of a uniform minimax task]. Matematicheskie metody v tehnike i tehnologijah: sbornik trudov mezhdunar. nauch. konf. [Mathematical methods in the equipment and technologies: collection of works of the international scientific conference]. Saratov, 2008, vol. 5, pp. 12 – 14. [In Russ.]
7. Kobak V.G., Titov D.V., Trocjuk N.I. Povyshenie jeffektivnosti modificirovannoj modeli Goldberga v odnorodnyh sistemah obrabotki informacii algoritmicheskimi preobrazovanijami [Increase in efficiency of the modified Goldberg's model in uniform systems of information processing by algorithmic transformations]. Rostov-on-Don, DGTU, 2015, 86 p. Available at: http://www.ntb.donstu.ru/content/2015191. (accessed 17.06.2016)
8. Shherbinina N.I., Kobak V.G., Zhukovskij A.G. Issledovanie vlijanija razlichnyh vidov migracij pri reshenii minimaksnoj zadachi ostrovnoj model'ju [Research of influence of different types of migrations at the solution of a minimax task island model]. Izv. vuzov. Sev.-Kavk. region. Tehn. nauki, 2016, no. 2(190), pp. 3 – 9. [In Russ.]
9. Kobak V.G. Metodologija sopostavitel'no-kriterial'noj analiticheskoj ocenki raspredelitel'nyh zadach i sredstva ee programmno algoritmicheskoj podderzhki. Diss. dokt. tekhn. nauk [Methodology of comparative and criteria analytical assessment of distributive tasks and means her programmatically algorithmic support. Dr. techn. sci. diss.]. Rostov-on-Don, 2008, 46 p.
10. Kurejchik V.M., Knysh D.S. [Parallel genetic algorithm]. Integrirovannye modeli i mjagkie vychislenija v iskusstvennom intellekte: sb. nauch. tr. V Mezhdunar. nauch.-praktich. konf [Models and problems of construction: the Integrated models and soft calculations in artificial intelligence: collection of scientific works of the V International scientific practical conference]. Moscow, Fizmatlit Publ., 2009, pp. 41 – 51. [In Russ.]
11. Whitley D., Rana S., Heckendorn R. The Island Model Genetic Algorithm: On Separability, Population Size and Convergence. USA: Colorado State University, 1998, 17 p.
12. Affenzeller M., Wagner S., Winkler S., Beham A. Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. USA: CRC Press, 2009, 364 p.
13. Kaljuka V.I., Kobak V.G., Trocjuk N.I., Zubakin V.V. Algoritmicheskoe uluchshenie modificirovannoj modeli Goldberga v odnorodnyh sistemah obrabotki informacii [Algorithmic improvement of the modified Goldberg's model in uniform systems of information processing]. Izv. vuzov. Sev.-Kavk. region. Tehn. Nauki, 2015, no. 2 (183), pp. 3 – 7. [In Russ.]