# A Hybrid Cellular Genetic Algorithm for the Traveling Salesman Problem

Authors: Yanlan Deng; Juxia Xiong; Qiuhong Wang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The traveling salesman problem (TSP), a typical non-deterministic polynomial (NP) hard problem, has been used in many engineering applications. Genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. However, it has some issues for solving TSP, including quickly falling into the local optimum and an insufficient optimization precision. To address TSP effectively, this paper proposes a hybrid Cellular Genetic Algorithm with Simulated Annealing (SA) Algorithm (SCGA). Firstly, SCGA is an improved Genetic Algorithm (GA) based on the Cellular Automata (CA). The selection operation in SCGA is performed according to the state of the cell. Secondly, SCGA, combined with SA, introduces an elitist strategy to improve the speed of the convergence. Finally, the proposed algorithm is tested against 13 standard benchmark instances from the TSPLIB to confirm the performance of the three cellular automata rules. The experimental results show that, in most instances, the results obtained by SCGA using rule 2 are better and more stable than the results of using rule 1 and rule 3. At the same time, we compared the experimental results with GA, SA, and Cellular Genetic Algorithm (CGA) to verify the performance of SCGA. The comparison results show that the distance obtained by the proposed algorithm is shortened by a mean of 7% compared with the other three algorithms, which is closer to the theoretical optimal value and has good robustness.


---

## Body

## 1. Introduction

Traveling salesman problem (TSP) is one of the most common combinatorial optimization problems, and it has been widely used in this field. At the same time, many problems in the field of combinatorial optimization can be formulated as special TSP instances [1]. For example, resource optimization in the shortest path and shop scheduling problems are the most frequent TSP applications [2–4]. In Word Sense Disambiguation (WSD), problems can also be solved by describing WSD as a TSP variant [5]. In the global positioning system (GPS), TSP can also be used as the basis for finding route problems [6]. It can be seen that the application of TSP is extensive; however, TSP is an NP-hart problem, and the number of feasible solutions increases significantly with the increase of nodes, which brings great difficulty to the solution [7]. If the exact algorithm is used to solve TSP, it will take a long time, so the feasibility of using the exact algorithm to solve TSP is very low. On the other hand, although using an approximate solution to solve TSP problems cannot guarantee an optimal solution, it can reach a satisfactory solution in a very short time [8]. Thus, with the development of heuristic algorithms [9–14], many experts and scholars have begun to apply heuristic algorithms to solve TSP, which provides new ideas for solving TSP [15–21].Genetic algorithm (GA) is an evolutionary algorithm proposed by Professor John H. Holland of the University of Michigan and his students from the late 1960s to the early 1970s [22]. GA uses biological evolution and genetic principles to imitate the generation and evolution process of all life and intelligence by drawing on the basis of biology. It is a bionic algorithm in a macroscopic sense and is applied to many optimization fields [23–26]. The coding method commonly used in genetic algorithms is binary coding, but most search space sequences do not correspond to feasible travel when binary coding is used. We can use ordinal coding and a partially mapped crossover (PMX) as the cross operator so that all the solutions obtained will be feasible solutions [27]. However, there are some disadvantages in using traditional GA to solve TSP, such as poor searchability and low convergence accuracy. On this basis, the improved GA also developed vigorously. Liu et al. [28] proposed an improved GA with decision cut-off algebra to solve TSP, which improves the convergence of the GA. Besides, Yu et al. [29] proposed an improved GA for solving TSP by a greedy algorithm, which used the greedy algorithm to generate the initial population and reduce the number of iterations. At the same time, the hybrid algorithm has also received the attention of many experts and scholars. For instance, Wang et al. [30] combined GA and SA, and proposed an improved simulated annealing genetic algorithm for solving TSP, improving the local search capabilities. Also, Zhang et al. [31] combined the GA and Firefly algorithm proposing a Firefly GA algorithm to solve TSP and prevent the algorithm from falling into local optimality. Moreover, Tao et al. [32] combined the GA and Ant Colony (AC) algorithm proposing a dynamic Ant Colony genetic algorithm to solve TSP, which improved the reinsertion of offspring to improve stability.Cellular genetic algorithm (CGA) is a hybrid of cellular automata and genetic algorithms. It has been applied to various decision-making problems [33]. However, the application of the CGA to TSP is very limited at present. To study the application of the CGA in TSP and improve GA’s optimization performance, this paper proposes a hybrid Cellular Genetic Algorithm with SA (SCGA). We improve TSP optimization performance by combining the cellular genetic algorithm and the simulated annealing algorithm. The contributions of this paper are as follows:(i)
The paper successfully applies the cellular genetic algorithm to solve TSP and proposed a hybrid Cellular Genetic Algorithm combined with a simulated annealing algorithm. The experimental results show that the hybrid cellular genetic algorithm’s optimization performance is better than GA, SA, and CGA.(ii)
The optimization performance of the three cellular automata rules in the SCGA is examined through experiments and concluded that cellular automata rules with a moderate total number of living cells are beneficial to algorithm optimization.The rest of this article is arranged as follows. Section2 is a brief introduction to the preliminary knowledge that will be used, including the traveling salesman problem model, the basic content of genetic algorithm (GA), simulated annealing (SA) algorithm, and cellular automata (CA). In Section 3, the proposed algorithm and its steps are explained in detail. Section 4 reveals the simulation results and discussions. Section 5 summarizes the full text and proposes the next step.


## 2. Preliminaries

### 2.1. Traveling Salesman Problem (TSP)

TSP is a commonly used test benchmark for optimization methods, which can be simply described as follows.Given the coordinates ofn cities, starting from any city, passing through the remaining cities only once, and finally returning to the starting city, there are n! routes. We need to choose the shortest route from these n! routes. In the symmetric Euclidean TSP, city A’'s distance to city B is equal to the distance from city B to city A. According to the description of TSP, the following mathematical model can be established [29]:(1)R=N1,N2,…,Nn,minfR,(2)fR=∑i=1n−1dNi,Ni+1+dNn,N1,(3)dNi,Ni+1=dNi+1,Ni.We use the city number as the city mark. The solution1,2,3,…,n represents a trip starting from city 1, along city 2, city 3, until city n, and finally back to city 1. N1,N2,…,Nn is a permutation of 1,2,3,…,n, and dNi,Ni+1 represents the Euclidean distance between city Ni and city Ni+1.


### 2.2. Genetic Algorithm (GA)

Genetic algorithm is one of the universal algorithms in the optimization field. The essence of GA is an efficient, parallel, and global search method. It can automatically acquire and accumulate search knowledge during the search process and adaptively control the search process to find the optimal solution [27, 34]. The traditional GA is mainly composed of population and population size, coding method, selection strategy, genetic operator, and stopping criterion [35–37]. The population is composed of chromosomes or individuals, and each individual corresponds to a feasible solution to the problem. The population size refers to the number of individuals in the population, which is a subset of the problem’s feasible region. Generally speaking, the larger the number of individuals in the population is, the more feasible solutions it contains, and the better the optimal solution will be. However, as the number of individuals in the population increases, the algorithm’s computation time will also increase, which affects the performance of the algorithm. Therefore, it is necessary to select an appropriate population size. The coding method is also called the gene expression method. The chromosomes in the population are composed of genes. Correctly coding the chromosomes is the basic and important work of GA. According to the mathematical model of TSP, we can choose the ordinal encoding as the encoding method, and each chromosome is composed of a nonrepetitive ordinal number 1,2,3,…,n. The selection strategy is the process of selecting parents from the current population. We can use the commonly used roulette as the selection operator. The pseudocode of the roulette operator is shown in Algorithm1, and the steps of the roulette operator are as follows:(i)
Step 1. Calculate the number NP of individuals to be selected according to the selection probability Pc(ii)
Step 2. Calculate the fitness value of each individual according to the following equation:(4)fk=1∑i=1n−1dNi,Ni+1+dNn,N1.(iii)
Step 3. Calculate the cumulative probability of an individual Pk:(5)Pk=∑i=1kfi∑j=1nfj.(iv)
Step 4. Randomly generate the number rand in [0, 1]; if Pi-1 < r and < Pi, select the ith individual. Repeat NP times to get the selected NP individualsAlgorithm 1:The pseudocode of the roulette operator.
Roulette operatorBeginInput: population, selection probabilityPcCalculate NP,fk, Pk,k=1,2,…,nfori = 1 to NPif rand <Pi and rand > Pi-1select theith individualEnd ifEnd forOutput: the selected individual.EndGenetic operators mainly include crossover and mutation, which is the most important part of the GA. We choose partially mapped crossover (PMX) and reverse order mutation to hide the infeasible solutions in the execution process. Reverse order mutation refers to reversing the order of the numbers between two tangent points. Therefore, the numbers will not change, and there will be no duplicate numbers. Figure1 is a schematic diagram of PMX, and the steps of PMX are as follows:Step 1. Randomly generate two cut points.Step 2. Exchange the part between two individual tangent points.Step 3. Determine the mapping relationship.Step 4. Restore the legitimacy of the individual according to the mapping relationship.Figure 1
Schematic diagram of PMX.The stopping criterion generally uses the maximum number of iterations, and the algorithm stops when the maximum number of iterations is reached. Algorithm2 shows the pseudocode of the GA for solving TSP.Algorithm 2:The pseudocode of genetic algorithm (GA) for solving TSP.
Genetic algorithm (GA) for solving TSPBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. selection probability Ps, crossover probability Pc, mutation probability Pm, the maximum number of iterations (Maxiter)Initialization: using ordinal coding to generate the initial population, number of iterationk = 1whilek ≤ MaxiterSelectionCrossoverMutationNew populationSave the optimal result in the iterationk = k + 1End whileOutput: the optimal result:R=N1,N2,…,Nn,fREnd


