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

Öz

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

• Tabu-arama,Paralel,Karesel atama problemi,Genetik

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

Abstract

With this study, we propose a novel parallel robust tabu-search algorithm (Parallel-Tabu-QAP) for the NP-Hard Quadratic Assignment Problem (QAP)of whose instances having large number of location and facilites have not been reported to be solved exactly so far. Parallel-Tabu-QAP algorithm that has two phases optimizes the parameters of tabu-search algorithm in its first phase by using genetic algorithms through generations. The individuals that have parameters of the tabu-search are optimized in a population that is located on a master processor. In the second phase, slave processors optimize the solution of the problem by restarting their search process in case of stagnations. With its stagnation prevention and parallel optimization talents, parallel-tabu-QAP algorithm is observed to obtain better results than its sequential and statically parameter-tuned counterparts. The algorithm has 0.05% deviation for the benchmark tests performed on more than 100 problem instances. These experimental results show that the parallel-tabu-QAP algoritm is one the best performing techniques in its heuristics algorithms class when compared with state-of-the-art QAP algorithms.

Keywords

• Tabu-search,Parallel,Quadratic assignment problem,Genetic

Kaynakça

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.