The Traveling Salesman Problem and Evolutionary Algorithms
School: Manzano High
Area of Science: Mathematics
Team Number: 082
School Name: Manzano High School
Area Of Science: Mathematics
Project Title: The Traveling Salesman Problem and Evolutionary Algorithms
Evolutionary algorithms apply the principles of evolution to finding an optimal solution of a complex problem. These algorithms are useful in solving problems which are otherwise too difficult to solve.
NP-complete problems are problems where the amount of time to solve the problem increases quickly with the size of the problem. Our focus is on the traveling salesman problem, which is finding the shortest path to travel between a list of cities with varying distances. Exact solutions to the problem become unfeasible as the number of cities increases due to large increase in computation time.
Our solution to the traveling salesman problem will use evolutionary algorithms to optimize the time it takes to obtain the near-optimal solution. We will compare the evolutionary algorithm to other methods, such as brute force techniques. Afterward, we will develop an equation that correlates the compute time of some of the algorithms to number of cities.
Progress to Date:
So far we have created generators for TSP problems in Python. Some of these problems will have known solutions (e.g. a straight line or a circle). These known-answer-tests will be used to see how well later algorithms solve the TSP problem. We have a random generator which will randomize the distance between the cities, the line generator which is great for checking if our solvers are working right, and a circles generator which allows us to do a circle and spokes shape which can be tricky for something like a greedy solver (which would have no trouble with the line generator). We have also written a greedy solver and two versions of a recursive brute force solver in Python. One version of the brute force solver checks every possible solution. The other brute force solver includes pruning, which will cut off whole branches of the recursion tree if the current distance is already greater than our current solution.
We have tested both brute force solvers to see how long they took on varying numbers of cities. To do so we created a program that would create a file of randomly generated cities, and pass it to the solver to solve, timing how long it took to solve, and pushing that to a file. We are able to use this data to extrapolate compute times for large numbers of cities that would take to long to solve using our brute force solutions by plotting these times on a logarithmic graph.
We have created a baseline for solving the TSP problem using exact solvers. We have also created generators for known-answer-tests so that we can check our evolutionary algorithms to see how "optimal" there solutions are. We have data that allows us to extrapolate solve times for problems we don't have time to solve.
With this base, we can find how good the evolutionary algorithms are and how long they take compared to the brute force solutions. We hope to see our evolutionary program solve for large numbers of cities (100's or thousands as compared to less than 20 for a brute force solver) with good accuracy (20% of the exact solution).
Sponsoring Teacher: Stephen Schum
Mail the entire Team