Vestnik of Don State Technical UniversityVestnik of Don State Technical UniversityВестник Донского государственного технического университета1992-5980351310.12737/5708МеханикаMechanicsМеханикаCompare of generational strategy application in Goldberg and Holland models for the homogeneous minimax problem solutionСравнение использования поколенческой стратегии в моделях Голдберга и Холланда при решении однородной минимаксной задачиКобакВалерий ГригорьевичKobakValeriy Григорьевичvalera33305@mail.ruТроцюкНаталья ИгоревнаTrotsyukNatalya ИгоревнаTrotsyukNaTa@yandex.ru3009201430092014143138144https://zh-szf.ru/en/nauka/article/3513/view
Представлен сравнительный анализ эффективности классических моделей Голдберга и Холланда и их модификаций, использующих различные варианты поколенческой стратегии. В классических генетических алгоритмах используется концепция, предполагающая, что количество особей в поколении не изменяется. Рассмотрен подход, позволяющий повысить эффективность работы стандартных моделей Голдберга и Холланда за счёт варьирования количества особей в поколении. Различные варианты поколенческой стратегии применены для решения однородной минимаксной задачи теории расписаний, относящейся к классу NP-полных задач. Проведённый вычислительный эксперимент для различного количества процессоров и работ показал, что данный подход позволяет значительно повысить эффективность работы генетических алгоритмов путём малых изменений стандартных моделей, позволяя получать решение, более близкое к точному.
The comparative analysis of the effectiveness of Goldberg and Holland’s classical models and their modifications using various options of the generational strategy is presented. The concept assuming that the number of individuals in a generation does not change is used in the classical genetic algorithms. An approach advancing the efficiency of standard Goldberg and Holland’s models through varying the number of individuals in a generation is considered. Various embodiments of the generational strategy are used to solve the homogeneous minimax scheduling problem related to the class of NP-complete problems. The computational experiment conducted for a various number of processors and works has shown that this approach can significantly improve the genetic algorithm efficiency by small changes in the standard models allowing obtain the solution that is closer to the accurate solution.
Введение. Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. Существуют различные варианты задач теории расписаний. Часть из них является NP-полными. NP-полные задачи образуют подмножество типовых задач в классе NP, к которым можно свести любую другую задачу из этого класса полиномиально быстрым алгоритмом решения [1, 8, 9]. В различных областях дискретной математики, комбинаторики и логики известно множество задач, принадлежащих к классу NP-полных задач. Для этих задач не найдены полиномиальные алгоритмы. Однако и не доказано, что таких алгоритмов не существует. Нахождение точного решения для задачи из класса NP-полных является практически невыполнимым. Поэтому для таких задач разрабатываются различные методы, позволяющие получить приближённое решение.
Кобак, В. Г. Сравнительные характеристики модификации модели Холланда при поко-ленческой стратегии / В. Г. Кобак, Н. И. Троцюк, Б. А. Рожковский // Тр. Сев.-Кавк. фил. Моск. техн. ун-та связи и информатики. - Ростов-на-Дону : ПЦ «Университет» Сев.-Кавк. фил. Моск. техн. ун-та связи и информатики, 2014. - Ч. 1. - С. 319-322.Kobak, V. G., Trotsyuk, N. I., Rozhkovskiy, B. A. Sravnitelnyye kharakteristiki modifikatsii modeli Khollanda pri pokolencheskoy strategii. Trudy Severo-Kavkazskogo filiala Moskovskogo tekhnich-eskogo universiteta svyazi i informatiki. [Comparative characteristics of Holland model modification under generational strategy. Proc. North Caucasian Branch of Moscow Technical University of Communications and Informatics.] Rostov-on-Don : Publ. Center «Universitet» SKF MTUSI, 2014, part 1, pp. 319-322 (in Russian).Кобак, В. Г. Сравнительный анализ алгоритмов : генетического с элитой и Крона с гене-тическим начальным распределением / В. Г. Кобак, Н. И. Троцюк // Мат. методы в технике и тех-нологиях : сб. тр. XXVI междунар. науч. конф. - Саратов, 2013. - Т. 12, ч. 2. - С. 62-64.Kobak, V. G., Trotsyuk, N. I. Sravnitelnyy analiz algoritmov: geneticheskogo s elitoy i Krona s geneticheskim nachalnym raspredeleniyem. Matematicheskiye metody v tekhnike i tekhnologiyakh : sb. trudov XXVI mezhdunar. nauch. konf. [Comparative analysis of algorithms: genetic one with elite and Crohn´s genetic initial distribution. Mathematical Methods in Engineering and Technology : Proc. XXVI Int. Sci. Conf.] Saratov, 2013, vol. 12, part 2, pp. 62-64 (in Russian).Кобак, В. Г. Использование поколенческой стратегии модели Голдберга при решении однородной минимаксной задачи / В. Г. Кобак, Н. И. Троцюк // Аспирант. - 2014. - № 2. - С. 62-64.Kobak, V. G., Trotsyuk, N. I. Ispolzovaniye pokolencheskoy strategii modeli Goldberga pri reshenii odnorodnoy minimaksnoy zadachi. [Application of Goldberg model generational strategy for homogeneous minimax problem solution.] Aspirant, 2014, no. 2, pp. 62-64 (in Russian).Базы данных. Интеллектуальная обработка информации / В. В. Корнеев [и др.]. - Москва : Нолидж, 2000. - 352 с.Korneyev, V. V., et al. Bazy dannykh. Intellektualnaya obrabotka informatsii. [Database. Intelligent information processing.] Moscow : Nolidzh, 2000, 352 p. (in Russian).Нейдорф, Р. А. Сравнительный анализ эффективности вариантов турнирного отбора ге-нетического алгоритма решения однородных распределительных задач / Р. А. Нейдорф, В. Г. Кобак, Д. В. Титов // Вестник Дон. гос. техн. ун-та. - 2009. - Т. 9, № 3. - С. 410-418.Neydorf, R. A., Kobak, V. G., Titiov, D. V. Sravnitelnyy analiz effektivnosti variantov turnirnogo otbora geneticheskogo algoritma resheniya odnorodnykh raspredelitelnykh zadach. [Comparative analysis of alternative effectiveness of genetic algorithm tournament selection for solving homogeneous allocation problems.] Vestnik of DSTU, 2009, vol. 9, no. 3, pp. 410-418 (in Russian).Курейчик, В. М. Генетические алгоритмы и их применение / В. М. Курейчик. - Изд. 2-е, доп. - Таганрог : Изд-во Таганрог. радиотехн. ун-та, 2002. - 242 с.Kureychik, V. М. Geneticheskiye algoritmy i ikh primeneniye. [Genetic algorithms and their application.] Taganrog : TRTU Publ. House, 2nd red., 2002, 242 p. (in Russian).Курейчик, В. М. Генетические алгоритмы / В. М. Курейчик, Л. А. Гладков, В. В. Курейчик. - Москва : Физматлит, 2006. - 319 с.Kureychik, V. М., Gladkov, L. A., Kureychik, V. V. Geneticheskiye algoritmy. [Genetic algo-rithms.] Moscow : Fizmatlit, 2006, 319 p. (in Russian).Коффман, Э. Г. Теория расписаний и вычислительные машины / Э. Г. Коффман. - Москва : Наука, 1984. - 336 с.Koffman, E. G. Teoriya raspisaniy i vychislitelnyye mashiny. [Scheduling theory and computers.] Moscow : Nauka, 1984, 336 p. (in Russian).Пашкеев, С. Д. Машинные методы оптимизации в технике связи / С. Д. Пашкеев, И. Р. Менязов, В. Д. Могилевский. - Москва : Связь, 1976. - 250 c.Pashkeyev, S. D., Menyazov, I. R., Mogilevskiy, V. D. Mashinnyye metody optimizatsii v tekhnike svyazi. [Machine optimization techniques in communication technology.] Moscow : Svyaz, 1976, 250 p. (in Russian).Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Воронеж : Воронеж. гос. техн. ун-т, 1995. - 69 с.Batishchev, D. I. Geneticheskiye algoritmy resheniya ekstremalnykh zadach. [Genetic algo-rithms for solving extremum problems.] Voronezh : VGTU, 1995, 69 p. (in Russian).