A stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Fen Bilimleri Enstitüsü, Türkiye

Tezin Onay Tarihi: 2016

Öğrenci: YAĞMUR AKSAN

Danışman: AHMET COŞAR

Özet:

The quadratic assignment problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems with its several real life applications. Layout design, scheduling, and assigning gates to planes at an airport are some of the interesting applications of the QAP. In this thesis, we improve the talents of a recent local search heuristic Breakout Local Search Algorithm (BLS) by using adapted Levenshtein Distance metric for similarity checking of the previously explored permutations of the QAP problem instances. In addition to this, the proposed algorithm, BLS-OpenMP-QAP (Breakout Local Search Algorithm with Open Multi-Processing for Quadratic Assignment Problem), makes use of the parallel computation paradigm of the contemporary multi-core architectures using OpenMP programming paradigm. The stagnation-aware search for the (near-)optimal solution of the QAP is executed concurrently on several cores with diversified trajectories while considering the similarity of the already detected local optima. The exploration of the search space is improved by selecting the starting points intelligently and speeding-up the fitness evaluations as many as the number of the processors/threads. The BLS-OpenMP-QAP algorithm is executed on 59 problem instances of the QAP library benchmark and the results shows that it is able to solve 57 of the instances exactly. The overall deviation for the algorithm is obtained as 0.019% on the average; therefore, it can be reported to be among the best algorithms in the literature.