Please use this identifier to cite or link to this item: https://hdl.handle.net/11499/1129
Title: Karesel atama probleminin tavlama benzetimi ve paralel programlama teknikleri kullanarak çözümü
Other Titles: Solving quadratic assignment problem using simulated annealing and parallel programming techniques
Authors: Akkaş, Selahattin
Advisors: Kadir Kavaklıoğlu
Keywords: Karesel Atama Problemi
Optimizasyon
Tavlama Benzetimi
Paralel Programlama
Quadratic Assignment Problem
Optimization
Simulated Annealing
Parallel Programming
Publisher: Pamukkale Üniversitesi Fen Bilimleri Enstitüsü
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.
URI: https://hdl.handle.net/11499/1129
Appears in Collections:Tez Koleksiyonu

Files in This Item:
File Description SizeFormat 
Selahattin Akkaş.pdf2.9 MBAdobe PDFThumbnail
View/Open
Show full item record



CORE Recommender

Page view(s)

90
checked on May 6, 2024

Download(s)

118
checked on May 6, 2024

Google ScholarTM

Check





Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.