# An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP

Authors: Yong Deng; Yang Liu; Deyun Zhou
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A new initial population strategy has been developed
to improve the genetic algorithm for solving the well-known combinatorial
optimization problem, traveling salesman problem. Based on thek-means
algorithm, we propose a strategy to restructure the traveling route by reconnecting
each cluster. The clusters, which randomly disconnect a link to connect
its neighbors, have been ranked in advance according to the distance among
cluster centers, so that the initial population can be composed of the random
traveling routes. This process is k-means initial population strategy. To test the performance of our strategy, a series of experiments on 14 different
TSP examples selected from TSPLIB have been carried out. The results show
that KIP can decrease best error value of random initial population strategy
and greedy initial population strategy with the ratio of approximately between
29.15% and 37.87%, average error value between 25.16% and 34.39% in the
same running time.


---

## Body

## 1. Introduction

Traveling salesman problem (TSP) is a well-known NP-hard problem in many real-world applications, such as job-shop scheduling and VLSI routing [1, 2]. The aim of TSP is to find a complete, minimal-cost tour when a salesman is required to visit each of n given cities once and only once [3]. So far, TSP has often been a touchstone for new strategies and algorithms proposed to solve combinatorial optimization problem. In this paper, we consider the symmetric TSP, where the distance from city i to city j is the same as from city j to city i.Many methods have been developed for solving TSP, including exact algorithms and approximate algorithms. The exact algorithms are carried out to find the optimal solution from all valid solutions in a number of steps. But, because of exponential complexity [3], they are always infeasible if the scale of TSP becomes large, for example, 100 cities with approximately 1
0
155 different solutions. In contrast, the approximate algorithms, especially many bioinspired algorithms [4–9], can obtain accepted solutions for many NP-hard problems with (relatively) short running time. These approaches are usually very simple, like Lin-Kernigan [10], colony optimization (ACO) [11], and so on [12, 13]. All of them are efficient approaches in most of the problems, but ACO, for example, is not suitable for large-scale TSP because of its computational cost O
(
m
n
2
), in which m is the ant numbers and n is the number of cities.Genetic algorithm (GA) [14] is a global search algorithm appropriate for problems with huge search, for example, TSP, in which the initial population decides iterations, the crossover realizes the construction of the offspring, and the mutation operator maintains the diversity of the individuals. So far, there is a lot of literature to improve the effectiveness of crossover and mutation [2, 15–19]. Besides, as the first step of any GA, how to initialize an efficient population plays an important role in the process of solving a problem based on GA. Toǧan and Daloǧlu [20] adopted the member grouping strategy to reduce the size of the problem and the initial population strategy to reduce the number of generations. Chen et al. [21] developed a feature-based initial population method for the optimization of job-shop problem. Sharma et al. [22] proposed a domain-specific initial population strategy for compliant mechanisms. Ahmed [23] used a sequential sampling method for generating initial population.In this paper, a new initial population method has been developed to increase the quality of initial population. Based on this method, the application performance of GA on TSP becomes more efficient. The rest of the paper is organized as follows. In Section2, some related background theories are presented. In Section 3, the proposed method is described. In Section 4, experimental results are evaluated. In the final section, a brief conclusion is given.


## 2. Preliminaries

Some basic theories are shown in this section, including TSP, GA, andk-means clustering.


### 2.1. Traveling Salesman Problem

TSP is one of the most widely studied combination optimization problems [3]. Mathematically, this problem can be stated as follows:(1)
T
d
=
∑
i
=
1
n
-
1
d
V
i
,
V
i
+
1
+
d
V
n
,
V
1
,where path set P
a
t
h
(
π
)
=
{
V
1
,
V
2
,
…
,
V
n
} is a permutation of cities {
1,2
,
…
,
n
} and d
(
V
i
,
V
i
+
1
) represents the distance from city V
i to city V
j. The aim of TSP is to find a path from path set P
a
t
h
(
π
) to minimize T
d.


### 2.2. Genetic Algorithm

