Adaptive Reinforcement-Based Genetic Algorithm for Combinatorial Optimization

Document Type : Research Article

Authors

1 Department of Software Engineering, University of Isfahan, Isfahan, Iran.

2 Department of Foreign Languages, University of Isfahan, Isfahan, Iran.

Abstract

Combinatorial optimization is the procedure of optimizing an objective function over the discrete configuration space. A genetic algorithm (GA) has been applied successfully to solve various NP-complete combinatorial optimization problems. One of the most challenging problems in applying GA is selecting mutation operators and associated probabilities for each situation. GA uses just one type of mutation operator with a specified probability in the basic form. The mutation operator is often selected randomly in improved GAs that leverage several mutation operators. While an effective GA search occurs when the mutation type for each chromosome is selected according to mutant genes and the problem landscape. This paper proposes an adaptive genetic algorithm that uses Q-learning to learn the best mutation strategy for each chromosome. In the proposed method, the success history of the mutant in solving the problem is utilized for specifying the best mutation type. For evaluating adaptive genetic algorithm, we adopted the traveling salesman problem (TSP) as a well-known problem in the field of optimization. The results of the adaptive genetic algorithm on five datasets show that this algorithm performs better than single mutation GAs up to 14% for average cases. It is also indicated that the proposed algorithm converges faster than single mutation GAs.

Keywords

References

