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.
Solution
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