Gezgin satıcı probleminin çözümünde parçacık sürü optimizasyonu algoritması performansının bulanık c-ortalamalar yöntemi ile iyileştirilmesi
Improving solution performance of the particle swarm optimization algorithm on traveling salesman problem with fuzzy c-means method
- Tez No: 398883
- Danışmanlar: YRD. DOÇ. DR. KASIM BAYNAL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: Türkçe
- Üniversite: Kocaeli Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 253
Özet
Gezgin satıcı problemleri (GSP) literatürün belki de en çok çalışılan ve farklı alanlarda uygulaması olan optimizasyon problemlerinden birisidir. Sahip olduğu hesaplamasal karmaşıklık nedeni ile optimum çözümünü kesin yöntemler ile bulmanın mümkün olmadığı GSP geliştirilen neredeyse her sezgisel algoritma için kendini ispatlama testi olarak ortaya konmaktadır. Genel olarak hızlı çalışan ve başarılı sonuçlar elde eden bir sezgisel yöntem olarak literatürde yer almakta olan parçacık sürü optimizasyonu (PSO) algoritmasının, GSP için ancak çok küçük ölçekli problemlerde kullanılabileceğine yönelik çıkarımlar olmuştur. Bu çalışma kapsamında Standart PSO ve bulanık c-ortalamalar (BCO) yöntemlerinin birleştirilmesi ile oluşturulan FCM-PSO-M, FCM-PSO-M2 ve FCM-PSO-U yöntemleri farklı ölçeklerde GSP üzerinde uygulanarak sonuçları standart PSO ile karşılaştırılmıştır. Çalışmada önerilen yöntemler, küçük ölçekli GSP'ler için çözüm kalitesi kriteri açısından standart PSO'ya göre daha iyi sonuçlar verirken işlem zamanı kriteri açısından standart PSO'dan daha kötü sonuçlar üretmektedir. Orta ve büyük ölçekli problemler için ise geliştirilmiş olan yöntemler hem işlem zamanı hem de çözüm kalitesi kriterleri açısından standart PSO algoritmasından daha iyi sonuçlar vermektedir. 18512 noktalı D18512 problemi için FCM-PSO-M2 (9x9) yöntemi, standart PSO'ya göre %5 daha kısa işlem süresinde ve 9,89 kat daha iyi bir çözüm kalitesi ile sonuç elde edilmiştir. Yine aynı problem için FCM-PSO-M2 (10x10) yöntemi ise standart PSO'ya göre %2 daha uzun işlem zamanında ancak 11,76 kat daha iyi bir çözüm kalitesi ile sonuçlar üretilmiştir. Çalışmada elde edilen sonuçlar, geliştirilen yöntemlerin standart PSO'ya göre her problem boyutunda çözüm kalitesi açısından daha iyi olmakta; orta ve büyük ölçekli problemlerde ise hem çözüm süresi hem de çözüm kalitesi açısından daha uygun ve avantajlı olduğunu göstermektedir.
Özet (Çeviri)
Traveling salesman problem, with applications in many different areas, is probably one of the most studied optimization problems in literature. As a result of its computational complexity optimum solutions to traveling salesman problems can not be calculated in reasonable time, as a result of this challange nearly every developed heuristic algorithm is being tested on this problem suites. Although it is regarded as a fast and succesful optimization algorithm in literature, particle swarm optimization (PSO) algorithm is regarded effective only in small scale traveling salesman problems. In this study FCM-PSO-M, FCM-PSO-M2 and FCM-PSO-U variants, which were developed by combining standart PSO and fuzzy c-means (FCM), are applied on different scaled problems and compared with standart PSO. Proposed methods in this study; improves solution quality for small scaled TSP problems but in terms of processing time proposed methods aren't as good as standart PSO method. But for medium and large scale TSP problems proposed methods improves both the solution quality and processing time of Standart PSO. For D18512 problem consisting of 18512 nodes, FCM-PSO-M2 (9x9) method has achieved 9,89 times better solution than standart PSO on %5 shorter processing time. Again for the same problem, FCM-PSO-M2 (10x10) has achieved 11,76 times better solutions at %2 more processing time then standart PSO. The results obtained by the developed methods, are better than standart PSO at all scales in terms of quality and better in medium and large scaled problems in terms of solution time.
Benzer Tezler
- Parçacık sürü optimizasyonu algoritmasının gezgin satıcı problemine uygulanması ve performansının incelenmesi
Application of particle swarm optimisation algorithm to travelling salesman problem and its performance investigation
MEHMET YASİN ÖZSAĞLAM
Yüksek Lisans
Türkçe
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiElektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. MEHMET ÇUNKAŞ
- Yapay atom algoritması ve ayrık problemlere uygulanması
Artificial atom algorithm and its application to discrete problems
AYŞE ERDOĞAN YILDIRIM
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ KARCI
- Çoklu gezgin satıcı probleminin sezgisel algoritmalar ile çözümü
Solving the multiple traveling salesman problem using heuristic algorithms
SEVDA DAYIOĞLU GÜLCÜ
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HUMAR KAHRAMANLI
- 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
MELİKE RUHAN AKÇA
Yüksek Lisans
Türkçe
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiElektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. HASAN ERDİNÇ KOÇER
- Optimizasyon problemlerinin çözümü için yapay arı kolonisi algoritması tabanlı yeni yaklaşımlar
Novel approaches based on articial bee colony algorithm to solve optimization pronlems
MUSTAFA SERVET KIRAN
Doktora
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MESUT GÜNDÜZ