Available online at www.sciencedirect.

com
Systems
Engineering
Procedia
Systems Engineering Procedia 00 (2011) 000–000
Systems Engineering Procedia 4 (2012) 226 – 235
www.elsevier.com/locate/procedia

The 2nd International Conference on Complexity Science & Information Engineering

Comparison of several intelligent algorithms for solving TSP

problem in industrial engineering
Wang Hui a
North China Electric Power University No.2 Beinong Rd., Huilongguan, Beijing, 102206, P.R.China

Abstract

The paper presents three intelligent algorithms, namely, basic genetic algorithm, Hopfield neural network and basic
ant colony algorithm to solve the TSP problem. Then different algorithms are compared in the perspectives of time
complexity, space complexity, the advantages and disadvantages of the calculation results, and difficulty level of
realization. We use the application of paired comparison matrix to make comprehensive evaluation, and then give the
value of comprehensive evaluation in engineering.

©
© 2011
2011 Published byElsevier
Published by ElsevierLtd.
Ltd.Selection
Selection and
and peer-review
peer-review under
under responsibility
responsibility of Desheng
of Desheng Dash Dash
Wu Wu.
Open access under CC BY-NC-ND license.

Keywords: basic genetic algorithm, Hopfield neural network, ant colony optimization, paired comparison matrix, TSP

1. Introduction

The travelling salesman problem (TSP) is a problem in combinatorial optimization studied in operations
research and theoretical computer science and in engineering. Given a list of cities and their pair wise
distances, the task is to find a shortest possible tour that visits each city exactly once.This is an NP-hard
problem, when a large number of nodes of G, if the use exhaustive search, the time complexity is O (n!) ,
2 2
if use the search of dynamic programming, the time complexity is O ( n 2 ) , combinatorial explosion
will occur in the both search methods. Therefore, the majority of domestic and foreign scholars began to
study intelligence algorithms for TSP, since the basic genetic algorithm appears, they began to examine
the use of genetic algorithm on solve TSP problems until present and proposed many improvements.
Reference [1] presents a genetic algorithm based on common path, reference [2] proposed a new genetic
algorithm through using multiple-search method. All these improved genetic algorithms are promising
approach for TSP problem. Hopfield network was proposed in 1970s, and in 1985, Hopfield proposed to
use CHNN for solving TSP problems, but Hopfield network prone to ineffective solutions and local
solutions, so many scholars have been studying how to improve the algorithm, reference [3] analyzed the
effectiveness of solving TSP with Hopfield, reference [4] through optimizing the Hopfield network and
path of the initial steps to improve the Hopfield network to solve TSP and received good results. Ant
colony algorithm which is effectiveness proposed a new computational intelligence algorithm for solving
TSP problems recently. Because of its use of pheromone heuristic function, can greatly reduce the search

* Corresponding author. Tel.+086-010-51963765; fax: +086-010-51963765.

E-mail address: [email protected].

2211-3819 © 2011 Published by Elsevier Ltd. Selection and peer-review under responsibility of Desheng Dash Wu.
Open access under CC BY-NC-ND license. doi:10.1016/j.sepro.2011.11.070
 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235 227

space, so compared to other algorithms it have better time performance, but precisely because of this, ant
colony algorithm is easy to fall into local optimal solution, reference [5] by dynamically adjusting the
pheromone volatility to present a dynamic ant colony algorithm and get a more satisfactory results. All of
these three algorithms for solving TSP problems have advantages and disadvantages. In this paper, these
three kinds of algorithms are compared in time complexity, space complexity, the advantages and
disadvantages of the calculation results, and difficulty level of realization, etc. We apply paired
comparison matrix to make comprehensive evaluation, and then give the value of comprehensive
evaluation.

2. The basic steps of three algorithms

2.1. The application of genetic algorithm for TSP

This paper uses a common framework of genetic algorithm to solve TSP. this section gives the
general framework of genetic algorithm, then given the steps of genetic operators’ algorithm.

Common framework for basic genetic algorithm

