Gezgin Satıcı Problemlerini Çözmek İçin Arı Algoritmasının İyileştirilmesi

Yıl 2022, , 65 - 74, 31.01.2022

Murat Şahin

https://doi.org/10.17671/gazibtd.991866

Cited By: 2

Öz

Gezgin satıcı problemi (GSP), optimizasyon alanında uzun süredir çalışılan popüler bir problemdir. Bu problemlerin çözümünde kullanılan en başarılı yöntemler ise metasezgisel algoritmalardır. Bu çalışmada, GSP'lerin çözümünde Arı Algoritmasının geliştirilmiş bir versiyonu kullanılmıştır. Klasik Arı Algoritmasına ek olarak iki farklı şehir seçimi ve yer değiştirme fonksiyonu geliştirilmiştir. Bu işlevler ile birden fazla ve değişken sayıdaki şehrin yerini değiştirmek mümkündür. Bu yeni fonksiyonlar klasik Arı Algoritmasının devamına eklenerek ve sadece elit bölgede kullanılmış ve bu bölümün daha elit hale gelmesini sağlamıştır. Böylece mevcut Arı Algoritmasına göre, daha az iterasyon ve arama ile daha iyi sonuçlar elde edilmiştir.

Anahtar Kelimeler

Arı Algoritması, gezgin satıcı problemi, çoklu yerleştirme, optimizasyon

Destekleyen Kurum

Roketsan A. Ş.

Teşekkür

Roketsan A. Ş.

Improvement of the Bees Algorithm for Solving the Traveling Salesman Problems

Öz

The traveling salesman problem (TSP) has been a popular problem studied in the optimization field for a long time. The most successful methods used in solving these difficult problems are metaheuristic algorithms. In this study, an improved version of the bees algorithm is used in the solution of TSPs. In addition to the classical bees algorithm, two different city selection and relocation functions have been developed. With these functions, it is possible to change the location of multiple and variable numbers of cities. These new functions have been added to the continuation of the classical bees algorithm and are used only on the elite site, ensuring that the elite site becomes more elite. Thus, better results could be obtained with less number of iterations and the number of the total evaluation compared to the existing bees algorithm.

Anahtar Kelimeler

The bees algorithm, the traveling salesman problem, multiple insertion, optimization.

Kaynakça

