Visualizing and Comparing TSP Solving Algorithms
- Problem Statement: Develop a program to visualize and compare the performance of Simulated Annealing and Genetic Algorithm approaches to the Traveling Salesman Problem. By focusing on the time complexity and solution convergence of these metaheuristic techniques, we can gain insight into computational time complexity of both algorithms and their solving approach.
- Objectives:• To develop a program to implement simulated annealing and genetic algorithm solutions for the traveling salesman problem (TSP). • To visualize their performance over increasing problem sizes. • Compare the computational time complexity between algorithms.
- Project date: 17 December, 2023
- Project URL: GitHub Repository
Abstract
The traveling salesman problem (TSP) aims to find the shortest route visiting each city exactly once in a list and returning to the starting city. As the number of cities grows, the solution space increases exponentially, making brute force approaches intractable. This project compares two heuristic techniques for TSP solutions - simulated annealing and genetic algorithms. Both leverage probabilistic transitions and bio-inspired operators to efficiently search large solution spaces. We develop a visualization program implementing these techniques to compare their time complexity on TSP instances of varying sizes. The goal is to gain insight into balancing solution quality with computational resources. By understanding the trade-offs between these two metaheuristics, we can select the appropriate technique for a given problem instance based on available resources and solution accuracy needs. This project provides guidance for applying heuristics on complex combinatorial optimization challenges involving exponential search spaces.