Help with a generic python algorithm for the traveling salesperson coding problem.

$66\mathrm{.}1$ A Genetic Algorithm for the Traveling Salesperson Problem

In this lab, you are tasked with writing the critical portions of a genetic algorithm to solve the traveling salesperson problem $($TSP$).$

Specifically you will write a routine ga$\_$tsp $($initial$\_$population, distances, generations$)$ which is given an initial population

of valid Hamiltonian paths $($initial$\_$population, which is a list of paths $[$tuples$]),$ a dictionary of distances $($distances$),$ and the

number of generations $($generations$)$ that your algorithm should run. After completing the requisite number of generations, ga$\_$tsp $()$

should return the best path $[$tuple$]$ from the final generation.

Note that a generation is defined as a single iteration of the algorithm $($parent selection, crossover, selection of the fittest population$)$

using a steady population across generations $($the same number of children as there are parents$).$ If you use a variation of the above

approach, such as creating half the number of children compared to the population size, you'll need to perform twice the number of

iterations $($generations$).$

Details

A path is a tuple listing all "cities" in the path. It assumed the path is a Hamiltonian circuit that completes by taking an edge from the last

city listed back to the first city listed. Do not list the first city twice $($at the start and end of the list$)!$

We are providing several supporting routines and files:

util.py contains three utility routines. cost$($path$,$ distances$)$ will return the cost of a path. As a debugging aid, cost$()$ checks that the path and distance dictionary are valid and will return None if not $($this should cause your code to throw a TypeError if you use the return value$).$ Note that cost$()$ may not detect all invalid paths. valid$\_$path$($path$)$ confirms the path is internally sound $($no repetitions$).$ best$\_$path$($list$\_$of$\_$paths, distances$)$ returns the best $($lowest cost$)$ path in list$\_$of$\_$paths.

load$\_$dist$($filename$)$ will load a dictionary of distances from the file named filename and can be imported from load$\_$dist.py$.$ The format of filename is individual lines of the form $"$A$,$ B$,$ distance" where A and B are city names and distance is a positive integer distance. A line causes the distance from A to B and B to A to be loaded into the dictionary. A line starting with # is a comment. Comment lines and blank lines are ignored. load$\_$dist also ensures that the distance from a node to itself is always zero. You can update the A to B $($B to A$)$ distance later in the file $--$ so if you want to slightly change the topology $($aka distances$),$ you can just add a custom update to the end of the file. load$\_$dist$()$ returns a list of all the city names and a dictionary of distances. load$\_$dist$()$ returns None, None if the file did not load properly.

tsp$.$py if run at the command line with a filename, so $\%$ python$3$ tsp$.$py filename will load distances from filename, compute an initial population, and call ga$\_$tsp$()$ to run $100$ generations and report if ga$\_$tsp$()$ found a better result than was in the initial population.

init$\_$pop.py contains two routines to create an initial population. These routines are called in tsp$.$py$.$ One version of the routine, init$\_$pop$($list$,$ dist$),$ take a list of cities and the distance matrix and generates a random set of initial paths of appropriate size. The other version, init$\_$lousy$(),$ intentionally creates an initial set of paths with high costs $--$ which may be useful for debugging. $($Instructions for using int$\_$lousy$()$ are in the file and in comments in tsp$.$py$).$

two$\_$opt.py contains the $2-$opt algorithm described in class, designed to use the lab's cost function. You are not required to use $2-$opt in your implementation. It is provided solely for your convenience.

We are providing two sample distance files: DIST$6-$simple is a simple $6$ city world with a clear best path. DIST$23-$basic is a $23$ city world divided up into $3$ districts $($clouds$).$

More Details

If ga$\_$tsp is given None for any argument it should return None. If generations is not positive, ga$\_$tsp should return None. You can assume distances and initial$\_$population are valid if non$-$None.

Performance

We have no big$-$O performance requirements for this assignment. Rather we will run some tests designed to see if your genetic algorithm finds better results than the best path in the initial population $($you can assume we'll rig the initial population so a range of better solutions are feasible$).$