A Comparative Analysis of Simulated Annealing and Genetic Algorithm

This Jupyter Notebook explores the Traveling Salesperson Problem (TSP) and compares the performance of two well-known optimisation algorithms: Simulated Annealing (SA) and Genetic Algorithm (GA).

The TSP is a classic combinatorial optimisation problem that seeks the shortest possible route visiting a set of cities exactly once and returning to the starting point. It has numerous real-world applications in logistics, transportation, and route planning.

Project Overview

This repository contains two notebooks:

1. p1_ssa_algo.ipynb – Implementation and analysis of Single-Search Algorithms (SSA) for TSP.
2. p2_main_sa_ga.ipynb – Comparison of Simulated Annealing (SA) and Genetic Algorithm (GA) on TSP.

The main objectives include:

• Evaluating solution quality, efficiency, and scalability of each algorithm.
• Visualising the routes generated and convergence trends.
• Comparing the strengths and weaknesses of single-search vs population-based approaches.

Single-Search Algorithms

Single-search algorithms focus on exploring and improving a single solution at a time, often relying on local search strategies. The algorithms considered are:

• Hill Climber
• Stochastic Hill Climbing – probabilistically explores random neighbors to improve solutions.
• Steepest Hill Climbing – deterministically moves to the best neighboring solution.
• Iterated Local Search – combines local optimization with heuristic perturbations to escape local optima.
• Tabu Search – uses memory structures to avoid revisiting recently explored solutions.
• Simulated Annealing (SA) – balances exploration and exploitation by probabilistically accepting worse solutions to escape local minima.

These algorithms are evaluated using key metrics: best distance, average distance, and standard deviation over multiple runs. The top-performing single-search algorithm is then compared with population-based methods like GA in p2_main_sa_ga.ipynb.

Population-Based Algorithm

• Genetic Algorithm (GA) – evolves a population of candidate solutions through selection, crossover, and mutation, aiming to converge to an optimal or near-optimal solution.

Features

• Route Visualizations – graphical representation of city tours for each algorithm.
• Performance Comparison – side-by-side evaluation of SA vs GA in terms of distance, runtime, and convergence.
• Convergence Analysis – plots showing how solutions improve over iterations or generations.
• Algorithm Insights – discussion of strengths, weaknesses, and suitability for complex TSP instances.

Usage

1. Clone or download this repository.
2. Open the notebooks in Jupyter Notebook or **Google Collab **.
3. Run p1_ssa_algo.ipynb to explore Single-Search Algorithms.
4. Run p2_main_sa_ga.ipynb to compare Simulated Annealing and Genetic Algorithm.

Conclusion

This repository provides an in-depth comparison of single-search and population-based optimisation algorithms for TSP, highlighting how algorithm design impacts solution quality, efficiency, and scalability. It serves as a practical reference for anyone interested in ** optimisation algorithms **.

Author

May S.