### 2.3. Simulated Annealing (SA) Algorithm

In 1953, Metropolis et al. [38] first proposed the simulated annealing algorithm (SA). In 1983, Kirkpatrick et al. [39] successfully used SA in combinatorial optimization problems, especially large-scale problems. SA is a general random search algorithm, which is an extension of the local search algorithm. It is derived from the simulation of the annealing process in thermodynamics [40]. Because modern SA can effectively solve NP complexity problems, avoid falling into local optima, and overcome initial value dependence, it has been widely used in engineering, production scheduling, control engineering, machine learning, and other fields [41–43]. SA mainly includes state expression, neighborhood definition, thermal equilibrium, and cooling control [39]. State expression is to describe the system’s energy state in a mathematical form, and one state corresponds to one solution of the problem. State expression is the main work of SA, which directly determines the neighborhood structure and size. A reasonable state expression method can reduce computational complexity and improve algorithm performance. Consistent with genetic algorithms, nonrepeated ordinal numbers are used to represent solutions. The neighborhood definition’s starting point is to ensure that the neighborhood’s solutions are distributed as much as possible in the entire solution space. The nature of the problem usually determines the definition of the neighborhood. Consistent with the mutation operator in GA, we use reverse order to form neighbor solutions. To replace the neighbor solution with the original solution is determined by the Metropolis criterion. Algorithm 3 shows the pseudocode of the Metropolis criterion. The thermal equilibrium is equivalent to the isothermal process in the physical annealing, which is the internal cycle process in SA. To ensure the equilibrium state, the number of internal cycles should be large enough, leading to an increase in computation time. The number of internal cycles is the length of the Markov chain L. Cooling control is the outer cycle process of SA. Unlike GA, SA uses a temperature drop to control the iteration of the algorithm. The algorithm stops when the temperature drops to the end temperature. The pseudocode of SA for solving TSP is shown in Algorithm 4, and the steps of SA for solving TSP are as follows:Step 1. Set initial parameters (including initial temperature, Markov chain length, cooling rate, and termination temperature.), and randomly generate an initial solution.Step 2. Using the reverse order method to generate a neighbor solution.Step 3. Move the neighbor according to Metropolis criterion.Step 4. Judge whether the thermal equilibrium is reached; if the thermal equilibrium is not reached, go to Step 2.Step 5. Lower the temperature. If the temperature reaches the end temperature, the algorithm will stop; otherwise, go to Step 2.Algorithm 3:The pseudocode of the Metropolis criterion.
Metropolis criterionBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. Solution S1 and neighbor solution S2, current temperature TCalculatefS1 and fS2 by equation (2)Δf=fS2−fS1, P=exp−Δf/TifΔf<0 or P > randS1=S2End ifOutput:S1EndAlgorithm 4:The pseudocode of simulated annealing (SA) algorithm for solving TSP.
Simulated annealing (SA) algorithm for solving TSPBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. Initial temperature T0, Markov chain length L, cooling rate R, and termination temperature TtInitialization: using ordinal coding to generate the initial solutionS, current temperature T = T0whileT ≤ Ttfori = 1 to LGenerate a neighbor solutionS1Metropolis criterionEnd forSave the optimal solution in the iterationT = T∗REnd whileOutput:R=N1,N2,…,Nn,fREnd


### 2.4. Cellular Automata (CA)

In 1948, Stanislaw M.Ulam and von Neumann proposed cellular automata (CA). CA is a simplified mathematical model for describing complex phenomena in nature [44]. CA reflects the law of self-replication of life through relatively simple rules. The realization of self-replication of life on the computer has brought a new revolution in computing and simulation fields. As a discrete model of a complex system, CA is an important experimental method for studying dynamic interaction and spatiotemporal evolution [45–47]. CA is composed of four parts: cell, cellular space, cellular neighbor’ type, and cellular automata rule [44].The choice of cellular neighbor’s type and cellular automata rule is a crucial part that affects CA’s performance. Here, the Moore neighborhood is utilized. The Moore neighborhood consists of a central cell (the one which is to be updated) and its eight geographical neighbors, north, west, south, east, north-east, north-west, south-west, and south-east, that is a total of nine cells [48]. Each central cell can be alive (st=1) or dead (st=0). If permutations and combinations are used to describe neighbors’ states, many unnecessary duplicate data will be generated. Therefore, there is no need to enumerate the states and positions of specific neighbors; just calculate the total number of cellular states in neighbors [49]. The sum of neighbors’ states is K; so, K can be any value between 0 and 8. Cellular automata rules [50] are as follows:(6)Rule1:st=1,st+1=1,K=2,3,0,K≠2,3,st=0,st+1=1,K=3,0,K≠3,Rule2:st=1,st+1=1,K=1,2,3,4,0,K≠1,2,3,4,st=0,st+1=1,K=4,5,6,7,0,K≠4,5,6,7,Rule3:st=1,st+1=1,K=2,4,6,8,0,K≠2,4,6,8,st=0,st+1=1,K=1,3,5,7,0,K≠1,3,5,7.Using different cellular automata rules, the total number of living cells in the cellular space is different, and the optimization performance will also be affected.


## 2.1. Traveling Salesman Problem (TSP)

TSP is a commonly used test benchmark for optimization methods, which can be simply described as follows.Given the coordinates ofn cities, starting from any city, passing through the remaining cities only once, and finally returning to the starting city, there are n! routes. We need to choose the shortest route from these n! routes. In the symmetric Euclidean TSP, city A’'s distance to city B is equal to the distance from city B to city A. According to the description of TSP, the following mathematical model can be established [29]:(1)R=N1,N2,…,Nn,minfR,(2)fR=∑i=1n−1dNi,Ni+1+dNn,N1,(3)dNi,Ni+1=dNi+1,Ni.We use the city number as the city mark. The solution1,2,3,…,n represents a trip starting from city 1, along city 2, city 3, until city n, and finally back to city 1. N1,N2,…,Nn is a permutation of 1,2,3,…,n, and dNi,Ni+1 represents the Euclidean distance between city Ni and city Ni+1.


## 2.2. Genetic Algorithm (GA)

Genetic algorithm is one of the universal algorithms in the optimization field. The essence of GA is an efficient, parallel, and global search method. It can automatically acquire and accumulate search knowledge during the search process and adaptively control the search process to find the optimal solution [27, 34]. The traditional GA is mainly composed of population and population size, coding method, selection strategy, genetic operator, and stopping criterion [35–37]. The population is composed of chromosomes or individuals, and each individual corresponds to a feasible solution to the problem. The population size refers to the number of individuals in the population, which is a subset of the problem’s feasible region. Generally speaking, the larger the number of individuals in the population is, the more feasible solutions it contains, and the better the optimal solution will be. However, as the number of individuals in the population increases, the algorithm’s computation time will also increase, which affects the performance of the algorithm. Therefore, it is necessary to select an appropriate population size. The coding method is also called the gene expression method. The chromosomes in the population are composed of genes. Correctly coding the chromosomes is the basic and important work of GA. According to the mathematical model of TSP, we can choose the ordinal encoding as the encoding method, and each chromosome is composed of a nonrepetitive ordinal number 1,2,3,…,n. The selection strategy is the process of selecting parents from the current population. We can use the commonly used roulette as the selection operator. The pseudocode of the roulette operator is shown in Algorithm1, and the steps of the roulette operator are as follows:(i)
Step 1. Calculate the number NP of individuals to be selected according to the selection probability Pc(ii)
Step 2. Calculate the fitness value of each individual according to the following equation:(4)fk=1∑i=1n−1dNi,Ni+1+dNn,N1.(iii)
Step 3. Calculate the cumulative probability of an individual Pk:(5)Pk=∑i=1kfi∑j=1nfj.(iv)
Step 4. Randomly generate the number rand in [0, 1]; if Pi-1 < r and < Pi, select the ith individual. Repeat NP times to get the selected NP individualsAlgorithm 1:The pseudocode of the roulette operator.
Roulette operatorBeginInput: population, selection probabilityPcCalculate NP,fk, Pk,k=1,2,…,nfori = 1 to NPif rand <Pi and rand > Pi-1select theith individualEnd ifEnd forOutput: the selected individual.EndGenetic operators mainly include crossover and mutation, which is the most important part of the GA. We choose partially mapped crossover (PMX) and reverse order mutation to hide the infeasible solutions in the execution process. Reverse order mutation refers to reversing the order of the numbers between two tangent points. Therefore, the numbers will not change, and there will be no duplicate numbers. Figure1 is a schematic diagram of PMX, and the steps of PMX are as follows:Step 1. Randomly generate two cut points.Step 2. Exchange the part between two individual tangent points.Step 3. Determine the mapping relationship.Step 4. Restore the legitimacy of the individual according to the mapping relationship.Figure 1
Schematic diagram of PMX.The stopping criterion generally uses the maximum number of iterations, and the algorithm stops when the maximum number of iterations is reached. Algorithm2 shows the pseudocode of the GA for solving TSP.Algorithm 2:The pseudocode of genetic algorithm (GA) for solving TSP.
Genetic algorithm (GA) for solving TSPBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. selection probability Ps, crossover probability Pc, mutation probability Pm, the maximum number of iterations (Maxiter)Initialization: using ordinal coding to generate the initial population, number of iterationk = 1whilek ≤ MaxiterSelectionCrossoverMutationNew populationSave the optimal result in the iterationk = k + 1End whileOutput: the optimal result:R=N1,N2,…,Nn,fREnd


