Back to Search
Start Over
A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem
- Source :
- Computers & Industrial Engineering. 103:105-115
- Publication Year :
- 2017
- Publisher :
- Elsevier BV, 2017.
-
Abstract
- A new version of BLS algorithm is introduced.Levenshtein Distance (LD) metric is applied to the BLS heuristic.The QAP is optimized with several processors using OpenMP.Significant improvements are obtained.The BLS-OpenMP can be reported as one of the best heuristics for the QAP. The Quadratic Assignment Problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems. Circuit-layout design, transportation/traffic engineering, and assigning gates to airplanes are some of the interesting applications of the QAP. In this study, we introduce an enhanced version of a recent local search heuristic, Breakout Local Search Algorithm (BLS), by using the Levenshtein Distance metric for checking the similarity of the new starting points to previously explored QAP permutations. The similarity-checking process prevents the local search algorithm, BLS, from getting stuck in already-explored areas. In addition, the proposed BLS Algorithm (BLS-OpenMP) incorporates multi-threaded computation using OpenMP. The stagnation-aware search for the optimal solutions of the QAP is executed concurrently on several cores with diversified trajectories while considering their similarity to already-discovered local optima. The exploration of the search space is improved by selecting the starting points intelligently and speeding up the fitness evaluations linearly with number of processors/threads. BLS-OpenMP has been tested on the hardest 59 problem instances of the QAPLIB, and it obtained 57 of the best known results. The overall deviation of the achieved solutions from the best known results is 0.019% on average, which is a significant improvement compared with state-of-the-art algorithms.
- Subjects :
- Mathematical optimization
021103 operations research
General Computer Science
Quadratic assignment problem
business.industry
Heuristic (computer science)
0211 other engineering and technologies
General Engineering
02 engineering and technology
Levenshtein distance
Local optimum
Metric (mathematics)
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Local search (optimization)
Guided Local Search
Heuristics
business
Algorithm
Mathematics
Subjects
Details
- ISSN :
- 03608352
- Volume :
- 103
- Database :
- OpenAIRE
- Journal :
- Computers & Industrial Engineering
- Accession number :
- edsair.doi...........3d0962c2d6ba286af5672e98f642d54b