A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem

Date

2013-07-01

Author

Tosun, Umut
Dokeroglu, Tansel
Coşar, Ahmet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

144
views

0
downloads

The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-known instances from the QAPLIB library. By increasing the number of processors, generations and population sizes we have been able to find solutions that are the same as (or very close to) the best reported solutions for large QAP instances in QAPLIB. In order to parallelise the Genetic Algorithm we generate and evolve separate solution pools on each cluster processor, using an island model. This model exchanges 10% of each processor's solutions at the initial stages of optimisation. We show experimentally that both execution times and solution qualities are improved for large QAP instances by using our Island Parallel Genetic Algorithm.

Subject Keywords

Genetic algorithms, Parallel algorithms, İsland parallel genetic algorithm, Quadratic assignment problem

URI

https://hdl.handle.net/11511/31259

Journal

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

DOI

https://doi.org/10.1080/00207543.2012.746798

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem Aksan, Yagmur; Dokeroglu, Tansel; Coşar, Ahmet (2017-01-01) 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 permut...
A method for chromosome handling of r-permutations of n-element set in genetic algorithms Üçoluk, Göktürk (1997-04-16) Combinatorial optimisation problems are in the domain of Genetic Algorithms (GA) interest. Unfortunately ordinary crossover and mutation operators cause problems for chromosome representations of permutations and some types of combinations. This is so because offsprings generated by means of the ordinary operators are of a great possibility no more valid chromosomes. A variety of methods and new operators that handle that sort of obscenities are introduced throughout the literature. A new method for represe...
A Stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture Aksan, Yağmur; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2016) 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 p...
A strong conic quadratic reformulation for machine-job assignment with controllable processing times Akturk, M. Selim; Atamturk, Alper; Gürel, Sinan (2009-05-01) we describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based only on the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation.
A Rayleigh–Ritz Method for Numerical Solutions of Linear Fredholm Integral Equations of the Second Kind Kaya, Ruşen; Taşeli, Hasan (2022-01-01) A Rayleigh–Ritz Method is suggested for solving linear Fredholm integral equations of the second kind numerically in a desired accuracy. To test the performance of the present approach, the classical one-dimensional Schrödinger equation -y″(x)+v(x)y(x)=λy(x),x∈(-∞,∞) has been converted into an integral equation. For a regular problem, the unbounded interval is truncated to x∈ [ - ℓ, ℓ] , where ℓ is regarded as a boundary parameter. Then, the resulting integral equation has been solved and the results are co...

Citation Formats

U. Tosun, T. Dokeroglu, and A. Coşar, “A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem,” INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, pp. 4117–4133, 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31259.