Yapay arı kolonisi algoritması kullanarak gezgin satıcı probleminin Türkiyedeki il ve ilçe merkezlerine uygulanması

Autor: Akça, Melike Ruhan
Přispěvatelé: Koçer, Hasan Erdinç, Enstitüler, Fen Bilimleri Enstitüsü, Elektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı, Elektronik ve Bilgisayar Sistemleri Eğitimi Anabilim Dalı
Jazyk: turečtina
Rok vydání: 2011
Předmět:
Popis: Bilgisayar teknolojisindeki gelişmelerin artmasıyla optimizasyon yöntemleri fen, sosyal ve sağ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. Bu problemlerden biri de üzerinde sıkça çalışılan ve literatürde gezgin satıcı problemi olarak bilinen en kısa yol bulma problemidir. Bu problem, haritada yer alan bir noktadan hareket eden satıcının her noktaya bir kere uğradıktan sonra en kısa şekilde başlangıç noktasına tekrar dönmesi üzerinedir. Gelişime dayalı ve sürü zekâsı temelli olmak üzere iki ana başlığa ayrılan sezgisel algoritmalar çeşitlilik göstermektedir. Bu tez çalışmasında sürü zekâsı temelli bir sezgisel algoritma olan yapay arı kolonisi algoritması kullanılarak Türkiye'deki il ve ilçe merkezleri için gezgin satıcı problemine çözüm bulunması hedeflenmiştir. Bununla birlikte literatürde yer alan gezgin satıcı test (benchmark) problemleri üzerinde de deneysel çalışmalar yapılmıştır. Son yıllarda oldukça popüler olan yapay arı kolonisi algoritması bal arılarının doğadaki besin arama 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ığı hibrit yapıda bir algoritma kullanılmıştır. Bununla birlikte bir yerel arama algoritması olan Opt-2 tekniği bu hibrit 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 hibrit yapıdaki algoritma uygulanmış ve sonuçlar karşılaştırılmıştır. Bununla birlikte ülkemizdeki 81 il ve 888 ilçe merkezi için deneysel uygulamalar gerçekleştirilmiş ve elde edilen sonuçlar literatür ile karşı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 oranla daha yüksek performans göstermektedir.
As developments in computer technology keep increasing, optimization methods are used for solutions of many applications in various fields such as social, health and applied sciences. Heuristic algorithm is an important alternative method which is used especially for problems that have more than one 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 salesman starts from one point and pays a visit to every point on the route and goes back to the starting point in the end. Heuristic algorithms are various and are based on two main titles, one is based on development and other one is based on swarm intelligence. In this dissertation it is aimed to solve tsp for cities and districts of Turkey by using artificial bee colony algorithm which is a swarm intelligence based heuristic algorithm. In addition, experimental studies are applied to travelling salesman test (benchmark) problems which are found in literature. Artificial bee colony algorithm is a quite popular and efficient method that is influenced from honey-bees? behaviours of food searching in nature. In this study a hybrid structured algorithm 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 salesman problems with known solutions in literature and solutions are also compared to each other. Experimental studies are applied for 81 city and 888 district centers and obtained solutions are assessed comparative to solutions of literature. According to the solution of this study, artificial bee colony algorithm gives a much better performance than particle swarm optimization and genetic algorithm in solving travelling salesman problem.
Databáze: OpenAIRE
Externí odkaz: