ПОРІВНЯЛЬНИЙ АНАЛІЗ ЗАСТОСУВАННЯ ЕВРИСТИЧНИХ АЛГОРИТМІВ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ TSP
Ключові слова:
генетичні алгоритми, NP-комплексна задача, TSP-задача, алгоритм мурашиної колонії, MATLAB
Анотація
Необхідність вирішення задачі комівояжера (TSP) часто виникає при вирішенні практично значущих оптимізаційних задач, таких як задачі в області економіки, логістики в найширшому діапазоні застосувань, в ланцюгах технічних програм. Досить часто специфіка цих задач вимагає отримання рішення, максимально наближеного до точного значення. Але задача TSP є NP-складною, тобто її точний розв’язок можна отримати лише за експоненціальний час. Тому розв’язувати задачу TSP за алгоритмом повного пошуку за наявності великої кількості вершин графа неефективно. Однак існують різноманітні евристичні алгоритми, які дозволяють знайти раціональне рішення цієї задачі з великою кількістю вершин за час, прийнятний для відповідної предметної області. У даній роботі задача комівояжера визначається як задача математичного програмування знаходження найкоротшого шляху руху комівояжера, метою якої є відвідування всіх об’єктів, задіяних у задачі в найкоротший термін і з мінімальними витратами. Відповідні адаптації евристичних алгоритмів, а саме генетичного алгоритму та алгоритму мурашиної колонії, розроблені в середовищі MATLAB. Проведено обчислювальний експеримент на вхідній вибірці, проведено порівняльний аналіз продуктивності двох евристичних алгоритмів і доведено ефективність використання евристичних алгоритмів для розв’язування NPкомплексних задач.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. The Traveling Salesman Problem: A Computational Study, D.L. Applegate, R.E. Bixby, V. Chvátal & W.J. Cook (2006). [Electronic resource]. URL: https://www.math.uwaterloo.ca/tsp/book/contents.html (Date accessed 11/01/2023).
2. Mathematical methods of operations research: a textbook/ E. A. Lavrov, L. P. Perhun, V. V. Shendryk and others. – Sumy: Sumy State University, 2017. – 212 p.
3. Hassan M. H. Mustafa, Ayoub Al-Hamadi, Mohamed Abdulrahman, Shahinaz Mahmoud, Mohammed O Sarhan On Comparative Analogy between Ant Colony Systems and Neural Networks Considering Behavioral Learning Performance// Journal of Computer Sciences and Applications. 2015, vol. 3 No. 3, 79-89.
4. Biological bases of ant colonies - [Electronic resource]. URL: http://posibniki.com.ua/post-prikladni-sistemi-kolektivnogo-intelektu-swarm-intelli-gence (Date of application 10/15/2023).
5. Rukundo, O., Cao, H. Advances on image interpolation based on ant colony algorithm. SpringerPlus 5, 403 (2016) - [Electronic resource]. URL: https://springerplus.springeropen.com/articles/10.1186/s40064-016-2040-9
6. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) 6th ed., New York, 2018, 455 p.
7. Divya M. A Comparison of Ant Colony Optimization Algorithms Applied to Distribution Network Reconfiguration// International Journal of Engineering Research & Technology, Volume 3, Issue 01, 2016. – pp. 1-4.
8. Hahsler M., Hornik K. TSP – Infrastructure for the Traveling Salesperson Problem// Journal of Statistical Software, December 2007, Vol. 23, Issue 2, 2007. – pp. 1-21.
9. Genetic algorithms. Key concepts and implementation methods. znannya.org : website. URL: http://www.znannya.org/view_ga_general (access date: 10/3/2023).
10. Sathya N., Muthukumaravel A. A review of the Optimization Algorithms on the Traveling Salesman Problem. Indian Journal of Science and Technology, Vol 8(29), DOI: 10.17485/ijst/2015/v8i1/84652, November 2015.
11. Genetic Algorithm Tom V. Mathew Assistant Professor, Department of Civil Engineering, Indian Institute of Technology Bombay, Mumbai-400076.
12. Ivanova E.A. "The possibility of applying genetic algorithms in solving scheduling problems" // Colloquium-journal. 2018. No. 3-1 (14). P. 36-38.
13. Dorigo, M. Ant algorithms and stimergy / M. Dorigo, E. Bonabeau, G. Theraulaz // Future Generation Computer Systems. — 2000. — No. 16. — P. 851-871.
14. Chivilikhin D., Ulyantsev V. Inferring Automata-Based Programs from Specification With Mutation-Based Ant Colony Optimization / Proceedings of the 16th Genetic and Evolutionary Computation Conference companion. - ACM, 2014. - p. 68.
15. Alexandrov A., Sergushichev A., Kazakov S., Tsarev F. Genetic Algorithm for Induction of Finite Automation with Continuous and Discrete Output Actions / Proceedings of the 2011 GECCO Conference Companion on Genetic and Evolutionary Computation. NY. : ACM. 2011, p. 778.
16. Getting Started with MATLAB. Version 6.5. The MathWorks, Inc., 2002.
2. Mathematical methods of operations research: a textbook/ E. A. Lavrov, L. P. Perhun, V. V. Shendryk and others. – Sumy: Sumy State University, 2017. – 212 p.
3. Hassan M. H. Mustafa, Ayoub Al-Hamadi, Mohamed Abdulrahman, Shahinaz Mahmoud, Mohammed O Sarhan On Comparative Analogy between Ant Colony Systems and Neural Networks Considering Behavioral Learning Performance// Journal of Computer Sciences and Applications. 2015, vol. 3 No. 3, 79-89.
4. Biological bases of ant colonies - [Electronic resource]. URL: http://posibniki.com.ua/post-prikladni-sistemi-kolektivnogo-intelektu-swarm-intelli-gence (Date of application 10/15/2023).
5. Rukundo, O., Cao, H. Advances on image interpolation based on ant colony algorithm. SpringerPlus 5, 403 (2016) - [Electronic resource]. URL: https://springerplus.springeropen.com/articles/10.1186/s40064-016-2040-9
6. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) 6th ed., New York, 2018, 455 p.
7. Divya M. A Comparison of Ant Colony Optimization Algorithms Applied to Distribution Network Reconfiguration// International Journal of Engineering Research & Technology, Volume 3, Issue 01, 2016. – pp. 1-4.
8. Hahsler M., Hornik K. TSP – Infrastructure for the Traveling Salesperson Problem// Journal of Statistical Software, December 2007, Vol. 23, Issue 2, 2007. – pp. 1-21.
9. Genetic algorithms. Key concepts and implementation methods. znannya.org : website. URL: http://www.znannya.org/view_ga_general (access date: 10/3/2023).
10. Sathya N., Muthukumaravel A. A review of the Optimization Algorithms on the Traveling Salesman Problem. Indian Journal of Science and Technology, Vol 8(29), DOI: 10.17485/ijst/2015/v8i1/84652, November 2015.
11. Genetic Algorithm Tom V. Mathew Assistant Professor, Department of Civil Engineering, Indian Institute of Technology Bombay, Mumbai-400076.
12. Ivanova E.A. "The possibility of applying genetic algorithms in solving scheduling problems" // Colloquium-journal. 2018. No. 3-1 (14). P. 36-38.
13. Dorigo, M. Ant algorithms and stimergy / M. Dorigo, E. Bonabeau, G. Theraulaz // Future Generation Computer Systems. — 2000. — No. 16. — P. 851-871.
14. Chivilikhin D., Ulyantsev V. Inferring Automata-Based Programs from Specification With Mutation-Based Ant Colony Optimization / Proceedings of the 16th Genetic and Evolutionary Computation Conference companion. - ACM, 2014. - p. 68.
15. Alexandrov A., Sergushichev A., Kazakov S., Tsarev F. Genetic Algorithm for Induction of Finite Automation with Continuous and Discrete Output Actions / Proceedings of the 2011 GECCO Conference Companion on Genetic and Evolutionary Computation. NY. : ACM. 2011, p. 778.
16. Getting Started with MATLAB. Version 6.5. The MathWorks, Inc., 2002.
Опубліковано
2024-04-30
Як цитувати
SkakalinaО. Порівняльний аналіз застосування евристичних алгоритмів для розв’язання задачі tsp / SkakalinaО., A. Kapiton // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2024. – Т. 2 (76). – С. 144-151. – doi:https://doi.org/10.26906/SUNZ.2024.2.144.
Розділ
Інформаційні технології
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
