Abstract
This chapter reveals the effect of combining mutation operators in Genetic Algorithm. Though mutation is a very effective genetic operator to escape the local optima, it has an adverse effect on computation time. It is quite a challenge to say how much probability is appropriate for mutation. The major contribution of this chapter is to design a mutation triggering method by combining three mutation operators (Swap, Insertion and 2-Opt) and applying adaptive probability. To decide which mutation can be activated at a given generation, a decision-making method named Mutation Triggering Method is proposed. To measure the performance of the proposed method, the classical traveling salesman problem was considered. The experimental result shows that the proposed method was able to find a better solution (travel cost) than the other approaches. For computation time, the proposed strategy did as well as other mutation strategies. In conclusion, the combination of several mutation operators can ensure the benefits of diversity as well as the benefits of faster convergence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Matai R, Singh SP, Mittal ML (2010) Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, InTech, Croatia
Shukla A, Pandey, HM, Mehrotra D (2015) Comparative review of selection techniques in genetic algorithm. In: 2015 international conference on futuristic trends on computational analysis and knowledge management (ABLAZE), pp 515–519
Larranaga P, Kuijpers CM, Murga RH, Inza I, Dizdarevic S (1999) Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artif Intell Rev 13(2):129–170
Sathya N, Muthukumaravel A (2015) A review of the optimization algorithms on traveling salesman problem. Indian J Sci Technol 8(1)
Tollis IG (2019) Chapter 10 the traveling salesman problem. https://www.csd.uoc.gr/~hy583/papers/ch11.pdf. Last accessed 10 Mar 2019
Maity S, Roy A, Maiti M (2019) A rough multi-objective genetic algorithm for uncertain constrained multi-objective solid travelling salesman problem. Granular Comput 4(1):125–142
Chang C (2015) A 2-opt with mutation operator to the traveling salesman problem. Int J Adv Eng Technol Comput Sci (IROSSS) 2(1):16–21
Alkafaween E, Hassanat A (2018) Improving TSP solutions using GA with a new hybrid mutation based on knowledge and randomness. ar**v preprint ar**v:1801.07233
Ahmed ZH (2013) A hybrid genetic algorithm for the bottleneck traveling salesman problem. ACM Trans Embed Comput Syst (TECS) 12(1):9
Xu J, Pei L, Zhu RZ (2018) Application of a genetic algorithm with random crossover and dynamic mutation on the travelling salesman problem. Procedia Computer Science 131:937–945
Singh DR, Singh MK, Singh T, Prasad R (2018) Genetic algorithm for solving multiple traveling salesmen problem using a new crossover and population generation. Computación y Sistemas 22(2)
Hussain A, Muhammad YS, Nauman Sajid M, Hussain I, Mohamd Shoukry A, Gani S (2017) Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Comput Intell Neurosci
Katayama K, Sakamoto H, Narihisa H (2000) The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem. Math Comput Model 31(10–12):197–203
Abdoun O, Abouchabaka J, Tajani C (2012) Analyzing the performance of mutation operators to solve the travelling salesman problem. ar**v preprint ar**v:1203.3099
Albayrak M, Allahverdi N (2011) Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Syst Appl 38(3):1313–1320
Deep K, Mebrahtu H (2011) Combined mutation operators of genetic algorithm for the travelling salesman problem. Int J Comb Optim Prob Inf 2(3):1–23
Toğan V, Daloğlu AT (2008) An improved genetic algorithm with initial population strategy and self-adaptive member grou**. Comput Struct 86(11–12):1204–1218
Maaranen H, Miettinen K, Mäkelä MM (2004) Quasi-random initial population for genetic algorithms. Comput Math Appl 47(12):1885–1895
Diaz-Gomez PA, Hougen DF (2007) Initial population for genetic algorithms: a metric approach. In Gem 43–49
Deng Y, Liu Y, Zhou D (2015) An improved genetic algorithm with initial population strategy for symmetric TSP. Math Prob Eng
Saini N (2017) Review of selection methods in genetic algorithms. Int J Eng Comput Sci 6(12):22261–22263
Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J Comput 3(4):376–384
Acknowledgements
This research work is partly supported by research grant RDU1703125 funded by Universiti Malaysia Pahang, http://www.ump.edu.my/. The authors would also like to thank Universiti Malaysia Pahang for publication support.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Qaiduzzaman, K.M. et al. (2020). A Mutation Triggering Method for Genetic Algorithm to Solve Traveling Salesman Problem. In: Mohd Razman, M., Mat Jizat, J., Mat Yahya, N., Myung, H., Zainal Abidin, A., Abdul Karim, M. (eds) Embracing Industry 4.0. Lecture Notes in Electrical Engineering, vol 678. Springer, Singapore. https://doi.org/10.1007/978-981-15-6025-5_15
Download citation
DOI: https://doi.org/10.1007/978-981-15-6025-5_15
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-6024-8
Online ISBN: 978-981-15-6025-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)