Genetic algorithm (GA) is an evolutionary algorithm based on natural election, developed by Holland [24]. It is to find approximate solutions for optimization and search problems by computer simulation [25]. The aim of GA is to achieve better results through selection, crossover, and mutation. Selection is to select the best solutions preferentially according to the fitness function from the population. The fitness function (f
(
T
d
)) is defined over the genetic representation and measures the quality of the represented solution. In this paper, 1
/
T
d is assigned to f
(
T
d
). Crossover and mutation are used to generate a second generation population of solutions from those selected. Crossover can vary the population from one generation to the next by recombining “parent” solutions. Mutation alters some gene of one solution to avoid local optimal solutions. In general, the basic steps of GA for a problem are shown in Algorithm 1.Algorithm 1:A simple genetic algorithm for TSP (x
y).
//x
y is a city-location matrix
t
←
1
// t is the current iterations
initializeP
o
p
(
t
) with N chromosomes P
o
p
i
(
t
)
// N is the pop size
while not (terminating condition) do
for i
←
1 to N do
f
i
←
f
(
P
o
p
i
(
t
)
)
// f is the fitness function
for i
←
1 to N do
N
e
w
P
o
p
i
(
t
+
1
) ← randomly choose P
o
p
i
(
t
)
∈
P
o
p
(
t
) with p
j
=
f
j
/
∑
k
=
1
N
f
k
C
r
o
s
s
P
o
p
(
t
+
1
) ← recombine (
N
e
w
P
o
p
(
t
+
1
)
) with P
c
//P
c is the crossover probability
M
u
t
P
o
p
(
t
+
1
) ← mutate (
C
r
o
s
s
P
o
p
(
t
+
1
)
) with P
m
//P
m is the mutation probability
P
o
p
(
t
+
1
)
←
M
u
t
P
o
p
(
t
+
1
)
t
←
t
+
1


### 2.3.k-Means Clustering

k-means clustering is as well-known as Lloyd’s algorithm [26], which aims to find k centers from n observations to minimize the mean distance from each observation to their nearest center. More details about the concepts and description of k-means clustering can be found in a lot of literature [26–28]. In this paper, we present a simple k-means clustering to the initial population.


## 2.1. Traveling Salesman Problem

TSP is one of the most widely studied combination optimization problems [3]. Mathematically, this problem can be stated as follows:(1)
T
d
=
∑
i
=
1
n
-
1
d
V
i
,
V
i
+
1
+
d
V
n
,
V
1
,where path set P
a
t
h
(
π
)
=
{
V
1
,
V
2
,
…
,
V
n
} is a permutation of cities {
1,2
,
…
,
n
} and d
(
V
i
,
V
i
+
1
) represents the distance from city V
i to city V
j. The aim of TSP is to find a path from path set P
a
t
h
(
π
) to minimize T
d.


## 2.2. Genetic Algorithm

Genetic algorithm (GA) is an evolutionary algorithm based on natural election, developed by Holland [24]. It is to find approximate solutions for optimization and search problems by computer simulation [25]. The aim of GA is to achieve better results through selection, crossover, and mutation. Selection is to select the best solutions preferentially according to the fitness function from the population. The fitness function (f
(
T
d
)) is defined over the genetic representation and measures the quality of the represented solution. In this paper, 1
/
T
d is assigned to f
(
T
d
). Crossover and mutation are used to generate a second generation population of solutions from those selected. Crossover can vary the population from one generation to the next by recombining “parent” solutions. Mutation alters some gene of one solution to avoid local optimal solutions. In general, the basic steps of GA for a problem are shown in Algorithm 1.Algorithm 1:A simple genetic algorithm for TSP (x
y).
//x
y is a city-location matrix
t
←
1
// t is the current iterations
initializeP
o
p
(
t
) with N chromosomes P
o
p
i
(
t
)
// N is the pop size
while not (terminating condition) do
for i
←
1 to N do
f
i
←
f
(
P
o
p
i
(
t
)
)
// f is the fitness function
for i
←
1 to N do
N
e
w
P
o
p
i
(
t
+
1
) ← randomly choose P
o
p
i
(
t
)
∈
P
o
p
(
t
) with p
j
=
f
j
/
∑
k
=
1
N
f
k
C
r
o
s
s
P
o
p
(
t
+
1
) ← recombine (
N
e
w
P
o
p
(
t
+
1
)
) with P
c
//P
c is the crossover probability
M
u
t
P
o
p
(
t
+
1
) ← mutate (
C
r
o
s
s
P
o
p
(
t
+
1
)
) with P
m
//P
m is the mutation probability
P
o
p
(
t
+
1
)
←
M
u
t
P
o
p
(
t
+
1
)
t
←
t
+
1


## 2.3.k-Means Clustering

k-means clustering is as well-known as Lloyd’s algorithm [26], which aims to find k centers from n observations to minimize the mean distance from each observation to their nearest center. More details about the concepts and description of k-means clustering can be found in a lot of literature [26–28]. In this paper, we present a simple k-means clustering to the initial population.


## 3. Proposed Method

