Combinatorial Optimization Using Particle Swarm Optimization Supported Genetic Algorithm and Artificial Bee Colony Algorithm

M5

Dr. Emrah Önder
İstanbul Üniversitesi İşletme Fakültesi Sayısal Yöntemler Anabilim Dalışletme Fakültesi Sayısal Yöntemler Anabilim Dalı

Araş. Gör. Muhlis Özdemir
İstanbul Üniversitesi İşletme Fakültesi Sayısal Yöntemler Anabilim Dalışletme Fakültesi Sayısal Yöntemler Anabilim Dalı

Araş. Gör. Bahadır Fatih Yıldırım
İstanbul Üniversitesi İşletme Fakültesi Sayısal Yöntemler Anabilim Dalışletme Fakültesi Sayısal Yöntemler Anabilim Dalı

Abstract

Combinatorial optimization problems are usually NP-hard and the solution space of them is very large. Therefore the set of feasible solutions cannot be evaluated one by one. Artificial Bee Colony (ABC), Particle Swarm Optimization (PSO) and Genetic Algorithms (GA) are meta-heuristic techniques for combinatorial optimization problems. ABC and PSO are swarm intelligence based approaches and they are nature-inspired optimization algorithms. In this study ABC and PSO supported GA techniques were used for finding the shortest route in condition of to visit every city one time but the starting city twice. The problem is a well-known Symmetric Travelling Salesman Problem. Our travelling salesman problem (TSP) consists of 81 cities of Turkey. ABC and PSO-based GA algorithms are applied to solve the travelling salesman problem and results are compared with ant colony optimization (ACO) solution. Our research mainly focused on the application of ABC and PSO based GA algorithms in combinatorial optimization problem. Numerical experiments show that ABC and PSO supported GA are very competitive and have good results compared with the ACO, when it is applied to the regarding problem.

Keywords: Artificial Bee Colony Algorithm, Clustering, Combinatorial Problems, Genetic Algorithm, Meta-Heuristics, Particle Swarm Optimization, Shortest Path, Traveling Salesman Problem

Jel Sınıflandırma: C61

Yapay Arı Koloni Algoritması ve Parçacık Sürü Optimizasyonu Destekli Genetik Algoritma İle Kombinatoryal Optimizasyon

Özet

Kombinatoryal optimizasyon problemleri genellikle NP-zor sınıfında yer alan ve çözüm uzayları çok büyük olan problemlerdir. Bu nedenle çözüm uzayında yer alan bütün çözümlerin tek tek denenmesi mümkün değildir. Yapay Arı Kolonisi (YAK), Parçacık Sürü Optimizasyonu (PSO) ve Genetik Algoritma (GA) kombinatoryal optimizasyon problemlerinin çözümü için geliştirilmiş olan meta-sezgisel tekniklerdir. YAK ve PSO doğadan esinlenilmiş sürü zekâsı temelli algoritmalardır. Bu çalışmada YAK ve PSO ile desteklenmiş GA tekniği bütün şehirlerin dolaşılması ve başlangıç şehrine dönmek koşuluyla en kısa rotanın bulunmasında kullanılacaktır. Problem herkesçe bilinen Simetrik Gezen Satıcı Problemi (SGSP)’dir. Bu çalışmada yer alan Gezen Satıcı Problemi (GSP) Türkiye’deki 81 şehirden oluşmaktadır. YAK ve PSO ile desteklenmiş GA tekniği GSP’nin çözümü için kullanılmış ve elde edilen sonuçlar Karınca Kolonisi Algoritması (KKA) ile elde edilen sonuçlar ile karşılaştırılmıştır. Araştırmamız YAK ve PSO ile desteklenmiş GA tekniği ile kombinatoryal optimizasyon probleminin çözümüne dayanmaktadır. Elde edilen sonuçlar göstermektedir ki YAK ve PSO ile desteklenmiş GA tekniği ile elde edilmiş olan sonuçlar KKO ile karşılaştırıldığında oldukça etkili ve iyi sonuçlardır.

Anahtar Kelimeler: En Kısa Yol, Genetik Algoritma, Gezen Satıcı Problemi, Kombinatoryel Problemler, Meta-Sezgiseller, Parçacık Sürü Optimizasyonu, Sınıflandırma, Yapay Arı Kolonisi Algoritması

  • Akay Bahriye, Karaboğa Derviş, A modified Artificial Bee Colony algorithm for real-parameter optimization, Information Sciences, 192, pp. 120–142, 2012
  • Chen, C.Y., Ye, F., Particle Swarm Optimization Algorithm and Its Application to Clustering Analysis, Proceedings of the 2004 IEEE, International Conference of Networking, Sensing and Control, Taipei, Taiwan, March, 2004, 789-79
  • Diwold K., Aderhold A., Scheidler A., Middendorf M., Performance evaluation of artificial bee colony optimization and new selection scheme, Memetic Computing, Volume 3, Issue 3, Sayfa 149–162, 2011
  • Karaboğa Derviş, Akay Bahriye, A Comparative Study of Artificial Bee Colony Algorithm, Applied Mathematics and Computation 214, pp. 108-132, 2009
  • Karaboğa Derviş, An Idea Based On Honey Bee Swarm For Numerical Optimization, Technical Report, pp. 1-10, 2005
  • Kennedy J., Eberhart R. C., Particle swarm optimization, in Proc. of the IEEE International Conference on Neural Networks, Piscataway, NJ, pp. 1942–1948, 1995
  • Kıran, Mustafa Servet, İşcan Hazım, Gündüz Mesut, The analysis of discrete artificial bee colony algorithm with neighborhood operator on traveling salesman problem, Neural Computing and Applications, pp. 1–13. doi:10.1007/s00521-011-0794-0, 2012
  • Liao Y.-F., Yau D.-H., Chen C.-L., Evolutionary algorithm to traveling salesman problems, Computers & Mathematics with Applications, Volume 64, Issue 5, 788–797, doi:10.1016/j.camwa.2011.12.018, 2012
  • Marinakis, Y., Marinaki, M., Dounias, G., Honey bees mating optimization algorithm for the Euclidean traveling salesman problem, Information Sciences, 181(20), pp. 4684–4698, doi:10.1016/j.ins.2010.06.032, 2011.
  • Republic of Turkey General Directorate of Highways web site (2013) http://www.kgm.gov.tr/Sayfalar/KGM/SiteTr/Root/Uzakliklar.aspx
  • Söyler Hasan, Keskintürk Timur, Karinca Kolonisi Algoritmasi ile Gezen Satici Probleminin Çözümü, 8. Türkiye Ekonometri ve İstatistik Kongresi, 2007.
  • Wen-liang Zhong, Jun Zhang, W. C., A Novel Discrete Particle Swarm Optimization to Solve Traveling Salesman Problem, Evolutionary Computation pp. 3283–3287, 2007.
  • Yen-Far Liao, Dun-Han Yau, Chieh-Li Chen, Evolutionary algorithm to traveling salesman problems, Computer and Mathematics with Applications 64, 788-797, 2012.

    Önder, E., Özdemir, M., Yıldırım, B. F. (2013). "Combinatorial Optimization Using Particle Swarm Optimization Supported Genetic Algorithm and Artificial Bee Colony Algorithm". Kafkas Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 4 (6), 59-70.

    Bu çalışma, 14. Uluslararası Ekonometri Yöneylem Araştırması ve İstatistik Sempozyumunda özet bildiri olarak sunulmuştur.