## 2.3. Simulated Annealing (SA) Algorithm

In 1953, Metropolis et al. [38] first proposed the simulated annealing algorithm (SA). In 1983, Kirkpatrick et al. [39] successfully used SA in combinatorial optimization problems, especially large-scale problems. SA is a general random search algorithm, which is an extension of the local search algorithm. It is derived from the simulation of the annealing process in thermodynamics [40]. Because modern SA can effectively solve NP complexity problems, avoid falling into local optima, and overcome initial value dependence, it has been widely used in engineering, production scheduling, control engineering, machine learning, and other fields [41–43]. SA mainly includes state expression, neighborhood definition, thermal equilibrium, and cooling control [39]. State expression is to describe the system’s energy state in a mathematical form, and one state corresponds to one solution of the problem. State expression is the main work of SA, which directly determines the neighborhood structure and size. A reasonable state expression method can reduce computational complexity and improve algorithm performance. Consistent with genetic algorithms, nonrepeated ordinal numbers are used to represent solutions. The neighborhood definition’s starting point is to ensure that the neighborhood’s solutions are distributed as much as possible in the entire solution space. The nature of the problem usually determines the definition of the neighborhood. Consistent with the mutation operator in GA, we use reverse order to form neighbor solutions. To replace the neighbor solution with the original solution is determined by the Metropolis criterion. Algorithm 3 shows the pseudocode of the Metropolis criterion. The thermal equilibrium is equivalent to the isothermal process in the physical annealing, which is the internal cycle process in SA. To ensure the equilibrium state, the number of internal cycles should be large enough, leading to an increase in computation time. The number of internal cycles is the length of the Markov chain L. Cooling control is the outer cycle process of SA. Unlike GA, SA uses a temperature drop to control the iteration of the algorithm. The algorithm stops when the temperature drops to the end temperature. The pseudocode of SA for solving TSP is shown in Algorithm 4, and the steps of SA for solving TSP are as follows:Step 1. Set initial parameters (including initial temperature, Markov chain length, cooling rate, and termination temperature.), and randomly generate an initial solution.Step 2. Using the reverse order method to generate a neighbor solution.Step 3. Move the neighbor according to Metropolis criterion.Step 4. Judge whether the thermal equilibrium is reached; if the thermal equilibrium is not reached, go to Step 2.Step 5. Lower the temperature. If the temperature reaches the end temperature, the algorithm will stop; otherwise, go to Step 2.Algorithm 3:The pseudocode of the Metropolis criterion.
Metropolis criterionBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. Solution S1 and neighbor solution S2, current temperature TCalculatefS1 and fS2 by equation (2)Δf=fS2−fS1, P=exp−Δf/TifΔf<0 or P > randS1=S2End ifOutput:S1EndAlgorithm 4:The pseudocode of simulated annealing (SA) algorithm for solving TSP.
Simulated annealing (SA) algorithm for solving TSPBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. Initial temperature T0, Markov chain length L, cooling rate R, and termination temperature TtInitialization: using ordinal coding to generate the initial solutionS, current temperature T = T0whileT ≤ Ttfori = 1 to LGenerate a neighbor solutionS1Metropolis criterionEnd forSave the optimal solution in the iterationT = T∗REnd whileOutput:R=N1,N2,…,Nn,fREnd


## 2.4. Cellular Automata (CA)

In 1948, Stanislaw M.Ulam and von Neumann proposed cellular automata (CA). CA is a simplified mathematical model for describing complex phenomena in nature [44]. CA reflects the law of self-replication of life through relatively simple rules. The realization of self-replication of life on the computer has brought a new revolution in computing and simulation fields. As a discrete model of a complex system, CA is an important experimental method for studying dynamic interaction and spatiotemporal evolution [45–47]. CA is composed of four parts: cell, cellular space, cellular neighbor’ type, and cellular automata rule [44].The choice of cellular neighbor’s type and cellular automata rule is a crucial part that affects CA’s performance. Here, the Moore neighborhood is utilized. The Moore neighborhood consists of a central cell (the one which is to be updated) and its eight geographical neighbors, north, west, south, east, north-east, north-west, south-west, and south-east, that is a total of nine cells [48]. Each central cell can be alive (st=1) or dead (st=0). If permutations and combinations are used to describe neighbors’ states, many unnecessary duplicate data will be generated. Therefore, there is no need to enumerate the states and positions of specific neighbors; just calculate the total number of cellular states in neighbors [49]. The sum of neighbors’ states is K; so, K can be any value between 0 and 8. Cellular automata rules [50] are as follows:(6)Rule1:st=1,st+1=1,K=2,3,0,K≠2,3,st=0,st+1=1,K=3,0,K≠3,Rule2:st=1,st+1=1,K=1,2,3,4,0,K≠1,2,3,4,st=0,st+1=1,K=4,5,6,7,0,K≠4,5,6,7,Rule3:st=1,st+1=1,K=2,4,6,8,0,K≠2,4,6,8,st=0,st+1=1,K=1,3,5,7,0,K≠1,3,5,7.Using different cellular automata rules, the total number of living cells in the cellular space is different, and the optimization performance will also be affected.


## 3. A Hybrid Cellular Genetic Algorithm (SCGA)

This section describes the main contents of SCGA in detail, including the dynamic evolution of cellular space, genetic operations, elitist strategy, and the steps of SCGA.


### 3.1. Dynamic Evolution of Cellular Space

A state matrix in the cellular space is composed of each cell state in the cellular space. In the iteration, each cell in the cellular space is used as the central cell, and the state of the central cell is updated using the cellular automata rules to form a new state matrix. The pseudocode of the dynamic evolution of the cellular space is shown in Algorithm5. Given a 10 × 10 cellular space arbitrarily, each cell state is randomly generated to form an initial state matrix (an n-th order square matrix N composed of 0 and 1), as shown in Figure 2. The cellular automata rule determines each cell’s updated state, for example, if the cell in the third row and the third column is the central cell. The central cell state is 1, and there are four cells in the neighboring cells with states equal to 1. According to rule 1, the central cell update state will be 0, while the central cell updated state will be 1, according to rule 2 or rule 3. It can be seen that the updated cellular state changes according to different cellular automata rules. Because dead cells do not perform genetic operations, we only consider the number of living cells. Figure 3 shows that when different cellular automata rules are selected, the total number of living cells will differ. Therefore, if rule 1 is chosen, the total number of living cells will eventually remain at about 10%, while if rule 2 is selected, the total number of living cells will eventually remain at about 38%. On the other hand, if rule 3 is selected, the total number of living cells will eventually remain in a range of 50%. The total number of living cells in the cellular space will affect the optimization performance of the algorithm. Aiming at the TSP, we will compare the optimal solutions obtained by applying these three rules in the hybrid cellular genetic algorithm through experiments.Algorithm 5:The pseudocode of the dynamic evolution of the cellular space.
Dynamic evolution of cellular spaceBeginInput: An n-th order square matrixN composed of 0 and 1, three cellular automata rulesfori = 1 to n2Calculate the sumK of 8 neighbors’ statesifNi=1ifK = 2 or K = 3 # rule 1ifK = 1 or K = 2 or K = 3 or K = 4 # rule 2ifK = 2 or K = 4 or K = 6 or K = 8 # rule 3Ni=1elseNi=0End ifelseifK = 3 # rule 1ifK = 4 or K = 5 or K = 6 or K = 7 # rule 2ifK = 1 or K = 3 or K = 5 or K = 7 # rule 3Ni=1elseNi=0End ifEnd ifEnd forOutput: New square matrixNEndFigure 2
State matrix.Figure 3
The change of the total number of living cells.


