Travelling Salesman Problem using Genetic Algorithm
Executive summary
The Travelling Salesman Problem is to find the best path for a salesman who intends to travel n number of cities. Cost of traversing this path is directly proportional to the distance covered. The distance matrix depicting the value between any two cities is chosen at random. Further on rank based strategy, the elite combination is made to mutate and they must produce further fittest surviving combinations. The best result on performing mutation and crossover is outputted as result. This report shows the results obtained after multiple runs using different mutation techniques and draw analysis to identify which set of technical approach brings better results in least amount of time.
Choice of approaches:
Approach I: Rankbased selection (Elitism) + Swap mutation + Cycle Crossover
Approach II: Rankbased selection + Displacement mutation + Cycle Crossover
List of assumption made in code
Analysis:
Analysis will be done in 2 parts: 1. Compare two GA strategies as decided.
The source code is run 10 times. Following data is recorded in Table 1.
Table 1
INDEX 
Approach I  SWAP MUTATION AND CYCLE CROSSOVER 
Approach II  DISPLACEMENT MUTATION & CYCLE CROSSOVER 

Cost 
Iteration 
Time (in ms) 
Cost 
Iteration 
Time 

1 
2096 
63 
6 
2275 
76 
17 
2 
1895 
65 
6 
2499 
66 
17 
3 
1845 
60 
6 
2212 
68 
16 
4 
1767 
59 
6 
2003 
79 
16 
5 
2044 
62 
2 
2606 
74 
11 
6 
1611 
64 
7 
2323 
70 
15 
7 
1780 
60 
7 
2240 
65 
16 
8 
1463 
63 
7 
2047 
60 
18 
9 
1673 
66 
2 
2320 
76 
14 
10 
1600 
63 
2 
2208 
53 
16 
Average Values 
1777.4 
62.5 
5.1 
2273.3 
68.7 
15.6 
Best value 
1463 
59 
2 
2003 
53 
11 
Observations
Inferences based on observation:
Graph 1 shows below support the inferences made:
Graph 2
Performance evaluation
The TSP problem under current scenario is symmetric. This implies that the cost to reach point B from A and point A from B is same. For an example involving only 3 cities say 1, 2 and 3. It is easy to compute the best path among [1, 2, 3] and [1, 3, 2] believing the salesman starts from city 1. But with increasing number of cities, these calculations of possible permutations will become complex, exhaustive and time consuming. The Genetic Algorithm approach aims to solve this issue. Evaluation has been made on the basis of performance displayed by these algorithms using an Intel core i3 processor system with respect to time, memory used and quality of solution obtained.
Table 2:
ALGORITHM 
COMPLEXITY 
Swap mutation + Cycle crossover 
O(n) X O(1) X O(mn) = O(mn^{2}) 
Displacement + Cycle crossover 
O(n) X O (^{N}p_{L}) x O (NL+1) X O(mn) = O(mn^{2}) x O(nl+1) X O (^{N}c_{L}) 
Dynamic Programming 
O(n!) 
Table 3:
Calculates complexity values for each solution technique
 Varying number of cities,
 Length of ‘l’ is set to be (n2),
 Value of ‘m’ is maxed out to be 100.
NUMBER OF CITIES 
SWAP + CYCLE 
DISPLACEMENT + CYCLE 
LOCAL SEARCH ALGORITHM / DIRECT COMPUTATION 
5 
2500 
75000 
120 
10 
10000 
2565000 
3628800 
20 
40000 
2.3e + 7 
2.43e +18 
50 
250000 
9.2e + 8 
3.04e + 64 
100 
1000000 
1.5e + 10 
9.3e + 157 
Conclusion
Based on the calculations above, it is clear that with increasing number of cities, swap mutation + cycle crossover will give cost values faster as compared to second GA approach or local search. Difference between complexities of algorithm is huge and suggests use of evolutionary genetic algorithm in real world computation where the geographical space is diverse and areas are divided into many cities. Using dynamic programming after a certain value of n will consume lot of space and time to yield results.
However, the GA algorithm may get stuck at local minima values. To avoid such situations , value of m and l must be changed accordingly and algorithm should be run multiple times before reaching to a result in real life applications. The aim must be to move as close to global minima as possible.
Urgenthomework helped me with finance homework problems and taught math portion of my course as well. Initially, I used a tutor that taught me math course I felt that as if I was not getting the help I needed. With the help of Urgenthomework, I got precisely where I was weak: Sheryl. Read More
Follow Us