Reşat Buğra ERKARTAL, Ömer ÇETİN, Atınç YILMAZ

Kablosuz Sensör Ağlarından Veri Toplama: Gezen Postacı Probleminin Paralel Genetik Algoritma ve Paralel Karınca Kolonisi ile Çözümü Üzerine OpenMP Uygulaması

Algoritmaların paralelleştirilmesi, birçok durumda aynı anda birden fazla çekirdek kullanırken zamanı azaltabilir. Genetik Algoritma (Genetic Algorithm- GA) ve Karınca Kolonisi (Ant Colony- AC) gibi algoritmalar doğrusal olmayan problemleri çözmek için yaygın olarak kullanılan optimizasyon algoritmaları olmasına rağmen, genellikle zaman alıcıdır. Bu çalışma, iyi bilinen bir NP-Zor problemi olan gezgin satıcı problemini (The Travelling Salesman Problem-TSP) hem paralel hem de seri GA ve AC kullanarak çözmeyi amaçlamaktadır. Uygulama olarak kablosuz sensör ağlarından (Wireless sensor Networks-WSNs) toplanan veriler kullanılmış ve çalışan algoritmaların performans değerleri karşılaştırılmıştır. WSN'lerde seyahat süresinin azaltılması, çok sekmeli iletimin neden olduğu enerji tüketimindeki kayıpları önler, ancak uzun bir gecikmeye neden olur. Ayrıca OpenMP (Open Multi-Processing) ile uygulama yapılmış ve seri programlama ile performansı karşılaştırılmıştır. Elde edilen bulgulara göre her iki yöntem de paralel çalıştığında süreyi yarı yarıya azaltırken; GA'nın performansı AC'den çok daha üstündür.

Data Collection from Wireless Sensor Networks: OpenMP Application on the Solution of Traveling Salesman Problem with Parallel Genetic Algorithm and Ant Colony Algorithm

Parallelization of algorithms can reduce time in many cases while using multiple cores at the same time. Although Algorithms such as Genetic Algorithm (GA) and Ant Colony (AC) are widely used optimization algorithms to solve the non-linear problems it is usually time consuming. This study aims to solve a well-known NP-Hard problem, The Travelling Salesman Problem (TSP), by using both parallel and serial GA and AC. As an application, the data collected from the wireless sensors networks (WSNs) were used and the performance values of the running algorithms were compared. Reducing the travelling time in WSNs avoids losses in energy consumption caused by multi-tab transmission, but causes a long delay. Additionally, application was made with Open Multi-Processing (OpenMP) and its performance was compared with serial programming. According to the findings while both methods reduces the time in half when they run parallel, the performance of GA is much superior than AC.

PDF

___

