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
Initial run on 48 states, obviously stunk. only had two ways to get
next generation and one of them was flawed.
many modifications to algorithm. this answer is being confirmed by
brute force now (3/31/98 12:18 pm) ---- stopped because of algorithm change
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
sum = 7339
sum = 10979. Note that this algorithm is not as good for the 48 states
as the previous.
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.
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
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
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
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
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
This revision ran for quite a while confirming the 10737. Then I wrote
a better version for #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
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