TSP using Genetic Algorithm

You are given a set of cities with random coordinates generated in a 2D plane. Your task is to solve the Travelling Salesman Problem (TSP) using a genetic algorithm. You need to generate the cities using a given seed, then run a genetic algorithm to find an approximate shortest route that visits every city exactly once and returns to the starting city.

The genetic algorithm involves the following steps:

• Initialization: Generate an initial population of candidate routes (random permutations of city indices).
• Fitness Evaluation: Compute the total distance of each route. The fitness is defined as the inverse of the total distance.
• Selection: Select routes probabilistically based on their fitness scores to form a mating pool.
• Crossover: Apply an ordered crossover (OX) operator on pairs of selected routes to generate offspring.
• Mutation: With a given mutation rate, randomly swap two cities in a route to maintain genetic diversity.
• Iteration: Repeat the evaluation, selection, crossover, and mutation steps for a given number of generations.

After the genetic algorithm completes, output the best route (a permutation of indices) and its total distance (formatted to two decimals). Note that all random operations must use the provided seed so that the program behavior is deterministic.

Mathematical Formulation:

Let \(C = \{(x_i,y_i)\}_{i=0}^{n-1}\) be the set of city coordinates. For a route \(P = (p_0, p_1, \ldots, p_{n-1})\), the total distance is given by:

[ D(P) = \sum_{i=0}^{n-1} \sqrt{(x_{p_i} - x_{p_{(i+1) \bmod n]}})^2 + (y_{p_i} - y_{p_{(i+1) \bmod n]}})^2} ]

Your solution should read input from standard input and output the result to standard output as described below.

inputFormat

The input is read from standard input and consists of five lines:

1. An integer n representing the number of cities.
2. An integer pop_size denoting the population size.
3. An integer generations denoting the number of generations to run the algorithm.
4. A floating-point number mutation_rate representing the mutation rate.
5. An integer seed to initialize the random number generator.

For example:

4
10
5
0.1
42

outputFormat

Your program should output two lines to standard output:

1. A space‐separated list of integers representing the best route (a permutation of indices from 0 to n-1).
2. The total distance of that route, formatted to two decimal places.

For example:

0 1 2 3
193.21

## sample

4
10
5
0.1
42

0 1 2 3
193.21

</p>