Gezgin Satıcı Probleminin Benzetilmiş Tavlama Yöntemiyle Çözümünde Paralel Hesaplamanın Kullanılması

Authors : Emrullah SONUÇ, Baha ŞEN, Şafak BAYIR

Pages : 856-860

View : 32 | Download : 32

Publication Date : 2015-02-06

Abstract :Bilgisayar bilimlerinde çözümü zor olan ve çözüme ulaşmak için gereken hesaplamaların bir hayli zaman aldığı problemlerin çözümünde sezgisel yaklaşımlar sergilenmektedir. Bu yaklaşımlara sahip algoritmalar, en iyi çözümü sunmak yerine çözüm zamanını azaltmayı hedefleyerek iyiye yakın çözüm elde etmeyi amaçlar. Bu yaklaşıma sahip olan Benzetilmiş Tavlama algoritması herhangi bir fonksiyonun global optimum değerini elde etmek için kullanılır. Bu sebeple, özellikle matematiksel modellerle gösterilemeyen kombinasyonel problemlerin optimizasyon uygulamalarında tercih edilir. Yapılan çalışmada Benzetilmiş Tavlama algoritması NP-tam zorluğunda olan Gezgin Satıcı Problemi üzerinde seri, CPU üzerinde paralelleştirilmiş ve GPU üzerinde paralelleştirilmiş yöntemler ile test edilmiştir. Çalışmada, paralel yöntemler seri uygulamaya nazaran zaman olarak uygun bir sonuç ver­mese maliyet açısından daha iyi çözümlerin elde edilmesini sağlamıştır. Sonuçlar maliyet değerleri üzerinden grafiklerle gösterilmiştir.
Keywords : Benzetilmiş Tavlama, Gezgin Satıcı Problemi, Paralel Hesaplama, OPENMP, GPU, CUDA