Step 6. Genetic Algorithm for TSP

Video

World

GA (TSP)
Genetic Algorithm to solve the Traveling Salesman Problem.

Notes

• Reload for a new random Traveling Salesman Problem.
• This shows that for large problems, "Routes looked at as fraction of possible routes" is tiny, yet route looks pretty good pretty fast.

Credits

• This is a port of "CC_035.4_TSP_GA" from The Coding Train.
• Original version is online at P5 editor.
• See videos parts one and two.
• See other links in code.

Exercise

1. Change parameters at the top.

2. Q. What is the smallest number of cities for which it will search all possible routes in a reasonable time?
   (Technically we are not sure it searches all n possible different routes. All we can say is it does n evolutionary tests. But that shows how a systematic algorithm could search all n routes in the same time.)

3. Change the code to do random search and see how it does.
4. Change the code to exhaustively (systematically) search where possible.