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
Yazar: AHMET YEKTA KAYMAN
Danışman: YRD. DOÇ. DR. KASIM BAYNAL
Kocaeli Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2015
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Metasezgiseller = Metaheuristics ; Parçacık sürü optimizasyonu = Particle swarm optimization

Ö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.

Abstract:
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.