KaydedilenlerDerginizi ekleyin

Dergiler / Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi / 2017 / Cilt: 23 Sayı: 5

Karesel atama problemi için yeni bir özuyarlamalı paralel güçlü tabu-arama algoritması

A self-adaptive parallel robust tabu-search algorithm for the quadratic assignment problem

Tansel Dökeroğlu

Sayfa
559–565
Yayın Tarihi
2017-10-20
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗

Ö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;} Bu çalışma ile Karesel Atama Problemi (KAP) olarak bilinen ve çok sayıda konum ve tesis içeren örnekler için en iyi çözümleri hala bulunamamış olan NP-zor bir kombinatoriyal problem için yeni bir paralel sezgisel algoritma önerilmektedir (paralel-tabu-KAP algoritması). İki safhası bulunan paralel-tabu-KAP algoritması, genetik algoritma safhasında efendi işlemcide bulunan popülasyon üzerinde sezgisel tabu-arama algoritmasının parametrelerini jenerasyonlar ile eniyilerken, tabu-arama safhasında işçi işlemciler üzerinde verilen problemin sonucunu farklı başlangıç noktaları ile eniyilemektedir. Yerel takılmaları, aramaya başka noktalardan yeniden başlayarak engelleme özelliğine sahip olan paralel-tabu-KAP algoritması, tek işlemci ile çalışan ve parametreleri statik olarak önceden tanımlanmış olan versiyonlarına göre daha iyi sonuçlar elde etmektedir. Yüzün üzerindeki bençmark problem ile yapılan deneyler sonucunda,   ortalama %0.05’lik bir sapma elde edilmiştir. Bu sonuçlar, paralel-tabu-KAP algoritmasının kendi sınıfındaki sezgisel algoritmalar içerisinde KAP’ın çözümü için önerilen en iyi algoritmalar arasında olduğunu göstermektedir.

Anahtar kelimeler
🔖

Bu Makaleye Atıf Yap

Dökeroğlu, T. (2017). Karesel atama problemi için yeni bir özuyarlamalı paralel güçlü tabu-arama algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, Cilt: 23 Sayı: 5, 559–565. https://ajindex.com/articles/1058907

📄 Tam Metin PDF Okuyucu

↗Yeni Sekme

PDF belgesi yükleniyor...

Kaynakça (17)

  1. Koopmans TC, Beckmann MJ. “Assignment problems and the location of economic activities”. Econometrica, 25(1), 53-76, 1957.
  2. Dokeroglu T. “Hybrid teaching-learning-based optimization algorithms for the quadratic assignment problem”. Computers & Industrial, 85, 86-101, 2015.
  3. Glover, F. “Tabu search part II”. ORSA Journal on Computing, 2(1), 4-32, 1990.
  4. Lstiburek M, Stejskal J, Misevicius A, Korecky J, El-Kassaby, YA. “Expansion of the minimum-inbreeding seed orchard design to operational scale”. Tree Genetics & Genomes, 11(1), 1-8, 2015.
  5. Burkard RE, Karisch SE, Rendl F. “QAPLIB a quadratic assignment problem library”. European Journal of Operational Research, 55(1), 115-119, 1991.
  6. Steinberg L. “The backboard wiring problem: A placement algorithm”. SIAM Review, 3(1), 37-50, 1961.
  7. Rossin DF, Springer MC, Klein BD. “New complexity measures for the facility layout problem: An empirical study using traditional and neural network analysis”. Computers and Industrial Engineering, 36(3), 585-602, 1999.
  8. Taillard E. “Robust taboo search for the quadratic assignment problem”. Parallel Computing, 17(4-5), 443-455, 1991.
  9. Stutzle, T. “Iterated local search for the quadratic assignment problem”. European Journal of Operational Research, 174(3), 1519-1539, 2006.
  10. Burkard RE, Karisch SE, Rendl F. “QAPLIB a quadratic assignment problem library”. European Journal of OperationalResearch, 55(1), 115-119, 1991.
  11. Misevicius, A. “An implementation of the iterated tabu search algorithm for the quadratic assignment problem”. OR Spectrum, 34(3), 665-690, 2012.
  12. James, T., Rego, C., & Glover, F. Multistart tabu search and diversification strategies for the quadratic assignment problem. IEEE Transactions on Systems, Man, and Cybernetics-part a: systems and humans, 39(3), 579-596, 2009.
  13. Fescioglu-Unver N, Kokar MM. “Self controlling tabu search algorithm for the quadratic assignment problem”. Computers & Industrial Engineering, 60(2), 310-319, 2011.
  14. James T, Rego C, Glover F. “A cooperative parallel tabu search algorithm for the QAP”. European Journal of Operational Research, 195(3), 810-826, 2009.
  15. Drezner Z. “The extended concentric tabu for the quadratic assignment problem”. European Journal of Operational Research, 160(2), 416-422, 2005.
  16. Goldberg D. Genetic algorithms in search, optimization and machine learning. 1st edition, New York, NY, USA, Addison-Wesley, 1989.
  17. Türkbey O. “A genetic algorithm using the local search heuristic in facilities layout problem: A memetic algorithm approach”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 8(2), 265-271, 2002.