The objective was to implement two different search algorithms to solve the Travelling Salesman Problem. The assignment also required enhancing the two basic algorithms with a variety of unorthodox techniques that might improve the algorithms searching time for the TSP.
The 1st algorithm chosen was Simulated Annealing.
The enhancements made in the simulated annealing algorithm was to generate the initial solution using a nearest neighbour algorithm, providing a better starting point than random generation and allowing for a smaller, but better search space. This lgorithm also consistently outperformed the random initial tour generation. There was also a difference in generation of successor tours in that at the initial generations, it was preferred to generate solutions using a random swap, to allow for more exploration of the search space, as it allowed for more variability in the solutions generated. However, as the temperature kept decreasing, inversion of the subtour was preferred to allow exploitation of the local optima that had been reached. This dynamic approach allowed for a higher chance of reaching good solutions.
The 2nd algorithm chosen was the 'Genetic Algorithm'.
The fitness function was changed to now be the inverse of the distances rather than the maximum distance removed from all others in the tour. This change allowed for an increase in sensitivity to distance variation between two solutions. Smaller reductions in tour length usually had large impact on the probability that it would be selected thus allowing for a higher chance of better parents to be selected for creating offsprings. A new kind of crossover was implemented, known as Cyclic Crossover (CX), which helps preserve sequences/segments of city distances, and in the later stages of the algorithm, allowed for good solutions to be preserved and potentially made better. CX helped enhance the exploitation apability of the algorithm, especially in the latter stages. This crossover was in conjunction with the strategy to increase the probability of CX being done rather than the use of random crossover, which had a higher probability at the start of the algorithm’s generations. Similarly, a new mutation technique was employed, which helped to cut off the worst consecutive distance between two cities in a tour, and replace it with a random city, this allowed for a better offsprings creation. Mutation was also enhanced in that it was done to allow higher rates of mutation to occur early on, to once again, allow for exploration of the search space. The combination of these strategies did end up working and the algorithm showed significant improvement than the general one, especially for the larger city sets.