ОГЛЯД МЕТОДІВ РОЗВ’ЯЗАННЯ ЗАДАЧ КОМІВОЯЖЕРА ДЛЯ ЗНАХОДЖЕННЯ ОПТИМАЛЬНОГО РІШЕННЯ ПРИ ВИКОНАННІ ЕКОНОМІЧНИХ ЗАДАЧ

  • Nataliya Boyko к.е.н., доцент, доцент кафедри Системи штучного інтелекту, Національний університет “Львівська політехніка”, Львів, Україна https://orcid.org/0000-0002-6962-9363
Ключові слова: транспортна задача; гальмінтонів цикл; остове дерево; задача комівояжера; цикл; транс обчислювальні задачі; алгоритм; редукція; параметри алгоритмів; налаштування параметрів.

Анотація

В даній роботі буде розглянуто декілька існуючих алгоритмів для розв’язання задачі комівояжера. Ціллю даної роботи буде оцінка якості роботи кожного з обраних алгоритмів, порівняння та аналіз отриманих результатів. Описані процеси розв’язку задач комбінаторної оптимізації. Розроблено підхід до налаштування параметрів алгоритму для широкого кола задач. В роботі обговорюються методи розробки формалізованого підходу до налаштування параметрів прикладних алгоритмів комбінаторної оптимізації, який дозволяє підвищити точність розв’язку алгоритмів. Розглядаються підходи та методи, які були виведені в результаті теоретичних розрахунків і досліджень, за допомогою яких можна розв’язати задачі комівояжера. Розглядаються математичні реалізації  алгоритмів методів меж і гілок (Алгоритм Літтла), найближчого сусіда, алгоритму Approx-TSP, мурашиного алгоритму. Результатом роботи даного дослідження являється графік з найоптимальнішим шляхом та часом роботи алгоритму. Для алгоритмів, які потребують спеціальних умов у роботі, матриця буде адаптована та буде враховано можливу похибку. Для решти – матриця буде містити однакові значення для більш точного аналізу. Ціллю даної роботи являється оцінка якості роботи кожного з обраних алгоритмів, порівняння та аналіз отриманих результатів. В статті розглядається підхід налаштування параметрів алгоритму розв’язування задач комівояжера. Для цього формується задача комівояжера та задача оптимізації параметрів на кінцевій сітці. Визначаються алгоритми та їх параметри, для яких будуть відбуватись налаштування. Формується підхід для налаштування параметрів алгоритму. Результатом роботи даного дослідження є графік з найоптимальнішим шляхом та часом роботи алгоритму. Для алгоритмів, які потребують спеціальних умов у роботі, матриця вже адаптована, з врахуванням можливої похибки. Для решти – матриця буде містити однакові значення для більш точного аналізу. Порівнюється складність алгоритму Approx-TSP - O(n) та методу меж і гілок - O(n * log2(n)), тобто при збільшенні матриці, час також буде збільшуватись пропорційно, але складність обрахунків алгоритму будуть збільшуватись зі збільшенням n. Аналізується процес обробки великих даних методом Approx – TSP та методом меж і гілок з врахуванням часу їхньої роботи. Також наводиться обрахунок кількості втрат (погрішність)для точних алгоритмів та приближених. В роботі проаналізована та візуалізована динаміка зміни погрішності відносно збільшення кількості міст.

Статистика завантажень

##plugins.generic.usageStats.noStats##

Посилання

Whitley, D. A. (1993). Genetic Algorithm Tutorial.

Rana, S. (1999). Examining the Role of Local Optima and Schema Processing in Genetic Search.

Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor.

Gen, M., Cheng, R. (1997). Genetic Algorithms and Engineering design, John Wiley & Sons, 352 p.

Hadjiconstantinou, E., Christofides, N. (1995). An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, vol. 83, pp. 39-56.

Lai, K.K., Chan, J.W.M. (1997). Developing a simulated annealing algorithm for the cutting stock problem, Computers & Industrial Engineering, vol. 32, pp. 115-127.

