Tour of the U. S.

5/21: At this point, I am declaring victory. It has tried 19,178,267,500 mutations of the solution, which I think is enough to call it correct. It should be noted, however, that 19 billion is less then 10 - 49%. However, most of the ones it didn't try are silly ones, such as the one found by algorithm #0, below. But, the fact still remains that it may not be the best solution. However, it is decidedly possible that it is.


Total length: 10,660 miles.

Below is the results of the major revisions of the algorithm through its evolution.

Algorithm #0

Initial run on 48 states, obviously stunk. only had two ways to get next generation and one of them was flawed.

Algorithm #1

many modifications to algorithm. this answer is being confirmed by brute force now (3/31/98 12:18 pm) ---- stopped because of algorithm change

Algorithm #2

sum = 6578, confirmed with brute force.

sum = 7339

sum = 10885
after reading the book on computer algorithms, I realized that a tour is supposed to be a complete circle. Fortunately, I only had to change code in two places, the part that sums the tours, and the part that prints them out.

Algorithm #3

sum = 7339

sum = 10979. Note that this algorithm is not as good for the 48 states as the previous.

Algorithm #4

With this, I made it so it could take a group of states and rotate it any number of times. However, it was weighted toward the small rotation widths. Notice that Kentucky would be better between Ohio and Indiana. sum = 10772.

Algorithm #5

We're getting there: I implemented a change where at the end, it would take every city and say, what if we moved that one city between these two?, for every pair of cities. This fixed kentucky/tenessee, but UT/WY/CO are back on the southern route. sum = 10904

Algorithm #6

In this algorithm, I made it so it tried every pair of cities in every position, including the pair in both orders. This made Inidina/Illanois area better, but I'll have to do it with three too make UT/WY/CO go on the northern troute. sum = 10875

Algorithm #7

Very unusual. In this algorithm, I added a "randomize" mutation: it would choose a random range, and just randomly move things around for a while. It made it find this answer in 1000 generations less than algorithm #6. It's also the best value so far.(by two miles) sum = 10770

Algorithm #8

This algorithm has the same result as #7. Here, I made it so it would do 7*(num nodes) generations of pure randomize mutations. The fact that it gave the same answer may or may not be significant. sum = 10770

Algorithm #9

I'm liking this. Best value so far by 33 miles. Cheyanne, Denver and Salt Lake City are back on the Northern leg, where they belong. The midwest is rather unusual, though... I may add another modification for it to do at the end. sum = 10737

Algorithm #10

This revision ran for quite a while confirming the 10737. Then I wrote a better version for #11.

Algorithm #11

4/19: This revision is a mostly re-written version of #10. It runs longer, faster, and is multi-instance aware. This way, I can run it on all the CS computers at once without any problems. (Obviously, I am turning down the priority of my program so the people who are actually using that computer don't notice a slowdown.) It is currently running to confirm the 10737 answer.
4/23: This revision just found 10673 miles. I'll graph it later after I get some kinks worked out of the program. (When I start it up on all 73 CS computers, about half of them crash. )
4/24: Found 10660. Fixed the problem with half of the 73 crashing, now about 4 crash spread out over the hour and a half running time. I can live with four crashing.
4/26: I accidentially deleted the data for the 10660. However, the first running of the program found it again.

Last update: 4/29/98