The first step of GA is to generate an initial population in which a set of possible solutions is contained. The quality of this population plays an important role in solving a problem by GA [20, 29]. As can be seen from Figure 1, in which a TSP of 14 cities is considered, Figure 1(d) is the best solution obtained from 3000 solutions generated randomly (RIP) [30] and Figure 1(b) is the best solution from 3000 alternatives with the proposed method (KIP), respectively. Figure 1(c) is the best solution of this problem.Figure 1
The processes to initialize the population withk-means clustering. Firstly, 14 nodes are clustered into 4 groups. Secondly, GA is used to obtain the local optimal path of each group and a global optimal path of 4 groups. Finally, disconnect and rewire to obtain the initial population.
(a)
k-means clustering
(b)
Randomly rewire to generate initial population
(c)
The best solution
(d)
Randomly initial populationKIG is developed for TSP solution based onk-means clustering and GA. k-means clustering is used to divide a large-scale TSP into some small problems to obtain local optimal solutions. Then, GA is carried out to globally optimize the alternatives generated by randomly rewiring each local optimal solution. Without loss of generality, consider a TSP with N cities, in which (
x
i
,
y
i
) denotes the location of city i, i
=
1,2
,
…
,
N. An initial population can be obtained as follows.Step 1.
N cities cluster into K groups with K
=
[
N
+
0.5
] based on k-means clustering.Step 2.
GA is used to obtain the local optimal path of each group and a global optimal path ofK groups.Step 3.
According to the global optimal path, one edge of each local optimal path disconnects to rewire the front and back groups.Step 4.
Repeating Step3, an initial population can be generated.Considering the 14 cities example as shown in Figure1, 14 cities cluster into 4 groups G
1
,
G
2
,
G
3
,
G
4. A global optimal path {
G
1
,
G
2
,
G
3
,
G
4
,
G
1
} (the black path) and 3 local optimal paths (the red and blue paths) can be seen from Figure 1(a). Then, select one edge from each group (L
1
,
L
2
,
L
3) and disconnect to rewire the front and back group, such as Figure 1(a) (disconnect) to Figure 1(b) (rewire). From Figure 1(b) (the best solution from the initial population) to Figure 1(c) (the best solution of this problem), one step ({
R
1
,
R
2
,
R
3
}
→
{
R
1
,
R
3
,
R
2
}) can be achieved. Besides, a performance about three methods on example a280 selected from TSPLIB [35] is shown in Figure 2.Figure 2
Three methods to initialize the population of problem a280 [35]. (a) is RIG, (b) is generated by a greedy method (GIP) [25], (c) is KIP, and (d) is the best solution of this problem.
(a)
Randomly initial population
(b)
Greedy initial population
(c)
k-means clustering initial population
(d)
The best solution


## 4. Experimental Results

