Yapay arı kolonisi algoritması kullanarak gezgin satıcı probleminin Türkiyedeki il ve ilçe merkezlerine uygulanması
Evaluation of traveling salesman problem to the nodes of city and township centers by using artificial bee colony algorithm
Yazar: MELİKE RUHAN AKÇA
Danışman: YRD. DOÇ. DR. HASAN ERDİNÇ KOÇER
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
Derece: Yüksek Lisans, 2011
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Sezgisel algoritmalar = Heuristic algorithms

Özet:
Bilgisayar teknolojisindeki gelişmelerin artmasıyla optimizasyon yöntemleri fen, sosyal vesağlık bilimleri alanlarındaki birçok uygulamanın çözümünde kullanılmaktadır. Sezgisel algoritmalar,özellikle birden farklı çözüme sahip olan problemlere uygulanan güçlü bir alternatif yöntemdir. Buproblemlerden biri de üzerinde sıkça çalışılan ve literatürde gezgin satıcı problemi olarak bilinen en kısayol bulma problemidir. Bu problem, haritada yer alan bir noktadan hareket eden satıcının her noktaya birkere uğradıktan sonra en kısa şekilde başlangıç noktasına tekrar dönmesi üzerinedir. Gelişime dayalı vesürü zekâsı temelli olmak üzere iki ana başlığa ayrılan sezgisel algoritmalar çeşitlilik göstermektedir. Butez çalışmasında sürü zekâsı temelli bir sezgisel algoritma olan yapay arı kolonisi algoritması kullanılarakTürkiye'deki il ve ilçe merkezleri için gezgin satıcı problemine çözüm bulunması hedeflenmiştir. Bununlabirlikte literatürde yer alan gezgin satıcı test (benchmark) problemleri üzerinde de deneysel çalışmalaryapılmıştır. Son yıllarda oldukça popüler olan yapay arı kolonisi algoritması bal arılarının doğadaki besinarama davranışından esinlenilerek geliştirilen etkili yöntemdir. Bu çalışmada arı kolonisi optimizasyonu(BCO) olarak bilinen algoritma ile yapay arı kolonisi algoritmasının (ABC) bir arada kullanıldığı hibrityapıda bir algoritma kullanılmıştır. Bununla birlikte bir yerel arama algoritması olan Opt-2 tekniği buhibrit yapı içerisine dahil edilerek lokal alanda iyileştirme gerçekleştirilmiştir. Literatürde sonuçlarıbilinen simetrik ve asimetrik yapıda küçük, orta ve büyük boyutlu gezgin satıcı test problemlerine hibrityapıdaki algoritma uygulanmış ve sonuçlar karşılaştırılmıştır. Bununla birlikte ülkemizdeki 81 il ve 888ilçe merkezi için deneysel uygulamalar gerçekleştirilmiş ve elde edilen sonuçlar literatür ilekarşılaştırmalı olarak değerlendirilmiştir. Çalışmada alınan sonuçlara göre, gezgin satıcı problemininçözümünde yapay arı kolonisi algoritması parçacık sürü optimizasyonu ve genetik algoritmaya oranladaha yüksek performans göstermektedir.

Abstract:
As developments in computer technology keep increasing, optimization methods are used forsolutions of many applications in various fields such as social, health and applied sciences. Heuristicalgorithm is an important alternative method which is used especially for problems that have more thanone solution. One of these problems is Travelling Salesman Problem, as it is known in the literature,which is also studied rather frequently. TSP is based on the shortest route possible in which the salesmanstarts from one point and pays a visit to every point on the route and goes back to the starting point in theend. Heuristic algorithms are various and are based on two main titles, one is based on development andother one is based on swarm intelligence. In this dissertation it is aimed to solve tsp for cities and districtsof Turkey by using artificial bee colony algorithm which is a swarm intelligence based heuristicalgorithm. In addition, experimental studies are applied to travelling salesman test (benchmark) problemswhich are found in literature. Artificial bee colony algorithm is a quite popular and efficient method thatis influenced from honey-bees? behaviours of food searching in nature. In this study a hybrid structuredalgorithm is used which is comprised of bee colony optimization and artificial bee colony. Nontheless,by including local search algorithm opt-2 tecnique in this hybrid structure, local development is realized.Algorithms are applied to small, medium and large symmetrical or asymmetrical travelling salesmanproblems with known solutions in literature and solutions are also compared to each other. Experimentalstudies are applied for 81 city and 888 district centers and obtained solutions are assessed comparative tosolutions of literature. According to the solution of this study, artificial bee colony algorithm gives amuch better performance than particle swarm optimization and genetic algorithm in solving travellingsalesman problem.