A Genetic Diversion
In the previous blog I mentioned that I had settled on some open source python, python-mip, to generate my route. It had code like this:
distances in an upper triangular matrix dists = [[83, 81, 113, 52, 42, 73, 44, 23, 91, 105, 90, 124, 57],
This is an array of data that represents the distance between all the destinations. I needed to make the same list but for my bridges. In Computing the optimal road trip across the U.S, Randal S. Olson has given us code to do that. So I installed the various python packages, got my google maps API Key, and ran the program. It failed. The data I had in my spreadsheet had entries like 42 46.638, -72 25.421 which works fine with google maps, but not with the python code. I also realized that since I was getting an exact route, I really should get my data more precise, and also get my data to the parking spot, not the bridge. So I went down the list and visited every bridge in Google Maps, found the parking spot, and copy pasted the new data, which looked like this: 42°46’38.7″N 72°25’24.2″W.
So I put that into the python code and it didn’t work, and yes, I tried things like removing the degree symbol and the quotes. But it did work on the addresses in the list. So I ran the program just see it run and I got all my data.
Next step was to get it into python-mip, right? Nope. You see, Dr. Olson also has a genetic solution. Now his genetic solution is not provably optimal, but it is fast. So I just had to run it.
But’s lets digress. What is a genetic program? It is a type of programming where you evolve a solution. You need two things, a way to represent your solution, in this case it would be the route, and fitness metric, a way of evaluating which solution is better. And just like “real” evolution the fittest solution wins. The way it works is that “DNA” from the better solution moves to the next generation, and both parents contribute the rest. Of course you have mutations, but where’s the fun if you’re not mutating, right? Fullstack Academy has a great, and short, video describing Genetic Programing and the TSP!
But yeah, I had to run it, even with the imprecise street addresses. And here’s the route. Actually, it’s up there, it was so narrow I nudged it up a tiny bit.
There are a few things to notice. The most obvious issue is that it crosses itself!
Go home genetics, you’re drunk! Intuitively this seems wrong. And in my reading, other researchers also think that solutions that cross are not optimal. But it did nail the beginning:
That’s better than I did. I did some hand waving saying, and just drive from the last bridge to the first to make the loop. This loop looks better. And it also seems to have really nailed the Campton area:
And finally, notice what it did in the White Mountains. Conway, then north up to Pittsburgh, then it hits Lincoln. That path never occurred to me.
So, how did it do? Uhhh, 668 miles. My hand route was 643 miles. But, it only ran 5,000 generations and that only took 15 seconds on my laptop. Let’s try larger numbers and see if that helps. (But I’m not hopeful, the video shows that a genetic algorithm for their weird circle route often converges on something not optimal.)
25,000 evolutions only trimmed 14 miles, so my hand drawn one was still 11 miles shorter. And it still get confused in the middle part of the state.
But… you can see that a genetic algorithm is a very efficient way of getting a pretty good answer.