Adaptive multi-operator metaheuristics for quadratic assignment problems

M.M. Drugan; E.Gh. Talbi

doi:10.1007/978-3-319-07494-8_11

Adaptive multi-operator metaheuristics for quadratic assignment problems

M.M. Drugan, E.Gh. Talbi

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

6 Citations (Scopus)

1 Downloads (Pure)

Abstract

Local search based algorithms are a general and computational efficient metaheuristic. Restarting strategies are used in order to not be stuck in a local optimum. Iterated local search restarts the local search using perturbator operators, and the variable neighbourhood search alternates local search with various neighbourhoods. These two popular restarting techniques, or operators, evolve independently and are disconnected. We propose a metaheuristic framework, we call it multi-operator metaheuristics, which allows the alternative or simultaneously usage of the two restarting methods. Tuning the parameters, i.e. the neighbourhood size and the perturbation rate, is essential for the performance of metaheuristics. We automatically adapt the parameters for the two restarting operators using variants of adaptive pursuit for the multi-operators metaheuristic algorithms. We experimentally study the performance of several instances of the new class of metaheuristics on the quadratic assignment problem (QAP) instances, a wellknown and difficult combinatorial optimization problem.

Original language	English
Title of host publication	EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V
Editors	A.-A. Tantar, E. Tantar, J.-Q. Sun, W. Zhang, Q. Ding, O. Schütze, M. Emmerich, P. Legrand, P. Del Moral, C.A. Coello Coello
Place of Publication	Berlin
Publisher	Springer
Pages	149-163
Number of pages	15
ISBN (Print)	9783319074931
DOIs	https://doi.org/10.1007/978-3-319-07494-8_11
Publication status	Published - 2014
Externally published	Yes
Event	International Conference on Evolutionary Computation V (EVOLVE 2014) - Beijing, China Duration: 1 Jul 2014 → 4 Jul 2014 Conference number: V

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	288
ISSN (Print)	21945357

Conference

Conference	International Conference on Evolutionary Computation V (EVOLVE 2014)
Abbreviated title	EVOLVE 2014
Country/Territory	China
City	Beijing
Period	1/07/14 → 4/07/14

Access to Document

10.1007/978-3-319-07494-8_11

Cite this

Drugan, M. M., & Talbi, E. G. (2014). Adaptive multi-operator metaheuristics for quadratic assignment problems. In A.-A. Tantar, E. Tantar, J.-Q. Sun, W. Zhang, Q. Ding, O. Schütze, M. Emmerich, P. Legrand, P. Del Moral, & C. A. Coello Coello (Eds.), EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V (pp. 149-163). (Advances in Intelligent Systems and Computing; Vol. 288). Springer. https://doi.org/10.1007/978-3-319-07494-8_11

Drugan, M.M. ; Talbi, E.Gh. / Adaptive multi-operator metaheuristics for quadratic assignment problems. EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V. editor / A.-A. Tantar ; E. Tantar ; J.-Q. Sun ; W. Zhang ; Q. Ding ; O. Schütze ; M. Emmerich ; P. Legrand ; P. Del Moral ; C.A. Coello Coello. Berlin : Springer, 2014. pp. 149-163 (Advances in Intelligent Systems and Computing).

@inbook{83835983656a412bb83d9422d0737d6f,

title = "Adaptive multi-operator metaheuristics for quadratic assignment problems",

abstract = "Local search based algorithms are a general and computational efficient metaheuristic. Restarting strategies are used in order to not be stuck in a local optimum. Iterated local search restarts the local search using perturbator operators, and the variable neighbourhood search alternates local search with various neighbourhoods. These two popular restarting techniques, or operators, evolve independently and are disconnected. We propose a metaheuristic framework, we call it multi-operator metaheuristics, which allows the alternative or simultaneously usage of the two restarting methods. Tuning the parameters, i.e. the neighbourhood size and the perturbation rate, is essential for the performance of metaheuristics. We automatically adapt the parameters for the two restarting operators using variants of adaptive pursuit for the multi-operators metaheuristic algorithms. We experimentally study the performance of several instances of the new class of metaheuristics on the quadratic assignment problem (QAP) instances, a wellknown and difficult combinatorial optimization problem.",

author = "M.M. Drugan and E.Gh. Talbi",

year = "2014",

doi = "10.1007/978-3-319-07494-8_11",

language = "English",

isbn = "9783319074931",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer",

pages = "149--163",

editor = "A.-A. Tantar and E. Tantar and J.-Q. Sun and W. Zhang and Q. Ding and O. Sch{\"u}tze and M. Emmerich and P. Legrand and {Del Moral}, P. and {Coello Coello}, C.A.",

booktitle = "EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V",

address = "Germany",

note = "International Conference on Evolutionary Computation V (EVOLVE 2014), EVOLVE 2014 ; Conference date: 01-07-2014 Through 04-07-2014",

}

