30BcqpdT

1\documentclass[conference,twocolumn]{IEEEtran}
2\IEEEoverridecommandlockouts
3% The preceding line is only needed to identify funding in the first footnote. If that is unneeded, please comment it out.
4\usepackage{cite}
5\usepackage{amsmath,amssymb,amsfonts}
6\usepackage{algorithmic}
7\usepackage{graphicx}
8\usepackage{textcomp}
9\usepackage{authblk}
10\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
11    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
12
13\pagenumbering{roman}
14
15
16    
17\begin{document}
18\title{Research Paper On The Travelling Salesman Problem Using Various Algorithms\\}
19
20\author[1]{Ahmed Nasser}
21\author[1]{Ahmed Hisham}
22\author[2]{Mohammed Salah}
23\author[1]{Omar Abdelfattah}
24\author[2]{Hesham Khaled}
25\author[1]{Youssef Walid}
26
27\affil[1]{Student ($3^{rd}$ year) Computer Engineering Department, Faculty of Engineering, Cairo University}
28\affil[2]{Student ($3^{rd}$ year) Electronics and Electrical Engineering Department, Faculty of Engineering, Cairo University}
29
30\maketitle
31\begin{abstract}
32The Travelling Salesman Problem (TSP) is an
33NP hard problem in Combinatorial Optimization,
34important in operations research and theoretical
35computer science. TSP is always fascinating for the computational scientists
36and poses interesting challenges to formulate fast and
37effective algorithms for its solution. It is really
38challenging to design a robust and effective algorithm,
39which can give optimal solutions to TSP with large
40dimensions. There are many algorithms proposed in the
41literature based on various branches of mathematics,
42graph theory, operation research and even in fuzzy
43theory. The amount of computational time to solve this
44problem grows exponentially as the number of cities.
45These problems demand innovative solutions if they are
46to be solved within a reasonable amount of time. This
47paper explores the solution of Travelling Salesman
48Problem using different algorithms. The aim of this paper
49is to review how minimum spanning tree, dynamic programming, and 
50genetic algorithms are applied to this problem and 
51find an efficient solution.
52\end{abstract}
53
54\begin{IEEEkeywords}
55TSP, Minimum Spanning Tree (MST), Dynamic Programming (DP), Genetic Algorithm (GA)
56\end{IEEEkeywords}
57
58\section{INTRODUCTION}
59
60The idea of the traveling salesman problem (TSP) is
61to find a tour of a given number of cities, visiting
62each city exactly once and returning to the starting
63city where the length of this tour is minimized.
64The first instance of the traveling salesman problem
65was from Euler in 1759 whose problem was to move
66a knight to every position on a chess board exactly
67once.
68The traveling salesman first gained fame in a book
69written by German salesman BF Voigt in 1832 on
70how to be a successful traveling salesman. He
71mentions the TSP, although not by that name, by
72suggesting that to cover as many locations as possible
73without visiting any location twice is the most
74important aspect of the scheduling of a tour. The
75origins of the TSP in mathematics are not really
76known all we know for certain is that it happened
77around 1931.
78The standard or symmetric traveling salesman
79problem can be stated mathematically as follows:
80Given a weighted graph G = (V,E) where the weight
81cij on the edge between nodes i and j is a nonnegative value, 
82find the tour of all nodes that has the
83minimum total cost.
84Currently the only known method guaranteed to
85optimally solve the traveling salesman problem of
86any size, is by enumerating each possible tour and
87searching for the tour with smallest cost. Each
88possible tour is a permutation of 123 . . . n, where n is
89the number of cities, so therefore the number of tours
90is n!. When n gets large, it becomes impossible to
91find the cost of every tour in polynomial time.
92
93\section{DEFINITION}
94
95Let G = (V, A) be a graph where V is a set of n
96vertices. A is a set of arcs or edges, and let C: ($C_{ij}$) be
97a distance (or cost) matrix associated with A. The
98TSP consists of determining a minimum distance
99circuit passing through each vertex once and only
100once. Such a circuit is known as a tour or
101Hamiltonian circuit (or cycle). In several
102applications, C can also be interpreted as a cost or
103travel time matrix.
104
105\subsection{As a graph problem}
106
107TSP can be modelled as an undirected weighted
108graph, such that cities are the graph's vertices, paths
109are the graph's edges, and a path's distance is the
110edge's length. It is a minimization problem starting
111and finishing at a specified vertex after having visited
112each othervertex exactly once. Often, the model is
113a complete graph (i.e. each pair of vertices is
114connected by an edge). If no path exists between two
115cities, adding an arbitrarily long edge will complete
116the graph without affecting the optimal tour.
117
118\begin{figure}[h]
119    \centering
120    \includegraphics[width=0.25\textwidth]{TSPexample.png}
121    \caption{Symmetric TSP with four cities}
122    \label{fig:TSPexample}
123\end{figure}
124
125\subsection{Asymmetric and symmetric}
126
127In the symmetric TSP, the distance between two cities
128is the same in each opposite direction, forming
129an undirected graph. This symmetry halves the
130number of possible solutions. In the asymmetric TSP,
131paths may not exist in both directions or the distances
132might be different, forming a directed graph. Traffic
133collisions, one-way streets, and airfares for cities with
134different departure and arrival fees are examples of
135how this symmetry could break down.
136
137\section{APPLICATIONS OF TSP}
138
139The most common practical interpretation of the TSP
140is that of a salesman seeking the shortest tour through
141n clients or cities. Several interesting permutation
142problems not directly associated with routing can also
143be described as TSPs. Here are some selected
144examples.
145\begin{enumerate}
146
147\item \textit{Computer wiring (Lenstra and Rinnooy Kan, 1975):}
148Some computer systems can be described as
149modules with pins attached to them. It is often
150desired to link these pins by means of wires, so that
151exactly two wires are attached to each pin
152and total wire length is minimized.
153
154\item \textit{Wallpaper cutting (Garfinkel, 1977):}
155Here, $n$ sheets must be cut from a roll of wallpaper on which
156a pattern of length 1 is repeated. For sheet $i$, denote
157by $a_i$ and $b_i$ the starting and ending points on the
158pattern where $0 <= a_i <= 1$ and $0 <= b_i <= 1$. Then
159cutting sheet $j$ immediately after sheet $i$ results in a
160waste of $C_{ij}=a_j-b_i$ if $b_i<=a_j$ or $C_{ij}=1+a_j-b_i$ if
161$b_i>a_j$ The objective is to order the $n$ sheets so as to
162minimize total waste.
163
164\item \textit{Hole punching (Reinelt, 1989):}
165In several manufacturing contexts, it is necessary to punch
166holes on boards or metallic sheets. The problem
167consists of determining a minimum-time punching
168sequence. Such a problem occurs frequently in
169metallic sheet manufacturing and in the construction
170of circuit boards. These problems are often of large
171scale and must be solved in realtime.
172
173\item \textit{Job sequencing:}
174Suppose $n$ jobs must be
175performed sequentially on a single machine and that
176$c_{ij}$ is the change-over time if job $j$ is executed
177immediately after job $i$. Then again, by introducting a
178dummy job, this problem can be formulated as a TSP.
179
180\item \textit{Dartboard design (Eiselt and Laporte, 1991):}
181Dartboards are circular targets with concentric
182circles, and 20 sectors identified by the numbers 1 to
18320. Players throw darts at target points on the board.
184In the most common version of the game, the
185objective is to reduce an initial value of 301 to zero
186by substracting scores. The game rewards accuracy in
187the throw and it is often more important to hit one's
188target that to merely register a large score. A natural
189objective for designing a dartboard is therefore to
190position the 20 numbers around the board so as to
191maximize players' risk. For fairly accurate players, it
192is reasonable to assume that the sector that is hit is
193always the targeted sector or its neighbour.
194
195\item \textit{Crystallography (Bland and Shallcross, 1989):}
196In crystallography, some experiments consist of
197taking a large number of X-ray intensity
198measurements on crystals by means of a detector.
199Each measurement requires that a sample of the
200crystal be mounted on an apparatus and that the 
201detector be positioned appropriately. The order in
202which the various measurements on a given crystal
203are made can be seen as the solution of a TSP. In
204practice, these problems are of large scale and
205obtaining good TSP solutions can reduce
206considerably the time needed to carry out all
207measurements.
208
209\item \textit{Overhauling gas turbine:}
210An application found by Plate, Lowe and Chandrasekaran is
211overhauling gas urbine engines in aircraft. Nozzleguide vane assemblies, consisting of nozzle guide
212vanes fixed to the circumference, are located at each
213turbine stage to ensure uniform gas flow. The
214placement of the vanes in order to minimize fuel
215consumption can be modelled as a symmetric TSP.
216
217\item \textit{Job scheduling:}
218The scheduling of jobs on a
219single machine given the time it takes for each job
220and the time it takes to prepare the machine for each
221job is also TSP. We try to minimize the total time to
222process each job.
223
224\end{enumerate}
225
226\section{METHODS OF SOLVING THE TSP}
227
228\textbf{Homaifar} states that “one approach which would
229certainly find the optimal solution of any TSP is the
230application of exhaustive enumeration and
231evaluation.
232The procedure consists of generating all possible
233tours and evaluating their corresponding tour length.
234The tour with the smallest length is selected as the
235best, which is guaranteed to be optimal. If we could
236identify and evaluate one tour per nanosecond (or one
237billion tours per second), it would require almost ten
238million years (number of possible tours = 3.2×1023)
239to evaluate all of the tours in a 25-city TSP”.
240Obviously we need to find an algorithm that will give
241us a solution in a shorter amount of time. As we said
242before, the traveling salesman problem is NP-hard so
243there is no known algorithm that will solve it in
244polynomial time. We will probably have to sacrifice
245optimality in order to get a good answer in a shorter
246time. Many algorithms have been tried for the
247traveling salesman problem. We will explore a few of
248these in this section.
249\\
250\\
251\textbf{Greedy Algorithms} are a method of finding a
252feasible solution to the traveling salesman problem.
253The algorithm creates a list of all edges in the graph
254and then orders them from smallest cost to largest
255cost. It then chooses the edges with smallest cost
256first, providing they do not create a cycle. The greedy
257algorithm gives feasible solutions however they are
258not always good.
259The Nearest Neighbor algorithm is similar to the
260greedy algorithm in its simple approach. We
261arbitrarily choose a starting city and then travel to the
262city closest to it that does not create cycle. We
263continue to do this until all cities are in the tour. This
264algorithm also does not always give good solutions
265because often the last edge added to the tour (that is,
266the edge $e_{n1}$ where $n$ is the number of cities) can be
267quite large.
268\\
269\\
270\textbf{A minimum spanning tree} is a set of $n-1$ edges
271(where again $n$ is the number of cities) that connect
272all cities so that the sum of all the edges used is
273minimized. Once we have found a minimum
274spanning tree for our graph we can create a tour by
275treating the edges in our spanning tree as
276bidirectional edges.
277We then start from a city that is only connected to
278one other city (this is known
279as a ’leaf’ city) and continue following untraversed
280edges to new cities. If there is no untraversed edge
281we go back along the previous edge. We continue to
282do this until we return to the starting city. This will
283give us an upper bound for the optimal traveling
284salesman tour. Note, however, that we will visit some
285cities more than once. We are able to fix this if
286whenever we need to traverse back to a city we have
287already been to, we instead go to the next unvisited
288city. When all cities have been visited we go directly
289back to the starting city.
290\\
291\\
292\textbf{Dynamic programming (DP)} is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again. If the given problem can be broken up in to smaller sub-problems and these smaller subproblems are in turn divided in to still-smaller ones, and in this process, if you observe some over-lappping subproblems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem.
293\\
294\\
295\textbf{Genetic algorithms} as a computational
296intelligence method is a search technique used in
297computer science to find approximate solutions to
298combinatorial optimization problems. The genetic
299algorithms are more appropriately said to be an
300optimization technique based on natural evolution.
301They include the survival of the fittest idea algorithm.
302The idea is to first "guess" the solutions and then
303combining the fittest solution to create a new
304generation of solutions which should be better than
305the previous generation.
306
307\section{MINIMUM SPANNING TREE APPROACH}
308Much study has gone into the minimum spanning tree (MST)
309to a great extent of this century and yet in spite of its obvious
310simplicity, it is still not entirely understood. The MST is
311simply finding a spanning tree of an undirected, joined graph,
312where each edge has some real number such that the sum of
313the weights of the selected edges is least.
314
315\subsection{MST Definition}
316By this, it can be described as a combinatorial optimization
317problem. A general problem definition of the MST is
318given an undirected graph $G = (V,E)$, where $V$ indicates
319vertices of set with $n = |V|$ and E edges of set with $m = |E|$
320and a real number $w(e)$ for each edge $e \in E$ referred to as the
321weight of edge $e$, the MST problem is defined as finding a
322spanning tree $T^*$ on $G$, such that $w(T^*)$ = $min_T \sum_{e\in T} w(e)$ is
323the minimum taken over all possible spanning trees of G. This
324problem can be solved by a lot of different algorithms. Such
325algorithm depending upon the assumptions taken, may be a
326randomized algorithm which can solve in linear expected
327time, linear worst case time or a solution which might be close
328to linear but not entirely linear.
329
330A lot of direct applications can be linked to MST. This is in
331the areas of wiring connections, computer and communication
332networks, flow network piping, leased-line telephone and
333power networks, as well as transportation network
334connections. MST proffers some form of solution to certain
335problems to which it less applicable directly, such including
336classification problems, clustering and reliability of network.
337MST algorithm can be used in quite a lot of exact and
338approximation algorithms for the capacitated Minimum
339Spanning Tree problem, the matching problem and multiterminal flow problem, 
340in this case occurring as a subproblem in the solution of other problems. 
341
342\subsection{Modelling TSP Using MST Algorithm}
343
344The minimum spanning tree may or may not be unique
345depending on the pair-wise distinction of its weight or cost on
346its edges.
347Given a set number of cities to visit to which every city is
348reachable from every other city somehow forming a tour, then
349a spanning tree of the tour is a connected sub-tour in which
350there are no cycles. The minimum spanning solution will be
351the minimum cost that will be needed to tour all cities at least
352once.
353The travelling salesman problem is finding the least path or
354cost to touring all cities under discussion once and returning
355to the starting city. To adapt the MST algorithm to solve the
356traveling salesman problem, certain assumptions need to be
357met for this model to work. It is assumed for
358expediency that the input graph is complete to guarantee that
359the starting city is adjacent to the last city
360
361\subsection{Adopting MST into TSP Algorithm}
362For a complete graph, $G (V, E)$:
363\begin{enumerate}
364    \item Choose an "anchor" vertex $u \in V[G]$.
365    \item Let the $u$ be the beginning and finishing point for
366salesman.
367    \item Construct a MST of the graph with $u$ as anchor
368    
369    
370        STEP 1: Make a set QSet that maintain track of
371        vertices already contained in MST.
372        
373        
374        STEP 2: Allot a key value to all vertices in the input
375        graph. All key values can be initialized as
376        ENDLESS. Allot key value as 0 for the anchor, $u$ so
377        that it is picked first.
378        
379        
380        STEP 3: While QSet does not contain all vertices
381            Pick a vertex $r$ which is not there in QSet and
382            has minimum key value then add $r$ to QSet.
383            
384            
385        Renew key value of all adjoining vertices of r. Loop
386        through all neighboring vertices to renew the key
387        values.
388        
389        
390        For each adjoining vertex $z$, if weight of edge $r-z$ is
391        less than the previous key value of $r$, update the key
392        value as weight of $r-z$.
393    \item Look into the vertex list attained in step 3 and purge
394        from it all recurring occurrences of the same vertex
395    \item Assume $H$ to be the order of vertices toured in a
396        pre-order walk of QSet, connect all unconnected
397        nodes
398    \item Present the Hamiltonian cycle $T$ that trips the
399        vertices in the order $H$.
400
401\end{enumerate}
402
403
404\subsection{MST Approach Results and Efficiency}
405
406\begin{figure}[h]
407    \centering
408    \includegraphics[width=0.25\textwidth]{MSTTSPexample.jpg}
409    \caption{TSP graph with four cities}
410    \label{fig:MSTTSPexample}
411\end{figure}
412
413The cost of the output produced by the above algorithm is never more than twice the cost of best possible output. Let us see how is this guaranteed by the above algorithm.
414Let us define a term full walk to understand this. A full walk is lists all vertices when they are first visited in preorder, it also list vertices when they are returned after a subtree is visited in preorder. The full walk of tree below would be $1\rightarrow 2\rightarrow 1\rightarrow 4\rightarrow 1\rightarrow 3\rightarrow 1$.
415Following are some important facts that prove the 2-approximateness:
416\begin{enumerate}
417    \item The cost of best possible Travelling Salesman tour is never less than the cost of MST. (The definition of MST says, it is a minimum cost tree that connects all vertices).
418    \item The total cost of full walk is at most twice the cost of MST (Every edge of MST is visited at-most twice)
419    \item The output of the above algorithm is less than the cost of full walk. In above algorithm, we print preorder walk as output. In preorder walk, two or more edges of full walk are replaced with a single edge. For example, $2\rightarrow 1$ and $1\rightarrow 4$ are replaced by one edge $2\rightarrow 4$. So if the graph follows triangle inequality, then this is always true.
420\end{enumerate}
421
422From the above three statements, we can conclude that the cost of output produced by the approximate algorithm is never more than twice the cost of best possible solution.
423
424We have discussed a very simple 2-approximate algorithm for the travelling salesman problem. There are other better approximate algorithms for the problem.
425
426\section{DYNAMIC PROGRAMMING APPROACH}
427\subsection{Definition}
428Dynamic Programming (DP) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. It is an efficient approach because it aims to breakdown the complexities and the nonlinear influences of the main problem to more linear and simple models giving the exact solution.
429Dynamic programming approach consists of three steps for solving a problem that is as follows:
430\begin{enumerate}
431\item The given problem is divided into subproblems as same as in divide and conquer rule. However dynamic programming is used when the subproblems are not independent of each other but they are interrelated. I.e. they are also called as overlapping problems.
432\item To avoid this type of recomputation of overlapping subproblem a table is created in which whenever a subproblem is solved, then its solution will be stored in the table so that in future its solution can be reused.
433\item The solution of the subproblem is combined in a bottom of manner to obtain the optimal solution of a given problem.
434\end{enumerate}
435\subsection{Modelling TSP Using DP Approach}
436for $n$ number of cities and each city corresponds to a vertex. Let the given set of vertices
437be {1, 2, 3, 4,….n}, let us consider $\phi$ as starting and ending point of output. For every other vertex $i$ (other than $\phi$), we find the minimum cost path with $\phi$ as the starting point, $i$ as the ending point and all vertices appearing exactly once. Let the cost of this path be $cost(i)$, the cost of corresponding cycle would be $cost(i) + distance(i,\phi)$, where distance $d(i,\phi)$ is the distance from $i$ to $\phi$. Finally, we return the minimum of all $[cost(i) + distance(i, \phi)]$ values. We can organize this approach into sequence of steps (Mapping, Primary, Mutuality and Minimization) that's all based on forward substitution of former steps into latter ones.
438\subsection{Algorithm Steps}
439Using the model in Fig. 2
440
441\begin{enumerate}
442\item \textbf{Mapping}: Storing distances between each city into a zero diagonal symmetric matrix, where  each element $(i,j)$ represents the mutual distance between vertex $i$ and vertex $j$.\\
443$$\begin{bmatrix}
4440 & 10 & 15 & 20\\
44510 & 0 & 35 & 25\\
44615 & 35 & 0 & 30\\
44720 & 25 & 30 & 0
448\end{bmatrix}$$
449\item \textbf{Primary Cost}: This step is all about getting the cost between each vertex $i$ that is reachable from starting city $\phi$ that will be used in the forward substitution as mentioned. Let the starting vertex $\phi$ be vertex (1):
450$C(4,1)=20, C(3,1)=15, C(2,1)=10$
451\item \textbf{Mutuality}: This step is similar to the previous step, but only getting cost of reaching other vertices $i$ by making one single step after the primary cost one. Mutuality could be done monotonously according to the number of vertices in each model, forward substituting results from the primary cost step to get the cost of the mutuality of each vertex.\\
452Cost of (2):\\
453$C(2,{3}) = d(2,3) + C(3,1) = 35$\\
454$C(2,{4}) = d(2,4) + C(4,1) = 45$\\
455Cost of (3):\\
456$C(3,{2}) = d(3,2) + C(2,1) = 45\\
457C(3,{4}) = d(3,4) + C(4,1) = 50$\\
458Cost of (4):\\
459$C(4,{2}) = d(4,2) + C(2,1) = 35\\
460C(4,{3}) = d(4,2) + C(2,1) = 45$
461
462\item \textbf{Minimization}: The lowest cycle cost of all the mutualizing made in the previous steps will represent our expected optimal answer, which takes place only when minimizing the combinations of the the mutuality and forward substituting all the results from the previous step to acquire our optimal tour length.
463
464$C(2,\{3,4\})=min(d(2,3)+C(3,\{4\}), d(2,4)+C(4,\{3\}))=80$
465
466$C(3,\{2,4\})=min(d(3,2)+C(2,\{4\}), d(3,4)+C(4,\{2\}))=65$
467
468$C(4,\{2,3\})=min(d(4,2)+C(2,\{3\}), d(4,3)+C(3,\{2\}))=75$
469
470And we can finally apply our optimal cost by,
471
472$C(1,\{2,3,4\})=min(d(1,2)+C(2,\{3,4\}),\\
473d(1,3)+C(3,\{2,4\}),d(1,4)+C(4,\{2,3\}))\\
474=min(90,80,95) = 80$
475
476\end{enumerate}
477
478\section{GENETIC ALGORITHM APPROACH} Genetic algorithms are based essentially on
479mimicking the survival of the fittest among the
480species generated by random changes in the gene-structure of the chromosomes 
481in the evolutionary biology. In order to solve any real life problem by
482GA, two main requirements are to be satisfied:
483\\
484(a) A string can represent a solution of the solution
485space
486\\
487(b) An objective function and hence a fitness function
488which measures the goodness of a solution can be
489constructed.
490
491\subsection{Genetic Algorithm Theory}
492The genetic algorithm process consists of the
493following steps:
494\begin{enumerate}
495\item \textbf{[Start]} Generate random population of n
496chromosomes (suitable solutions for the problem)
497\item \textbf{[Fitness]} Evaluate the fitness $f(x)$ of each
498chromosome $x$ in the population
499\item \textbf{[New population]} Create a new population by
500repeating following steps until the new population is
501complete
502\item \textbf{[Selection Select]} two parent chromosomes from a
503population according to their fitness (the better
504fitness, the bigger chance to be selected)
505\item \textbf{[Crossover]} is performed with a probability
506known as crossover probability that crossover the
507selected parents to produce a new offspring
508(children). If crossover probability is 0\%, children are
509an exact copy of parents.
510\item \textbf{[Mutation]} is performed with a probability known
511as mutation probability that mutate new offspring at
512each locus (position in chromosome).
513\item \textbf{[Accepting]} Place new offspring in a new
514population
515\item \textbf{[Replace]} Use new generated population for a
516further run of algorithm
517\item \textbf{[Test]} If the termination condition is satisfied, then
518stop the algorithm, and return the best solution in
519current population
520\item \textbf{[Loop]} Go to step 2
521\end{enumerate}
522
523\subsection{Genetic Coding}
524To apply GA for any optimization problem, one has
525to think a way for encoding solutions as feasible
526chromosomes so that the crossovers of feasible
527chromosomes result in feasible chromosomes. The
528techniques for encoding solutions vary by problem
529and, involve a certain amount of art. For the TSP,
530solution is typically represented by chromosome of
531length as the number of nodes in the problem.
532Each gene of a chromosome takes a label of node
533such that no node can appear twice in the same
534chromosome. There are mainly two representation
535methods for representing tour of the TSP – adjacency
536representation and path representation. We consider
537the path representation for a tour, which simply lists
538the label of nodes. For example, let {1, 2, 3, 4, 5} be
539the labels of nodes in a 5 node instance, then a tour
540$1\rightarrow 3\rightarrow 4\rightarrow 2\rightarrow 5 \rightarrow1$
541may be represented as (1, 3, 4, 2, 5). 
542
543\subsection{Reproduction operator}
544
545In reproduction/selection process, chromosomes are
546copied into next generation mating pool with a
547probability associated with their fitness value. By
548assigning to next generation a higher portion of the
549highly fit chromosomes, reproduction mimics the
550Darwinian survival-of-the-fittest in the natural world.
551In natural population, fitness is determined by a
552creature’s ability to survive predators, pestilence, and
553other obstacles to adulthood and subsequent
554reproduction. In this phase no new chromosome is
555produced. The commonly used reproduction operator
556is the proportionate reproduction operator, where a
557string is selected for the mating pool with a
558probability proportional to its fitness value. We have
559considered the stochastic remainder selection method
560for our genetic algorithms
561
562\subsection{Genetic Algorithm Process}
563
564\begin{enumerate}
565\item \textbf{Encoding:} A suitable encoding is found for the
566solution to our problem so that each possible solution
567has unique encoding and the encoding is some form
568of a string. We do have a graph such as the one
569described above and we can encode it in the same
570way, only our matrix will have a one in the $i$, $j^{th}$ 
571position if there is an arc from node $i$ to node $j$ in the
572tour and a zero otherwise. For example, the matrix
573$$\begin{bmatrix}
5740 & 0 & 1\\
5751 & 0 & 0\\
5760 & 1 & 0
577\end{bmatrix}$$
578represents the tour that goes from city 1 to city 3, city
5793 to city 2 and city 2 to city 1.
580This encoding is known as matrix representation.
581\\
582\item \textbf{Evaluation:} The initial population is then selected,
583usually at random though alternative techniques
584using heuristics have also been proposed. The fitness
585of each individual in the population is then computed
586that is, how well the individual fits the problem and
587whether it is near the optimum compared to the other
588individuals in the population.
589We use the evaluation function to decide how 'good'
590a chromosome is. The evaluation function usually
591comes straight from the problem. In our case the
592evaluation function would simply be the function $f =
593-2x^2 + 4x - 5$, and because we are trying to
594maximize the function, the larger the value for $f$, the
595better. So, in our case, we would evaluate the
596function with the two values 7 and 12. $f(7)
597= -71$, $f(12) = -241$
598Obviously 7 is a better solution than 12, and would
599therefore have a higher fitness.
600This fitness is then used to decide the probability that
601a particular chromosome would be chosen to
602contribute to the next generation. We would
603normalize the scores that we found and then create a
604cumulative probability distribution. This is then used
605in the crossover process.
606\\
607\item \textbf{Crossover:} The fitness is used to find the
608individual's probability of crossover. Crossover is
609where the two individuals are recombined to create
610new individuals which are copied into the new
611generation.
612Crossover can be a fairly straightforward procedure.
613In our example, which uses the simplest case of
614crossover, we randomly choose two chromosomes to
615crossover, randomly pick a crossover point, and then
616switch all genes after that point. For example, using
617our chromosomes
618$v_1 = 0111$
619$v_2 = 1100$
620we could randomly choose the crossover
621point after the second gene
622$v_1 = 01 | 11$,
623$v_2 = 11 | 00$
624Switching the genes after the crossover point would
625give
626$v_{01} = 0100 = 4$,
627$v_{02} = 1111 = 15$.
628We now have two new chromosomes which would
629be moved into the next population, called the next
630generation.
631Not every chromosome is used in crossover. The
632evaluation function gives each chromosome a ’score’
633which is used to decide that chromosome’s
634probability of crossover. The chromosomes are
635chosen to crossover randomly and the chromosomes
636with the highest scores are more likely to be chosen.
637We use the cumulative distribution created in the
638evaluation stage to choose the chromosomes.
639\\
640\item \textbf{Mutation:} Next mutation occurs. Some
641individuals are chosen randomly to be mutated and
642then a mutation point is randomly chosen. The
643character in the corresponding position of the string
644is changed.
645Mutation is used so that we do not get trapped in a
646local optimum. Due to the randomness of the process
647we will occasionally have chromosomes near a local
648optimum but none near the global optimum.
649Therefore the chromosomes near the local optimum
650will be chosen to crossover because they will have
651the better fitness and there will be very little chance
652of finding the global optimum. So mutation is a
653completely random way of getting to possible
654solutions that would otherwise not be found.
655\\
656\item \textbf{Decoding:} Once this is done, a new generation has
657been formed and the process is repeated until some
658stopping criteria have been reached. At this point the
659individual who is closest to the optimum is decoded
660and the process is complete.
661\end{enumerate}
662
663\subsection{Methodology}
664A simple GA works by randomly generating an
665initial population of strings, which is referred as gene
666pool and then applying (possibly three) operators to
667create new, and hopefully, better populations as
668successive generations. The first operator is
669reproduction where strings are copied to the next
670generation with some probability based on their
671objective function value. The second operator is
672crossover where randomly selected pairs of strings
673are mated, creating new strings. The third operator,
674mutation, is the occasional random alteration of the
675value at a string position. The crossover operator
676together with reproduction is the most powerful
677process in the GA search. Mutation diversifies the
678search space and protects from loss of genetic
679material that can be caused by reproduction and
680crossover. So, the probability of applying mutation is
681set very low, whereas the probability of crossover is
682set very high.
683\subsection{Steps of Algorithm}
684\begin{enumerate}
685\item Randomly create the initial population of
686individual string of the given TSP problem and create
687a matrix representation of the cost of the path
688between two cities.
689\item Assign the fitness to each chromosome in the
690population using fitness criteria measure. $F(x) = 1/x$
691where, $x$ represents the total cost of the string. The
692selection criteria depend upon the value of string if it
693is close to some threshold value.
694\item Create new off-spring population from two
695existing chromosomes in the parent population by
696applying crossover operator.
697\item Mutate the resultant off-springs if required. NOTE:
698After the crossover off spring population has the
699fitness value higher than the parents.
700\item Repeat step 3 and 4 until we get an optimal
701solution to the problem.
702\end{enumerate}
703
704\section{BENCHMARKS AND RESULTS}
705
706We benchmarked the Bruteforce algorithm, the Dynamic Programming algorithm and the Minimum Spanning Tree algorithm on an i7 4771H @ 3.7GHz, 16 GB 2400 MHz memory computer, using a sample size of 12 cities and 15 cities, the results were as following:
707
708$$\begin{tabular}{ |p{1.85cm}||p{1.85cm}|p{1.85cm}| }
709 \hline
710 \multicolumn{3}{|c|}{Time Benchmark Between Algorithms} \\
711 \hline
712    Algorithm & $n = 12$ & $n = 15$\\
713 \hline
714    MST & ${<} 10^{-6}$ s & ${<} 10^{-6}$ s\\
715 \hline
716    Bruteforce & 6.66016 s & 19251.49 s\\
717 \hline
718    DP & 0.001996 s & 0.015005 s\\
719 \hline
720\end{tabular}$$
721
722The sample of 12 cities had an optimal solution of 264 and as shown above, all the algorithms returned the same optimal solution, however our modified MST approach had a small chance to hit the optimal solution and it managed to reach that solution due to how the test case is formed. There is also a very slight difference between the Bruteforce algorithm and the DP algorithm (6.66016 vs 0.001996 seconds).
723The sample of 15 cities had an optimal solution of 291 and both the Bruteforce and DP approaches reached the optimal solution successfully (as expected) but with a huge difference in timing (19251.4963 vs 0.015005) respectively, this shows how the DP approach massively improved the exact calculations of the TSP problem, but keeping in mind that the DP approach has a space complexity of $O(2^n n^2)$ which requires a computer with large memory in hand to process. The MST approach achieved a solution of 291 which is better than the average TSP cycle in this sample as the MST algorithm is a 2-approximate algorithm.
724
725We conclude that the MST approach is the fastest, but it doesn't always return an exact solution but it the solution it returns is always better than the average cycle which is enough for us in a lot of cases considering the small running time of the algorithm $O(logn)$, the Bruteforce algorithm isn't efficient to use as it runs in $O(n!)$ but it is the intuitive way to solve this problem, we benchmarked the naive way to show the usefulness of the DP algorithm, as it also returns the exact solution but in a faster time $O(n^2 2^n)$ but also in space complexity of $O(n^2 2^n)$, the Genetic algorithm runs in $O(Kmn)$ which is faster than the DP algorithm but it doesn't guarantee an exact solution, however the solution is usually better than the MST approach,bit it requires a trained model to execute.
726
727$$\begin{tabular}{ |p{1.85cm}||p{1.5cm}|p{1.5cm}|p{2cm}|  }
728 \hline
729 \multicolumn{4}{|c|}{Comparison Between Algorithms} \\
730 \hline
731    Algorithm & Complexity &Advantage&Disadvantage\\
732 \hline
733    MST Approach & O(logn) & Fastest & No solution accuracy\\
734 \hline
735    Dynamic Programming & O($n^22^n$) & Global optimal solution & Expensive for both memory and time\\
736 \hline
737    Genetic Algorithm & O(Kmn) & Best solution using "fitness" criteria & No optimal solution\\
738 \hline
739\end{tabular}$$
740
741\section{CONCLUSION}
742
743The MST Approach to the TSP Problem is the fastest approach, however it does not always give the best answer, but it is a 2-approximate algorithm as stated in the paper, meaning that it's solution is good enough. While the Dynamic Programming solution gives a guaranteed optimal answer to the TSP, it is very slow and inefficient to use as it runs in exponential time and requires exponential memory, but it is still faster than the Bruteforce approach which runs in $n!$ time. The Genetic algorithm appear to find good solutions for the Travelling Salesman Problem,however it depends very much on the way the problem is encoded and which crossover and mutation methods are used Overall, it seems that genetic algorithms have proved suitable for solving the traveling salesman problem. As yet, genetic algorithms have not found a better solution to the traveling salesman problem than is already known, but many of the already known best solutions have been found by some genetic algorithm method also.
744
745\section{FUTURE WORK}
746
747A lot of work is still to be done considering the TSP problem as it is of high importance in the field of Computer Science and to provide an effective way to solve will help us in a lot of applications, so in the future we plan to improve how the Genetic algorithm evaluates the fitness of every generation and the deviation of every generation from one another, it is also required to provide an accurate benchmark on an optimized genetic algorithm to compare its effectiveness with other algorithms benchmarked above
748
749\begin{thebibliography}{00}
750\bibitem{b1} J. Holland, Adaptation in Natural and
751Artificial Systems : An Introductory
752Analysis with applications to biology ,
753Control and Artificial Intelligence. The
754University of Michigan Press,1975.
755\bibitem{b2} Jean-Yves Potvin, “Genetic Algorithms for
756the Traveling Salesman Problem” Centre de
757Recherche sur les Transports Université de
758Montréal C.P. 6128, Succ. A Montréal
759(Québec) Canada H3C 3J7.
760\bibitem{b3} Naveen kumar, Karambir, Rajiv Kumar,
761“A Genetic Algorithm Approach To Study
762Travelling Salesman Problem”, Journal of
763Global Research in Computer Science,
7642012, Vol. 3, No. (3).
765\bibitem{b4} Saloni Gupta, Poonam Panwar “Solving
766Travelling Salesman Problem Using Genetic
767Algorithm” International Journal of
768Advanced Research in Computer Science
769and Software Engineering Volume 3, Issue
7706, June 2013.
771\bibitem{b5} Varunika Arya, Amit Goyal, Vibhuti
772Jaiswal ”An Optimal Solution To Multiple
773Travelling Salesperson Problem Using
774Modified Genetic Algorithm” International
775Journal of Application or Innovation in
776Engineering \& Management (IJAIEM)
777Volume 3, Issue 1,2014.
778\bibitem{b6} S.N.Sivanandam, S.N.Deepa "Introduction
779to Genetic Algorithms" Springer-Verlag
780Berlin Heidelberg 2008.
781
782\bibitem{b7} Monica Sehrawat, Sukhvir Singh,”Modified
783Order Crossover (OX) Operator ” International Journal on Computer Science
784and Engineering (IJCSE) ISSN 0975-3397
785Vol. 3 No. 5 May 2011.
786
787\bibitem{b8} R. Matai, S. Singh, M. L. Mittal,“Traveling Salesman
788Problem: an Overview of Applications, Formulations,
789and Solution Approaches”Traveling Salesman Problem,
790Theory and Applications. InTech, 2010.
791
792\bibitem{b9} https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
793
794\bibitem{b10} Buckly, J. J., Possibilistic linear programming with triangular fuzzy numbers, fuzzy sets and system, 26, 135-138, 1998.
795
796\bibitem{b11} Rommelfanger H., Wolf J. and Hanuschek R., Linear programming with fuzzy objectives, Fuzzy Sets and System, 29, 195-206, 1989.
797
798\end{thebibliography}
799
800
801\end{document}