More Web Proxy on the site http://driver.im/

research-article

Using reinforcement learning for tuning genetic algorithms

Authors:

Marwan Abdelatti,

Manbir SodhiAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 1503 - 1507

https://doi.org/10.1145/3449726.3463203

Published: 08 July 2021 Publication History

Abstract

Genetic algorithms (GAs) are a subclass of evolutionary algorithms often used to solve difficult combinatorial or non-linear problems. However, most GAs have to be configured for a particular problem type, and even then, the performance depends on many hyperparameters and reproduction operators. In this paper, a reinforcement learning (RL) approach is designed to adaptively set parameters for a GA used for solving a Capacitated Vehicle Routing Problem (CVRP). An RL agent interacts with the GA environment by taking actions that affect the parameters governing its evolution, starting from a given initial point. The results obtained by this RL-GA procedure are then compared with those obtained by alternate static parameter values. For a set of benchmark problems, the solutions obtained by the RL-GA are better (up to 11% improvement) than those obtained for the set as compared to the alternate approach. Examination of the results shows that the RL-GA maintains great diversity in the population pool, especially as the iterations accrue. Computational runs are traced to show how the RL agent learns from population diversity and solution improvements over time, leading to near-optimal solutions.

References

[1]

Marwan F Abdelatti, Abdeltawab Hendawy, and Manbir S Sodhi. 2021. Optimizing a GPU-Accelerated Genetic Algorithm for the Vehicle Routing Problem. In 2021 Genetic and Evolutionary Computation Conference Companion (GECCO '21 Companion).

Digital Library

[2]

Marwan F Abdelatti and Manbir S Sodhi. 2020. An improved GPU-accelerated heuristic technique applied to the capacitated vehicle routing problem. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 663--671.

Digital Library

[3]

Aldeida Aleti and Irene Moser. 2016. A systematic literature review of adaptive parameter control methods for evolutionary algorithms. ACM Computing Surveys (CSUR) 49, 3 (2016), 1--35.

Digital Library

[4]

Tariq Alzyadat, Mohammad Yamin, and Girija Chetty. 2020. Genetic algorithms for the travelling salesman problem: a crossover comparison. International Journal of Information Technology 12, 1 (2020), 209--213.

[5]

Arif Arin, Ghaith Rabadi, and Resit Unal. 2011. Comparative studies on design of experiments for tuning parameters in a genetic algorithm for a scheduling problem. International Journal of Experimental Design and Process Optimisation 2, 2 (2011), 102--124.

[6]

Tapan P Bagchi and Kalyanmoy Deb. 1996. Calibration of GA parameters: the design of experiments approach. Computer Science and Informatics 26 (1996), 46--56.

[7]

Barrie M Baker and MA Ayechew. 2003. A genetic algorithm for the vehicle routing problem. Computers & Operations Research 30, 5 (2003), 787--800.

Digital Library

[8]

Richard J Bauer Jr, Richard J Bauer, et al. 1994. Genetic algorithms and investment strategies. Vol. 19. John Wiley & Sons.

[9]

A Benaini and A Berrajaa. 2018. Genetic algorithm for large dynamic vehicle routing problem on GPU. In 2018 4th International Conference on Logistics Operations Management (GOL). IEEE, 1--9.

[10]

Fei Chen, Yang Gao, Zhao-qian Chen, and Shi-fu Chen. 2005. SCGA: Controlling genetic algorithms with Sarsa (0). In International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06), Vol. 1. IEEE, 1177--1183.

[11]

IM Coelho, PLA Munhoz, LS Ochi, MJF Souza, C Bentes, and R Farias. 2016. An integrated CPU-GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups. International Journal of Production Research 54, 4 (2016), 945--962.

[12]

George B Dantzig and John H Ramser. 1959. The truck dispatching problem. Management science 6, 1 (1959), 80--91.

[13]

Abel Garcia-Najera and John A Bullinaria. 2009. Comparison of similarity measures for the multi-objective vehicle routing problem with time windows. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation. 579--586.

Digital Library

[14]

John J Grefenstette. 1986. Optimization of control parameters for genetic algorithms. IEEE Transactions on systems, man, and cybernetics 16, 1 (1986), 122--128.

Digital Library

[15]

Giorgos Karafotias, Mark Hoogendoorn, and AE Eiben. 2015. Evaluating reward definitions for parameter control. In European Conference on the Applications of Evolutionary Computation. Springer, 667--680.

[16]

Giorgos Karafotias, Mark Hoogendoorn, and Ágoston E Eiben. 2014. Parameter control in evolutionary algorithms: Trends and challenges. IEEE Transactions on Evolutionary Computation 19, 2 (2014), 167--187.

Digital Library

[17]

P Read Montague. 1999. Reinforcement learning: an introduction, by Sutton, RS and Barto, AG. Trends in cognitive sciences 3, 9 (1999), 360.

