ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2020; 4: 13-18
http://dx.doi.org/10.17213/1560-3644-2020-4-13-18
РЕШЕНИЕ ОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ ПРИ РАЗЛИЧНЫХ ПОДХОДАХ ФОРМИРОВАНИЯ НАЧАЛЬНОГО ПОКОЛЕНИЯ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Жуковский Александр Георгиевич – д-р полит. наук, профессор, канд. техн. наук, доцент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: zhykovskij@mail.ru
Липченко Юрий Петрович – ст. преподаватель, кафедра «Физвоспитание», Донской государственный технический университет, г. Ростов-на-Дону. Россия. E-mail: Petyka59@yandex.ru
Шевченко Вадим Вадимович – бакалавр, Донской государственный технический университет, г. Ростов-на-Дону. Россия. E-mail: gusynin.vadim@mail.ru
Аннотация
Рассматривается решение распределительной задачи для однородных систем с помощью модели Голдберга и ее модификаций. Проводится исследование как влияет формирование начального поколения на точность работы генетического алгоритма. Кроме случайного формирования, исследовалось начальное поколение с детерминированными алгоритмами, где использовались самые популярные спи-сочные методы и алгоритм Пашкеева. Схема формирования различных вариантов запуска представлена в статье. В качестве критерия эффективности был использован минимаксный критерий. Аналитически определить, какой из подходов лучше, практически невозможно, поэтому был проведен обширный вычислительный эксперимент для разного количества особей и разного количества останова генетиче-ского алгоритма. Для полноты исследования эксперимента было сгенерировано большое количество исходных случайных матриц в определенном диапазоне, что позволяет с большой долей вероятности сделать результирующий вывод. Проведён анализ результатов работы каждого из предложенных алго-ритмов и сделаны выводы об их эффективности при решении задачи, относящейся к NP-полным, что поможет практически при конструировании однородных систем.
Ключевые слова: распределительная задача; однородная система; модель Голдберга; модификация алгоритма; вычислительные эксперименты; множество заданий; списочные алгоритмы; начальная популяция.
Полный текст: [in elibrary.ru]
Ссылки на литературу
1. Коффман Э.Г. Теория расписания и вычислительные машины. M.: Наука, 1987.
2. Кобак В.Г, Золотых О.А., Жуковский А.Г., Ростов А.Н. Различные подходы к решению однородной минимаксной задачи теории расписаний эвристическими алгоритмами // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 1. С. 41 – 46. DOI: 10.17213/0321-2653-2016-1-41-46
3. Кобак В.Г, Щербинина Н.И., Жуковский А.Г. Исследование поколенческой стратегии при решении однородной и неоднородной минимаксной задачи различными модификациями генетического алгоритма // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 4. С. 3 – 10. DOI: 10.17213/0321-2653-2016-4-3-10.
4. Кобак В.Г, Золотых О.А., Жуковский А.Г., Ростов А.Н. Решение однородной минимаксной задачи различными модификациями алгоритма Крона // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 3.С. 3 – 8. DOI: 10.17213/ 0321-2653-2016-3-3-8.
5. Кобак В.Г., Рудова И.Ш. Возможности использования элитных особей при решении задачи коммивояжера моделью Голдберга // Вестн. Донского гос. техн. ун-а. 2016. Т.16, № 2(85). С. 129 – 135. DOI:10.12737/19695.
6. Кобак В.Г, Поркшеян В.М., Жуковский А.Г., Пешкевич А.А. Решение задачи коммивояжера гибридной генетической моделью при использовании путевого подхода // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2017. № 2. С. 5 – 9. DOI: 10.17213/0321-2653-2017-2-5-9.
7. Кобак В.Г, Рудова И.Ш. Исследование влияния сильных мутаций при решении задачи коммивояжера модифицированной моделью Голдберга // Изв. ЮФУ. Техн. науки. 2017. № 3. С. 140 – 148. DOI: 10.23683/2311-3103-2017-3-140-148.
8. Кобак В.Г, Жуковский А.Г., Кузин А.П. Исследование применения одноточечного кроссовера при решении неоднородной минимаксной задачи // Эл. науч.-техн. журн. «Инженерный вестн. Дона». 2018. № 1(48). 58 с.
9. Кобак В.Г, Жуковский А.Г., Кузин А.П. Исследование модификаций турнирного отбора при решения неоднородной минимаксной задачи модифицированной моделью Голдберга // Эл. науч.-техн. журн. «Инженерный вестник Дона». 2018. № 2(49). 67 с.
10. Кобак В.Г, Кривошей Н.И. Исследование модифицированной модели Уитли с различным количеством и различными методами формирования элитных особей // Вестн. Донского гос. техн. ун-та. 2018. Т.18, № 2. С. 223 – 229. DOI: 10.23947/1992-5980-2018-18-2-223-229.