An Improved Cuckoo Search Algorithm With Stud Crossover for Chinese TSP Problem

Introduction

First formulated in 1930, in the theory of computational complexity, TSP is an NP-hard problem in combinatorial optimization, and it has an important topic in operations research and theoretical computer science. The TSP can be used in several applications, such as planning, logistics and the manufacture of microchips. In effect, the TSP is not only viewed as a mere problem; on the contrary, it is looked down upon as a class of problems. In other words, many other problems can be modeled and transformed into TSP. Therefore, the TSP study is of vital importance in computer science and optimization. However, in general, it has been found to be hard to find the satisfactory solutions within polynomial time by the traditional methods.

Inspired by the biological, physical and chemical phenomenon in nature, various metaheuristic methods (Wang and Tan, 2019) have been proposed and can be used to solve TSP, such as artificial bee colony (ABC) (Karaboga and Basturk, 2007; Li and Yin, 2012c; Wang and Yi, 2018), differential evolution (DE) (Li et al., 2019c; Li and Yin, 2012a; Mlakar et al., 2017; Storn and Price, 1997), cuckoo search (CS) (Gandomi et al., 2013; Li et al., 2019a; Li et al., 2019b; Li et al., 2020a; Li et al., 2020b; Li et al., 2013; Yang and Deb, 2009), particle swarm optimization (PSO) (Kennedy and Eberhart, 1995; Mirjalili and Lewis, 2013; Shieh et al., 2011; Sun et al., 2017; Wang et al., 2018a), monarch butterfly optimization (MBO) (Dhillon et al., 2020; Ghetas and Chan, 2018; Wang et al., 2019a), biogeography-based optimization (BBO) (Li and Yin, 2012b; Saremi et al., 2014; Simon, 2008; Wang et al., 2014a), harmony search (HS) (Geem et al., 2001; Gholizadeh and Barzegar, 2012; Yadav et al., 2012), earthworm optimization algorithm (EWA) (Wang et al., 2018b), elephant herding optimization (EHO) (Li et al., 2020c; Velliangiri and Pandey, 2020; Wang et al., 2016a), gravitational search algorithm (GSA) (Mirjalili and Lewis, 2014; Rashedi et al., 2009; Yin et al., 2011), firefly algorithm (FA) (Gandomi et al., 2011; Guo et al., 2013; Yang, 2010b), interior search algorithm (ISA) (Gandomi, 2014), ant colony optimization (ACO) (Dorigo et al., 1996; Kıran et al., 2012), moth search (MS) algorithm (Wang, 2018), bat algorithm (BA) (Fister et al., 2015; Yang, 2010a), grey wolf optimizer (GSO) (Mirjalili et al., 2014a), and krill herd (KH) (Gandomi and Alavi, 2012; Guo et al., 2014; Li et al., 2014; Wang et al., 2019b). Due to the excellent performance, these metaheuristic algorithms have been widely used in various applications, like scheduling (Gao et al., 2019; Li and Yin, 2013a), big data optimization (Yi et al., 2018; Yi et al., 2020), multi- objective/many-objective optimization (Gu and Wang, 2020; Zhang et al., 2020), path planning (Wang et al., 2012a; Wang et al., 2012b), test-sheet composition (Duan et al., 2012), classification (Wang et al., 2016c), unit commitment (Srikanth et al., 2018), node localization (Li et al., 2019d), inverse problem (Li et al., 2018), feature selection (Li and Yin, 2013b), parameter estimation (Li and Yin, 2014), global numerical optimization (Li et al., 2011), image segmentation (Zhang et al., 2011), and neural network training (Mirjalili et al., 2014b; Mirjalili et al., 2012).