Genetic Algorithm with Optimal Recombination for
the Asymmetric Travelling Salesman Problem
arXiv:1706.06920v2 [] 19 Dec 2017

Anton V. Eremeev, Yulia V. Kovalenko∗
December 20, 2017

Sobolev Institute of Mathematics,
4, Akad. Koptyug avenue,
630090, Novosibirsk, Russia.
Email: eremeev@oﬁm.oscsbras.ru, julia.kovalenko.ya@yandex.ru
Abstract
We propose a new genetic algorithm with optimal recombination for the
asymmetric instances of travelling salesman problem. The algorithm incorporates
several new features that contribute to its effectiveness: 1. Optimal recombination
problem is solved within crossover operator. 2. A new mutation operator performs
a random jump within 3-opt or 4-opt neighborhood. 3. Greedy constructive
heuristic of W. Zhang and 3-opt local search heuristic are used to generate the
initial population. A computational experiment on TSPLIB instances shows that
the proposed algorithm yields competitive results to other well-known memetic
algorithms for asymmetric travelling salesman problem.
Keywords: Genetic Algorithm, Optimal Recombination, Local Search

1

Introduction

Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization
problem [8]. Given a complete digraph G with the set of vertices V = {v1 , . . . , vn }, the
set of arcs A = {(vi , vj ) : vi , vj ∈ V, i 6= j} and arc weights (lengths) cij ≥ 0 of each
arc (vi , vj ) ∈ A, the TSP asks for a Hamiltonian circuit of minimum length. If cij 6= cji
for at least one pair (vi , vj ) then the TSP is called the Asymmetric Travelling Salesman
Problem (ATSP). Numerous metaheuristics and heuristics have been proposed for the
TSP and the genetic algorithms (GAs) are among them (see e.g. [2, 3, 7, 16, 18]).
The performance of GAs depends signiﬁcantly upon the choice of the crossover operator, where the components of parent solutions are combined to build the oﬀspring.
A supplementary problem that emerges in some versions of crossover operator is called
Optimal Recombination Problem (ORP). Given two feasible parent solutions, ORP consists in ﬁnding the best possible oﬀspring in view of the basic principles of crossover [13].
∗

This research is supported by the Russian Science Foundation grant 15-11-10009.

1

Experimental results [3, 16, 18] indicate that ORP may be used successfully in genetic
algorithms.
In this paper, we propose a new GA using the ORP with adjacency-based representation to solve the ATSP. Two simple crossover-based GAs for ATSP using ORPs were
investigated in [7] but no problem-speciﬁc local search procedures or ﬁne-tuning of parameters were used. In comparison to the GAs from [7], the GA proposed in this paper
uses a 3-opt local search heuristic and a problem-speciﬁc heuristic of W. Zhang [19] to
generate the initial population. In addition, this GA applies a new mutation operator,
which performs a random jump within 3-opt or 4-opt neighborhood. The current GA is
based on the steady state replacement [14], while the GAs in [7] were based on the elitist
recombination (see e.g. [9]). The experimental evaluation on instances from TSPLIB library shows that the proposed GA yields results competitive to those obtained by some
other well-known evolutionary algorithms for the ATSP.

2

Genetic Algorithm

