A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem

Tosun U., Dokeroglu T., COŞAR A.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, cilt.51, sa.14, ss.4117-4133, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 51 Sayı: 14
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1080/00207543.2012.746798
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.4117-4133
  • Anahtar Kelimeler: genetic algorithms, parallel algorithms, island parallel genetic algorithm, quadratic assignment problem, TABU SEARCH ALGORITHM, ALLOCATION PROBLEM, PATH-RELINKING, OPTIMIZATION, STRATEGIES
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.