A DISCRETE PARTICLE SWARM ALGORITHM WITH SYMMETRY METHODS FOR DISCRETE OPTIMIZATION PROBLEMS

Year 2023, Volume: 11 Issue: 3, 610 - 634, 01.09.2023

Emine Baş Gülnur Yıldızdan

https://doi.org/10.36306/konjes.1199674

Abstract

Particle Swarm Optimization (PSO) is a commonly used optimization to solve many problems. The PSO, which is developed for continuous optimization, is updated to solve discrete problems and Discrete PSO (DPSO) is obtained in this study. With DPSO, the Traveling Salesman Problem (TSP), which is well-known in the literature as a discrete problem, is solved. In order to improve the results, the swap method, the shift method, and the symmetry method are added to DPSO. The symmetry method is a new and successful method. The variations of the DPSO occurred according to the selected method type (DPSO1 (swap method), DPSO2 (shift method), DPSO3 (swap and shift methods), DPSO4 (symmetry method), DPSO5 (swap, shift, and symmetry methods), DPSO6 (swap, shift, symmetry, and 2-opt methods)). The effect of each method on the performance of the DPSO has been studied in detail. To demonstrate the success of the variations of the DPSO, the results are additionally compared with many well-known and new discrete algorithms in the literature. The results showed that the performance of DPSO has improved with the symmetry method and it has achieved better results than the discrete heuristic algorithms recently proposed in the literature.

Keywords

Swap, Shift, Symmetry, 2-OPT, Discrete Optimization, TSP

AYRI OPTİMİZASYON PROBLEMLERİ İÇİN SİMETRİ YÖNTEMLİ AYRIK BİR PARÇACIK SÜRÜSÜ ALGORİTMASI

Abstract

Parçacık Sürü Optimizasyonu (PSO), birçok problemi çözmek için yaygın olarak kullanılan bir optimizasyon yöntemidir. Bu çalışmada sürekli optimizasyon problemleri için geliştirilen PSO, ayrık optimizasyon problemleri çözmek için tekrar güncellenmiştir. Böylece Ayrık PSO (DPSO) elde edilmiştir. DPSO ile literatürde ayrık bir problem olarak bilinen Gezgin Satıcı Problemi (GSP) çözülmüştür. Sonuçları iyileştirmek için DPSO'ya takas yöntemi, kaydırma yöntemi ve simetri yöntemi eklenmiştir. Simetri yöntemi yeni ve başarılı bir yöntemdir. DPSO varyasyonları seçilen yöntem türüne (DPSO1 (takas yöntemi), DPSO2 (kaydırma yöntemi), DPSO3 (takas ve kaydırma yöntemi), DPSO4 (simetri yöntemi), DPSO5 (takas, kaydırma ve simetri yöntemleri), DPSO6 (takas, kaydırma, simetri ve 2 seçenekli yöntemler)). Her yöntemin DPSO'nun performansı üzerindeki etkisi ayrıntılı olarak incelenmiştir. DPSO'nun varyasyonlarının başarısını göstermek için, sonuçlar ayrıca literatürdeki birçok iyi bilinen ve yeni ayrık optimizasyon algoritmalarıyla karşılaştırılmıştır. Sonuçlar, simetri yöntemi ile DPSO'nun performansının arttığını ve literatürde son zamanlarda önerilen ayrık sezgisel algoritmalardan daha iyi sonuçlar elde ettiğini göstermiştir.

Keywords

Takas, Kaydırma, Simetri, 2-OPT, Ayrık Optimizasyon, TSP

References