### 3.2. Genetic Operations

SCGA puts the individual as a cell into the cellular space, selects the living cell, and forms the parents with the best cell among neighbors. Then, the parents perform crossover and mutation operations. If the cellular state is dead, no crossover and mutation operations are performed. Algorithm6 shows the pseudocode for the genetic operations.Algorithm 6:The pseudocode for genetic operations.
Genetic operationsBeginInput: An n-th order square matrixN composed of 0 and 1, cellular space,city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,ynCalculate the total distancefiR of each individual in the cellular space by Equation (2)fori = 1 to n2ifNi=1Select the ith individual and the individual with smallest total distance among the 8 neighborsCrossoverMutationNew the ith individualEnd ifEnd forOutput: New cellular spaceEndAssuming that the number of cities is 10 and the number of populations is 100, the corresponding cellular space is a 2D grid of 10 × 10 units. The algorithm works as follows:(i)
Randomly generate 100 individuals to form the initial population and associate the individuals with the cells one-to-one(ii)
If Figure2 is used as the state matrix of the cellular space at the initial moment, the individual is represented by the letter. The number after the letter represents the state of the cell, as shown in Figure 4(iii)
Take the individual V in the third row and second column as the central cell(iv)
In the current iteration, the cellular state is living (state 1)(v)
Tables1 and 2 show that the individual with the shortest distance among neighbors is AE, so choose AE and V and perform crossover and mutation operations as parents:Firstly, the parents can get the offspring individuals O1 and O2 after PMX.Perform the reverse mutation on O1 and O2 to get the individuals O3 and O4, as shown in Table3.The new individuals obtained after genetic manipulation are O3 and O4; the best progeny is O3, and O3 is better than V; so O3 replaces V to complete the genetic operation.Figure 4
Cell and state matrix.Table 1
Central cell and neighbors.
CellRouteDistanceCellRouteDistanceCellRouteDistanceK3 4 6 9 7 1 8 10 2 5316.0711U6 2 4 8 9 3 1 5 7 10344.9062AE7 8 1 9 3 5 10 4 2 6244.1511L8 9 4 6 10 5 2 7 1 3262.5791V4 3 2 7 10 6 8 1 5 9290.6597AF2 3 8 4 6 10 9 7 5 1267.6944M4 8 12 7 3 9 10 6 5260.2487W2 4 8 5 7 3 6 1 9 10299.5755AG1 10 4 8 6 5 7 2 9 3288.2223Table 2
City coordinates.
Number12345678910x37495220402117315251y52496426304763623321Table 3
Individuals in crossover and mutation process.
CellRouteDistanceCellRouteDistanceV4 3 2 7 10 6 8 1 5 9290.6597O29 3 2 7 10 6 8 4 1 5296.2696AE7 8 1 9 3 5 10 4 2 6244.1511O31 8 4 9 3 5 10 2 6 7258.7903O14 8 1 9 3 5 10 2 6 7264.5371O49 4 8 6 10 7 2 3 1 5286.1712


### 3.3. Elitist Strategy

The living central cell and the best neighbor get offspring after crossover and mutation operations. If the distance between the optimal progeny and central cell is not compared, and the optimal progeny directly replaces the central cell, the inferior solution may enter the population. If the central cell’s distance is better than the optimal progeny distance, and the central cell is not replaced, it may fall into a local optimum. In order to solve the above problems, SCGA sets an elite individual retention strategy after the crossover and mutation operations. When the optimal progeny’s obtained distance after the crossover and mutation operation is less than the distance of the center cell, the center cell is directly replaced with the optimal progeny. Otherwise, after performing the simulated annealing operation on the optimal progeny, new offspring are obtained, and the central cell is replaced with the new offspring. Algorithm7 shows the pseudocode of the elitist strategy. Through the elitist strategy, the living central cell can be optimized as much as possible to avoid falling into the local optimum.Algorithm 7:The pseudocode of elitist strategy.
Elitist strategyBeginInput: Central cellS1 and new individual S2city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,ynCalculatefS1 and fS2 by Equation (2)iffS1>fS2S1=S2elseOptimizeS2 using simulated annealing algorithmS1=S2End ifOutput:S1End


### 3.4. Process of SCGA

SCGA, as explained before, has three main contents: the dynamic evolution of cellular space, genetic operations, and elitist strategy. In this section, we will introduce the main steps of applying SCGA to solve TSP. Algorithm8 shows the pseudocode of the proposed hybrid Cellular Genetic Algorithm with SA (SCGA) and its required steps for the TSP solution.(i)
Step 1. Population initialization:(a)
Initialize the following parameters:(i)
Crossover probabilityPc,(ii)
Mutation probabilityPm,(iii)
Cooling rater,(iv)
Initial temperatureT0,(v)
Population size Num,(vi)
The size of cellular space Num. C,(vii)
Maximum iteration times Maxiter,(viii)
Markov chain lengthL,(ix)
Termination temperatureTt;(b)
Randomly generate the initial population as cellular space and state matrix (an n-th order square matrixN composed of 0 and 1).(ii)
Step 2. Calculate the city distance matrix.(iii)
Step 3. Calculate the total distance of individuals in the population.(iii)
Step 4. Take each cell as the central cell in turn.(c)
If the central cell state is 1, then it is the central cell and the best cell from neighbors to form the parents. Otherwise, skip to Step 7.(v)
Step 5. Perform crossover and mutation operations on the parents to get the offspring.(vi)
Step 6. If the distance of the optimal progeny is longer than the distance of the central cell, the simulated annealing algorithm is used to optimize the optimal progeny and replace the central cell after optimization. Otherwise, the optimal progeny will directly replace the central cell.(vii)
Step 7. Update the state matrix according to the cellular automata rule.(viii)
Step 8. Calculate the distance of individuals in the current population and store the best individuals.(ix)
Step 9. Judge the stop condition.(d)
Stop when the maximum number of iterations is reached. Otherwise, skip to Step 4.Algorithm 8:The pseudocode of the hybrid cellular genetic algorithm (SCGA) for solving TSP.
The hybrid cellular genetic algorithm (SCGA) for solving TSPBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. Pc, Pm, r, T0, Num,Num. C, Maxiter,L, TtInitialization: using ordinal coding to generate randomly the initial population as cellular space, generate randomly an n-th order square matrixN composed of 0 and 1 as state matrix, number of iteration k = 1whilek ≤ Maxiterfori = 1 to n2ifNi=1Genetic operationsElitist strategyEnd ifSave the optimal result in the iterationEnd fork = k +1End whileOutput: the optimal result:R=N1,N2,…,Nn,fREnd


## 3.1. Dynamic Evolution of Cellular Space

A state matrix in the cellular space is composed of each cell state in the cellular space. In the iteration, each cell in the cellular space is used as the central cell, and the state of the central cell is updated using the cellular automata rules to form a new state matrix. The pseudocode of the dynamic evolution of the cellular space is shown in Algorithm5. Given a 10 × 10 cellular space arbitrarily, each cell state is randomly generated to form an initial state matrix (an n-th order square matrix N composed of 0 and 1), as shown in Figure 2. The cellular automata rule determines each cell’s updated state, for example, if the cell in the third row and the third column is the central cell. The central cell state is 1, and there are four cells in the neighboring cells with states equal to 1. According to rule 1, the central cell update state will be 0, while the central cell updated state will be 1, according to rule 2 or rule 3. It can be seen that the updated cellular state changes according to different cellular automata rules. Because dead cells do not perform genetic operations, we only consider the number of living cells. Figure 3 shows that when different cellular automata rules are selected, the total number of living cells will differ. Therefore, if rule 1 is chosen, the total number of living cells will eventually remain at about 10%, while if rule 2 is selected, the total number of living cells will eventually remain at about 38%. On the other hand, if rule 3 is selected, the total number of living cells will eventually remain in a range of 50%. The total number of living cells in the cellular space will affect the optimization performance of the algorithm. Aiming at the TSP, we will compare the optimal solutions obtained by applying these three rules in the hybrid cellular genetic algorithm through experiments.Algorithm 5:The pseudocode of the dynamic evolution of the cellular space.
Dynamic evolution of cellular spaceBeginInput: An n-th order square matrixN composed of 0 and 1, three cellular automata rulesfori = 1 to n2Calculate the sumK of 8 neighbors’ statesifNi=1ifK = 2 or K = 3 # rule 1ifK = 1 or K = 2 or K = 3 or K = 4 # rule 2ifK = 2 or K = 4 or K = 6 or K = 8 # rule 3Ni=1elseNi=0End ifelseifK = 3 # rule 1ifK = 4 or K = 5 or K = 6 or K = 7 # rule 2ifK = 1 or K = 3 or K = 5 or K = 7 # rule 3Ni=1elseNi=0End ifEnd ifEnd forOutput: New square matrixNEndFigure 2
State matrix.Figure 3
The change of the total number of living cells.


