SavedAdd your journal

Journals / Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi / 2018 / Cilt: 24 Sayı: 5

Comparison of simulated annealing parallelization methods for quadratic assignment problems

Karesel atama problemleri için tavlama benzetimi paralelleştirme yöntemlerinin karşılaştırılması

Selahattin Akkaş, Kadir Kavaklıoğlu

Pages
898–905
Publication Date
2018-10-12
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗

Özet

Normal 0 false false false TR X-NONE X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Normal Tablo"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri",sans-serif; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi; mso-ansi-language:TR;} Karesel atama problemi (KAP), NP-hard sınıfındaki en zor kombinatoryal optimizasyon problemlerinden birisidir. Problemin zorluğundan dolayı birçok araştırmacı bu tip atama problemini çalışılmaktadır. Bu çalışmada tavlama benzetimi yöntemi MATLAB platformunda paralelleştirilerek iyi bilinen bir KAP Kütüphanesi olan QAPLIB’den alınan 36 örnek problemi çözmek için kullanılmıştır. Değişik paralelleştirme yöntemlerinin performansları kullanılan problemler için karşılaştırılmıştır. Sonuç olarak seri tavlama benzetimi yöntemiyle karşılaştırıldığında, paralel yöntemlerin uygun parametreler kullanıldığında daha hızlı sonuç verdiği görülmüştür.

Keywords
🔖

Cite This Article

Akkaş, S., Kavaklıoğlu, K. (2018). Comparison of simulated annealing parallelization methods for quadratic assignment problems. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, Cilt: 24 Sayı: 5, 898–905. https://ajindex.com/articles/1058728

📄 Full Text PDF Viewer

References (22)

  1. Koopmans TC, Beckmann M. “Assignment problems and the location of economic activities”. Econometrica, 25(1), 53-76, 1957.
  2. Loiola EM, de Abreu NMM, Boaventura-Netto PO, Hahn P, Querido T. “A survey for the quadratic assignment problem”. Europian Journal of Operational Research, 176(2), 657-690, 2007.
  3. Paul G. “Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem”. Operations Research Letters, 38(6), 577-581, 2010.
  4. Onbaşoǧlu E, Özdamar L. “Parallel simulated annealing algorithms in global optimization”. Journal of Global Optimization, 19(1), 27-50, 2001.
  5. Ferreiro AM, García JA, López-Salas JG, Vázquez C. “An efficient implementation of parallel simulated annealing algorithm in GPUs”. Journal of Global Optimization, 57(3), 863-890, 2013.
  6. Laursen PS. “Parallel heuristic search-introductions and a new approach”. Solving Combinatorial Optimization Problems in Parallel. Editors: Ferreira A, Pardalos P. Lecture Notes in Computer Science, 1054, 248-274, 1996.
  7. Holmqvist K, Migdalas A, Pardalos PM. Parallelized Heuristics for Combinatorial Search. Editors: Migdalas A, Pardalos PM, Storøy S. Parallel Computing in Optimization, 269-294, Boston, MA, USA, Springer, 1997.
  8. Hussin MS, Stützle T. “Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances”. Computers & Operation Research, 43, 286-291, 2014.
  9. Said GAENA, Mahmoud AM, El-Horbaty ESM. “A comparative study of meta-heuristic algorithms for solving quadratic assignment problem”. International Journal of Advanced Computer Science and Applications, 5(1), 1-6, 2014.
  10. Karami M, Niroomand S, Mirzaei N, Vizvari B. “Analysis and performance measurement of existing solution methods of quadratic assignment problem”. International Journal of Electronics, Mechanical and Mechatronics Engineering, 3(2), 557-570, 2014.
  11. Ghandeshtani KS, Mollai N, Seyedkashi SMH, Neshati MM. “New simulated annealing algorithm for quadratic assignment problem”. ADVCOMP 2010: The Fouth International Conference on Advanced Engineering Computing and Applications in Sciences, Florence, Italy, 25-30 October 2010.
  12. Wang JC. “A multistart simulated annealing algorithm for the quadratic assignment problem”. 3rd International Conference on Innovations in Bio-Inspired Computing and Applications, Kaohsiung, Taiwan, 26-28 September 2012.
  13. Kovac M. “Solving quadratic assignment problem in parallel using local search with simulated annealing elements”. The International Conference on Digital Technologies 2013, Zilina, Slovakia 29-31 May 2013.
  14. Kaviani MA, Abbasi M, Rahpeyma B, Yusefi MM. “A hybrid tabu search-simulated annealing method to solve quadratic assignment problem”. Decision Science Letters, 3(3), 391-396, 2014.
  15. Paul G. “A GPU implementation of the simulated annealing heuristic for the quadratic assignment problem”. Computing Research Repository, arXiv: 1208.2675, 2012.
  16. Rao SS. Engineering Optimization Theory and Practice. 4th ed. New Jersey, USA, Wiley, 2009.
  17. Chen H, Flann NS, Watson DW. “Parallel genetic simulated annealing: a massively parallel SIMD algorithm”. IEEE Transactions on Parallel and Distributed Systems, 9(2), 126-136, 1998.
  18. Burkard RE, Çela E, Karisch SE, Rendl F. "QAPLIB”. http://anjos.mgi.polymtl.ca/qaplib/ (09.05.2017).
  19. Nugent CE, Vollmann TE, Ruml J. “An experimental comparison of techniques for the assignment of facilities to locations”. Operations Research, 16(1), 150-173, 1968.
  20. Skorin-Kapov J. “Tabu search applied to the quadratic assignment problem”. ORSA Journal of Computing, 2(1), 33-45, 1990.
  21. Burkard RE, Karisch SE, Rendl F. “QAPLIB A quadratic assignment problem library”. Journal of Global Optimization, 10(4), 391-403, 1997.
  22. Li Y, Pardalos PM. “Generating quadratic assignment test problems with known optimal permutations”. Computational Optimization and Applications, 1(2), 163-184, 1992.