STEP0 Q=generateinitialpopulation( )；// Initialize population Q
STEP1 F=calculateobjectfitness(Q)； // calculated fitness(F) of population Q
STEP2 FOR i=1 to T BEGIN // T is the iteration step
STEP3 selectoperator(Q,F)； // Selection operator
STEP4 crossoveroperator(Q,pc)； // crossover operator
STEP5 mutationoperator(Q,F,pm)；// mutation operator
STEP6 F=calculateobjectfitness(Q)；// calculated fitness(F) of population Q
STEP7 END

2.1.1. Encoding and decoding

This paper is using the decimal coding to encoding for the path. For example, a chromosome
193,264,785 that represent a path, the path from the starting city 1, followed city 9,3,2,6,4,7,8,5 and finish
return to the city 1.

2.1.2. Fitness function

Fitness function is calculated by the reciprocal of the path distance, that is, the longer the path the
smaller the fitness, and vice versa. Formula is: 1 , while n , It represents path length.
f = S = ∑ d i ,i +1
S i

2.1.3. Selection operator

We use classic roulette wheel method to select the operator. First we calculate the fitness of each
individual. Then calculate the probability of individual to be selected and use roulette method to choice
the next generation of individual.

2.1.4. Crossover operator

(1) Select two individuals which were recorded as X and Y from the population.
228 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235

(2) Select two crossover points are denoted i and j randomly, generally i ＜ j .

(3) We set a new individual T, make T = Y, then remove the cities which belong to X i to X j .The

first bit to the i − 1 of Z m is same as the first bit to the i − 1 of Tm . The i bit to the j of Z m is same as the i bit
to the j bit of Tm . then send the i bit and behind of the i bit of Tm to Z.then get the individual Z.
(4)Similarly, we can get another individual W. For example, let X = (1,2,3,4,5,6,7,8), Y =
(3,4,5,1,7,8,2,6), i = 3, j = 5 , then Z = (1,7,3,4,5,6,2,8), W = (2,3,1,7,8,4,5,6)

2.1.5. Mutation operator

In this paper, we use a heuristic mutation operator[6]. Heuristic mutation operator use neighborhood
heuristic techniques to improve the efficiency of future generations. We selected λgenes Randomly.
Product neighborhood by transposition of all selected genes, then evaluate all neighbor points, select the
best neighborhood to be offspring .For example, P: (264735891), selected three positions 2,6,8 by
random, we can obtain five different individuals by change their positions: A1: (264739851), A2:
(254736891), A3: (254739861), A4: ( 229473586 1), A5: (294736851) then choose the best variation to
be offspring.

2.2 the appellation of Hopfield network for TSP

The core of Hopfield Network for TSP is to determine the network energy function and derive the
equation of state of the network. We are running the network to reach a steady state, the steady-state is a
solution for the problem.

2.2.1. The energy function of Hopfield network for TSP

reference[4] proposed a simplified energy function.
2 2v xi
A   B  
E= ∑  ∑ v xi − 1 + ∑  ∑ v xi − 1 + D ∫ ∑ d xy v y ,i +1dv xi (1)
2 i x  2 i x  0 y

The state equation is:

du xi    
= − A ∑ vxi − 1 − B ∑ v yi − 1 − D ∑ d xy v y ,i+1 (2)
dt  i   Y  y

1  u 
v xi = 1 + tanh xi  (3)
2  λ 

2.2.2. The steps of Hopfield Network for TSP

SETP0 FOR t=1 to T // T is the number of iterations
STEP1 v 0 =InitV()； //Initialize v0
STEP2 u 0 = λ arctan h(2 × v 0 − 1) ；
 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235 229

STEP3 v =Hopfield(A,B,D,N,F, v 0 , u 0 ,T1, d t , λ )

STEP4 FOREACH v i IN v
STEP5 IF v i >=0.99 THEN v i =1
STEP6 IF v i <=0.01 THEN v i =0
STEP7 END
STEP8 IF v is not valid THEN ‘Ineffective solution’
STEP9 END
Which, T1 is the number of inner loop iterations of Hopfield network, dt is the length of iteration
step, the value of initial νis from reference [4]. Hopfield network function uses the state equation which
given in 2.2.1 to obtain the solution.

2.3 The application of ant colony algorithm for TSP