[1] P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, Genetic algorithms for the travelling salesman problem: A review of representations and operators, Artif. Intell. Rev. 13(2), 129–170 (1999).
[2] J. K. Lenstra and A. H. G. R. Kan, Some simple applications of the travelling salesman problem, J. Oper. Res. Soc. 26(4), 717–733 (1975).
[3] J. H. Holland and others, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.
[4] A. Downey, The little book of semaphores. Green Tea Press, 2008.
[5] B. Gavish and S. C. Graves, The travelling salesman problem and related problems, 1978.
[6] G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, Some applications of the generalized travelling salesman problem, J. Oper. Res. Soc. 47(12), 1461–1467 (1996).
[7] D. Karapetyan and G. Gutin, Lin--Kernighan heuristic adaptations for the generalized traveling salesman problem, Eur. J. Oper. Res. 208(3), 221–232 (2011).
[8] K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Eur. J. Oper. Res. 126(1), 106–130 (2000).
[9] K. Helsgaun, General k-opt submoves for the Lin-Kernighan TSP heuristic, Math. Program. Comput. 1(2), 119–163 (2009).
[10] M. Jünger, G. Reinelt, and G. Rinaldi, The traveling salesman problem, Handbooks Oper. Res. Manag. Sci. 7, 225–330 (1995).
[11] G. G. Emel and Ç. Taşkin, Genetik algoritmalar ve uygulama alanlari, Uludağ} Üniversitesi İktisadi ve İdari Bilim. Fakültesi Derg. 21(1), 129–152 (2002).
[12] J. R. Cheng and M. Gen, Parallel Genetic Algorithms with GPU Computing, in Industry 4.0, T. Bányai and A. P. F. De Felice, Eds. Rijeka: IntechOpen, 2020.
[13] T. Elmas and S. Taşkıran, “Paralel Yazılım Geliştirme Sürecinde Yarış Durumu Denetimi,” Yazılım Kalitesi ve Yazılım Geliştirme Araçları Sempozyumu, İstanbul, 2008.
[14] O. M. Sallabi and Y. Elhaddad, An improved genetic algorithm to solve the traveling salesman problem, 2009.
[15] M. Nowostawski and R. Poli, “Parallel genetic algorithm taxonomy,” in 1999 Third International Conference on Knowledge-Based Intelligent Information Engineering Systems. Proceedings (Cat. No. 99TH8410), 1999. pp. 88–92.
[16] V. Dwivedi, T. Chauhan, S. Saxena, and P. Agrawal, Travelling salesman problem using genetic algorithm, IJCA Proc. Dev. Reliab. Inf. Syst. Tech. Relat. Issues (DRISTI 2012), 2012.
[17] K. Rani and V. Kumar, Solving travelling salesman problem using genetic algorithm based on heuristic crossover and mutation operator, Int. J. Res. Eng. Technol. 2(2), 27–34 (2014).
[18] F. H. Khan, N. Khan, S. Inayatullah, and S. T. Nizami, Solving TSP problem by using genetic algorithm, Int. J. Basic Appl. Sci. 9(10), 79–88 (2009).
[19] M. L. Islam, D. Pandhare, A. Makhthedar, and N. Shaikh, A Heuristic Approach for Optimizing Travel Planning Using Genetics Algorithm, Int. J. Res. Eng. Technol. eISSN, 2014, pp. 1163–2319.
[20] S. Gupta and P. Panwar, Solving travelling salesman problem using genetic algorithm, Int. J. Adv. Res. Comput. Sci. Softw. Eng. 3(6), 376–380 (2013).
[21] H. R. Er and N. Erdogan, “Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster,” arXiv Prepr. arXiv1401.6267, 2014.
[22] M. Abbasi, M. Rafiee, M. R. Khosravi, A. Jolfaei, V. G. Menon, and J. M. Koushyar, An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems, J. cloud Comput. 9(1), 1–14, 2020.
[23] A. Siemiński and M. Kopel, Solving dynamic TSP by parallel and adaptive ant colony communities, J. Intell. & Fuzzy Syst. 37(6), 7607–7618 (2019).
[24] P. Yelmewad and B. Talawar, Parallel iterative hill climbing algorithm to solve TSP on GPU, Concurr. Comput. Pract. Exp. 31(7), 4974 (2019).
[25] G. A. Sena, D. Megherbi, and G. Isern, Implementation of a parallel genetic algorithm on a cluster of workstations: traveling salesman problem, a case study, Futur. Gener. Comput. Syst. 17(4), 477–488 (2001).
[26] A. Di Placido, C. Archetti, and C. Cerrone, A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance, Comput. & Oper. Res. 145, 105831 (2022).
[27] S. K. R. Kanna, K. Sivakumar, and N. Lingaraj, Development of deer hunting linked earthworm optimization algorithm for solving large scale traveling salesman problem, Knowledge-Based Syst. 227, 107199 (2021).
[28] M. M. Krishna, N. Panda, and S. K. Majhi, Solving traveling salesman problem using hybridization of rider optimization and spotted hyena optimization algorithm, Expert Syst. Appl. 183, 115353 (2021).
[29] W. P. Computing and I. Foster, Designing and building parallel programs. Addison-Wesley, 1995.
[30] M. J. Brauer, M. T. Holder, L. A. Dries, D. J. Zwickl, P. O. Lewis, and D. M. Hillis, Genetic Algorithms and Parallel Processing in Maximum-Likelihood Phylogeny Inference,Mol. Biol. Evol. 19(10), 1717–1726 (2002).