We conduct the experiments on a computer with Intel Core i3-2120 3.30 GHz processor using MATLAB R2013a. To test the efficiency of the proposed method, 14 different TSP are taken from the TSPLIB [35] and 10 trials are examined for each problem. Without loss of generality, an improved GA developed by Kirk [34] was used to test the efficiency of the proposed method. The basic steps of this improved method are shown in Algorithm 2.Algorithm 2:An improved genetic algorithm for TSP (x
y) developed by Kirk [34].
//x
y is a city-location matrix
t
←
1
// t is the current iterations
initializeP
o
p
(
t
) with N chromosomes P
o
p
i
(
t
)
// N is the pop size
while not (terminating condition) do
for i
←
1 to N do
f
i
←
f
(
P
o
p
i
(
t
)
)
// f is the fitness function
for i
←
1 to N do
P
o
p
i
(
t
+
1
) ← choose P
o
p
k
(
t
) satisfy f
k
>
f
j
,
j
∈
{
i
,
i
+
1
,
i
+
2
,
i
+
3
}    and j
≠
k
P
o
p
i
+
1
(
t
+
1
) ← mutate P
o
p
i
(
t
+
1
) by flip mutation method [31]
P
o
p
i
+
2
(
t
+
1
) ← mutate P
o
p
i
(
t
+
1
) by swap mutation method [32]
P
o
p
i
+
3
(
t
+
1
) ← mutate P
o
p
i
(
t
+
1
) by slide mutation method [33]
i
←
i
+
4
t
←
t
+
1Firstly, the same iteration (20000) is considered to analyze the time cost and the quality of the solutions. There is no crossover but three mutations occurred100
% at each iteration in the software. As we can see from Table 1, KIP is superior to other methods: 64.29
% of best error results and 78.57
% of average error results. Then, the same running time is used to analyze the iterations and the quality of the solutions by three methods on each problem. 64.29
% of best error results and 78.57
% of average error results demonstrate KIP more efficiently as shown in Table 2. Besides, Figure 3 shows the best solution varies by time about example pcb442.Table 1
Results of different strategies with the same iterations.
Method
RIP
GIP
KIP
Examples
Best err. (%)
Ave. err. (%)
Ave. time (s)
Best err. (%)
Ave. err. (%)
Ave. time (s)
Best err. (%)
Ave. err. (%)
Ave. time (s)
berlin52
0.0000
5.1418
16.9338
0.0000
1.9531
18.2832
0.0000
3.0120
16.3208
kroA100
2.3761
4.8328
20.3049
0.2787
4.0082
22.5599
0.1035
2.5505
20.3318
pr144
1.3889
4.7425
23.4091
3.1847
6.0775
26.6297
2.0176
3.5041
26.5335
ch150
5.6974
9.5032
23.8436
4.1780
5.9298
27.4067
5.1038
6.7850
25.4257
kroB150
2.9646
6.4505
23.8947
6.3054
8.2309
27.4617
3.3544
5.8072
25.5628
pr152
1.4383
4.4424
24.1544
3.1397
4.2628
27.4174
2.5998
3.5800
26.4204
rat195
6.7733
9.2618
27.2911
7.8855
11.2154
30.5484
8.7133
11.3242
30.0717
d198
3.9011
6.8199
27.5327
5.1889
6.3098
32.1868
2.8149
4.5911
32.5780
kroA200
10.4079
13.3538
27.8636
11.1678
12.2504
32.4812
5.3725
8.8791
31.8691
ts225
16.0522
17.9204
29.5267
14.6896
15.499
33.6234
10.3008
14.5409
34.1776
pr226
5.2754
9.1196
29.7816
8.6261
12.9046
35.4601
4.9741
6.1991
36.3008
pr299
20.1269
24.5098
35.0112
29.1241
30.3129
42.5489
14.6584
17.0753
44.6964
lin318
30.1053
34.0994
36.2227
24.9692
31.5281
45.8366
15.0669
17.2412
47.2462
pcb442
54.7724
58.4570
45.8070
44.7984
49.0039
57.0011
22.5887
24.0461
62.8187
Average
11.5200
14.9039
27.9698
11.6812
14.2490
32.8175
6.9763
9.2240
32.8824Table 2
Results of different strategies with the same time.
Method
RIP
GIP
KIP
Examples
Best err. (%)
Ave. err. (%)
Ave. time (s)
Best err. (%)
Ave. err. (%)
Ave. time (s)
Best err. (%)
Ave. err. (%)
Ave. time (s)
berlin52
2.2890
5.6054
16.3333
4.5497
5.4338
16.3333
0.0000
3.0120
16.3208
kroA100
2.4233
4.8220
20.3425
0.7447
4.4327
20.3425
0.1035
2.5505
20.3318
pr144
1.5751
2.9365
26.5358
1.8611
4.8923
26.5358
2.0176
3.5041
26.5335
ch150
4.7941
9.8965
25.4282
5.0946
7.7747
25.4282
5.1038
6.7850
25.4257
kroB150
2.9470
5.9548
25.5686
3.4723
6.9908
25.5686
3.3544
5.8072
25.5628
pr152
3.0562
4.2483
26.4266
1.7454
3.9500
26.4266
2.5998
3.5800
26.4204
rat195
6.3251
8.6355
30.0770
11.4580
12.9902
30.0770
8.7133
11.3242
30.0717
d198
4.4745
5.3608
32.5886
4.4171
4.9603
32.5886
2.8149
4.5911
32.5780
kroA200
9.3804
11.7009
31.8710
8.4947
11.349
31.871
5.3725
8.8791
31.8691
ts225
9.7628
13.5387
34.1798
11.1856
16.8642
34.1798
10.3008
14.5409
34.1776
pr226
6.6253
7.0874
36.3014
9.6295
12.8062
36.3014
4.9741
6.1991
36.3008
pr299
18.0739
21.8767
44.7099
24.5210
28.4839
44.7099
14.6584
17.0753
44.6964
lin318
25.4203
27.0580
47.2527
28.4007
29.9471
47.2527
15.0669
17.2412
47.2462
pcb442
40.6996
43.8170
62.8216
41.6218
45.9415
62.8216
22.5887
24.0461
62.8187
Average
9.8462
12.3242
32.8884
11.2283
14.0583
32.8884
6.9763
9.2239
32.8824Figure 3
Three strategies, for example, pcb442.


## 5. Conclusion

In this paper, we present a new initial population strategy (KIP) to improve GA that is used to find the optimal solution for the well-known traveling salesman problem (TSP). To test the performance of this strategy, 14 different TSP examples selected from TSPLIB and two other methods (RIP and GIP) are used to experimentalize. The results show that the proposed method is efficient:64.29
% of best error results and 78.57
% of average error results (Tables 1 and 2). KIP can decrease best error value of RIP and GIP with the ratio of approximately between 39.44
% and 40.28
%, average error value between 35.27
% and 38.11
% in the same iterations (Table 1). KIP can decrease best error value of RIP and GIP with the ratio of approximately between 29.15
% and 37.87
%, average error value between 25.16
% and 34.39
% in the same running time.



---

*Source: 212794-2015-10-05.xml*