Drugan, MM & Talbi, EG 2014, Adaptive multi-operator metaheuristics for quadratic assignment problems. in A-A Tantar, E Tantar, J-Q Sun, W Zhang, Q Ding, O Schütze, M Emmerich, P Legrand, P Del Moral & CA Coello Coello (eds), EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V. Advances in Intelligent Systems and Computing, vol. 288, Springer, Berlin, pp. 149-163, International Conference on Evolutionary Computation V (EVOLVE 2014), Beijing, China, 1/07/14. https://doi.org/10.1007/978-3-319-07494-8_11

Adaptive multi-operator metaheuristics for quadratic assignment problems. / Drugan, M.M.; Talbi, E.Gh.
EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V. ed. / A.-A. Tantar; E. Tantar; J.-Q. Sun; W. Zhang; Q. Ding; O. Schütze; M. Emmerich; P. Legrand; P. Del Moral; C.A. Coello Coello. Berlin: Springer, 2014. p. 149-163 (Advances in Intelligent Systems and Computing; Vol. 288).

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

TY - CHAP

T1 - Adaptive multi-operator metaheuristics for quadratic assignment problems

AU - Drugan, M.M.

AU - Talbi, E.Gh.

N1 - Conference code: V

PY - 2014

Y1 - 2014

N2 - Local search based algorithms are a general and computational efficient metaheuristic. Restarting strategies are used in order to not be stuck in a local optimum. Iterated local search restarts the local search using perturbator operators, and the variable neighbourhood search alternates local search with various neighbourhoods. These two popular restarting techniques, or operators, evolve independently and are disconnected. We propose a metaheuristic framework, we call it multi-operator metaheuristics, which allows the alternative or simultaneously usage of the two restarting methods. Tuning the parameters, i.e. the neighbourhood size and the perturbation rate, is essential for the performance of metaheuristics. We automatically adapt the parameters for the two restarting operators using variants of adaptive pursuit for the multi-operators metaheuristic algorithms. We experimentally study the performance of several instances of the new class of metaheuristics on the quadratic assignment problem (QAP) instances, a wellknown and difficult combinatorial optimization problem.

AB - Local search based algorithms are a general and computational efficient metaheuristic. Restarting strategies are used in order to not be stuck in a local optimum. Iterated local search restarts the local search using perturbator operators, and the variable neighbourhood search alternates local search with various neighbourhoods. These two popular restarting techniques, or operators, evolve independently and are disconnected. We propose a metaheuristic framework, we call it multi-operator metaheuristics, which allows the alternative or simultaneously usage of the two restarting methods. Tuning the parameters, i.e. the neighbourhood size and the perturbation rate, is essential for the performance of metaheuristics. We automatically adapt the parameters for the two restarting operators using variants of adaptive pursuit for the multi-operators metaheuristic algorithms. We experimentally study the performance of several instances of the new class of metaheuristics on the quadratic assignment problem (QAP) instances, a wellknown and difficult combinatorial optimization problem.

UR - http://www.scopus.com/inward/record.url?scp=84927553571&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-07494-8_11

DO - 10.1007/978-3-319-07494-8_11

M3 - Chapter

AN - SCOPUS:84927553571

SN - 9783319074931

T3 - Advances in Intelligent Systems and Computing

SP - 149

EP - 163

BT - EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V

A2 - Tantar, A.-A.

A2 - Tantar, E.

A2 - Sun, J.-Q.

A2 - Zhang, W.

A2 - Ding, Q.

A2 - Schütze, O.

A2 - Emmerich, M.

A2 - Legrand, P.

A2 - Del Moral, P.

A2 - Coello Coello, C.A.

PB - Springer

CY - Berlin

T2 - International Conference on Evolutionary Computation V (EVOLVE 2014)

Y2 - 1 July 2014 through 4 July 2014

ER -

Drugan MM, Talbi EG. Adaptive multi-operator metaheuristics for quadratic assignment problems. In Tantar AA, Tantar E, Sun JQ, Zhang W, Ding Q, Schütze O, Emmerich M, Legrand P, Del Moral P, Coello Coello CA, editors, EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V. Berlin: Springer. 2014. p. 149-163. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-319-07494-8_11

Adaptive multi-operator metaheuristics for quadratic assignment problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this