🧬 Genetic Algorithm for Traveling Salesman Problem (TSP)

This project implements a hybrid Genetic Algorithm (GA) enhanced with 2-opt Local Search to solve various Traveling Salesman Problem instances from the TSPLIB library.

🧠 Methodology

The algorithm utilizes advanced genetic operators and local optimization to find near-optimal routes:

• Fitness Function: Routes are evaluated based on the inverse of the total distance: $Fitness = \frac{1}{Distance}$.
• Hybrid Selection: A 50-50 balance between Rank-Based Selection and Roulette Wheel Selection is used to maintain population diversity and selection pressure.
• Crossover: Cycle Crossover (CX) is implemented to ensure that children inherit valid permutations without creating duplicate cities.
• Mutation: A 10% mutation rate is applied, randomly choosing between Insert Mutation and Random Slide (Displacement).
• Local Search (2-opt): In each generation, the elite individual is further optimized using the 2-opt algorithm to reach local optima faster.

📊 Results

The performance of the algorithm has been tested on multiple datasets. Convergence graphs are automatically saved in the results/ directory.

Dataset	Cities	Best Distance Result	Results Graph
berlin52	52	~11516
att48	48	~44626
a280	280	~12364
att532	532	~655610

Note on Parameters: The results above were obtained by tuning pop_size and max_generations for each specific dataset to ensure optimal convergence. Larger instances like att532 require significantly higher population sizes and generation counts due to the complexity of the search space.

📂 Project Structure

• data/: Contains .tsp data files.
• src/: Contains the main Python script ga_tsp_solver.py.
• results/: Stores automatically saved convergence plots (.png).
• .gitignore: Excludes environment and cache files.

🚀 Getting Started

1. Clone the repository:

   git clone https://github.com/goktu9/TSP-Evolutionary-Algorithm.git

2. Install dependencies:

   pip install matplotlib numpy

3. Configure and Run:
   • Open src/ga_tsp_solver.py.
   • At the bottom of the script (Section 5), update the filename_to_run variable and adjust the pop_size or max_generations as needed.
   • Execute the solver:

   python src/ga_tsp_solver.py