Write an EA to solve the Traveling Salesman Problem (TSP).

Using any EA packages or libraries is not permitted. Please implement your own EA from scratch.

1. Input

The standard input of TSP is a list of city ID and coordinates as follows,

1 11003.611100 42102.500000

2 11108.611100 42373.888900

3 11133.333300 42885.833300

4 11155.833300 42712.500000

5 11183.333300 42933.333300

6 11297.500000 42853.333300

7 11310.277800 42929.444400

8 11416.666700 42983.333300

9 11423.888900 43000.277800

10 11438.333300 42057.222200

Two input files, TSP_WesternSahara_29 and TSP_Uruguay_734, will be provided in BrightSpace. The representation of your EA should be the permutation of all city IDs and the fitness function is the total tour length. Your program will be tested from the command line using the two problem instances. Your program should have at least three arguments, the population size, the mutation rate, and the crossover rate. Provide a readme.txt file to describe how to execute your program from the command line and if there are any extra parameters to input.

2. Output

To the standard output, the best fitness, worst fitness, and the average fitness in the population of each generation, the final best solution in the format of a permutation of all city IDs and its fitness.

Submit the following three items in a zip file.

A) Your source code

B) A readme.txt for program execution instruction (your program should be able to execute using command line)

C) A document on the description of your algorithm and its results.

This should include a table listing

a) Initialization method

b) Parent selection method

c) Mutation method

d) Crossover method

e) Survivor selection method

f) Termination condition

g) Set of parameters

h) Runtime for each TSP instance

and a graph showing the best fitness, worst fitness, and average fitness in the population as a function of generation for each TSP instance.