The genetic algorithm is a random search method that models a process of evolution of
a population of individuals [14]. Each individual is a sample solution to the optimization
problem being solved. The components of an individual are called genes. Individuals of a
new population are built by means of reproduction operators (crossover and/or mutation).
The crossover operator produces the oﬀspring from two parent individuals by combining
and exchanging their genes. The mutation adds small random changes to an individual.
The formal scheme of the GA with steady state replacement is as follows:
Steady State Genetic Algorithm
Step 1. Construct the initial population and assign t := 1.
Step 2. Repeat steps 2.1-2.4 until some stopping criterion is satisﬁed:
2.1. Choose two parent individuals p1 , p2 from the population.
2.2. Apply mutation to p1 and p2 and obtain individuals p′1 , p′2 .
2.3. Create an oﬀspring p′ , applying a crossover to p′1 and p′2 .
2.4. Choose a least ﬁt individual in population and replace it by p′ .
2.5. Set t := t + 1.
Step 3. The result is the best found individual w.r.t. objective function.
Our implementation of the GA is initiated by generating N initial solutions, and the
population size N remains constant during the execution of the GA. Two individuals
of the initial population are constructed by means of the problem-speciﬁc heuristic of
W. Zhang [19]. The heuristic ﬁrst solves the Assignment Problem, and then patches the
cycles of the optimum assignment together to form a feasible tour. R. Karp [12] proposed
two variants of the patching. In the ﬁrst one, some cycle of maximum length is selected
and the remaining cycles are patched into it. In the second one, cycles are patched one
by one in a special sequence, starting with a shortest cycle. All other N − 2 individuals
of the initial population are generated using the arbitrary insertion method [18], followed
by a local search heuristic with a 3-opt neighborhood (see Subsection 2.2).
Each parent on Step 2.1 is chosen by s-tournament selection: sample randomly s individuals from the current population and select a ﬁttest among them.
Operators of crossover and mutation are described in Subsections 2.1 and 2.3.
2

2.1

Recombination Operators

Suppose that feasible solutions to the ATSP are encoded as vectors of adjacencies, where
the immediate predecessor is indicated for each vertex. Then the optimal recombination
problem with adjacency-based representation [6] consists in ﬁnding a shortest travelling
salesman’s tour which coincides with two given feasible parent solutions in arcs belonging
to both solutions and does not contain the arcs absent in both solutions. These constraints
are equivalent to a requirement that the recombination should be respectful and gene
transmitting as deﬁned in [13]. The ORP with adjacency-based representation for the
ATSP is shown to be NP-hard but it can be reduced to the TSP on graphs with bounded
n
vertex degrees [6]. The resulting TSP may be solved in O(n2 2 ) time by means of an
adaptation of the algorithm proposed by D. Eppstein [5]. A detailed description of the
reduction can be found in [6]. An experimental evaluation of the ORP with adjacencybased representation in a crossover-based GA was carried out in [7]. The experiments
showed that the CPU cost of solving the ORPs in this GA is acceptable and decreases with
iterations count, due to decreasing population diversity. In what follows, the optimized
crossover operator, which solves the ORP with adjacency-based representation will be
called Optimized Directed Edge Crossover (ODEC). This operator may be considered as
a deterministic “direct descendant” of Directed Edge Crossover (DEC) [17]. Unlike DEC,
Optimized Directed Edge Crossover guarantees genes transmission.
An alternative way for solution encoding to the ATSP is the position-based representation, where a feasible solution is encoded as a sequence of the vertices of the TSP tour.
The computational experiment performed in [7] indicates that the ORP for the adjacencybased representation has an advantage over the ORP for the position-based representation
on ATSP instances from TSPLIB library. Therefore, in this paper we consider only the
adjacency-based representation.
Note that most of the known GAs for the TSP (see e.g. [2, 10, 16]) apply a local
search on GA iterations. However an optimal recombination may be considered as a bestimproving move in a neighborhood deﬁned by two parent solutions. So we use a local
search only at the initialization stage.

2.2

Local Search Heuristic

In general, k-opt neighborhood for TSP is deﬁned as the set of tours that can be obtained
from a given tour by replacing k arcs. Our Local Search Heuristic is a typical local search
heuristic that explores a subset of 3-opt neighborhood.
We try to improve the current tour by changing three of its arcs (see Figure 1). To
this end, we consider all possible arcs of the current tour as candidates for arc (vi1 , vi2 ) to
be deleted in the order of decreasing length. Observe that, in our search, the possibilities
for choosing vi3 (arc (vi1 , vi3 ) is added) may be limited to those vertices that are closer
to vi1 than vi2 . To use this property, for each vertex v we store a list of the remaining
vertices in the order of increasing length from v. Considering candidates for vi3 , we start
at the beginning of vi1 ’s list and proceed down the list until a vertex u with cvi1 ,u ≥ cvi1 ,vi2
is reached. Moreover, only the ⌈0.2n⌉ nearest vertices are stored in the sorted list of
each vertex, which allows to reduce the running time and the memory usage as observed
in [10]. Finally, among all vertices belonging to the closed cycle C created by (vi1 , vi3 ),
we choose a vertex vi5 that would produce the most favorable 3-change. Local Search
3

