poster

Reinforcement learning for adaptive operator selection in memetic search applied to quadratic assignment problem

Authors:

Stephanus Daniel Handoko,

Duc Thien Nguyen,

Zhi Yuan,

Hoong Chuin LauAuthors Info & Claims

GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 193 - 194

https://doi.org/10.1145/2598394.2598451

Published: 12 July 2014 Publication History

Get Access

Abstract

Memetic search is well known as one of the state-of-the-art metaheuristics for finding high-quality solutions to NP-hard problems. Its performance is often attributable to appropriate design, including the choice of its operators. In this paper, we propose a Markov Decision Process model for the selection of crossover operators in the course of the evolutionary search. We solve the proposed model by a Q-learning method. We experimentally verify the efficacy of our proposed approach on the benchmark instances of Quadratic Assignment Problem.

References

[1]

K. A. De Jong. Evolutionary Computation: A Unified Approach, MIT Press, 2006.

Digital Library

Google Scholar

[2]

D. H. Wolpert and W. G. Macready. No Free Lunch Theorems for Optimization. IEEE T. Evolut. Comput., 1(1):67--82, 1997.

Digital Library

Google Scholar

[3]

M. Birattari, et al. F-Race and Iterated F-Race: An overview. Experimental Methods for the Analysis of Optimization Algorithms, 311--336, 2010.

Google Scholar

[4]

E. Krempser, et al. Adaptive Operator Selection at the Hyper-level. LNCS, 7492:378--387, 2012.

Digital Library

Google Scholar

[5]

Á. Fialho, et al. Extreme Value Based Adaptive Operator Selection. LNCS, 5199:175--184, 2008.

Digital Library

Google Scholar

[6]

J. Maturana, et al. Autonomous Operator Management for Evolutionary Algorithms. J. Heuristics, 16(6):881--909, 2010.

Digital Library

Google Scholar

[7]

Z. Yuan, et al. An Empirical Study of Off-line Configuration and On-line Adaptation in Operator Selection. LNCS, in Press.

Google Scholar

[8]

M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994.

Crossref

Google Scholar

[9]

G. Francesca, et al. Off-line and On-line Tuning: A Study on Operator Selection for A Memetic Algorithm Applied to the QAP. LNCS, 6622:203--214, 2011.

Digital Library

Google Scholar

[10]

P. Merz and B. Freisleben. Fitness Landscape Analysis and Memetic Algorithms for the QAP. IEEE T. Evolut. Comput., 4(4):337--352, 2000.

Digital Library

Google Scholar

Cited By

View all

Pei JLiu JMei YLi XHandl J(2024)Learning from Offline and Online Experiences: A Hybrid Adaptive Operator Selection FrameworkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654062(1017-1025)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654062
Xue FChen YWang PYe YDong JDong T(2024)A decomposition-based multi-objective evolutionary algorithm with Q-learning for adaptive operator selectionThe Journal of Supercomputing10.1007/s11227-024-06258-880:14(21229-21283)Online publication date: 7-Jun-2024
https://doi.org/10.1007/s11227-024-06258-8
Pei JTong HLiu JMei YYao XSilva SPaquete L(2023)Local Optima Correlation Assisted Adaptive Operator SelectionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590399(339-347)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590399
Show More Cited By

Index Terms

Reinforcement learning for adaptive operator selection in memetic search applied to quadratic assignment problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Memetic search for the quadratic assignment problem

We present a memetic algorithm (called BMA) for the well-known QAP.BMA integrates BLS within the population-based evolutionary computing framework.BMA is able to attain the best-known results for 133 out of 135 QAP benchmark instances.We provide ...
Penguins Search Optimization Algorithm to Solve Quadratic Assignment Problem
BDCA'17: Proceedings of the 2nd international Conference on Big Data, Cloud and Applications

This paper presents an application of new metaheuristics, based on the penguins hunting strategy, Penguins search optimization algorithm (PeSOA) for solving one of the most difficult NP-hard combinatorial optimization problems in discret case the ...
A tabu search algorithm for the quadratic assignment problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1524 pages

ISBN:9781450328814

DOI:10.1145/2598394

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2014

Check for updates

Qualifiers

Poster

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO Comp '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
161
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)3

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pei JLiu JMei YLi XHandl J(2024)Learning from Offline and Online Experiences: A Hybrid Adaptive Operator Selection FrameworkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654062(1017-1025)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654062
Xue FChen YWang PYe YDong JDong T(2024)A decomposition-based multi-objective evolutionary algorithm with Q-learning for adaptive operator selectionThe Journal of Supercomputing10.1007/s11227-024-06258-880:14(21229-21283)Online publication date: 7-Jun-2024
https://doi.org/10.1007/s11227-024-06258-8
Pei JTong HLiu JMei YYao XSilva SPaquete L(2023)Local Optima Correlation Assisted Adaptive Operator SelectionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590399(339-347)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590399
Tian YLi XMa HZhang XTan KJin Y(2023)Deep Reinforcement Learning Based Adaptive Operator Selection for Evolutionary Multi-Objective OptimizationIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2022.31468827:4(1051-1064)Online publication date: Aug-2023
https://doi.org/10.1109/TETCI.2022.3146882
Hu ZGong WPedrycz WLi Y(2023)Deep reinforcement learning assisted co-evolutionary differential evolution for constrained optimizationSwarm and Evolutionary Computation10.1016/j.swevo.2023.10138783(101387)Online publication date: Dec-2023
https://doi.org/10.1016/j.swevo.2023.101387
Yi WQu R(2023)Automated Design of Search Algorithms based on Reinforcement LearningInformation Sciences10.1016/j.ins.2023.119639(119639)Online publication date: Sep-2023
https://doi.org/10.1016/j.ins.2023.119639
Durgut RAydin MRakib A(2022)Transfer Learning for Operator Selection: A Reinforcement Learning ApproachAlgorithms10.3390/a1501002415:1(24)Online publication date: 17-Jan-2022
https://doi.org/10.3390/a15010024
Dantas APozo A(2022)The Impact of State Representation on Approximate Q-Learning for a Selection Hyper-heuristicIntelligent Systems10.1007/978-3-031-21686-2_4(45-60)Online publication date: 19-Nov-2022
https://doi.org/10.1007/978-3-031-21686-2_4
Pei JMei YLiu JYao X(2022)An Investigation of Adaptive Operator Selection in Solving Complex Vehicle Routing ProblemPRICAI 2022: Trends in Artificial Intelligence10.1007/978-3-031-20862-1_41(562-573)Online publication date: 4-Nov-2022
https://doi.org/10.1007/978-3-031-20862-1_41
Dantas ARego APozo AKrawiec K(2021)Using deep Q-network for selection hyper-heuristicsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463187(1488-1492)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463187
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Memetic search for the quadratic assignment problem

Penguins Search Optimization Algorithm to Solve Quadratic Assignment Problem

A tabu search algorithm for the quadratic assignment problem