Yıl 2018, Cilt 4, Sayı 2, Sayfalar 123 - 127 2018-06-27

A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem

Erdener Özçetin [1] , Gürkan Öztürk [2]

40 64

In this study, quadratic assignment problem, which is a hard combinatorial optimization problem, is examined to solve by a new approach. To reach the optimal results by using mathematical programming approaches cannot be possible even for some sorts of small and middle scaled problems in a reasonable time interval. Huge amounts of data are being progressed simultaneously by graphics processing units located on computers’ graphics card. Therefore, a parallel iterated local search algorithm has been proposed to solve the quadratic assignment problem by using graphics processing units’ simultaneously progressing property. This parallel algorithm and the sequential one on central processing units are tested and compared for test problems in literature. Indeed, it is observed that the parallel algorithm works averagely 6.31 times faster for Skorin problems and 11.93 times faster for Taillard problems faster than sequentially one.

Quadratic assignment problem (QAP), local search algorithms, graphics processing units (GPU), CUDA
  • T. C. Koopmans ve M. J. Beckmann, “Assignment problems and the location of economic activities,” Econometrica, vol. 25, pp. 53-76, 1957.
  • S. Sahni ve T. Gonzalez, “P-complete approximation problems,” Journal of the Association of Computing Machinery, vol. 23, pp. 555-565, 1976.
  • S. Kirkpatrick, C. Gelat ve M. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983.
  • R. Burkard ve F. Rendl, “A thermodynamically motivated simulation procedure for combinatorial optimization problems,” European Journal of Operational Research, vol. 17, pp. 169-174, 1984.
  • M. Wilhelm ve T. Ward, “Solving quadratic assignment problems by 'simulated annealing',” IIE Transactions, vol. 19, pp. 107-119, 1987.
  • N. Abreu, T. Querido ve P. Boaventura-Netto, “A simulated annealing for the quadratic assignment problem,” Rairo-Operations Research, vol. 33, pp. 249-273, 1999.
  • T. Stützle ve M. Dorigo, “ACO Algorithms for the Quadratic Assignment Problem,” New Ideas in Optimization,McGraw-Hill, 1999.
  • M. Dorigo, V. Maniezzo ve A. Colorni, “The Ant System: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, vol. 26, pp. 1-13, 1996.
  • J. Kochhar, B. Foster ve S. Heragu, “A genetic algorithm for the unequal area facility layout problem,” Computers & Operations Research, vol. 25, pp. 583-594, 1998.
  • Z. Drezner, “A New Genetic Algorithm for the Quadratic Assignment Problem,” Informs Journal on Computing, vol. 15, pp. 320-330, 2003.
  • F. Glover, “Tabu Search - Part I,” ORSA Journal on Computing, vol. 1, pp. 190-206, 1989.
  • J. Skorin-Kapov, “Tabu Search Applied to the Quadratic Assignment Problem,” ORSA Journal on Computing, vol. 2, pp. 33-45, 1990.
  • E. D. Taillard, “Robust taboo search for the quadratic assignment problem,” Parallel Computing, vol. 17, pp. 443-455, 1991.
  • A. Misevičius ve A. Ostreika, “Defining Tabu tenure for the Quadratic Assignment Problem,” Information Technology and Control, vol. 36, 2007.
  • "Developer Centers: CUDA Zone,” nVIDIA,. Available: http://developer.nvidia.com/cuda/what-cuda.
  • S. Tsutsui ve N. Fujimoto, “Solving Quadratic Assignment Problems by Genetic Algorithms with GPU Computation: A Case Study,” GECCO, Montreal, 2009.
  • S. Tsutsui ve N. Fujimoto, “Fast QAP Solving by ACO with 2-opt Local Search on a GPU,” IEEE Section Congres, San Francisco, 2011.
  • M. Czapinski, “An effective Parallel Multistart Tabu Search for Quadratic Assignment Problem CUDA platform,” J. Parallel Distrib. Comput., vol. 73(11), pp. 1461-1468, 2013.
  • E. Özçetin ve G. Öztürk, “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units,” ANADOLU UNIVERSITY JOURNAL OF SCIENCE AND TECHNOLOGY –A Applied Sciences and Engineering, vol. 17, no. 1, pp. 167-180, 2016.
Birincil Dil en
Konular Mühendislik
Dergi Bölümü Articles
Yazarlar

Yazar: Erdener Özçetin
Kurum: HİTİT ÜNİVERSİTESİ
Ülke: Turkey


Yazar: Gürkan Öztürk

Bibtex @araştırma makalesi { ijet346573, journal = {International Journal of Engineering Technologies}, issn = {2149-0104}, eissn = {2149-5262}, address = {İstanbul Gelişim Üniversitesi}, year = {2018}, volume = {4}, pages = {123 - 127}, doi = {}, title = {A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem}, key = {cite}, author = {Öztürk, Gürkan and Özçetin, Erdener} }
APA Özçetin, E , Öztürk, G . (2018). A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem. International Journal of Engineering Technologies, 4 (2), 123-127. Retrieved from http://dergipark.gov.tr/ijet/issue/38459/346573
MLA Özçetin, E , Öztürk, G . "A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem". International Journal of Engineering Technologies 4 (2018): 123-127 <http://dergipark.gov.tr/ijet/issue/38459/346573>
Chicago Özçetin, E , Öztürk, G . "A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem". International Journal of Engineering Technologies 4 (2018): 123-127
RIS TY - JOUR T1 - A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem AU - Erdener Özçetin , Gürkan Öztürk Y1 - 2018 PY - 2018 N1 - DO - T2 - International Journal of Engineering Technologies JF - Journal JO - JOR SP - 123 EP - 127 VL - 4 IS - 2 SN - 2149-0104-2149-5262 M3 - UR - Y2 - 2018 ER -
EndNote %0 International Journal of Engineering Technologies A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem %A Erdener Özçetin , Gürkan Öztürk %T A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem %D 2018 %J International Journal of Engineering Technologies %P 2149-0104-2149-5262 %V 4 %N 2 %R %U
ISNAD Özçetin, Erdener , Öztürk, Gürkan . "A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem". International Journal of Engineering Technologies 4 / 2 (Haziran 2018): 123-127.