• Z. Daoqing, J. Mingyan, “Parallel Discrete Lion Swarm Optimization Algorithm for Solving Traveling Salesman Problem”, Journal of Systems Engineering and Electronics, 31(4), 751 – 760, 2020.
• J. Xie, L. R. G. Carrillo, L. Jin, “An Integrated Traveling Salesman and Coverage Path Planning Problem for Unmanned Aircraft Systems”, IEEE Control Systems Letters, 3(1), 67-72, 2019.
• X. Meng, J. Li, X. Dai, J. Dou, “Variable Neighborhood Search for a Colored Traveling Salesman Problem”, IEEE Transactions on Intelligent Transportation Systems, 19(4), 1018-1026, 2018.
• E. Çelik, N. Öztürk, “Doğru Akım Motor Sürücüleri için PI Parametrelerinin Simbiyotik Organizmalar Arama Algoritması ile Optimal Ayarı”, Bilişim Teknolojileri Dergisi, 10(3), 311-318, 2017.
• M. Mavrovouniotis, F. M. Müller, S. Yang, “Ant Colony Optimization with Local Search for Dynamic Traveling Salesman Problems”, IEEE Transactions on Cybernetics, 47(7), 1743-1756, 2017.
• X. Chen, P. Zhang, G. Du, F. Li, “Ant Colony Optimization Based Memetic Algorithm to Solve Bi-Objective Multiple Traveling Salesmen Problem for Multi-Robot Systems”, IEEE Access, 6, 21745-21757, 2018.
• E. Liao, C. Liu, “A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem”, IEEE Access, 6, 38921-38933, 2018.
• Y. Liu, B. Cao, “A Novel Ant Colony Optimization Algorithm with Levy Flight”, IEEE Access, 8, 67205-67213, 2020.
• D. Karaboga, B. Gorkemli, “Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms”, International Journal on Artificial Intelligence Tools, 28(1), 1-28, 2019.
• X. Dong, Q. Lin, M. Xu, Y. Cai, “Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem”, IET Intelligent Transport Systems, 13(10), 1483-1491, 2019.
• L. Wang, R. Cai, M. Lin, Y. Zhong, “Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem”, IEEE Access, 7, 144366-144380, 2019.
• X. Han, Y. Dong, L.Yue, Q. Xu, “State Transition Simulated Annealing Algorithm for Discrete-Continuous Optimization Problems”, IEEE Access, 7, 44391-44403, 2019.
• A. Arram, M. Ayob, G. Kendall, A. Sulaıman, “Bird Mating Optimizer for Combinatorial Optimization Problems”, IEEE Access, 8, 96845-96858, 2020.
• I. K. Gupta, A. Choubey, S. Choubey, S., “Randomized bias genetic algorithm to solve traveling salesman problem”, 8th International Conference on Computing, Communication and Networking Technologies (ICCCNT), Delhi, India, 1-6, 2017.
• D. T. Pham, A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim, M. Zaidi, “The Bees Algorithm – A Novel Tool for Complex Optimisation Problems”, Intelligent production machines and systems, 2nd I*PROMS Virtual International Conference, 454-459, 2006.
• M. Zarchi, B. Attaran, “Performance improvement of an active vibration absorber subsystem for an aircraft model using a bees algorithm based on multi-objective intelligent optimization”, Engineering Optimization Volume, 49(11), 1905-1921, 2017.
• S. Rajagopalan, V. C. Thippana, A. M. Parimi, “Optimal Placement of the Interline Power Flow Controller using the Bees Algorithm to minimize power loss”, 4th International Conference on Electrical Energy Systems (ICEES), Chennai, India, 212-217, 2018.
• M. K. Sharma, P. Phonrattanasak, N. Leeprechanon, “Improved bees algorithm for dynamic economic dispatch considering prohibited operating zones”, IEEE Innovative Smart Grid Technologies - Asia (ISGT ASIA), Singapore, 1-6, 2015.
• N. Y. Braiwish, F. J. Anayi, A. A. Fahmy, E. E. Eldukhri, “Design optimisation of Permanent Magnet Synchronous Motor for electric vehicles traction using the Bees Algorithm”, 49th International Universities Power Engineering Conference (UPEC), Cluj-Napoca, Romania, 1-5, 2014.
• I. Tkach, Y. Edan, A. Jevtic, S. Y. Nof, “Automatic Multi-sensor Task Allocation Using Modified Distributed Bees Algorithm”, IEEE International Conference on Systems, Man, and Cybernetics, Manchester, United Kingdom, 1401-1406, 2013.
• M. S. Packianather, B. Yuce, E. Mastrocinque, F. Fruggiero, D. T. Pham, A. Lambiase, A., “Novel Genetic Bees Algorithm applied to single machine scheduling problem”, World Automation Congress (WAC), Kona, Big Island of Hawaii, 906-911, 2014.
• N. Mollabakhshi, M. Eshghi, M., “Combinational circuit design using bees algorithm”, IEEE Conference Anthology, Piscataway, NJ, 1-4, 2013.
• M. Alzaqebah, S. Jawarneh, H. M. Sarim, S. Abdullah, “Bees Algorithm for Vehicle Routing Problems with Time Windows”, International Journal of Machine Learning and Computing, 8(3), 236-240, 2018.
• B. Yuce, E. Mastrocinque, A. Lambiase, M. S. Packianather, D. T. Pham, “A multi-objective supply chain optimisation using enhanced Bees Algorithm with adaptive neighbourhood search and site abandonment strategy”, Swarm and Evolutionary Computation, 18(1), 71-82, 2014.
• E. Koc, Bees algorithm: theory, improvements and applications, Phd thesis, Cardiff University, UK, 2010.
• S. Otri, Improving the bees algorithm for complex optimisation problems, Phd thesis, Cardiff University, UK, 2011.
• S. Zeybek, E. Koc, “The vantage point bees algorithm”, 7th International Joint Conference on Computational Intelligence (IJCCI), Lisbon, Portugal, 340–45, 2015.
• A. H. Ismail, N. Hartono, S. Zeybek, D. T. Pham, “Using the Bees Algorithm to solve combinatorial optimisation problems for TSPLIB”, IOP Conf. Series: Materials Science and Engineering 847, Indonesia, 1-9, 2020.
• Zeybek, S., Ismail, A. H., Hartono, N., Caterino, M., & Jiang, K., “An Improved Vantage Point Bees Algorithm to Solve Combinatorial Optimization Problems from TSPLIB”, In Macromolecular Symposia, 396(1), 1-4, 2021.
• L. Baronti, M. Castellani, D. T. Pham, “An analysis of the search mechanisms of the bees algorithm”, Swarm and Evolutionary Computation, 59, 1-30, 2020.
• G. Reinelt, “Tsplib - a traveling salesman problem library”, ORSA journal on computing, 3(4), 376–84, 1991.
• W. Tan, J. Gao, J. Rao, “Ant colony algorithm based on data classification”, IOP Conf. Series: Materials Science and Engineering, 768(7), Shanghai, China, 072099, 2020.
• M. R. Othman, Z. A. Othman, “Ayman Ibraheem Srour, Nor Samsiah Sani, A Hybrid Water Flow-Like Algorithm and Variable Neighbourhood Search for Traveling Salesman Problem”, International Journal on Advanced Science, Engineering and Information Technology, 9(5), 1505-1511, 2019.
• Y. Şahin, “Sezgisel Ve Metasezgisel Yöntemlerin Gezgin Satıcı Problemi Çözüm Performanslarının Kıyaslanması”, Bolu Abant İzzet Baysal Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 19(4), 911-932, 2019.