Статья

Название статьи ИССЛЕДОВАНИЕ ВЛИЯНИЯ СИЛЬНЫХ МУТАЦИЙ ПРИ РЕШЕНИИ ЗАДАЧИ КОММИВОЯЖЕРА МОДИФИЦИРОВАННОЙ МОДЕЛЬЮ ГОЛДБЕРГА
Автор И.Ш. Рудова, В.Г. Кобак
Рубрика РАЗДЕЛ II. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ И УПРАВЛЕНИЯ
Месяц, год 03, 2017
Индекс УДК 519.6
DOI
Аннотация Исследовано влияние сочетания различных кроссоверов и мутаций на результат работы генетического алгоритма (ГА) при решении задачи коммивояжера (ЗК). ЗК является NP сложной задачей дискретной оптимизации, для которой не найдено, а возможно и не существует алгоритма, позволяющего находить точное решение за полиномиальное время. Вероятность мутации и кроссовера в предложенном алгоритме составляет 100%. Испытания проводились на графах средней размерности. ГА один из эффективных полиномиальных алгоритмов для нахождения приближённых решений ЗК. ГА относится к эволюционные методам решения задач, предназначенных для поиска предпочтительных решений и основаны на статистическом подходе к исследованию ситуаций и итерационным приближении к искомому состоянию систем. В использованной версии ГА применяется модифицированная модель Голдбегрга. В качестве стратегии отбора в ГА использовалась стратегия - «Сравнение мутирующей особи с предком, а далее лучшей из них со случайной особью в поколении». Она показала себя, как одна из лучших в ходе различных вычислительных экспериментов. Разработано программное обеспечение, реализующие данный алгоритм. Предложенный метод позволяет находить известное лучшее решение для графов до 30 вершин. А также отклонение лучшего найденного решения от оптимального не превышает 5.1%, что является вполне допустимым для графов с размерностью от 50 до 60 вершин. Также следует отметить, что разница между лучшим и средним значениями из 30 запусков составляет приблизительно 1.5 %.

Скачать в PDF

Ключевые слова Задача коммивояжера; генетический алгоритм; граф; модель Голдберга; селекция, мутация; кроссовер; природные вычисления; гамильтонов цикл.
Библиографический список 1. Задача коммивояжёра. Википедия. – URL: https://ru.wikipedia.org/Задача_коммивояжёра (дата обращения: 10.02.2017).
2. Vairamuthu M., Porselvi S., DR. A. N. Balaji, J. Rajesh Babu. Artificial Immune System algo-rithm for multi objective flow shop scheduling problem // International Journal of Innovative Research in Science, Engineering and Technology. – K.L.N. College of Engineering and Technology, Madurai, Tamil Nadu, India, March 2014. – No. 3. – P. 1391-1395.
3. Мудров В.И. Задача о коммивояжере. – М.: Либроком, 2013. – 16 с.
4. Why we are transposing or reversing the directions of all arcs (edges) in the Kosaraju two pass algorithm? – Режим доступа: https://www.quora.com/Why-we-are-transposing-or-reversing-the-directionsof-all-arcs-edges-in-the-Kosaraju-two-pass-algorithm (дата обращения: 02.03.2017).
5. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs. – Режим дос-тупа: https://www.cs.princeton.edu/~bwk/btl.mirror/new/partitioning.pdf (дата обращения: 02.03.2017).
6. Matthias M., Fikret E. Genetic Algorithms For Vertex Splitting in DAGs. – Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.8018&rep=rep1&type=pdf (дата обращения: 15.03.2017).
7. Abdel K.I. Path Partition in Directed Graph-Modeling and Optimization // New Trends in Mathematical Sciences. – Faculty of Arts and Sciences, Islamic University of Lebanon, 2013. – No. 1. – P. 74-84.
8. Alamdari S., Mehrabian A. On a DAG Partitioning Problem. – Режим доступа: http://www.math.uwaterloo.ca/~amehrabi/Articles/DAG_Partitioning.pdf (дата обращения: 23.03.2017).
9. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2006. – 320 с.
10. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моде-лирования. – М.: Физматлит, 2003. – 432 с.
11. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс, 2013. – 1328 с.
12. Каширина И.Л. Введение в эволюционное моделирование: учебное пособие / под ред. Е.С. Котляровой. – Воронеж: Изд-во ВГУ, 2007. – 40 с.
13. Кобак В. Г., Кавтарадзе И.Ш., Бормотов В.В., Швидченко С.А. Решение задачи комми-вояжера модифицированной моделью Гольдберга с помощью различного вида мутаций // Тр. Северо-Кавказского филиала Московского техн. ун-та связи и информатики: меж-дунар. молодеж. науч.-практ. конф. T. 1. – Ростов-на-Дону, 2014. – С. 258-261.
14. Кобак В.Г., Рудова И.Ш. Возможности использования элитных особей при решении задачи коммивояжера моделью Гольдберга // Вестник компьютерных и информационных технологий. – 2016. – № 11 (149). – C. 3-7.
15. Кобак В.Г., Рудова И.Ш., Жуковский А.Г. Сравнительный анализ модифицированной модели Гольдберга и муравьиного алгоритма при решении задачи коммивояжера // Тр. Северо-Кавказского филиала Московского техн. ун-та связи и информатики: междунар. молодеж. науч.-практ. конф. T. 1. – Ростов-на-Дону, 2015. – С. 362-365.
16. Кобак В.Г., Рудова И.Ш. Возможности использования элитных особей при решении задачи коммивояжера моделью Гольдберга // Вестник Донского государственного тех-нического университета. – 2016. – Т. 16, № 2 (85). – C. 129-135.
17. Кобак В.Г., Рудова И.Ш. Решение задачи коммивояжера модифицированной моделью Гольдберга с использованием различных сильных мутаций // Сб. тр. Юбилейной конф. студентов и молодых ученых, посвященной 85-летию ДГТУ. – Ростов-на-Дону: ДГТУ, 2015. – С. 146-156.
18. Кобак В.Г., Рудова И.Ш., Жуковский А.Г., Швидченко С.А. Использование сильной му-тации при решении задачи коммивояжера // Современные тенденции развития науки и технологий. – 2016. – № 6-1.
19. Решение задачи коммивояжера модифицированной моделью Голденберга с помощью совместного использования муравьиного и генетического алгоритмов: свидетельство о государственной регистрации программ для ЭВМ / Рудова И.Ш., Кобак В.Г.
– 2016610345; дата регистрации 11.01.16 г.
20. TSP_LIB. – URL: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (дата обращения 20.02.17).

Comments are closed.