Initial ant colony algorithm is graph-based algorithms, is proposed by Gutjahr WJ in 2000. The steps
of algorithm are as follows:
STEP0: The TSP for n cities. N={1,2,…,n}，A={(i,j), i,j∈ N}，The matrix for distance between
cities (dij)n×n, We set value of each arc(i,j) is τij(0)=1/|A in TSP graph. We suppose m ants are working,
all the ants are starting from the same city i0. The best solution current is w = (1,2, ..., n).
STEP1 (outer loop) if accordance with stopping rule of algorithm, stop the calculation and output
the best solution which we calculate. Otherwise, the ant s starts from i0.L (s) represents the collection of
cities which ant walked, and at first L (s) is the empty.
STEP2 (inner loop) We calculated according to the order 1≤s≤m of ants. When the ants in the city i,
if L(s ) = N or {l | (i, l ) ∈ A, l ∉ L( s )} = Φ ,complete the calculation of s-ants. Otherwise, if L(s ) ≠ N and
T = {l | (i, l ) ∈ A, l ∉ L(s )} , − {i0 ≠ Φ} ,it will according with the probability pij =
τ ij (k − 1)
, j ∈T
to reach j ,
∑ τ ij (k − 1)
leΤ

L( s ) = L( s )  { j}, i = j .if L( s ) ≠ N and T = {l | (i, l ) ∈ A, l ∉ L( s )} = Φ,−{i0 ≠ Φ} ,it will

reach i0 , L( s ) = L( s )  { j}, i = j ;then repeat STEP 2.
STEP3 For 1≤s≤m, if L( s ) = N , we according to the order of city to calculation in the length of path.
If L( s ) ≠ N , the length of path will set to an infinite value (not up).then compare in the path length of m
ants, denoted by the shortest path of ant is t If f (L(t ) ) < f (L(W ) ) ,we will use the following formula for
path W to strengthen the pheromone and reduce the pheromone on the other path, the function is :

 ρ 
τ ij (k ) = (1 − ρ k −1 )τ ij (k − 1) + k −1  (i, j ) ∈ W 
 W  (4)
τ (k ) = (1 − ρ )τ (k − 1)  (i, j ) ∈ W 
 ij k −1 ij 
We will get new τ ij (k ), k = k + 1 , then repeat steps STEP 1.
230 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235

3. Comparison of three algorithms

3.1. Comparison of Time complexity

The time complexities of selection operator, crossover operator and mutation operator in genetic
algorithm are O(n n), O(n P n 2 ), O(n P n 2 ) . While n0 is the initial size of population. For under normal
0 0 c 0 m

circumstances pc > p m , so O(n P n 2 ) > O(n P n 2 ) > O(n n) . T is the number of outer iterations, so the
0 c 0 m 0

time complexity of outer loop is O(Tn n 2 ) . The time complexity of Initial population generation
0

algorithm and the fitness function calculation are O(n n) < O(Tn n 2 ) . So the time complexity of genetic
0 0

algorithm is O(Tn n 2 ) .
0

The time complexity of the inner loop in Hopfield network is O(T n 2 ) . While T1 is the number of
1

inner loop iterations. T is the number of outer iterations. So the time complexity of Hopfield network

is O(TT n 2 ) .
1

The time complexity of inner loop in ant colony algorithm is O(mn 2 ) , while m is the number of ants,

T is the number of outer iterations. So the time complexity of ant colony algorithm is O(Tmn 2 ) .
2
Genetic algorithms, Hopfield networks and ant colony algorithm's time complexity are O(Tn0 n ) ，
O(TT1n 2 ) and O(Tn0 n 2 ) > O(TT1n 2 ) >
O(Tmn 2 ) , obviously, O(Tmn 2 ) .That is, the time complexity of
the genetic algorithm the highest, the lowest time complexity is ant colony algorithm.

3.2. Comparison of Space complexity

The distance matrixes of three algorithms must be saved and will takes n2 of the space. Genetic
algorithm need to save the population, so it needs n0 n of the space, under normal circumstances n0 > n , so
genetic algorithm space complexity is O(n0 n) . Hopfield network needs to save v, u . v, u are small as n 2

.so the space complexity of Hopfield network is O(n 2 ) . Pheromone matrix and the parameter β of ant