[1] J. H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992. [ bib ]
[2] S. Varadarajan and D. Whitley. A parallel ensemble genetic algorithm for the traveling salesman problem. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 636--643. ACM, 2021. [ bib | DOI ]
[3] C. H. Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science, 4(3):237--244, 1977. [ bib | DOI ]
[4] D. Wojtczak. On Strong NP-Completeness of Rational Problems. In International Computer Science Symposium in Russia, page 308–320. Springer, 2018. [ bib | DOI ]
[5] K. Yang, X. You, S. Liu, and H. Pan. A novel ant colony optimization based on game for traveling salesman problem. Applied Intelligence, 50(12):4529–4542, 2020. [ bib | DOI ]
[6] W. Gao. Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem. Soft Computing, 25(4):3263–3289, 2021. [ bib | DOI ]
[7] Y. Hu, Z. Zhang, Y. Yao, X. Huyan, X. Zhou, and W. S. Lee. A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs. Engineering Applications of Artificial Intelligence, 97:104061, 2021. [ bib | DOI ]
[8] M. Shahmanzari and D. Aksen. A Multi-Start Granular Skewed Variable Neighborhood Tabu Search for the Roaming Salesman Problem. Applied Soft Computing, 102:107024, 2021. [ bib | DOI ]
[9] V. Pandiri, A. Singh, and A. Rossi. Two hybrid metaheuristic approaches for the covering salesman problem. Neural Computing and Applications, 32(19):15643–15663, 2020. [ bib | DOI ]
[10] L. Meng, S. Yin, and X. Hu. A New Method Used for Traveling salesman problem Based on Discrete Artificial Bee Colony Algorithm. TELKOMNIKA (Telecommunication Computing Electronics and Control), 14(1):342--348, 2016. [ bib | DOI ]
[11] D. Wojtczak. A Bee Colony Optimization Algorithm for Traveling Salesman Problem. In 2008 Second Asia International Conference on Modelling & Simulation (AMS), pages 818--823. IEEE, 2008. [ bib | DOI ]
[12] Y. Cui, J. Zhong, F. Yang, S. Li, and P. Li. Multi-Subdomain Grouping-Based Particle Swarm Optimization for the Traveling Salesman Problem. IEEE Access, 8:227497 -- 227510, 2020. [ bib | DOI ]
[13] D. B. Fogel. Evolutionary artificial intelligence. University of California, 1992. [ bib | DOI ]
[14] C. Lee and X. Yao. Evolutionary programming using mutations based on the Levy probability distribution. IEEE Transactions on Evolutionary Computation, 8(1):1--13, 2004. [ bib | DOI ]
[15] M. Ji, H. Tang, and J. Guo. A single-point mutation evolutionary programming. Information Processing Letters, 90(6):293--299, 2004. [ bib | DOI ]
[16] S. Lee, H. Jun, and K. Sim. Performance improvement of evolution strategies using reinforcement learning. In FUZZ-IEEE'99. 1999 IEEE International Fuzzy Systems. Conference Proceedings (Cat. No. 99CH36315), pages 639--644. IEEE, 1999. [ bib | DOI ]
[17] H. Dong, J. He, H. Huang, and W. Hou. Evolutionary programming using a mixed mutation strategy. Information Sciences, 177(1):312--327, 2007. [ bib | DOI ]
[18] H. Zhang and J. Lu. Adaptive evolutionary programming based on reinforcement learning. Information Sciences, 178(4):971--984, 2008. [ bib | DOI ]
[19] H. H. Chieng and N. Wahid. A performance comparison of genetic algorithm’s mutation operators in n-cities open loop travelling salesman problem. In Recent Advances on Soft Computing and Data Mining, pages 89--97. Springer, 2014. [ bib ]
[20] E. Osaba, X. Yang, F. Diaz, P. Lopez-Garcia, and R. Carballedo. An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems. Engineering Applications of Artificial Intelligence, 48:59--71, 2016. [ bib | DOI ]
[21] G. Laporte. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2):231--247, 1992. [ bib | DOI ]
[22] P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13(2):129--170, 1999. [ bib | DOI ]
[23] L. V. Snyder and M. S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, 174(1):38--53, 2006. [ bib | DOI ]
[24] F. C. de Lima Junior, J. D. de Melo, and A. D. D. Neto. Using Q-learning Algorithm for Initialization of the GRASP Metaheuristic and Genetic Algorithm. In 2007 International Joint Conference on Neural Networks, pages 1243--1248. IEEE, 2007. [ bib | DOI ]
[25] J. Xu, L. Pei, and R. Zhu. Application of a Genetic Algorithm with Random Crossover and Dynamic Mutation on the Travelling Salesman Problem. Procedia Computer Science, 131(1):937--945, 2018. [ bib | DOI ]
[26] M. Albayrak and N. Allahverdi. Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms. Expert Systems with Applications, 38(3):1313--1320, 2011. [ bib | DOI ]
[27] S. S. Ray, S. Bandyopadhyay, and S. K. Pal. New operators of genetic algorithms for traveling salesman problem. In Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004, pages 497--500. IEEE, 2004. [ bib | DOI ]
[28] K. Deep and H. Mebrahtu. New Variations of Order Crossover for Travelling Salesman Problem. International Journal of Combinatorial Optimization Problems and Informatics, 2(1):2--13, 2011. [ bib | DOI ]
[29] Z. H. Ahmed. Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator. International Journal of Biometrics & Bioinformatics (IJBB), 3(6), 2010. [ bib | DOI ]
[30] S. M. Abdel-Moetty and A. O. Heakil. Enhanced Traveling Salesman Problem Solving using Genetic Algorithm Technique with modified Sequential Constructive Crossover Operator. International Journal of Computer Science and Network Security (IJCSNS), 12(6), 2012. [ bib | DOI ]
[31] M. M. Alipour, S. N. Razavi, M. R. Feizi Derakhshi, and M. A. Balafar. A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem. Neural Computing and Applications, 30(9):2935--2951, 2018. [ bib | DOI ]
[32] P. Victer Paul, C. Ganeshkumar, P. Dhavachelvan, and R. Baskaran. A novel ODV crossover operator-based genetic algorithms for traveling salesman problem. Soft Computing, 24(17):12855--12885, 2020. [ bib | DOI ]
[33] O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, and F. Neumann. Local search and the traveling salesman problem: A feature-based characterization of problem hardness. In International Conference on Learning and Intelligent Optimization, pages 115--129. Springer, 2012. [ bib | DOI ]
[34] Z. A. Ali, S. A. Rasheed, and N. N. Ali. An enhanced hybrid genetic algorithm for solving traveling salesman problem. Indonesia Journal of Electrical Engineering and Computuper Science, 18(2):1035--1039, 2020. [ bib | DOI ]
[35] F. Liu and G. Zeng. Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Systems with Applications, 36(3):6995--7001, 2009. [ bib | DOI ]
[36] K. M. Qaiduzzaman, S. Khatun, M. Afsa, S. Sobhan, M. Elias Hossain, S. M. Shaharum, and M. Rahman. A mutation triggering method for genetic algorithm to solve traveling salesman problem. In Embracing Industry 4.0, pages 159--170. Springer, 2020. [ bib ]
[37] G. Reinhelt. TSPLIB: a library of sample instances for the TSP (and related problems) from various sources and of various types. URL: http://comopt. ifi. uniheidelberg. de/software/TSPLIB95, 2014. [ bib | DOI ]
[38] E. Osaba, R. Carballedo, F. Diaz, E. Onieva, I. de la Iglesia, and A. Perallos. Crossover versus Mutation: A Comparative Analysis of the Evolutionary Strategy of Genetic Algorithms Applied to Combinatorial Optimization Problems. Scientific World Journal, 2014, 2014. [ bib | DOI ]
[39] B. Koohestani. A crossover operator for improving the efficiency of permutation-based genetic algorithms. Expert Systems with Applications, 151:113381, 2020. [ bib | DOI ]
Journal of Computing and Security
Volume 9, Issue 1 - Serial Number 1
January 2022
Pages 71-84

Files

History

  • Receive Date: 01 December 2021
  • Revise Date: 12 June 2022
  • Accept Date: 03 July 2022

Share

How to cite

Statistics