Traveling Salesman Problem $($TSP$)$

The Traveling Salesman Problem $($TSP$)$ is a fundamental combinatorial optimization problem characterized by the following key aspects:

Shortest Possible Tour: The primary objective of the TSP is to find the shortest possible tour that enables a salesperson to visit a predefined set of cities exactly once and return to the starting city. In this context, a "tour" refers to the sequence in which the cities are visited, forming a closed loop.

Cities as Nodes: In the TSP$,$ the cities are typically represented as nodes or vertices in a graph. Each city is connected to every other city through edges or arcs, and these connections define the distances or edge weights between cities. These distances represent the cost or distance associated with traveling from one city to another.

Permutation of Cities: The fundamental goal of the TSP is to determine a permutation of cities that results in the minimum total distance traveled. This permutation represents the optimal order in which the cities should be visited to minimize the salesperson's travel distance. It is worth noting that the starting and ending point of the tour is usually the same city, as the salesperson returns to the initial location after visiting all cities.

Genetic Algorithm $($GA$)$

The Genetic Algorithm is a heuristic optimization technique inspired by the process of natural selection.

GA uses the principles of selection, crossover $($recombination$),$ mutation, and population evolution to search for optimal solutions.

In this project, the GA is used to evolve and improve solutions to the TSP$.$

General Steps of Genetic Algorithm

The Genetic Algorithm $($GA$)$ employed to solve the Traveling Salesman Problem $($TSP$)$ follows a series of well$-$defined steps to iteratively evolve and improve candidate solutions:

Initialization: At the beginning of the GA process, an initial population of candidate solutions, also known as tours, is created. In the context of the TSP$,$ this involves generating a set of random permutations of cities. Each permutation represents a different tour.

Selection: The selection step involves choosing parent solutions from the current population based on their fitness, which in the case of the TSP$,$ corresponds to the shortness of the tour. The project employs the tournament selection method, where individuals are randomly grouped into tournaments, and the fittest individuals from each tournament are selected as parents for the next generation.

Crossover $($Recombination$)$: In the crossover step, offspring solutions are created by combining genetic material from two parent solutions. For this project, ordered crossover $($also known as partially mapped crossover$)$ is used. It involves selecting a segment of one parent's tour and filling in the remaining cities with the order from the other parent's tour. The crossover rate parameter is used to control the likelihood of crossover occurring.

Mutation: Mutation introduces small random changes into some offspring solutions. In this project, swap mutation is applied, which means that with a certain mutation rate, two cities in the tour are randomly selected and swapped. This introduces diversity and helps avoid getting stuck in local optima.

Replacement: In the replacement step, old solutions in the current population are replaced with the new offspring solutions. The goal is to maintain the population size and replace less fit solutions with potentially better ones.

Termination: The iterative process of selection, crossover, mutation, and replacement is repeated for a fixed number of generations or until a termination criterion is met. The termination criterion could be a maximum number of generations, convergence of the best tour found, or a time limit$.$ In this project, we will use the number of generations for simplicity.

Genetic Algorithm Parameters

There are four major parameters that should be included. You can pass them as parameters to the constructor of the algorithm. You will need to tweak their values if your algorithm does not run efficiently. I will suggest some good starting values here.

Population size You can start with $10$ times of the number of cities.

Number of generations You can start with $100$ times of the number of cities.

Crossover rate Start with $0\mathrm{.}8$

Mutation rate Start with $0\mathrm{.}2$

The algorithm class

Refer to the provided brute$-$force algorithm for the recommended interface for the algorithm.

$.$computeShortestTour$()$ to return the distance of the best tour

$.$getBestTour$()$ to return the tour as a vector type value

Input CSV File

To facilitate the Traveling Salesman Problem $($TSP$)$ solving process, it's essential to efficiently handle the input CSV file containing connectivity information. The following steps outline how to process the data:

Input File Format: The provided input CSV file has the following format:

The file contains $20$ lines of $20$ comma$-$separated double values.

The values represent distances or costs between cities in a symmetric ma