Bandit-inspired memetic algorithms for solving quadratic assignment problems

Fr. Puglierin; M.M. Drugan; M.A. Wiering

doi:10.1109/CEC.2013.6557814

Bandit-inspired memetic algorithms for solving quadratic assignment problems

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 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 language	English
Title of host publication	2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Pages	2078-2085
ISBN (Print)	978-1-4799-0453-2
DOIs	https://doi.org/10.1109/CEC.2013.6557814
Publication status	Published - 2013
Externally published	Yes

Keywords

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

Access to Document

10.1109/CEC.2013.6557814

Cite this

@inproceedings{0d6897ab9d4545bbb79f04db0e28c9af,

title = "Bandit-inspired memetic algorithms for solving quadratic assignment problems",

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.",

keywords = "Meta-heuristics, Memetic Algorithms, Combinatorial Optimization, Quadratic Assignment Problem, Multiarmed Bandit Algorithms",

author = "Fr. Puglierin and M.M. Drugan and M.A. Wiering",

year = "2013",

doi = "10.1109/CEC.2013.6557814",

language = "English",

isbn = "978-1-4799-0453-2",

pages = "2078--2085",

booktitle = "2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

Bandit-inspired memetic algorithms for solving quadratic assignment problems. / Puglierin, Fr.; Drugan, M.M.; Wiering, M.A.
2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico. Piscataway: Institute of Electrical and Electronics Engineers, 2013. p. 2078-2085.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Bandit-inspired memetic algorithms for solving quadratic assignment problems

AU - Puglierin, Fr.

AU - Drugan, M.M.

AU - Wiering, M.A.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Meta-heuristics

KW - Memetic Algorithms

KW - Combinatorial Optimization

KW - Quadratic Assignment Problem

KW - Multiarmed Bandit Algorithms

U2 - 10.1109/CEC.2013.6557814

DO - 10.1109/CEC.2013.6557814

M3 - Conference contribution

SN - 978-1-4799-0453-2

SP - 2078

EP - 2085

BT - 2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

ER -

Bandit-inspired memetic algorithms for solving quadratic assignment problems

Abstract

Keywords

Access to Document

Fingerprint

Cite this