Heuristic stops if no favorable 3-change is possible, otherwise it proceeds to the next step
with a new tour obtained.

Figure 1: 3-change and quad change.
In order to reduce the running time of the presented local search heuristic, we use the
well-known “donЎt look bits” and “ﬁrst improving move” strategies presented in [10] for
local search based on 3-opt neighborhood.

2.3

Mutation Operators

The mutation is applied to each parent solution on Step 2.2 with probability pmut , which
is a tunable parameter of the GA. We implement two mutation operators that perform a
random jump within 3-opt or 4-opt neighborhood. Each time one of the operators is used
for mutation with equal probability.
The ﬁrst mutation operator makes a 3-change (see Section 2.2). First of all, an
arc (vi1 , vi2 ) is chosen at random among all arcs of the given tour. After that, an
arc (vi1 , vi3 ) is chosen using the following idea from [11]. For each possible arc (vi1 , u),
we calculate F (u) = cv,u + |C(u)| · caver , where v is the immediate predecessor of u in the
given tour, |C(u)| is the length of the cycle created by u and caver is the average weight of
arcs in graph G. Then an arc (vi1 , vi3 ) is chosen uniformly at random among the top 50%
of arcs (vi1 , u) w.r.t. F (u) value. The reason for taking into account the value of |C(u)|
when (vi1 , vi3 ) is being chosen is that the bigger the value of C(u) the more options for
(vi4 , vi5 ) will become available subsequently. Finally, we choose the arc (vi6 , vi5 ) among
the arcs of C(vi3 ) so that the most favorable 3-change is produced.
The second mutation operator is based on 4-opt neighborhood and implements a quad
change [11] (see Figure 1). Here two arcs (vi1 , vi2 ) and (vi7 , vi8 ) are selected randomly and
removed, while the other two arcs for deletion are chosen so that the most favorable quad
change is obtained.

3

Computational Experiments

This section presents the results of computational experiments on the ATSP instances
from TSPLIB library [15]. The GA was programmed in Java (NetBeans IDE 7.2.1) and
tested on a computer with Intel Core 2 Duo CPU E7200 2.53 GHz processor, 2 Gb RAM.
In the experiments, we set the population size N = 100, the tournament size s = 10 and
the mutation probability pmut = 0.1.
Our GA is restarted every time as soon as the current iteration number becomes twice
the iteration number when the best incumbent was found, until the overall execution
4

time reached the limit. Moreover, if the greedy heuristic of W. Zhang generates only
one subcycle, this indicates that the ATSP instance was solved to optimality, and the
algorithm stops. The best solution found over all restarts was returned as the result. We
have also tested an alternative approach, where the GA runs for the whole given period
of time without restarts but it turned to be inferior to the GA with the restart rule.
The ﬁrst computational experiment is aimed at comparison of the performance of
our GA based on ODEC (GAODEC ) with SAX/RAI memetic algorithm (MASAX/RAI )
from [2], which has one of the best results in the literature on metaheuristics for the
ATSP. In order to put the considered algorithms into equal positions, GAODEC was given
the CPU-time limit (denoted as T ) by a factor 3 less than the CPU resource used by
MASAX/RAI in [2]. This scaling factor chosen on the basis a rough comparison of computers by means of performance table [4]. For a statistical comparison, on each instance
we executed GAODEC 1000 times. In each execution GAODEC was given the same CPUtime limit indicated above. In [2], MASAX/RAI was run 20 times on each instance. Table 1
shows the obtained results, where Fopt represents the frequency of ﬁnding an optimum,
∆err is the average percentage deviation of the length of a resulting solution from the
optimum, ∆init denotes the average percentage deviation of the length of the best initial
solution from the optimum. As seen from Table 1, GAODEC achieved 100% success rate
on 17 out of 26 instances. On each instance, GAODEC found optima in not less than
91% of runs.
The statistical analysis of experimental data was carried out using a signiﬁcance test
of the null hypothesis from [1], Ch. 8, §2. Suppose that two algorithms are compared
in terms of probability of “success”, where “success” corresponds to ﬁnding an optimal
solution. Let P1 and P2 denote the probabilities of success for the considered algorithms.
The null hypothesis is expressed by P1 = P2 .
The test procedure is as follows. Under the null hypothesis, the estimate of common
ˆ N1 +Pˆ2 N2
success rate is P̂ = P1 N
, where Pˆ1 denotes the frequency of success in N1 runs for
1 +N2
the ﬁrst algorithm and Pˆ2 is the frequency of success in N2 runs for the second algorithm.
Then the diﬀerence Pˆ1 − Pˆ2 is expressed
q in units of the standard deviation by calculating
ˆ
ˆ
ˆ = P̂ (1−P̂ ) + P̂ (1−P̂ ) is the estimation of the standard
the statistic A = |P1 −P2 | , where SD
ˆ
SD

N1

N2

deviation.
It is supposed that statistic A is normally distributed. To test the null hypothesis
versus the alternative one at a conﬁdence level α, we compare the computed A to the
quantile of standard normal distribution zα/2 . If A is lager than zα/2 , the null hypothesis
is rejected. Otherwise the null hypothesis is accepted. At α = 0.05 we have z0.025 = 1.96.
The values of statistic A for algorithms GAODEC and MASAX/RAI are found and presented
in the last column of Table 1 (‘∗’ indicates the statistical signiﬁcance diﬀerence between
GAODEC and MASAX/RAI at level α = 0.05).
In 14 out of 26 instances, GAODEC ﬁnds an optimum more frequently than MASAX/RAI
(in 12 cases among these, the diﬀerence between the frequencies of ﬁnding an optimum
is statistically signiﬁcant). Both algorithms demonstrate 100% frequency of obtaining
an optimum on 10 problems. Note that the heuristic of W. Zhang is very eﬃcient on
series rbg and the optimal solutions to all rbg instances were found in the considered
algorithms at the initialization stage. MASAX/RAI slightly outperforms GAODEC only
on two instances ftv90 and ftv100, but the diﬀerences are not statistically signiﬁcant.
Moreover, the average quality of the resulting solutions for GAODEC is approximately in
5

Table 1: Computational Results for the ATSP Instances
Instance

ftv33
ftv35
ftv38
p43
ftv44
ftv47
ry48p
ft53
ftv55
ftv64
ft70
ftv70
ftv90
ftv100
kro124p
ftv110
ftv120
ftv130
ftv140
ftv150
ftv160
ftv170
rbg323
rbg358
rbg403
rbg443
Average

∆init
0.00
0.00
0.00
0.00
0.098
0.199
0.978
0.438
0.002
0.032
0.367
1.025
0.063
0.386
0.164
0.287
0.156
0.342
0.111
0.739
0.026
0.108
0.00
0.00
0.00
0.00
0.212

GAODEC
Fopt
1
1
1∗
1∗
1∗
1
0.997∗
1
1
1
1∗
1∗
0.976
0.92
0.996∗
0.972
0.912∗
0.934
0.947∗
0.982∗
1∗
1∗
1
1
1
1
0.986

Genetic Algorithms
GAER
∆err
∆init
Fopt
∆err
0.00
0.00
1
0.00
0.00
0.00
1
0.00
0.00
0.131
1
0.00
0.00
0.00
1
0.00
0.00
0.167
0.874
0.078
0.00
0.338
1
0.00
0.0001
3.511
0.520
0.092
0.00
5.073
0.668
0.035
0.00
0.002
1
0.00
0.00
0.376
0.989
0.002
0.00
0.321
0.583
0.013
0.00
1.525
0.660
0.098
0.003
0.318
0.516
0.007
0.013
1.092
0.784
0.016
0.0001
0.288
0.322
0.033
0.003
0.305
0.854
0.025
0.008
2.463
0.430
0.506
0.008
1.841
0.361
0.068
0.004
0.601
0.463
0.065
0.002
1.358
0.532
0.068
0.00
0.958
0.491
0.099
0.00
0.334
0.222
0.141
0.00
0.00
1
0.00
0.00
0.00
1
0.00
0.00
0.00
1
0.00
0.00
0.00
1
0.00
0.0016
0.808
0.741
0.0518

