Bandit-Inspired Memetic Algorithms for Solving Quadratic Assignment Problems

Francesco Puglierin, Madalina Drugan, Marco Wiering

Research output: Chapter in Book/Report/Conference proceedingConference paperResearch

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 three hard QAP instances, and the results show that BIMA significantly outperforms these competitors.
Original languageEnglish
Title of host publicationProceedings of the IEEE Congress on Evolutionary Computation, CEC 2013
PublisherIEEE
Pages2078-2085
ISBN (Print)978-1-4799-0452-5
Publication statusPublished - Jun 2013
Event2013 IEEE Congress on Evolutionary Computation - Cancun, Mexico
Duration: 20 Jun 201323 Jun 2013

Publication series

NameProceedings of the IEEE Congress on Evolutionary Computation, CEC 2013

Conference

Conference2013 IEEE Congress on Evolutionary Computation
CountryMexico
CityCancun
Period20/06/1323/06/13

Keywords

  • Iterated local search
  • Memetic algorithms
  • Quadratic assignment problem

Cite this