Karesel atama probleminin tavlama benzetimi ve paralel programlama teknikleri kullanarak çözümü

Abstract

Karesel atama problemi NP-zor sınıfında bir problem olup çözümü en zor problemlerden biridir. Problemin zorluğu nedeniyle kesin yöntemler kullanılarak boyutu büyük problemler için makul zamanda sonuç bulunamamaktadır. Bu çalışmada karesel atama problemlerinin çözümünde kullanılan meta-sezgisel yöntemlerden birisi olan tavlama benzetimi yöntemi MATLAB ortamında değişik şekillerde paralelleştirilmiştir. Paralel yöntemler ile klasik seri tavlama benzetimi yöntemi arasında süre ve iterasyon olarak karşılaştırmalar yapılmıştır. Paralelleştirme işleminde iş istasyonunda 12 MATLAB işçisi kullanılmıştır. Karşılaştırmalar örnek karesel atama problemlerinin bulunduğu bir kütüphane olan QAPLIB’den alınan 36 örnek problem üzerinde yapılmıştır. İşçiler arasında hiç haberleşmenin yapılmadığı asenkron hesaplamalı tavlama benzetimi ve belirli aralıklarla işçiler arasında veri paylaşımının yapıldığı senkron hesaplamalı tavlama benzetimi yönteminin klasik seri tavlama benzetimine göre daha iyi sonuçlar verdikleri görülmüştür.

Quadratic assignment problem which is a problem under the category of NP-hard is one of the hardest problems to be solved. Because of the difficulty of the problem, it is hard to get results for big problems in a reasonable time period by using exact methods. In this study, simulated annealing method which is one of the meta-heuristic methods used in solving quadratic problems was parallelized in various categories in MATLAB. Parallel methods were compared and contrasted with classical serial simulated annealing method in terms of execution time and number of iterations. On parallelization, 12 workers were used on the workstation. Comparisons have been done for 36 sample problems taken from QAPLIB which is a library that has sample quadratic assignment problems. It has been observed that asynchronous computed simulated annealing method in which there is no communication among workers and synchronous computed simulated annealing method in which communication is done in certain intervals given better results in comparison to serial simulated annealing.