ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2021; 4: 5-10
http://dx.doi.org/10.17213/1560-3644-2021-4-5-10
РЕШЕНИЕ ОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ ЭКСПЕРИМЕНТАЛЬНЫМ АЛГОРИТМОМ БЕЗ ВОЗВРАТОВ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. valera33305@mail.ru
Шевченко Вадим Вадимович – магистр, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия.
Аннотация
Рассматривается решение распределительной задачи для однородных систем с помощью эвристического алгоритма без возвратов, генетической модели и использование в модифицированной модели Голдберга в качестве элитной особи. Данная задача является NP-полной и решается точными алгоритмами до определенных размеров. Поэтому получили большое распространение генетические, списочные и другие эвристические алгоритмы. Предлагается для решения однородной минимаксной задачи алгоритм без возвратов, основанный на идее алгоритма Романовского, но в отличие от него не является точным. Аналитически доказать, насколько экспериментальный алгоритм лучше или хуже списочных алгоритмов, не получается в силу сложности задачи. При решении модифицированной моделью Голдберга использовался элитизм, где в качестве элитной модели применялся экспериментальный алгоритм. Проведён анализ результатов работы каждого из предложенных алгоритмов и сделаны выводы об их эффективности.
Ключевые слова: распределительная задача, однородная система, эвристический алгоритм без возвратов, модель Голдберга, вычислительные эксперименты, множество заданий, списочные алгоритмы, начальная популяция
Полный текст: [in elibrary.ru]
Ссылки на литературу
1. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. С. 216.
2. Кобак В.Г., Титов Д.В. Исследование турнирного отбора в генетическом алгоритме для решения однородной минимаксной задачи // Математические методы в технике и технологиях – ММТТ – 21: сб. тр. Междунар. науч. конф. Саратов. 2008. №.2. С. 12.
3. Кобак В.Г., Поркшеян В.М., Кузин А.П. Использование различных вариантов мутации при решении неоднородной минимаксной задачи модифицированной моделью Голдберга // Науч.-практич. журн. «Аспирант». 2017. № 10. С. 26 – 29.
4. Аль-Хулайди А.А., Чернышев Ю.О. Разработка параллельного алгоритма нахождения оптимального решения транспортной задачи на кластере // Инженерный вестн. Дона. 2011. № 2. URL: ivdon.ru/ru/magazine/archive/n2y 2011/445/. (дата обращения 07.09.2021)
5. Нетёсов А.С. Эволюционно-генетический подход к решению задач оптимизации. Сравнительный анализ генетических алгоритмов с традиционными методами оптимизации // Инженерный вестн. Дона. 2011. № 3 URL: ivdon.ru/ru/ magazine/archive/n3y2011/459/. (дата обращения 07.09.2021)
6. Курейчик В. М., Кныш Д. С. Параллельный генетический алгоритм. Модели и проблемы построения // Интегрированные модели и мягкие вычисления в искусственном интеллекте: сб. науч. тр. V Междунар. науч.-практ. конф. М.: Физматлит, 2009. С. 41 – 51.
7. Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989. Р. 28 – 33.
8. Affenzeller M., Wagner S., Winkler S., Beham A. Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. USA: CRC Press, 2009. P. 364.
9. Каширина И.Л. Введение в эволюционное моделирование: учеб. пособие. Воронеж: ИПЦ ВГУ, 2007. С. 40.
10. Панченко Т.В. Генетические алгоритмы. Астрахань: Астраханский университет, 2007. С. 87.