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: Rank-based selection (Elitism) + Swap mutation + Cycle Crossover
Approach II: Rank-based 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(mn2) |
Displacement + Cycle crossover |
O(n) X O (NpL) x O (N-L+1) X O(mn) = O(mn2) x O(n-l+1) X O (NcL) |
Dynamic Programming |
O(n!) |
Table 3:
Calculates complexity values for each solution technique
- Varying number of cities,
- Length of ‘l’ is set to be (n-2),
- 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.
Assignment Writing Help
Engineering Assignment Services
Do My Assignment Help
Write My Essay Services