Tsai, R.D., Malstrom, E.M., Meeks, H.D. (1988). A two-dimensional palletizing procedure for warehouse loading operations, IIE Transactions, vol. 20, pp. 418–425.

Boyko, N., Pytel, A. (2021). Application of Genetic Algorithms for Optimization of Salesman's Tasks and Their Modeling by Sequential Selection, in: Proceedings of the 5th International Conference on Computational Linguistics and Intelligent Systems (COLINS 2021). Volume I: Main Conference Lviv, Ukraine, April 22-23, pp. 969-981.

Hrytsyshyn, Y., Kryvyy, R., Tkatchenko, S. (2007). Genetic Programming For Solving Cutting Problem, Proceedings of the IXth International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics, CADSM 2007, Polyana, Ukraine, pp. 280-282.

Korpyljov, D., Sviridova, T., Tkachenko, S. (2007). Using of genetic algorithms in design of Hybrid Integrated Circuits, Proceedings of the IXth International Conference on “The Experience of Designing and Application of CAD Systems in Microelectronics” CADSM 2007, Polyana, Ukraine, 302 p.

Boyko, N., Moroz, O. (2021). Comparative Analysis of Regression Regularization Methods for Life Expectancy Prediction in: Modern Machine Learning Technologies and Data Science Workshop. Proc. 3rd International Workshop MoMLeT&DS 2021. Lviv-Shatsk, Ukraine, June 5-6, pp. 310-326.

Boyko, N., Kmetyk-Podubinska, K., Andrusiak, I. (2021) Application of Ensemble Methods of Strengthening in Search of Legal Information. In: Babichev S., Lytvynenko V. (eds) Lecture Notes in Computational Intelligence and Decision Making. ISDMCI 2021. Lecture Notes on Data Engineering and Communications Technologies, vol 77. Springer, Cham., pp. 188-200. https://doi.org/10.1007/978-3-030-82014-5_13

Larra Naga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I., Dizdarevic, S. (1999). Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators,. Artificial Intelligence Review, Kluwer Academic Publishers. Printed in the Netherlands, Vol. 13(2), pp. 129–170.

Majumdar, J., Bhunia, A.K. (2011). Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times. Journal of Computational and Applied Mathematics, Elsevier, Vol. 235, Issue 9, pp. 3063-3078.

Semenkina, O. Е., Popov, E. А., Semenkina, O. Е. (2013). Self-configuring evolutionary algorithms for travelling salesman problem. Journal of Siberian State Aerospace University named after academician M. F. Reshetnev , Vol. 4(50), pp. 134-139.

Mitchell, M. (1999). An Introduction to Genetic Algorithms, Cambridge USA, London UK: MIT Press.

Shabalov, A., Semenkin, E., Galushin, P. (2011). Automatized Design Application Of Intelligent Information Technologies for Data Mining Problems. Joint IEEE Conference “The 7th Inter-national Conference on Natural Computation & The 8th International Conference on Fuzzy Systems and Knowledge Discovery”, Shanghai, China, pp. 2659–2662.

Semenkin, E., Semenkina, M.(2012). Self configuring genetic algorithm with modified uniform crossover operator, Advances in Swarm Intelligence, ICSI 2012, Part 1, LNCS 7331, Springer, Heidelberg, pp. 414.–421.

Chen, X., Zhang, P., Du, G., Li, F. (2018). Ant colony optimization based memetic algorithm to solve bi-objective multiple traveling salesmen problem for multi-robot systems, Received March 14, 2018, accepted April 12, 2018, date of publication April 19, 2018, date of current version May 9, Digital Object Identifier 10.1109/ACCESS.2018.2828499

Grady, L., Schwartz, E. L. (2006). Isoperimetric Graph partitioning for Image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.28(3), pp.469-475.

Gaber, J., Bakhouya, M. (2007). An Immune Inspired-based Optimization Algorithm: Application to the Traveling Salesman Problem. Advanced Modeling and Optimization, Vol. 9(1), pp. 105–116.

Переглядів анотації: 106
Завантажень PDF: 40
Опубліковано
2021-06-30