## 3.2. Genetic Operations

SCGA puts the individual as a cell into the cellular space, selects the living cell, and forms the parents with the best cell among neighbors. Then, the parents perform crossover and mutation operations. If the cellular state is dead, no crossover and mutation operations are performed. Algorithm6 shows the pseudocode for the genetic operations.Algorithm 6:The pseudocode for genetic operations.
Genetic operationsBeginInput: An n-th order square matrixN composed of 0 and 1, cellular space,city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,ynCalculate the total distancefiR of each individual in the cellular space by Equation (2)fori = 1 to n2ifNi=1Select the ith individual and the individual with smallest total distance among the 8 neighborsCrossoverMutationNew the ith individualEnd ifEnd forOutput: New cellular spaceEndAssuming that the number of cities is 10 and the number of populations is 100, the corresponding cellular space is a 2D grid of 10 × 10 units. The algorithm works as follows:(i)
Randomly generate 100 individuals to form the initial population and associate the individuals with the cells one-to-one(ii)
If Figure2 is used as the state matrix of the cellular space at the initial moment, the individual is represented by the letter. The number after the letter represents the state of the cell, as shown in Figure 4(iii)
Take the individual V in the third row and second column as the central cell(iv)
In the current iteration, the cellular state is living (state 1)(v)
Tables1 and 2 show that the individual with the shortest distance among neighbors is AE, so choose AE and V and perform crossover and mutation operations as parents:Firstly, the parents can get the offspring individuals O1 and O2 after PMX.Perform the reverse mutation on O1 and O2 to get the individuals O3 and O4, as shown in Table3.The new individuals obtained after genetic manipulation are O3 and O4; the best progeny is O3, and O3 is better than V; so O3 replaces V to complete the genetic operation.Figure 4
Cell and state matrix.Table 1
Central cell and neighbors.
CellRouteDistanceCellRouteDistanceCellRouteDistanceK3 4 6 9 7 1 8 10 2 5316.0711U6 2 4 8 9 3 1 5 7 10344.9062AE7 8 1 9 3 5 10 4 2 6244.1511L8 9 4 6 10 5 2 7 1 3262.5791V4 3 2 7 10 6 8 1 5 9290.6597AF2 3 8 4 6 10 9 7 5 1267.6944M4 8 12 7 3 9 10 6 5260.2487W2 4 8 5 7 3 6 1 9 10299.5755AG1 10 4 8 6 5 7 2 9 3288.2223Table 2
City coordinates.
Number12345678910x37495220402117315251y52496426304763623321Table 3
Individuals in crossover and mutation process.
CellRouteDistanceCellRouteDistanceV4 3 2 7 10 6 8 1 5 9290.6597O29 3 2 7 10 6 8 4 1 5296.2696AE7 8 1 9 3 5 10 4 2 6244.1511O31 8 4 9 3 5 10 2 6 7258.7903O14 8 1 9 3 5 10 2 6 7264.5371O49 4 8 6 10 7 2 3 1 5286.1712


## 3.3. Elitist Strategy

The living central cell and the best neighbor get offspring after crossover and mutation operations. If the distance between the optimal progeny and central cell is not compared, and the optimal progeny directly replaces the central cell, the inferior solution may enter the population. If the central cell’s distance is better than the optimal progeny distance, and the central cell is not replaced, it may fall into a local optimum. In order to solve the above problems, SCGA sets an elite individual retention strategy after the crossover and mutation operations. When the optimal progeny’s obtained distance after the crossover and mutation operation is less than the distance of the center cell, the center cell is directly replaced with the optimal progeny. Otherwise, after performing the simulated annealing operation on the optimal progeny, new offspring are obtained, and the central cell is replaced with the new offspring. Algorithm7 shows the pseudocode of the elitist strategy. Through the elitist strategy, the living central cell can be optimized as much as possible to avoid falling into the local optimum.Algorithm 7:The pseudocode of elitist strategy.
Elitist strategyBeginInput: Central cellS1 and new individual S2city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,ynCalculatefS1 and fS2 by Equation (2)iffS1>fS2S1=S2elseOptimizeS2 using simulated annealing algorithmS1=S2End ifOutput:S1End


## 3.4. Process of SCGA

SCGA, as explained before, has three main contents: the dynamic evolution of cellular space, genetic operations, and elitist strategy. In this section, we will introduce the main steps of applying SCGA to solve TSP. Algorithm8 shows the pseudocode of the proposed hybrid Cellular Genetic Algorithm with SA (SCGA) and its required steps for the TSP solution.(i)
Step 1. Population initialization:(a)
Initialize the following parameters:(i)
Crossover probabilityPc,(ii)
Mutation probabilityPm,(iii)
Cooling rater,(iv)
Initial temperatureT0,(v)
Population size Num,(vi)
The size of cellular space Num. C,(vii)
Maximum iteration times Maxiter,(viii)
Markov chain lengthL,(ix)
Termination temperatureTt;(b)
Randomly generate the initial population as cellular space and state matrix (an n-th order square matrixN composed of 0 and 1).(ii)
Step 2. Calculate the city distance matrix.(iii)
Step 3. Calculate the total distance of individuals in the population.(iii)
Step 4. Take each cell as the central cell in turn.(c)
If the central cell state is 1, then it is the central cell and the best cell from neighbors to form the parents. Otherwise, skip to Step 7.(v)
Step 5. Perform crossover and mutation operations on the parents to get the offspring.(vi)
Step 6. If the distance of the optimal progeny is longer than the distance of the central cell, the simulated annealing algorithm is used to optimize the optimal progeny and replace the central cell after optimization. Otherwise, the optimal progeny will directly replace the central cell.(vii)
Step 7. Update the state matrix according to the cellular automata rule.(viii)
Step 8. Calculate the distance of individuals in the current population and store the best individuals.(ix)
Step 9. Judge the stop condition.(d)
Stop when the maximum number of iterations is reached. Otherwise, skip to Step 4.Algorithm 8:The pseudocode of the hybrid cellular genetic algorithm (SCGA) for solving TSP.
The hybrid cellular genetic algorithm (SCGA) for solving TSPBeginInput: city coordinates:X=x1,x2,…,xn, Y=y1,y2,…,yn. Pc, Pm, r, T0, Num,Num. C, Maxiter,L, TtInitialization: using ordinal coding to generate randomly the initial population as cellular space, generate randomly an n-th order square matrixN composed of 0 and 1 as state matrix, number of iteration k = 1whilek ≤ Maxiterfori = 1 to n2ifNi=1Genetic operationsElitist strategyEnd ifSave the optimal result in the iterationEnd fork = k +1End whileOutput: the optimal result:R=N1,N2,…,Nn,fREnd


## 4. Experimental Results and Discussion

Here, instances in the TSPLIB test library are selected, and GA, SA, CGA, and SCGA (cellular automata rules 1–3) are used to solve these instances. All of the proposed algorithms are implemented using MATLAB R2018b using a laptop equipped with Windows 10 Ultimate 64 bit operating system, processor Intel Core i7-10510U CPU, 12 GB of RAM, and 1.80 GHz processor speed.


### 4.1. Experiments Settings

13 instances from TSPLIB are selected for simulation experiments. To avoid the influence of randomness, the results of the experiments on each algorithm for each instance were taken independently over 10 repeated times. The result is expressed by the route distance obtained from the experiment. The basic parameters of SCGA include crossover probabilityPc = 0.9, mutation probability Pm = 0.05, cooling rate r = 0.9, and initial temperature T0 = 100. The other parameters are shown in Table 4, where Num, Num. C, Maxiter, L, and Tt represent population size, the size of cellular space, maximum iteration times, Markov chain length, and termination temperature values which are identified. The basic parameters of GA are initialized as the population size Num = 100, generation gap GGAP = 0.9, and maximum iteration times Maxiter = 10000. The basic parameters of SA are also initialized as Markov chain length L = 500 and termination temperature Tend = 0.001. The basic parameters of CGA are assigned initial values as mutation probability Pm = 0.5 and maximum iteration times Maxiter = 10000. The other parameters that are not mentioned are the same as those of SCGA.Table 4
The parameters of instances.
InstanceNumNum.CMaxiterLTtatt4840020 × 20501000.01berlin5240020 × 20501000.01bier127160040 × 401005000.001ch130160040 × 401005000.001chn3140020 × 20501000.01eil5140020 × 20501000.01eil7690030 × 301005000.01kroa10040020 × 20501000.01kroa200160040 × 401005000.001oliver3040020 × 20501000.01pr107160040 × 40505000.001pr136160040 × 401005000.001pr152160040 × 401005000.001


