ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2020; 1: 5-10
http://dx.doi.org/10.17213/1560-3644-2020-1-5-10
ПОДХОД К УМЕНЬШЕНИЮ ВРЕМЕНИ РАБОТЫ ДВУХЭТАПНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Жуковский Александр Георгиевич – д-р полит. наук, профессор, канд. техн. наук, доцент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: zhykovskij@mail.ru
Пешкевич Алексей Андреевич – аспирант, Донской государственный технический университет, г. Ростов-на-Дону. Россия. E-mail: alexschume@mail.ru
Аннотация
Рассматривается проблема решения задачи коммивояжера – одна из многочисленных задач из области комбинаторной оптимизации. Комбинаторная оптимизация – это широкая и бурно развивающаяся область математического программирования и дискретной математики, исследующая структурные и оптимизационные задачи на объектах, имеющих выраженный комбинаторный смысл. Задача коммивояжера входит в число NP-полных и является трансвычислительной. Поэтому для ее решения используются алгоритмы (генетические, муравьиные и т.д.), достигающие приближенных решений за полиномиальное время. Предлагается использовать модифицированный двухэтапный алгоритм на основе модифицированной модели Голдберга. Модель Голдберга рассматривается с наиболее эффективными кроссовером и мутацией, которые были исследованы в предыдущих работах. При увеличении количества особей и количества повторов увеличивается точность решения, однако увеличивается время получения решения. По причине роста времени для получения оптимального и субоптимального решения был поставлен вычислительный эксперимент, состоящий в распараллеленных запусках алгоритма. По результатам вычислительного эксперимента сравнивается эффективность параллельного и последовательного подхода. Применение распараллеливания приводит к существенному уменьшению времени работы алгоритма при сохранении точности решения на уровне последовательного подхода.
Ключевые слова: кроссовер; генетический алгоритм; модифицированная модель Голдберга; мутация; задача коммивояжера; особь; поколение; распараллеливание; двухэтапный генетический алгоритм.
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Задача коммивояжера // Википедия – Свободная энциклопедия. URL https://ru.wikipedia.org/wiki/Задача_коммивояжера (дата обращения 11.10.2018).
- Гладков, Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учеб. пособие. Ростов н/Д.: Ростиздат, 2004. 400 с.
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ / под ред. Л.Н. Красножан. М.: Вильямс, 2013. 1328 с.
- Трансвычислительная задача // Википедия – Свободная энциклопедия. URL https://ru.wikipedia.org/wiki/ Трансвычислительная_задача (дата обращения 11.10.2018).
- Полиномиальное время // Дискретная математика: алгоритмы. URL http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis /np-completeness-2004 (дата обращения 12.10.2018).
- Пешкевич А.А., Кобак В.Г., Жуковский А.Г. Решение задачи коммивояжера с использованием двухэтапного генетического алгоритма / Инженерный вестн. Дона. 2018. № 3. С. 83 – 92.
- Каширина И.Л. Введение в эволюционное моделирование. Воронеж: Изд-во ВГУ, 2007 URL https://docs.google.com/ viewerng/viewer?url=http%3A//window.edu.ru/resource/519/59519/files/may07048.pdf (дата обращения 11.10.2018).
- Кобак В.Г, Жуковский А.Г., Пешкевич А.А. Сравнение путевого и порядкового подходов при решении задачи коммивояжёра модифицированной моделью Голдберга. Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2017. №1. С. 3 – 7. DOI: 10.17213/0321-2653-2017-1-3-7.
- Руководство по языку C# // Microsoft https://docs.microsoft. com/ru-ru/dotnet/csharp/ (дата обращения 11.01.2019).
- TSP_LIB // Ruprecht-Karls-Universität Heidelberg. URL http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (дата обращения 11.10.2018).
- Матрица расстояний // Википедия – Свободная энциклопедия. URL https://ru.wikipedia.org/wiki/ Матрица_расстояний (дата обращения 11.10.2018).
- Кобак В.Г, Рудова И.Ш. Возможности использования элитных особей при решении задачи коммивояжера моделью Голдберга / Вестн. Донского гос. техн. ун-та. 2016. № 2. С. 129 – 135. DOI: 10.12737/19695.
- Кобак В.Г, Кривошей Н.И. Исследование модифицированной модели Уитли с различным количеством и различными методами формирования элитных особей / Вестн. Донского гос. техн. ун-та. 2018. № 2. С. 223 – 229. DOI 10.23947/1992-5980-2018-18-2-223-229.
- Библиотека параллельных задач (TPL) // Microsoft URL https://docs.microsoft.com/ru-ru/dotnet/standard/parallel-program ming/task-parallel-library-tpl (дата обращения 10.01.2019).
- Кобак В.Г, Жуковский А.Г., Кузин А.П. Исследование модификаций турнирного отбора при решения неоднородной минимаксной задачи модифицированной моделью Голдберга / Инженерный вестн. Дона. № 2. 2018. С. 67 – 77. URL http://ivdon.ru/ru/magazine/archive/N2y2018/4962 (дата обращения 22.01.2019)