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 Classification: 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ı