### 4.2. Comparison of Cellular Automata Rules

In order to test the optimization of the three cellular automata rules, the experiment is performed using rule 1, rule 2, and rule 3 in SCGA using the same parameters applied in the previous experiments. Figure5 shows the optimal paths of eil51, pr107, bier127, and kroa200. Table 5 shows the best solutions, the worst solutions, the mean value, and the standard deviation of 10 repeated experiments. The boldface in the table represents the optimal value. As can be seen, in the instances of att48, berlin52, chn31, oliver30, pr107, and pr152, the best solutions obtained using rule 1, rule 2, and rule 3 are equal. In the instances of bier127, ch130, and kroa100, the best solutions obtained using rule 2 and rule 3 are also equal, and both are better than the best solutions obtained using rule 1. In the instances of eil51 and eil76, the best solutions obtained using rule 2 are better than the best solutions obtained using rule 1 and rule 3. Only in the instance of pr136, the best solutions obtained by using rule 1 and rule 3 are better than the best solutions obtained using rule 2. In the instance of kroa200, the best solution obtained using rule 3 is better than the best solution obtained using rule 2. In most instances, the worst solutions obtained using rule 2 are better than the worst solutions obtained using rule 1 and rule 3. Only in the instances of kroa100 and pr136, the worst solutions obtained using rule 1 and rule 3 are better than the worst solutions obtained using rule 2. At the same time, in 10 repeated experiments, the mean value and the standard deviation computed using rule 2 are better than the mean value and the standard deviation computing using rule 1 and rule 3. It can be seen that, in most instances, a better and more stable optimal solution can be obtained by using rule 2 in SCGA. In other words, the optimization performance of cellular automata rules with a moderate total number of living cells is giving better results than other rules.Figure 5
The optimal paths: (a) eil51; (b) pr107; (c) bier127; (d) kroa200.
(a)(b)(c)(d)Table 5
Comparison of cellular automata rules.
InstanceOptRuleBestWorstMeanStDatt4833522Rule 133523.708533555.276533530.022112.6272Rule 233523.708533523.708533523.70850.0000Rule 333523.708533555.276533526.86539.4704berlin527452Rule 17544.36597544.36597544.36590.0000Rule 27544.36597544.36597544.36590.0000Rule 37544.36597544.36597544.36590.0000bier127118282Rule 1118822.0753118822.0753118822.07530.0000Rule 2118293.5238118293.5238118293.52380.0000Rule 3118293.5238118293.5238118293.52380.0000ch13015377Rule 16225.44336225.44336225.44330.0000Rule 26183.02516183.97326183.40430.4645Rule 36183.02516205.65326189.908310.3112chn3115377Rule 115377.711315377.711315377.71130.0000Rule 215377.711315377.711315377.71130.0000Rule 315377.711315377.711315377.71130.0000eil51426Rule 1430.4455436.7443433.25491.9062Rule 2428.8718432.1911429.97231.1064Rule 3430.4455434.1932432.09741.1403eil76538Rule 1549.4996552.0326550.69440.6931Rule 2547.1706551.4043548.18471.4609Rule 3547.3471552.0326549.52511.4484kroa10021282Rule 121320.957021767.556521513.1620142.7024Rule 221285.443221362.979521309.437927.5103Rule 321285.443221359.864921315.217928.7554kroa20029368Rule 129834.363529865.946429840.680112.6332Rule 229588.234029599.404729596.05355.1191Rule 329533.062029599.404729577.915222.7067oliver30420Rule 1423.7406423.7406423.74060.0000Rule 2423.7406423.7406423.74060.0000Rule 3423.7406423.7406423.74060.0000pr10744303Rule 144301.683744301.683744301.68370.0000Rule 244301.683744301.683744301.68370.0000Rule 344301.683744301.683744301.68370.0000pr13696772Rule 197102.317097138.189197105.904210.7616Rule 297160.005597181.190497164.24258.4740Rule 396795.403097102.317096856.7858122.7656pr15273682Rule 173683.640673683.640673683.64060.0000Rule 273683.640673683.640673683.64060.0000Rule 373683.640673683.640673683.64060.0000


### 4.3. Comparison of Other Algorithms

In order to verify the optimization of SCGA, SCGA, CGA, GA, and SA are applied to the instances. The experimental results are shown in Tables6–8.Table 6
The best solution and the worst solution.
InstanceOptMetricGASACGASCGAatt4833522Best34149.374334013.281933961.110633523.7085Worst36386.889236208.306934609.504733555.2765berlin527542Best7899.00837684.58297812.56657544.3659Worst8538.63118240.46008252.48647544.3659bier127118282Best128515.2927126213.1835123577.8803118293.5238Worst135685.9343132724.0594127274.5241118822.0753ch1306110Best6541.89806493.49786350.01916183.0251Worst6997.08406901.18486559.83276225.4433chn3115377Best15487.206215450.507915377.711315377.7113Worst16265.992616097.418715891.343115377.7113eil51426Best437.6323439.5980438.5469428.8718Worst464.2338458.5167459.2966436.7443eil76538Best570.9642575.2977562.0046547.1706Worst608.9891619.4997584.2497552.0326kroa10021282Best21985.335122094.403821544.095321285.4432Worst24611.469324663.0452323080.915821767.5565kroa20029368Best32405.948634196.653731724.852729533.0620Worst41893.286636233.360433755.301429865.9464oliver30420Best424.6918423.7406423.7406423.7406Worst476.1180425.1044429.5888423.7406pr10744303Best45983.433945161.742244579.188144301.6837Worst50060.878249392.836747261.235944301.6837pr13696772Best104784.6839105372.1700102047.993596795.4030Worst114883.2612110519.6460106732.057597181.1904pr15273682Best75801.262076992.774974888.938873683.6406Worst81017.335283021.764178170.397673683.6406Table 7
The mean value and standard deviation.
InstanceOptMetricGASACGASCGAatt4833522Mean35198.242834873.574134341.473733526.8653StD775.3089742.4642218.01129.4704berlin527542Mean8221.63187964.20327967.75327544.3659StD175.0246166.5235108.12870.0000bier127118282Mean131581.2788128983.7461125262.8687118469.7076StD2448.70822325.30371235.5069249.1616ch1306110Mean6751.41056749.05066467.49836199.5853StD147.3786125.485770.323119.4134chn3115377Mean15781.252815697.686015568.149215377.7113StD256.7062205.2499171.75380.0000eil51426Mean454.4414446.8963443.9726431.7748StD9.14656.26785.57691.9750eil76538Mean590.0867589.7360570.9942549.4681StD13.126211.37606.32391.6194kroa10021282Mean23548.746523095.524822203.635221379.2726StD674.8707803.5809451.3302127.6113kroa20029368Mean37475.004534987.519232519.852629671.5496StD2563.0760589.8787536.6872120.7940oliver30420Mean443.1219424.0513425.4695423.7406StD19.07210.53171.45900.0000pr10744303Mean48158.458447656.828945861.512844301.6837StD1505.60241540.8192833.15440.0000pr13696772Mean108845.5545107333.6988103717.242397042.3108StD2690.46931450.65171462.0469151.2063pr15273682Mean78641.479780403.538876394.631973683.6406StD1537.26791712.5745907.16300.0000Table 8
The best solution error and the mean value error.
InstanceMetricGA (%)SA (%)CGA (%)SCGA (%)att48Best.Err1.878.011.310.01Mean.Err5.004.032.440.01berlin52Best.Err4.739.263.590.03Mean.Err9.015.605.650.03bier127Best.Err8.6512.214.480.01Mean.Err11.249.055.900.16ch130Best.Err7.0712.953.931.20Mean.Err10.5010.465.851.47chn31Best.Err0.724.690.000.00Mean.Err2.632.091.240.00eil51Best.Err2.737.632.950.67Mean.Err6.684.914.221.36eil76Best.Err6.1315.154.461.70Mean.Err9.689.626.132.13kroa100Best.Err3.3015.891.230.02Mean.Err10.658.524.330.46kroa200Best.Err10.3423.388.030.56Mean.Err27.6019.1310.731.03oliver30Best.Err1.121.220.890.89Mean.Err5.510.961.300.89pr107Best.Err3.7911.490.620.00Mean.Err8.707.573.520.00pr136Best.Err8.2814.215.450.02Mean.Err12.4810.917.180.28pr152Best.Err2.8812.681.640.00Mean.Err6.739.123.680.00As shown in Table6, based on the instances of kroa200, bier127, pr136, and ch130, the distance of the SCGA best solutions is shorter than the distance of the GA best solutions by 9.73%, 8.64%, 8.25%, and 5.80%, respectively. Besides, based on the instances of kroa200, pr136, bier127, eil76, and ch130, the distance of the SCGA best solutions is shorter than the distance of the SA best solutions by 15.79%, 8.86%, 6.69%, 8.25%, 5.14%, and 5.02%, respectively. In the instances of kroa200 and pr136, the distance of the best solutions obtained by using SCGA is shorter than the distance of the best solutions obtained by using CGA by 7.42% and 5.43%, respectively. The SCGA best solutions are better than the GA best solutions in these 13 instances. Only in the instances of oliver30 and chn31, the distance of the SCGA best solutions is equal to the CGA best solutions’ distance. Besides, in the instance of oliver30, the SCGA best solution’s distance is equal to the distance of the SA best solution. Moreover, the SCGA worst solutions are better than the GA, SA, and CGA worst solutions in these 13 instances.It is shown in Table7, based on the instances of kroa200, pr136, bier127, kroa100, ch130, berlin52, ch130, and pr107, that the SCGA solution mean distance is shorter than the GA mean distance solutions by 26.30%, 12.16%, 11.07%, 10.15%, 8.98%, 8.90%, and 8.71%, respectively. In the instances of kroa200, pr136, pr152, bier127, ch130, and kroa100, the SCGA mean distance is shorter than the SA distance mean value by 17.92%, 10.61%, 9.12%, 8.87%, 8.86%, and 8.03%, respectively. In the instances of kroa200 and pr136, the distance of the SCGA mean value is shorter than the CGA mean distance by 9.60% and 6.88%, respectively. At the same time, the standard deviations of the SCGA are the smallest.This paper uses SCGA to solve these instances and accounts for four decimal places. So, there will be a slight error when comparing with the known optimal solution. In Table8, the calculation equations for the best solution error and the mean value error are as follows:(7)Best.Err=Best−OptOpt,Mean.Err=Mean−OptOpt.It is shown in Table8, in the instances of chn31, pr107, and pr152, that the SCGA best solution errors are about 0%. Only in the instances ch130 and eil76, the SCGA best solution errors are greater than 1%.From Tables6–8, we conclude the following.The optimal solution, the worst solution, the mean value, and the standard deviation obtained by solving the TSP instances using our proposed algorithm (SCGA) are better than GA, SA, and CGA. Using SCGA to solve the TSP instances gives the closest values to the theoretical optimal value. Figure6 shows the box plots of 10 independents runs of instances kroa100, pr152, att48, and eil76. The box plots of SCGA always locate the lowest position in four instances. Furthermore, these box plots of SCGA are close to the straight lines, which indicate that SCGA has the smallest degree of the difference between the best value, the mean value, the worst value, and the median value. As mentioned before, SCGA significantly outperforms GA, SA, and CGA.Figure 6
Box plots for comparing 10-runs results of GA, SA, CGA, and SCGA: (a) kroa100; (b) pr152; (c) att48; (d) eil76.
(a)(b)(c)(d)