[18]

Douglas C Montgomery. 2017. Design and analysis of experiments. John wiley & sons.

[19]

Sibylle D Muller, Nicol N Schraudolph, and Petros D Koumoutsakos. 2002. Step size adaptation in evolution strategies using reinforcement learning. In Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600), Vol. 1. IEEE, 151--156.

[20]

James E Pettinger and Richard M Everson. 2002. Controlling genetic algorithms with reinforcement learning. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. 692--692.

Digital Library

[21]

Antón Rey, Manuel Prieto, José Ignacio Gómez, Christian Tenllado, and J Ignacio Hidalgo. 2018. A CPU-GPU parallel ant colony optimization solver for the vehicle routing problem. In International Conference on the Applications of Evolutionary Computation. Springer, 653--667.

[22]

Yoshitaka Sakurai, Kouhei Takada, Takashi Kawabe, and Setsuo Tsuruta. 2010. A method to control parameters of evolutionary algorithms by using reinforcement learning. In 2010 Sixth International Conference on Signal-Image Technology and Internet Based Systems. IEEE, 74--79.

Digital Library

[23]

Arash Nasrolahi Shirazi, Meghan Steinhaus, Matthew Agostinelli, and Manbir Sodhi. 2016. Fuzzy cell genetic algorithm approach for flexible flow-line scheduling model. In 2016 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 1--7.

[24]

Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. Machine learning 8, 3-4 (1992), 279--292.

[25]

Christopher John Cornish Hellaby Watkins. 1989. Learning from delayed rewards. (1989).

[26]

Mieczysław Wodecki, Wojciech Bożejko, Szymon Jagiełło, and Jarosław Pempera. 2015. Parallel Cost Function Determination on GPU for the Vehicle Routing Problem. In International Conference on Artificial Intelligence and Soft Computing. Springer, 778--788.

Cited By

Humeniuk DKhomh FAntoniol G(2024)Reinforcement Learning Informed Evolutionary Search for Autonomous Systems TestingACM Transactions on Software Engineering and Methodology10.1145/368046833:8(1-45)Online publication date: 27-Jul-2024
https://dl.acm.org/doi/10.1145/3680468
de Lacerda Mde Lima Neto FLudermir TKuchen H(2023)Out-of-the-box parameter control for evolutionary and swarm-based algorithms with distributed reinforcement learningSwarm Intelligence10.1007/s11721-022-00222-z17:3(173-217)Online publication date: 7-Jan-2023
https://doi.org/10.1007/s11721-022-00222-z
Abdelatti MSodhi MSendag R(2022)A Multi-GPU Parallel Genetic Algorithm For Large-Scale Vehicle Routing Problems2022 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC55821.2022.9926363(1-8)Online publication date: 19-Sep-2022
https://doi.org/10.1109/HPEC55821.2022.9926363

Index Terms

Using reinforcement learning for tuning genetic algorithms

Recommendations

Genetic Reinforcement Learning for Neurocontrol Problems
Special issue on genetic algorithms

Empirical tests indicate that at least one class of genetic algorithms yields good performance for neural network weight optimization in terms of learning rates and scalability. The successful application of these genetic algorithms to supervised ...
A weight-coded genetic algorithm for the capacitated arc routing problem
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

In this paper we present a weight coded genetic algorithm (GA) based approach to the capacitated arc routing problem (CARP). In comparison to metaheuristic algorithms, simple constructive heuristic algorithms often produce poor quality solutions to the ...
Tuning genetic algorithm parameters using design of experiments
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

Tuning evolutionary algorithms is a persistent challenge in the field of evolutionary computing. The efficiency of an evolutionary algorithm relates to the coding of the algorithm, the design of the evolutionary operators and the parameter settings for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2021

2047 pages

ISBN:9781450383516

DOI:10.1145/3449726

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
357
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)11

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Humeniuk DKhomh FAntoniol G(2024)Reinforcement Learning Informed Evolutionary Search for Autonomous Systems TestingACM Transactions on Software Engineering and Methodology10.1145/368046833:8(1-45)Online publication date: 27-Jul-2024
https://dl.acm.org/doi/10.1145/3680468
de Lacerda Mde Lima Neto FLudermir TKuchen H(2023)Out-of-the-box parameter control for evolutionary and swarm-based algorithms with distributed reinforcement learningSwarm Intelligence10.1007/s11721-022-00222-z17:3(173-217)Online publication date: 7-Jan-2023
https://doi.org/10.1007/s11721-022-00222-z
Abdelatti MSodhi MSendag R(2022)A Multi-GPU Parallel Genetic Algorithm For Large-Scale Vehicle Routing Problems2022 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC55821.2022.9926363(1-8)Online publication date: 19-Sep-2022
https://doi.org/10.1109/HPEC55821.2022.9926363

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents