SHORT PAPER 
IMPACT OF CROSSOVER PROBABILITY ON SYMMETRIC TRAVEL SALESMAN PROBLEM EFFICIENCY 

 

Impact of Crossover Probability on Symmetric 
Travel Salesman Problem Efficiency 

http://dx.doi.org/10.3991/ijim.v9i1.4196 

S.F.Abu-owida and  W.S.Alsharafat  
Al al-Bayt University, Mafraq, Jordan 

 
 
 

Abstract—Genetic algorithm (GA) is a powerful evolution-
ary searching technique that is used successfully to solve 
and optimize problems in different research areas. Genetic 
Algorithm (GA) considered as one of optimization methods 
used to solve Travel salesman Problem (TSP). The feasibil-
ity of GA in finding TSP solution is dependent on GA opera-
tors; encoding method, population size, number of genera-
tions in general. In specific, crossover and its probability 
play a significant role in finding possible solution for Sym-
metric TSP (STSP). In addition, crossover should be deter-
mined and enhanced in term  reaching optimal or at least 
near optimal. In This paper, we spot the light on using mod-
ified crossover method called Modified sequential construc-
tive crossover and its impact on reaching optimal solution. 
To justify the relevance of parameters value in solving TSP, 
a set comparative analysis conducted on different crossover 
methods values. 

Index Terms—Genetic Algorithm, Crossover, mutation, 
TSP. 

I. INTRODUCTION 
The Travelling Salesman Problem (TSP) is a relatively 

ancient problem: it was precept as forward as 1759 by 
Euler, who’s interest was in solution the Knights’ tour 
proposition [1] .The extremity ‘move seller’ was first 
usage in 1932, in a German Leger ‘The travelling sales-
man, how and what he should do to get mandate and be 
fruitful in his businesses, literal by a veteran journey 
salesman[2].The origins of the TSP in mathematics aren’t 
actually understood -all we know for certain is that it 
occurs around 1931 by the mathematicians Sir William 
Rowaw Hamilton and Thomas Penyngton Kirkman from 
Ireland and Britain relatively [2]. 

The TSP is one of hard and old problems in computer 
science. It can be stated as: a graph with vertex (cities), 
and edge (distance, or travel time etc.). The TSP imple-
mented to find shortest tour that each city visited exactly 
once and then returns to the starting city. 

The TSP is categorized in two groups: symmetric trav-
elling salesman problem (STSP) where the distances be-
tween two cities equal forward and backward and there 
are (n !1)!/2 possible solutions. In opposite, Asymmetric 
TSP considered the distances between two cities where 
forward path differ than backward path and there are (n 
!1)! possible solutions.[3]  

In a STSP is complete undirected graph G= (V, A) 
where V= {1,…., n} is a cites set, E={ (i,j): i,j!V, i<j } is 
an edge set and {(i,j): i,j!V, i"j is an arc set. A cost ma-
trix C (cii) is defined on E or on A. The cost matrix satis-
fies the triangle inequality whenever cij"Ci k + C k j , for 
all i,j,k . In particular, this is the case of a planar problem 

for which the vertices are points pi= (xi,yi) in the plane, 

and cij =    is the Euclidean 
distance. The triangle inequality is also satisfied if cii is 
the length of the shortest path i from j to on G[4]. 

II. RELATED WORK  
In term of finding optimal solution for STSP, if possi-

ble, several methods have been adapted and enhanced to 
reach this target. In addition, several researches have 
worked on modifying crossover techniques which consid-
ered as one of Genetic Algorithm (GA) operations. 

Ahmed in [5] has adapted a new crossover operator 
called Sequential Constructive crossover (SCX). SCX 
works by producing a child by using better parents edges 
based on their values that may exist in structure of parents 
and maintain the node sequence as in parent. After that, If 
the node not exists in any of the parent, then perform 
search within the nodes {2, 3, …, n} to find the node. 

 Whitley in [6] has adapted Hybrid Genetic Algorithm 
for solving TSP called Generalized Partition Crossover   
(GPX) .The GPX is a hybrid GAs with LK-search which 
derived from Partition Crossover (PX). LK-search works 
by finding better tours using double bridge moves. The 
GPX   find near optimal in responsible time.  

Researchers in [7] have focused on cyclic crossover 
(CX)    the comparative study and analysis of the Partially 
Matched Crossover (PMX),   and ordered crossover  (OX) 
operators. In this paper used   Roulette Wheel to selected 
parents, 1000 iterations as terminate conditions and ran-
domly mutations used in this paper. The results show that 
the distance measured by PMX the minimum as compared 
to distance measured by CX operator and distance meas-
ured by CX operator is less than the distance measured 
OX that mean PMX crossover gain improvement when 
comparative with the CX and OX crossover operator. 

Researchers in [8] have proposed Greedy Crossover 
called Improved Greedy Crossover (IGX) to solve STSP 
using GAs. IGX search for one node using two auxiliary 
double-linked lists that considered as a resource for two 
parents to reduce memory usage. When a node is selected 
to be part child structure, offspring, it will be deleted from 
both double-liked. So IGX targeted to select the offspring 
depended on closer to their parents. 

Ahmed in [9] has proposed the ordered clustered travel-
ling salesman problem. This method focused on divided 
vertex network into predetermined clusters to find the 
least cost for TSP. In this paper companies a hybrid genet-
ic algorithm using sequential constructive crossover, 2 
option search, and a local search. IT started with vertex 1 
and sequentially searches both of the parent chromosomes 

     p  p  (     

60 http://www.i-jim.org



SHORT PAPER 
IMPACT OF CROSSOVER PROBABILITY ON SYMMETRIC TRAVEL SALESMAN PROBLEM EFFICIENCY 

 

and considers the first unvisited vertex of the present clus-
ter appearing after vertex 1 in each parent. If no unvisited 
vertex after vertex 1 is available in any of the parents, 
search sequentially from the starting of that parent and 
consider the first unvisited vertex of the cluster. Secondly, 
selected the node closely to selected node If there is not 
any vertex left in that cluster, then go to the next cluster. 
Finally, if the offspring is a complete chromosome, then 
stop; otherwise, rename the present vertex. 

Patvichaichod and his colleagues in [10] have devel-
oped the new procedures of GAs, which is called Hybrid 
Encoding GAs with multi-relations, HEGAs. The HEGAs 
is developed by using a new encoding, which mixes the 
binary encoding with the integer encoding using GAs for 
investigate TSP problem which each of the vertices has 
many edges and different cost. The methods worry from 
the different weights   in which the problem has more 
complexity. The algorithm representation method of 
chromosomes using binary (represents the edges) and 
integer numbers (represents the vertices). In the HEGAs, 
the one-point crossover is used and in the HEGA, the 
exchange mutation is used by sampling the two genes 
from the vertices and the values are exchanged  .Finally, 
the next evolution to a new generation is then begun and 
the evolution progress persevere to the determine genera-
tion, which is the termination of the HEGAs. 

Different optimization techniques have been adapted to 
solve TSP. A number of these methods are; Simulating 
Annealing in [11], Swarm Intelligent [12], Ant colony 
[13], Neural network [13, 14] beside of Genetic Algo-
rithm.  

III. GENETIC ALGORITH WITH MODIFIED CROSSOVER 
GA is an optimization problem has been adapted in 

term of finding solution for complex problem as TSP. To 
implement GA, a set of operations take a place to gain 
results starting from encoding routes to construct popula-
tion. All populations are evaluated using fitness function. 
Next new generation will be produce by implementing 
selection, crossover and mutation taking into account 
termination criteria to determine whether continue to pro-
duce next generation or stop.  The main GA operation as 
follows:  

A. Route encoding 
There are several encoding method can be used such as 

binary, real and integer. For solving TSP, integer coding 
has been selected to represent cities .Where each cities 
position can take any integer in {1, 2... n} without any 
duplication of cities.  Figure 1; represent an example on 
route encoding.  
 router 1 : {5 -> 16 -> 6-> 1->10->9->3->17->8->15->12-
>4->13->14->2->7->11}. 

Figure 1.  Route encoding 

B. Fitness function 
The GA used quantifies function called fitness function 

which acts as indicator for reaching solution. This value 
calculated for each individual in population. In TSP, fit-
ness function represents calculated distance between cit-
ies. The object function for TSP is minimizing fitness 
value as represented in following equation 4.1. 

F(x) = 1/f(x)                    (1)   

Where f(x) is calculated cost of the tour represented by 
route. 

C. Selection  
To maintain the diversity between generations, selec-

tion parents that they will participate in producing new 
childs, offspring. For this purpose, different selection 
methods have been developed by researchers to accom-
plish this task. In this work we adapted Roulette Wheel 
Selection (RWS). RWS focused on selecting parents with 
high probability where this probability depends on parent's 
fitness value. RWS works by adding all individual fitness 
value (denoted by #fi) then calculate the expected proba-
bility for each individual by dividing its fitness value over 
cumulative fitness values for all parents as shown in equa-
tion 2.  

                                   (2)     Where: 

Fi: Individual fitness  
F: Average fitness   
                                   

D. Modified Sequential Constructive Crossover (MSCX)  
We have developed crossover operator in term of reach-

ing optimal solution of TSP. This operator gives results 
which are remarkably better than the others crossover 
operator .It produces a child, offspring, by taking ad-
vantage of better links values provided by their parents. It 
also uses the better links value, which are not present in 
the parent’s structure. The detailed clarifications about 
how it works are as follows: 

1. Start  
2. Parents split into group. 
3. Start from initial node presented in parent 1. 
4. Sequentially search in all groups in the both of the 

parents and take care into unvisited node that ap-
peared after the node 1 in both parents. If don’t found 
the next node (the node that is not yet visited) after 
initial node in both parents, search in data set to find 
minimum cost. After this go to (5). 

5. Suppose the 'node $ found in parent1 while node %' 
found in parent 2, then selecting the next node and go 
to (7). 

6. If cost of $ < cost of %, then select node $, otherwise 
select node % as the next node and considered as a 
part of a child, offspring, If the offspring is a com-
plete, then stop, otherwise, return to (4). 

7. Repeat  

E. Mutation  
Mutation takes a place after crossover with certain 

probability denoted by Pm.  Mutation is random changing 
in cities order in route for produced Childs.  Mutation 
concerns in introducing certain diversity in the population 
to be differ than existing population. In addition, mutation 
suitable for more exploration to discover unknown situa-
tions in search space and avoid local optima. For experi-
mental tests  Pm  = 0.01. 

iJIM ‒ Volume 9, Issue 1, 2015 61



SHORT PAPER 
IMPACT OF CROSSOVER PROBABILITY ON SYMMETRIC TRAVEL SALESMAN PROBLEM EFFICIENCY 

 

F. Termination 
Different termination criteria may take a place to stop. 

One of termination criteria is running the algorithm ac-
cording to specific number of iterations, or when fitness 
value converges to stable value. In this paper we consid-
ered number of iterations as stopping criteria which equals 
10000 iterations. 

IV. EXPERIMENTAL RESULTS 
In this section, we investigate the effectiveness of modi-

fying crossover operation in GA. For comparison purpos-
es, we used Error of solution for each instance and aver-
age as a measurement tool. In addition to perform experi-
mental result we use benchmark STSP instance reported 
in TSPLIB [16]. Table I presents the main features for 
dataset instances that will be used in comparison. 

TABLE I.   
INSTANCES PROPERTIES 

Instances Number of cites Optimal 
gr17 17 2085 
fri26 26 937 
bays29 29 2020 

 dantzig42 42 699 
swiss42 42 1273 

 
In Table II, we notice that MSCX achieves the intended 

target to reach near optimal solution measured by low 
error rate.Figure 1 shows these results. 

TABLE II.   
TABLE 2: MSCX ERROR % 

Instances Error % 
gr17 0.00
fri26 0.00 

bays29 0.01 
dantzig42 0.04 

swiss42 0.03 
 

 
Figure 2. MSCX error rate

For comparative purposes, we compare MSCX results 
with HGA because both HGA and MSCX used STSP 
dataset instances. 

In Table III, we present comparative between HGA and 
MSCX which applied on different city size. This shows 
that MSCX gained approximately better result than HGA. 
Figure 2, presents result in table 3. 

TABLE III.   
ERROR % FOR HGA AND MSCX 

Instances 
HGA MSCX 

Error % Error %
gr17 0.21 0 
fri26 0.02 0 

dantzig42 0 0.04 
swiss42 0.26 0.03 

 

 
Figure 3.  Error % for HGA and MSCX crossover. 

V. CONCLUSION AND FUTURE WORK 
In this paper, we provide modified crossover operation, 

MSCX, which shows improvement in solving TSP by 
tuning up GA operations as crossover. In addition, GA 
considered an efficient algorithm in solving optimization 
problems as TSP.  To achieve better results more investi-
gations have to be taken on crossover probability and how 
the results will be affected by changing type of GA. 

REFERENCES 
[1] Matai1, R., S.P, Singh and Matai. M. 2010. Traveling Salesman 

Problem: An Overview of Applications, Formulations, and Solu-
tion Approaches. In Tech.www.intechopen.com. 

[2] Michalewicz, Z. (1994), Genetic Algorithms + Data Structures = 
Evolution Programs, (2nd ed), Berlin: Spring. 

[3] Davendra, D. (2010), Traveling Salesman Problem, Theory and 
Applications, (1st ed), Croatia: InTech. http://dx.doi.org/10. 
5772/547 

[4] Gupta, S., Panwar. P, (2013), Solving Travelling Salesman Prob-
lem Using Genetic Algorithm, International Journal of Advanced 
Research in Computer Science and Software Engineering, Accept-
ed for Publication. 

[5] Ahmed.Z. (2010), Genetic Algorithm for the Traveling Salesman 
Problem using Sequential Constructive Crossover Operator, Inter-
national Journal of Biometrics & Bioinformatics, Accepted for 
Publication. 

[6] Whitley D, Hains. D and H. Adele. (2010), A Hybrid Genetic 
Algorithm for the Traveling Salesman Problem using Generalized 
Partition Crossover, Accepted for Publication. 

[7] Kumar .N, Karambir, Kumar.R, (2012), A Comparative Analysis 
of PMX, CX and OX Crossover operators for solving Travelling 
Salesman Problem, International Journal of Latest Research in 
Science and Technology, Accepted for Publication. 

[8] Esmkhan H and Zamanifar.K, (2012), Developing Improved 
Greedy Crossover to Solve Symmetric Traveling Salesman Prob-
lem, Accepted for Publication. 

[9] Ahmed.Z, (2014), the Ordered Clustered Travelling Salesman 
Problem: A Hybrid Genetic Algorithm, Hindawi, Accepted for 
Publication Programs, (2nd ed), Berlin: Spring  

[10] Patvichai chod, S., (2011). An Improved Genetic Algorithm for 
the TravelingSalesman Problem with Multi-Relations, Journal of 
Computer Science, Accepted for Publication. 

!"

!#!$"
!""#"$%$

%&&'&"("

!"

!#)"

!#*"

!#+"

,&)-".&/*0"12345/,6*"78/776*"

9:;"%&&'&"
("

<=>?"%&&'&"
("

62 http://www.i-jim.org



SHORT PAPER 
IMPACT OF CROSSOVER PROBABILITY ON SYMMETRIC TRAVEL SALESMAN PROBLEM EFFICIENCY 

 

[11] Genga,X.,  Chenb,Z., Yanga,W., Shia,K., and  Zhaoa, K. 2011. 
Solving the traveling salesman problem based on an adaptive sim-
ulated annealing algorithm with greedy search, Applied Soft 
Computing, Volume 11, Issue 4, June 2011, Pages 3680–3689. 
http://dx.doi.org/10.1016/j.asoc.2011.01.039 

[12] Tao, Y., Cui, D., Miao, X., and Chen, H. 2007. An Improved 
Swarm Intelligence Algorithm for Solving TSP Problem. Third In-
ternational Conference on Intelligent Computing, ICIC 2007, 
Qingdao, China, August 21-24. 

[13] Su,Z., Hlaing and Khine,A. 2011. Solving Traveling Salesman 
Problem by Using Improved Ant Colony Optimization Algorithm, 
, IACSIT, International Journal of Information and Education 
Technology, Vol. 1, No. 5, December 2011. 

[14] Siqueira,P., Scheer,S., and Steiner, M. 2008. A Recurrent Neural 
Network to Traveling Salesman Problem. Travelling Salesman 

Problem, ISBN 978-953-7619-10-7, pp. 202, September 2008, I-
Tech, Vienna, Austria. 

[15] Reilly, R., Tichmev,P. 2003. Neural network approach to solving 
the Traveling Salesman Problem, Journal of Computing Sciences 
in Colleges, Volume 19 Issue 1, October 2003, Pages 41-61. 

[16]  http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ 

AUTHORS 
S.F.Abu-owida and W.S.Alsharafat are with Prince 

Hussein Bin Abdullah Faculty of Information Technology, 
Al al-Bayt University, Mafraq, Jordan. 

Submitted 08 October 2014. Published as resubmitted by the authors 
25 January 2015. 

 

iJIM ‒ Volume 9, Issue 1, 2015 63


	iJIM – Vol. 9, No. 1, 2015
	Impact of Crossover Probability on Symmetric Travel Salesman Problem Efficiency