M ASAX/RAI
A
0
0
0
0
11.6
0
24.9
19.9
0
3.3
22.9
20.2
23.6
8.6
31.8
9.4
22.9
26.8
23.7
23.5
26.1
35.7
0
0
0
0
12.9

T,
sec.
0.097
0.11
0.103
0.16
0.137
0.157
0.187
0.187
0.167
0.22
0.32
0.277
0.317
0.4
0.457
0.57
0.73
0.727
0.887
0.897
1.093
1.307
0.03
0.03
0.032
0.033
0.371

∆init
12.83
0.14
0.13
0.05
7.01
2.70
5.42
18.20
3.61
3.81
1.88
3.33
3.67
3.24
6.46
4.7
8.31
3.12
2.23
2.3
1.71
1.38
0.00
0.00
0.00
0.00
3.701

Fopt
1
1
0.25
0.55
0.35
1
0.85
1
1
1
0.4
0.95
1
1
0.90
0.90
0.35
0.90
0.70
0.90
0.80
0.75
1
1
1
1
0.829

∆err
0.00
0.00
0.10
0.01
0.44
0.00
0.03
0.00
0.00
0.00
0.03
0.01
0.00
0.00
0.01
0.02
0.14
0.01
0.08
0.01
0.02
0.05
0.00
0.00
0.00
0.00
0.0369

A
0
0
27.6
21.3
25.7
0
8.8
0
0
0
24.6
7.1
0.7
1.3
5.6
1.9
8.3
0.6
4.7
2.6
14.2
15.9
0
0
0
0
6.6

23 times better than the average quality for MASAX/RAI . The quality of initial solutions
is better in our algorithm. (Note that we use the local search at the initialization stage,
while MASAX/RAI applies a local search only on GA iterations.)
Recently, Tinós at el. [16] proposed a GA with new crossover operator GAPX, which
presents very competitive results in terms of frequencies of ﬁnding an optimum, but its
CPU resource usage is signiﬁcantly higher than that of GAODEC . On all of 16 TSPLIBinstances tested in [16] GA with GAPX demonstrated 100% success, while GAODEC
displayed 99.96% success on average. However, the average CPU-time T of our GA was
0.22 sec. on these instances, and the overall CPU-time of GA with GAPX was 98.38 sec.
on a similar computer.
In the second experiment, we compare our steady state GA to the similar GA with
the population management strategy known as elitist recombination [9] (GAER ) under
the same CPU-time limit. The results are also listed in Table 1. The eighth column
represents the values of statistic A for comparison of GAER against GAODEC on all ATSP
instances. We estimate the average frequency of ﬁnding optimal solutions for GAER
as approximately 60% of the average frequency for GAODEC (the diﬀerence between the
frequencies is statistically signiﬁcant), except for 10 of 26 instances where both algorithms
have 100% success. Note that the GA with elitist recombination maintains the population
diversity better. Due to this reason, the GA with elitist recombination outperformed the
steady state GA in our preliminary experiments with no restarts, which were organized
analogously to the experiments in [7]. The restarts performed in GAODEC allow to avoid
localization of the search and restore the population diversity, leading to better results.
We carried out the third experiment in order to compare the optimized crossover
6

ODEC to its randomized prototype DEC. This experiment clearly showed an advantage
of ODEC over DEC. The modiﬁcation of GAODEC , where operator DEC substitutes
ODEC, on average gave only 45% frequency of obtaining an optimum within the same
CPU time limit. Moreover, for the large-scale problems such as ftv120, ftv130, ftv140,
ftv150 and ftv170 the GA with DEC found optimal solution no more than once out of
1000 runs.
We also estimate that the average frequency of success of the GAs with optimal recombination reported in [7] is twice as small compared to such frequency for GAODEC ,
even though the GAs in [7] were given more CPU time.

