1. A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem
- Author
-
Umut Tosun, Tansel Dokeroglu, and Ahmet Cosar
- Subjects
Mathematical optimization ,education.field_of_study ,Island model ,Quadratic assignment problem ,Strategy and Management ,Population ,Crossover ,Parallel algorithm ,Management Science and Operations Research ,Industrial and Manufacturing Engineering ,Parallel genetic algorithm ,Domain (software engineering) ,Genetic algorithm ,education ,Algorithm ,Mathematics - Abstract
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 experiment...
- Published
- 2013