Bandit-inspired memetic algorithms for solving quadratic assignment problems

Fr. Puglierin, M.M. Drugan, M.A. Wiering

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

In this paper we propose a novel algorithm called the Bandit-Inspired Memetic Algorithm (BIMA) and we have applied it to solve different large instances of the Quadratic Assignment Problem (QAP). Like other memetic algorithms, BIMA makes use of local search and a population of solutions. The novelty lies in the use of multi-armed bandit algorithms and assignment matrices for generating novel solutions, which will then be brought to a local minimum by local search. We have compared BIMA to multi-start local search (MLS) and iterated local search (ILS) on five QAP instances, and the results show that BIMA significantly outperforms these competitors.
Original languageEnglish
Title of host publication2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages2078-2085
ISBN (Print)978-1-4799-0453-2
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Meta-heuristics
  • Memetic Algorithms
  • Combinatorial Optimization
  • Quadratic Assignment Problem
  • Multiarmed Bandit Algorithms

Cite this