Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
181
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.