Implement a genetic algorithm to find a solution to the Traveling Salesman problem for the following distance matrix: In the above distance matrix, each city is labeled 1, 2, 3, ..., 9 along the top...

AI - Genetic Algorithm for the Traveling Salesman Problem


Implement a genetic algorithm to find a solution to the Traveling Salesman problem for the following distance matrix: In the above distance matrix, each city is labeled 1, 2, 3, ..., 9 along the top row and the left column. The distance between city #4 and city #2 is 10 units. Your solution should specify the order of the cities and the distance of the trip. For example, you might get something like: Starting at city 9: Order: 9 -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 9 to 2 is 17 units 2 to 1 is 2 units 1 to 3 is 11 units 3 to 4 is 5 units https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Distance_matrix 4 to 5 is 6 units 5 to 6 is 12 units 6 to 7 is 19 units 7 to 8 is 21 units 8 to 9 is 6 units For a total distance of 99 units. Which is not an optimal solution. A better solution would be something like: Starting at city 1: Order: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 1 1 to 2 is 2 units 2 to 3 is 13 units 3 to 4 is 5 units 4 to 5 is 6 units 5 to 6 is 12 units 6 to 7 is 19 units 7 to 8 is 21 units 8 to 9 is 6 units 9 to 1 is 5 units for a total distance of 89 units. You want your algorithm to find the best combination of city orders to give you the lowest distance traveled possible. In comments in your program, identify your fitness function, mutation function, encoding scheme. It must have some manifestation of crossover, mutation, fitness test, and generational reproduction. To make it easy to identify and organize, I'd place the functionality for each of these in their own functions. Run your algorithm at least ten times, experiment with a different initial population size each time, different number of generations, and report your best solution given your chosen population size and number of generations. Hints: • Here is a tutorial that you may find helpful: tutorial.ppt . • Here is a paper written on the subject. • Don't forget, you are judging fitness by distance and trying to get to a global minimum. • An example crossover function could pick a subset of cities and copy that over, filling in the rest of the set in the same order, filling in the gaps. Example: Parents: 8 6 7 5 3 0 9 1 2 4 ( the subset is underlined ) 0 1 2 3 4 5 6 7 8 9 Child: 1 2 4 5 3 0 9 6 8 7 https://bb.csueastbay.edu/bbcswebdav/pid-7053183-dt-content-rid-70001720_1/xid-70001720_1 https://www.hindawi.com/journals/cin/2017/7430125/