## 4.1. Experiments Settings

13 instances from TSPLIB are selected for simulation experiments. To avoid the influence of randomness, the results of the experiments on each algorithm for each instance were taken independently over 10 repeated times. The result is expressed by the route distance obtained from the experiment. The basic parameters of SCGA include crossover probabilityPc = 0.9, mutation probability Pm = 0.05, cooling rate r = 0.9, and initial temperature T0 = 100. The other parameters are shown in Table 4, where Num, Num. C, Maxiter, L, and Tt represent population size, the size of cellular space, maximum iteration times, Markov chain length, and termination temperature values which are identified. The basic parameters of GA are initialized as the population size Num = 100, generation gap GGAP = 0.9, and maximum iteration times Maxiter = 10000. The basic parameters of SA are also initialized as Markov chain length L = 500 and termination temperature Tend = 0.001. The basic parameters of CGA are assigned initial values as mutation probability Pm = 0.5 and maximum iteration times Maxiter = 10000. The other parameters that are not mentioned are the same as those of SCGA.Table 4
The parameters of instances.
InstanceNumNum.CMaxiterLTtatt4840020 × 20501000.01berlin5240020 × 20501000.01bier127160040 × 401005000.001ch130160040 × 401005000.001chn3140020 × 20501000.01eil5140020 × 20501000.01eil7690030 × 301005000.01kroa10040020 × 20501000.01kroa200160040 × 401005000.001oliver3040020 × 20501000.01pr107160040 × 40505000.001pr136160040 × 401005000.001pr152160040 × 401005000.001


## 4.2. Comparison of Cellular Automata Rules

In order to test the optimization of the three cellular automata rules, the experiment is performed using rule 1, rule 2, and rule 3 in SCGA using the same parameters applied in the previous experiments. Figure5 shows the optimal paths of eil51, pr107, bier127, and kroa200. Table 5 shows the best solutions, the worst solutions, the mean value, and the standard deviation of 10 repeated experiments. The boldface in the table represents the optimal value. As can be seen, in the instances of att48, berlin52, chn31, oliver30, pr107, and pr152, the best solutions obtained using rule 1, rule 2, and rule 3 are equal. In the instances of bier127, ch130, and kroa100, the best solutions obtained using rule 2 and rule 3 are also equal, and both are better than the best solutions obtained using rule 1. In the instances of eil51 and eil76, the best solutions obtained using rule 2 are better than the best solutions obtained using rule 1 and rule 3. Only in the instance of pr136, the best solutions obtained by using rule 1 and rule 3 are better than the best solutions obtained using rule 2. In the instance of kroa200, the best solution obtained using rule 3 is better than the best solution obtained using rule 2. In most instances, the worst solutions obtained using rule 2 are better than the worst solutions obtained using rule 1 and rule 3. Only in the instances of kroa100 and pr136, the worst solutions obtained using rule 1 and rule 3 are better than the worst solutions obtained using rule 2. At the same time, in 10 repeated experiments, the mean value and the standard deviation computed using rule 2 are better than the mean value and the standard deviation computing using rule 1 and rule 3. It can be seen that, in most instances, a better and more stable optimal solution can be obtained by using rule 2 in SCGA. In other words, the optimization performance of cellular automata rules with a moderate total number of living cells is giving better results than other rules.Figure 5
The optimal paths: (a) eil51; (b) pr107; (c) bier127; (d) kroa200.
(a)(b)(c)(d)Table 5
Comparison of cellular automata rules.
InstanceOptRuleBestWorstMeanStDatt4833522Rule 133523.708533555.276533530.022112.6272Rule 233523.708533523.708533523.70850.0000Rule 333523.708533555.276533526.86539.4704berlin527452Rule 17544.36597544.36597544.36590.0000Rule 27544.36597544.36597544.36590.0000Rule 37544.36597544.36597544.36590.0000bier127118282Rule 1118822.0753118822.0753118822.07530.0000Rule 2118293.5238118293.5238118293.52380.0000Rule 3118293.5238118293.5238118293.52380.0000ch13015377Rule 16225.44336225.44336225.44330.0000Rule 26183.02516183.97326183.40430.4645Rule 36183.02516205.65326189.908310.3112chn3115377Rule 115377.711315377.711315377.71130.0000Rule 215377.711315377.711315377.71130.0000Rule 315377.711315377.711315377.71130.0000eil51426Rule 1430.4455436.7443433.25491.9062Rule 2428.8718432.1911429.97231.1064Rule 3430.4455434.1932432.09741.1403eil76538Rule 1549.4996552.0326550.69440.6931Rule 2547.1706551.4043548.18471.4609Rule 3547.3471552.0326549.52511.4484kroa10021282Rule 121320.957021767.556521513.1620142.7024Rule 221285.443221362.979521309.437927.5103Rule 321285.443221359.864921315.217928.7554kroa20029368Rule 129834.363529865.946429840.680112.6332Rule 229588.234029599.404729596.05355.1191Rule 329533.062029599.404729577.915222.7067oliver30420Rule 1423.7406423.7406423.74060.0000Rule 2423.7406423.7406423.74060.0000Rule 3423.7406423.7406423.74060.0000pr10744303Rule 144301.683744301.683744301.68370.0000Rule 244301.683744301.683744301.68370.0000Rule 344301.683744301.683744301.68370.0000pr13696772Rule 197102.317097138.189197105.904210.7616Rule 297160.005597181.190497164.24258.4740Rule 396795.403097102.317096856.7858122.7656pr15273682Rule 173683.640673683.640673683.64060.0000Rule 273683.640673683.640673683.64060.0000Rule 373683.640673683.640673683.64060.0000


## 4.3. Comparison of Other Algorithms