colony algorithm are only need n 2 of the space, so the space complexity of ant colony algorithm is O(n 2 ) .

So the time complexity of genetic algorithm, Hopfield networks and ant colony algorithm
 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235 231

are O(n0 n) , O(n 2 ) and O(n 2 ) ,and O(n0 n) > O(n 2 ) = O(n 2 ) That is, the space complexity of the genetic

algorithm the largest, Hopfield networks and ant colony algorithm have the same space complexity.

3.3. Comparison results

3.3.1. Comparative the merits of the results

This paper uses TSPLB eil51 to compare the results of the three algorithms. Genetic algorithm uses
the following parameters: initial population size n0= 5000, crossover probability pc = 0.3, mutation
probability p m = 0.01, the maximum number of iterations T = 2000. Value of global optimal is 1007.9.
The optimal path length of genetic algorithm's generations is shown in Fig 1

Fig .1 the optimal path length of genetic algorithm's generations

Hopfield network using the parameters as
follows:. A = 500, B = 500, D = 100, λ = 0.02, T1 = 200, T = 100 , and the best path length is 1392.3. The
optimal path length of Hopfield network is shown in Figure 2.
232 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235

Fig.2 The optimal path length of Hopfield network

The parameters of ant colony algorithm for TSP as
follows: m = 10, T = 500, α = 1, β = 5, ρ = 0.1, Q = 600 , 1 1 and the best path length is 480.13.
τ= ,η =
D D
The optimal path length of ant colony algorithm is shown in Figure 3

Fig 3 the optimal path length of ant colony algorithm

The optimal solution of eil51 published on TSPLB[7] is 426. The optimal results of genetic
algorithms, Hopfield networks and ant colony algorithm were 1007.9, 1392.3 and 480.13.The result of ant
colony algorithm is most approach the optimal solution. The results of genetic algorithm and Hopfield
network are quite different from the value of the optimal result.
 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235 233

3.3.2. Contrast the partial and overall of the results

Genetic algorithm can ensure the population's evolution by selecting the operator, crossover
operator and mutation operator, while selection operator to ensure the best individual parent to survive in
a larger probability, crossover probability to use a certain desired cross-breeding to produces a more
excellent offspring, mutation operator to a certain mutation probability to the progeny gene mutation
expect better offspring.Because of crossover and mutation operators, genetic algorithm can escape local
optimum and make it possible to find the global optimum. The result of Hopfield network and ant colony
algorithms is good or bad depends on parameter, the value of parameter directly affect the convergence of
the algorithm and results of the pros and cons. And these two algorithms are easy to fall into local
optimum.

3.4. Comparison the implementation of algorithm

In this paper, we use the code lines of algorithm to reflect the amount of algorithm implementation.
The amount of code lines of three algorithms implemented in MATLAB are 186, 93 and 96. From the
lines of codes, the most difficult is genetic algorithm.

4. Comprehensive Evaluations

Based on the analysis in Section 3, three algorithms are compared in time complexity, space
complexity, the advantages and disadvantages of the calculation results, and difficulty level of realization,
etc. We use the application of paired comparison matrix to make comprehensive evaluation, and then give
the value of comprehensive evaluation.
The value of aij in paired comparison matrix from reference [8].
The time complexity, space complexity, the advantages and disadvantages of the calculation results
and difficulty level of realization of three algorithms can use comparison to obtain comparison matrix A
as follows.

 1 1 
 1 5 7
 3 3 
 1 1 1
1 3
 5 7 7 
 3 7 1 3 9
 1 
 3 7 1 7
 3 
 1 1 1 1
 1

 7 3 9 7 

The maximum eigenvalue of the matrix is λmax =5.3573. CI is extent of inconsistency of a pair-wise
comparison matrix A (n> 1), the formula is:

λmax ( A) − n (5)
CI =
n −1
234 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235

Then we can know CI=0.0893，RI=1.12

CI 0.0893
CR = = = 0.0798 < 0.1 (6)
RI 1.12

This shows that A is not a consistent matrix, but A is according with consistency, and the
inconsistency of A is acceptable. The maximum eigenvector after normalized of matrix A is

