ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2017; 2: 5-9
http://dx.doi.org/10.17213/0321-2653-2017-2-5-9
РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЁРА ГИБРИДНОЙ ГЕНЕТИЧЕСКОЙ МОДЕЛЬЮ ПРИ ИСПОЛЬЗОВАНИИ ПУТЕВОГО ПОДХОДА
Кобак Валерий Григорьевич – д-р техн. наук, профессор, Донской государственный технический университет, г. Ростов-на-Дону, Россия. Тел. 8-918-580-21-89. E-mail: valera33305@mail.ru
Поркшеян Виталий Маркосович – канд. физ.-мат. наук, профессор, Донской государственный технический университет, г. Ростов-на-Дону, Россия. Тел. 8-918-893-67-70. E-mail: SPU-40@DONSTU.ru
Жуковский Александр Георгиевич – профессор, д-р полит. наук, канд. техн. наук, доцент, Донской государственный технический университет, г. Ростов-на-Дону, Россия. Тел. 8-961-313-68-67. E-mail: zhykovskij@mail.ru
Пешкевич Алексей Андреевич – магистрант, Донской государственный технический университет, г. Ростов-на-Дону, Россия. Тел. 8-908-179-27-05. E-mail: alexschume@mail.ru
Аннотация
Рассмотрено решение задачи коммивояжёра с гибридной генетической моделью с использованием путевого подхода. Для путевого представления используется упорядоченный кроссовер и «жадная мутация». Для решения задачи коммивояжёра указанным способом реализовано программное средство, с помощью которого получены результаты и сделан вывод о том, что использование гибрида моделей Голдберга и CHC при решении позволяет получить оптимальное или субоптимальное решение для графа с большим количеством вершин.
Ключевые слова: задача коммивояжёра; генетический алгоритм; ген; модель Голдберга; модель CHC; путевое представление; кроссовер; упорядоченный кроссовер; жадная мутация.
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Zadacha kommivoyazhera [The travelling salesman problem]. Vikipediya. Available at: https://ru.wikipedia.org/Zadacha_kommivoyazhera (accessed 10.10.2016)
- Gladkov L.A., Kureichik V.V., Kureichik V.M. Geneticheskie algoritmy [Genetic algorithms]. Rostov-on-Don, Rostizdat, 2004, 400 p.
- Kormen T., Leizerson Ch., Rivest R., Shtain K. Algoritmy: postroenie i analiz [Algorithms: construction and analysis]. Moscow, Vil'yams Publ., 2013, 1328 p.
- Transvychislitel'naya zadacha [Transcomputational problem]. Vikipediya. Available at: https://ru.wikipedia.org/wiki/Transvychislitel'naya_zadacha (accessed 10.10.2016)
- Predel Bremermanna [Bremermann's limit]. Vikipediya. Available at: https://ru.wikipedia.org/wiki/Predel_Bremermanna (accessed 10.10.2016)
- Emel'yanov V.V., Kureichik V.V., Kureichik V.M. Teoriya i praktika evolyutsionnogo modelirovaniya [Theory and practice of evolutionary modeling]. Moscow, FIZMATLIT Publ., 2003, 432 p.
- Kashirina, I.L. Vvedenie v evolyutsionnoe modelirovanie [Introduction to evolutionary simulation]. Voronezh, Izd-vo VGU, 2007, 40 p.
- Boroznov, V.O. Issledovanie resheniya zadachi kommivoyazhera [Investigation of solving the travelling salesman problem]. Astrakhan, Vestnik AGTU, 2009.
- Polinomial'noe vremya [Polynomial time]. SGU. Available at: http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/np-completeness-2004 (accessed 12.10.2016)
- Distance matrix. Vikipediya. Available at: https://ru.wikipedia.org/wiki/Distance_matrix (accessed 11.10.2016)
- TSP_LIB. Available at: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (accessed 11.10.2016)