In order to verify the optimization of SCGA, SCGA, CGA, GA, and SA are applied to the instances. The experimental results are shown in Tables6–8.Table 6
The best solution and the worst solution.
InstanceOptMetricGASACGASCGAatt4833522Best34149.374334013.281933961.110633523.7085Worst36386.889236208.306934609.504733555.2765berlin527542Best7899.00837684.58297812.56657544.3659Worst8538.63118240.46008252.48647544.3659bier127118282Best128515.2927126213.1835123577.8803118293.5238Worst135685.9343132724.0594127274.5241118822.0753ch1306110Best6541.89806493.49786350.01916183.0251Worst6997.08406901.18486559.83276225.4433chn3115377Best15487.206215450.507915377.711315377.7113Worst16265.992616097.418715891.343115377.7113eil51426Best437.6323439.5980438.5469428.8718Worst464.2338458.5167459.2966436.7443eil76538Best570.9642575.2977562.0046547.1706Worst608.9891619.4997584.2497552.0326kroa10021282Best21985.335122094.403821544.095321285.4432Worst24611.469324663.0452323080.915821767.5565kroa20029368Best32405.948634196.653731724.852729533.0620Worst41893.286636233.360433755.301429865.9464oliver30420Best424.6918423.7406423.7406423.7406Worst476.1180425.1044429.5888423.7406pr10744303Best45983.433945161.742244579.188144301.6837Worst50060.878249392.836747261.235944301.6837pr13696772Best104784.6839105372.1700102047.993596795.4030Worst114883.2612110519.6460106732.057597181.1904pr15273682Best75801.262076992.774974888.938873683.6406Worst81017.335283021.764178170.397673683.6406Table 7
The mean value and standard deviation.
InstanceOptMetricGASACGASCGAatt4833522Mean35198.242834873.574134341.473733526.8653StD775.3089742.4642218.01129.4704berlin527542Mean8221.63187964.20327967.75327544.3659StD175.0246166.5235108.12870.0000bier127118282Mean131581.2788128983.7461125262.8687118469.7076StD2448.70822325.30371235.5069249.1616ch1306110Mean6751.41056749.05066467.49836199.5853StD147.3786125.485770.323119.4134chn3115377Mean15781.252815697.686015568.149215377.7113StD256.7062205.2499171.75380.0000eil51426Mean454.4414446.8963443.9726431.7748StD9.14656.26785.57691.9750eil76538Mean590.0867589.7360570.9942549.4681StD13.126211.37606.32391.6194kroa10021282Mean23548.746523095.524822203.635221379.2726StD674.8707803.5809451.3302127.6113kroa20029368Mean37475.004534987.519232519.852629671.5496StD2563.0760589.8787536.6872120.7940oliver30420Mean443.1219424.0513425.4695423.7406StD19.07210.53171.45900.0000pr10744303Mean48158.458447656.828945861.512844301.6837StD1505.60241540.8192833.15440.0000pr13696772Mean108845.5545107333.6988103717.242397042.3108StD2690.46931450.65171462.0469151.2063pr15273682Mean78641.479780403.538876394.631973683.6406StD1537.26791712.5745907.16300.0000Table 8
The best solution error and the mean value error.
InstanceMetricGA (%)SA (%)CGA (%)SCGA (%)att48Best.Err1.878.011.310.01Mean.Err5.004.032.440.01berlin52Best.Err4.739.263.590.03Mean.Err9.015.605.650.03bier127Best.Err8.6512.214.480.01Mean.Err11.249.055.900.16ch130Best.Err7.0712.953.931.20Mean.Err10.5010.465.851.47chn31Best.Err0.724.690.000.00Mean.Err2.632.091.240.00eil51Best.Err2.737.632.950.67Mean.Err6.684.914.221.36eil76Best.Err6.1315.154.461.70Mean.Err9.689.626.132.13kroa100Best.Err3.3015.891.230.02Mean.Err10.658.524.330.46kroa200Best.Err10.3423.388.030.56Mean.Err27.6019.1310.731.03oliver30Best.Err1.121.220.890.89Mean.Err5.510.961.300.89pr107Best.Err3.7911.490.620.00Mean.Err8.707.573.520.00pr136Best.Err8.2814.215.450.02Mean.Err12.4810.917.180.28pr152Best.Err2.8812.681.640.00Mean.Err6.739.123.680.00As shown in Table6, based on the instances of kroa200, bier127, pr136, and ch130, the distance of the SCGA best solutions is shorter than the distance of the GA best solutions by 9.73%, 8.64%, 8.25%, and 5.80%, respectively. Besides, based on the instances of kroa200, pr136, bier127, eil76, and ch130, the distance of the SCGA best solutions is shorter than the distance of the SA best solutions by 15.79%, 8.86%, 6.69%, 8.25%, 5.14%, and 5.02%, respectively. In the instances of kroa200 and pr136, the distance of the best solutions obtained by using SCGA is shorter than the distance of the best solutions obtained by using CGA by 7.42% and 5.43%, respectively. The SCGA best solutions are better than the GA best solutions in these 13 instances. Only in the instances of oliver30 and chn31, the distance of the SCGA best solutions is equal to the CGA best solutions’ distance. Besides, in the instance of oliver30, the SCGA best solution’s distance is equal to the distance of the SA best solution. Moreover, the SCGA worst solutions are better than the GA, SA, and CGA worst solutions in these 13 instances.It is shown in Table7, based on the instances of kroa200, pr136, bier127, kroa100, ch130, berlin52, ch130, and pr107, that the SCGA solution mean distance is shorter than the GA mean distance solutions by 26.30%, 12.16%, 11.07%, 10.15%, 8.98%, 8.90%, and 8.71%, respectively. In the instances of kroa200, pr136, pr152, bier127, ch130, and kroa100, the SCGA mean distance is shorter than the SA distance mean value by 17.92%, 10.61%, 9.12%, 8.87%, 8.86%, and 8.03%, respectively. In the instances of kroa200 and pr136, the distance of the SCGA mean value is shorter than the CGA mean distance by 9.60% and 6.88%, respectively. At the same time, the standard deviations of the SCGA are the smallest.This paper uses SCGA to solve these instances and accounts for four decimal places. So, there will be a slight error when comparing with the known optimal solution. In Table8, the calculation equations for the best solution error and the mean value error are as follows:(7)Best.Err=Best−OptOpt,Mean.Err=Mean−OptOpt.It is shown in Table8, in the instances of chn31, pr107, and pr152, that the SCGA best solution errors are about 0%. Only in the instances ch130 and eil76, the SCGA best solution errors are greater than 1%.From Tables6–8, we conclude the following.The optimal solution, the worst solution, the mean value, and the standard deviation obtained by solving the TSP instances using our proposed algorithm (SCGA) are better than GA, SA, and CGA. Using SCGA to solve the TSP instances gives the closest values to the theoretical optimal value. Figure6 shows the box plots of 10 independents runs of instances kroa100, pr152, att48, and eil76. The box plots of SCGA always locate the lowest position in four instances. Furthermore, these box plots of SCGA are close to the straight lines, which indicate that SCGA has the smallest degree of the difference between the best value, the mean value, the worst value, and the median value. As mentioned before, SCGA significantly outperforms GA, SA, and CGA.Figure 6
Box plots for comparing 10-runs results of GA, SA, CGA, and SCGA: (a) kroa100; (b) pr152; (c) att48; (d) eil76.
(a)(b)(c)(d)


## 5. Conclusions

In order to solve the TSP effectively, a hybrid Cellular Genetic Algorithm with SA (SCGA) is proposed. The algorithm combines the principles of GA, CA, and SA to improve the optimization GA’s performance. Experimental results show that SCGA is superior to GA, SA, and CGA in solving the TSP. It proves that SCGA has high optimization performance and robustness when solving the TSP.We studied the optimization performance of three cellular automata rules for the TSP solution. In addition to the three cellular automata rules studied in this paper, other cellular automata rules may have higher optimization performance. We combined the simulated annealing algorithm and the cellular genetic algorithm to enhance the TSP solution’s optimization performance. In addition to the simulated annealing algorithm, the cellular genetic algorithm was combined with other algorithms and effectively enhanced the TSP solution’s optimization performance. Common traveling salesman problems include symmetric traveling salesman problem, asymmetric traveling salesman problem, multiperson traveling salesman problem, and multitarget traveling salesman problem. This paper studied only the symmetric traveling salesman problem based on the Euclidean distance. The optimization performance of the asymmetric traveling salesman problem and other traveling salesman problems has not been verified. In addition, it is not clear how to apply the hybrid cellular genetic algorithm to other optimal combination problems, such as knapsack problems, production scheduling problems, and clustering. These issues are worthy of our further discussion, and they will be the focus of our future work.



---

*Source: 6697598-2021-02-09.xml*