4

Conclusions

We proposed a steady-state GA with adjacency-based representation using an optimal
recombination and a local search to solve the ATSP. An experimental evaluation on instances from TSPLIB library shows that the proposed GA yields results competitive to
those of some other state-of-the-art genetic algorithms. The experiments also indicate
that the proposed GA dominates a similar GA based on the population management
strategy, known as elitist recombination. The restarts performed in the proposed GA
allow to avoid localization of search and restore the population diversity, leading to better
results when the steady-state population management is used. The experiments also show
an advantage of the deterministic optimized crossover over its randomized prototype.

References
[1] Brown, B.W., Hollander, M.: Statistics: A Biomedical Introduction. John Wiley &
Sons, Inc (1977)
[2] Buriol, L.S., Franca, P.M., Moscato, P.: A new memetic algorithm for the asymmetric traveling salesman problem. Journal of Heuristics 10, 483–506 (2004)
[3] Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS Journal on Computing 15(2), 233–248 (2003)
[4] Dongarra, J.J.: Performance of various computers using standard linear equations
software. Tech. Rep. CS-89-85, University of Manchester (2014), 110 p.
[5] Eppstein, D.: The traveling salesman problem for cubic graphs. Journal of Graph
Algorithms and Applications 11(1) (2007)
[6] Eremeev, A.V., Kovalenko, J.V.: Optimal recombination in genetic algorithms for
combinatorial optimization problems: Part II. Yugoslav Journal of Operations Research 24(2), 165–186 (2014)
[7] Eremeev, A.V., Kovalenko, J.V.: Experimental evaluation of two approaches to
optimal recombination for permutation problems. In: 16th European Conference,
EvoCOP 2016, LNCS. pp. 138–153. Porto, Portugal (2016)

7

[8] Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory
of NP-completeness. W. H. Freeman and Company, San Francisco (1979)
[9] Goldberg, D., Thierens, D.: Elitist recombination: An integrated selection recombination GA. In: First IEEE World Congress on Computational Intelligence,. vol. 1,
pp. 508–512. IEEE Service Center, Piscataway, New Jersey (1994)
[10] Johnson, D.S., McGeorch, L.A.: The traveling salesman problem: a case study. In:
Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp.
215–336. John Wiley & Sons Ltd. (1997)
[11] Kanellakis, P.C., Papadimitriou, C.H.: Local search for the asymmetric traveling
salesman problem. Oper. Res. 28, 1086–1099 (1980)
[12] Karp, R.M.: A patching algorithm for the nonsymmetric traveling-salesman problem. SIAM Journal on Computing 8, 561–573 (1979)
[13] Radcliﬀe, N.J.: The algebra of genetic algorithms. Annals of Mathematics and
Artiﬁcial Intelligence 10(4), 339–384 (1994)
[14] Reeves, C.R.: Genetic algorithms for the operations researcher. INFORMS Journal
on Computing 9(3), 231–250 (1997)
[15] Reinelt, G.: TSPLIB – a traveling salesman problem library. ORSA Journal on
Computing 3(4), 376–384 (1991)
[16] Tinós, R., Whitley, D., Ochoa, G.: Generalized asymmetric partition crossover
(GAPX) for the asymmetric TSP. In: The 2014 Annual Conference on Genetic and
Evolutionary Computation. pp. 501–508. ACM New York, NY (2014)
[17] Whitley, D., Starkweather, T., Shaner, D.: The traveling salesman and sequence
scheduling: Quality solutions using genetic edge recombination. In: Davis, L. (ed.)
Handbook of Genetic Algorithms, pp. 350–372. Van Nostrand Reinhold, NY (1991)
[18] Yagiura, M., Ibaraki, T.: The use of dynamic programming in genetic algorithms
for permutation problems. Eur. Jour. Oper. Res. 92, 387–401 (1996)
[19] Zhang, W.: Depth-ﬁrst branch-and-bound versus local search: A case study. In:
17th National Conf. on Artiﬁcial Intelligence. pp. 930–вҐҮ935. Austin, TX (2000)

8