• R. Eberhard, J. Kennedy, “A New Optimizer Using Particle Swarm Theory,” Proceedings of 1995 IEEE 6th International Symposium, pp. 39 – 43.
• M. Mahi, Ö.K. Baykan, H. Kodaz, “A new hybrid method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt algorithms for Traveling Salesman Problem,” Applied Soft Computing, vol. 30, pp. 484-490, 2015.
• Ş. Öztürk, R. Ahmad, N. Akhtar, “Variants of Artificial Bee Colony algorithm and its applications in medical image processing,” Applied Soft Computing, vol. 97, Part A, pp. 106799, 2020.
• F. A. Hashim, A. G. Hussien, “Snake Optimizer: A novel meta-heuristic optimization algorithm,” Knowledge-Based Systems, vol. 242, pp. 108320, 2022.
• T. S. L. V. Ayyarao, N. S. S. Ramakrishna, R. M. Elavarasan, N. Polumahanthi, M. Rambabu, G. Saini, B.Khan, B.Alatas, "War Strategy Optimization Algorithm: A New Effective Metaheuristic Algorithm for Global Optimization," in IEEE Access, vol. 10, pp. 25073-25105, 2022.
• D. Połap, M. Woźniak, “Red fox optimization algorithm,” Expert Systems with Applications, vol. 166, pp. 114107, 2021.
• L. Yi, “Study on an Improved PSO Algorithm and its Application for Solving Function Problem,” International Journal of Smart Home, vol. 10, no. 3, pp. 51 – 62, 2016.
• W. Deng, R. Chen, B. He, Y.Q. Liu, L. F. Yin, J. H. Guo, “A novel two-stage hybrid swarm intelligence optimization algorithm and application,” Soft Computing, vol. 16, no. 10, pp. 1707-1722, 2012.
• W. Deng, H. M. Zhao, J. J. Liu, X. L. Yan, Y. Y. Li, L. F. Yin, C. H. Ding, “An improved CACO algorithm based on adaptive method and multi-variant strategies,” Soft Computing, vol. 19 no. 3, pp. 701- 713, 2015.
• X. H. Shi, Y. Zhou, L. M. Wang, Q. X. Wang, Y. C. Liang, “A Discrete Particle Swarm Optimization Algorithm for Travelling Salesman Problem,” Computational Methods, 2006, pp. 1063–1068.
• O. E. Turgut, M. S. Turgut, M. T. Coban, “Chaotic quantum behaved particle swarm optimization algorithm for solving nonlinear system of equations,” Computers and Mathematics with Applications, vol. 68, no. 4, pp. 508-530, 2014.
• Z. L. Gaing, "Discrete particle swarm optimization algorithm for unit commitment," 2003 IEEE Power Engineering Society General Meeting (IEEE Cat. No.03CH37491), 2003, pp. 418-424.
• A. Unler, A. Murat, “A discrete particle swarm optimization method for feature selection in binary classification problems,” vol. 206, no. 3, pp. 528-539, 2010.
• S. Strasser, R. Goodman, J. Sheppard, S. Butcher, “A New Discrete Particle Swarm Optimization Algorithm,” GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016, 2016, pp. 53–60.
• Q. K. Pan, M. F. Tasgetiren, Y. C. Liang, “A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem,” vol. 35, no. 9, pp. 2807-2839, 2008.
• H. Izakian, B. T. Ladani, A. Abraham, V. Snasel, “A Discrete Particle Swarm Optimization Approach For Grid Job Scheduling,” International Journal of Innovative Computing, Information and Control, vol. 6, no. 9, pp. 1-09, 2010.
• E. Baş, E. Ülker, “Dıscrete socıal spıder algorıthm for the travelıng salesman Problem,” Artificial Intelligence Review, vol. 54, pp. 1063–1085, 2021.
• M. A. Al-Furhud, Z. H. Ahmed, “Genetic Algorithms for the Multiple Travelling Salesman Problem,” (IJACSA) International Journal of Advanced Computer Science and Applications, vol. 11, no. 7, 2020.
• K. Panwar, K. Deep, “Discrete Grey Wolf Optimizer for symmetric travelling salesman problem,” Applied Soft Computing, vol. 105, pp. 107298, 2021.
• M. Gunduz, M. Aslan, “DJAYA: A discrete Jaya algorithm for solving traveling salesman problem,” Applied Soft Computing, vol. 105 pp. 107275, 2021.
• A. C. Cinar, S. Korkmaz, M. S. Kiran, “A discrete tree-seed algorithm for solving symmetric traveling salesman Problem,” Engineering Science and Technology, vol. 23, pp. 879–890, 2020.
• E. Osaba, J. D. Ser, A. Sadollah, M. N. Bilbao, D. Camacho, “A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem,” vol. 71, pp. 277-290, 2018.
• S. S. Choong, L. P. Wong, C. P. Lim, “An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem,” vol. 44, pp. 622-635, 2019.
• F. Dahan, K. El Hindi, H. Mathkour, H. AlSalman, “Dynamic Flying Ant Colony Optimization (DFACO) for Solving the Traveling Salesman Problem,” Sensors, vol. 19, no. 8, pp. 1837, 2019.
• Y. Zhong, J. Lin, L. Wang, H. Zhang, “Hybrid discrete artificial bee colony algorithm with threshold acceptance criterion for traveling salesman problem,” Information Sciences, vol. 421, pp. 70-84, 2017.
• W. Gao, “New Ant Colony Optimization Algorithm for the Traveling Salesman Problem,” vol. 13, no. 1, pp. 44 – 55, 2020.
• X. Dong, Y. Cai, “A novel genetic algorithm for large scale colored balanced traveling salesman problem,” vol. 95, pp. 727-742, 2019.
• N. Rokbani, R. Kumar, A. Abraham, A. M. Alimi, H. V. Long, S. Priyadarshini, L. H. Son, “Bi-heuristic ant colony optimization-based approaches for traveling salesman problem,” Soft Computing, vol. 25, pp. 3775–3794, 2021.
• C. Wu, X. Fu, J. Pei, Z. Dong, "A Novel Sparrow Search Algorithm for the Traveling Salesman Problem," in IEEE Access, vol. 9, pp. 153456-153471, 2021.
• Z. Zhang, Y. Han, “Discrete sparrow search algorithm for symmetric traveling salesman problem,” Applied Soft Computing, vol. 118, pp. 108469, 2022.
• Y. Huang, X. N. Shen, X. You, “A discrete shuffled frog-leaping algorithm based on heuristic information for traveling salesman problem,” Applied Soft Computing, vol. 102, pp. 107085, 2021.
• Z. Zhang, J. Yang, “A discrete cuckoo search algorithm for traveling salesman problem and its application in cutting path optimization,” Computers & Industrial Engineering, vol. 169, pp. 108157, 2022.
• T. Zhang, Y. Zhou, G. Zhou, W. Deng, Q. Luo, “Discrete Mayfly Algorithm for spherical asymmetric traveling salesman problem,” Expert Systems with Applications, vol. 221, pp. 119765, 2023.
• Y. Chunhua, T. Xiaolin, Z. Xiaojun, G. Weihua, “State transition algorithm for traveling salesman problem,” in: Proceedings of the 31st Chinese Control Conference IEEE, 2012, pp. 2481–2485.
• X. Zhou, D. Y. Gao, C. Yang, W. Gui, “Discrete state transition algorithm for unconstrained integer optimization problems,” Neurocomputing, vol. 173, pp. 864–874, 2016.
• M. Gündüz, M. S. Kiran, E. Özceylan, “A hierarchic approach based on swarm intelligence to solve the traveling salesman problem,” Turkish Journal of Electrical Engineering and Computer Sciences, vol. 23, no. 1, pp. 103- 117, 2015.
• A. Hatamlou, “Solving travelling salesman problem using black hole algorithm,” Soft Computing, vol. 22, pp. 8167–8175, 2018.
• G. A. Croes, “A method for solving traveling-salesman problems”, Operations research, vol. 6, no. 6, pp. 791–812, 1958.
• G. Reinelt, “TSPLIB—A traveling salesman problem library”, ORSA Journal on Computing, vol. 3, no. 4, pp. 267–384, 1991.