U A = (0.1679,0.0534,0.4619,0.2861,0.0307) Z .From this value, we can know when evaluate an algorithm is

good or bad. First, we should find the calculation results of different algorithm. Second, we calculate
local partial and overall partial of calculation results. Third, we find it`s time complexity and space
complexity. Last, we ensure the difficulty level of realization this algorithm. For find comprehensive
evaluation on these three algorithms, we analyzer the results base on section 3 can construct the
comparison matrix B1-5 from time complexity, space complexity, the advantages and disadvantages of the
calculation results, and difficulty level of realization. The value of comparison matrix B1-5 as follow:

 1 1  1  
1   1 1 1 3     1 1
 3 5 1   5  1 3 3  1 
1  5 5 1 1 1  3 3
B1 =  3 1 , B2 =  5 1 1 , B3 =  1 , B4 =  1 1 , B5 =  3 1 1
 3 3 7 3 
5 3 1
5
 1 1 5 7 1 1  3
 1 1 
       1 1   
    3 
After test, matrix B1-5 all is right. The weight vector of B1-5 are:

U1 = (0.1047 0.2583 0.6370) Z

U 2 = (0.0909 0.4545 0.4545) Z

U 3 = (0.1884 0.0810 0.7306) Z

U 4 = (0.6000 0.2000 0.2000) Z

U 5 = (0.1429 0.4286 0.4286) Z

They can be considered the point at the time complexity, space complexity, the advantages and
disadvantages of the calculation results, and difficulty level of realization of each algorithm. Finally,
calculate the total score of each algorithm.
P (GA) = 0.17 × 0.10 + 0.05 × 0.09 + 0.46 × 0.19 + 0.29 × 0.60 + 0.03 × 0.14 = 0.29
P( HNN ) = 0.17 × 0.29 + 0.05 × 0.45 + 0.46 × 0.08 + 0.29 × 0.20 + 0.03 × 0.42 = 0.18
P( ANN ) = 0.17 × 0.63 + 0.05 × 0.45 + 0.46 × 0.73 + 0.29 × 0.20 + 0.03 × 0.42 = 0.53
 Wang Hui / Systems Engineering Procedia 4 (2012) 226 – 235 235

Genetic algorithms, Hopfield networks and ant colony algorithm consolidated total scores were 0.29,
0.18, 0.53, that the best algorithm is ant colony algorithm, second is genetic algorithm, third is Hopfield
network.

5. Conclusion

This paper presents three intelligent algorithms, namely, basic genetic algorithm, Hopfield neural
network and basic ant colony algorithm, solving of the TSP problem in engineering. Then these different
kinds of algorithms are compared in time complexity, space complexity, the advantages and
disadvantages of the calculation results, and difficulty level of realization, etc. We use the engineering
application of paired comparison matrix to make comprehensive evaluation, and then give the value of
comprehensive evaluation. This method of comprehensive evaluation is relatively simple and useful.

References

[1]Zhang Jingqang, Cao Yunfu. ( 2004), A Genetic Algorithm Based on Common Path for TSP [J], Journal of Computer
Engineering and Applications, 40[20]:58~61．
[2]Chen Jing, Yang Xiaofan, Zeng Zhi. ( 2006), A Genetic Algorithm Base on Gene Bank and Multiple-Searching Method for
TSP [J],Computer Science，33(8):195~201
[3]Zhao Jianming, Yao Nianmin. (2009), Study on the Efficiency of solving TSP Based on Hopfield Network [j], Science
Technology and Engineering ,9(2):437－439
[4]Jiang Guojun. (2001), A modified algorithm of Hopfield network to solve TSP, [j]. Journal o f Zhejiang University (Science
Edition), 28(2):160~163
[5]Li Yong, Duan Zhengcheng.(2003), A New Ant System for TSPs [J], Journal of Computer Engineering and Applications,
39(17):103~106
[6]Wang Zhengying, Shi Bingxin.(2001) , Solving QoS Multicast Routing Problem Based on Heuristic Genetic Algorithm [J],
Chinese Journal of computer, 24(1):55~61
[7]http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsplib.html
[8]Gan Yingai etc,2005, Tsinghua University Press ,Operations Research.