Algorithm of the Gods V1.2

  • Thread starter Thread starter Alex Balfour
  • Start date Start date
A

Alex Balfour

Algorithm of the Gods V1.2 is now available from:

http://www.stokepoges.plus.com

Algorithm of the Gods solves "Travelling Salesman" problems for up to
3000 towns and cities. New features in V1.2 (thanks to New Zealander
Tony Cooper) are:

A graphical interface has been added to allow the interactive plotting
of the points (left-click to place a point at the cursor) and to allow
the progress of the convergence to be viewed visually. This second
capability provides dramatic visual evidence of the effectiveness of the
underlying algorithm.

By compiling optimised code with run-time checks removed, running times
have been significantly improved. For example, on an AMD Athlon XP 1900+
based system, a 500-point problem now takes around 33 seconds, and a
1000-point problem around 85 seconds.

Enjoy!

Alex Balfour
 
Algorithm of the Gods V1.2 is now available from:

Algorithm of the Gods solves "Travelling Salesman" problems
Click to expand...

< snip >

Which problems ? Anyone got any idea what this program is for ?
 
----- Original Message -----
From: "John Fitzsimons"
8<snip>8
Newsgroups: alt.comp.freeware
Sent: Sunday, February 22, 2004 6:25 AM
Subject: Re: Algorithm of the Gods V1.2

< snip >

Which problems ? Anyone got any idea what this program is for ?
Click to expand...

The "Traveling Salesman" problem is a famous
and important theoretical mathematics problem
(in Graph Theory, Combinatorics, Computational
Mathematics, Combinatorial Optimization, ...)
with practical applications.

It's been around a long time (maybe since the
1920's?).

It's a very famous problem in Computer Science
because it seems so simple, but is so very hard.
(There is an obvious brute force solution.
The real problem is finding a better solution,
that doesn't take so long to compute.)


Given a finite set of cities (or locations, or
destinations) and the distances (or "costs" of travel)
between them, how do you (relatively quickly) find a
minimal length (cost) path that goes (from city to city)
thru all the cities?

I.e., find the best (shortest) path for a "traveling
salesman" with a given list of cities to visit.


I don't remember whether the problem specifies a
start or stop city, or maybe insists the route be a loop.

I don't remember whether the problem requires that
each city be visited only once, or maybe that just
falls out as a result of the preliminary analysis, or
maybe there is an example which requires returning
to a city more than once.


A brute force solution, computing the length of each
possible path, is too slow, for large numbers of cities.


The problem is simple to state, and can even be
done by brute force by hand for small examples,
but gets exponentially harder as the number of
"cities" increases.

It looks like it should be easy to do by computer,
but for large numbers of cities, the brute force
approach is just too slow.

It is surprising how much work one more city
creates.


If you "relax" the "minimum length" requirement,
things improve a little. I.e. how do you find a
good (not necessarily minimal) path?

Last I knew, the best practical solutions did not
guarantee absolute minimum length paths, but
generated heuristic good-but-not-necessarily-best
answers.

(Hmm . . . I could be wrong about that. ????)


Umm . . . searching for "Traveling Salesman Problem"
will lead you to sites like
http://www.math.princeton.edu/tsp/
Traveling Salesman Problem - Home Page
which contains
http://www.math.princeton.edu/tsp/histmain.html
History of the Traveling Salesman Problem
which might explain this better.


Maybe these are a better introduction
http://www.crpc.rice.edu/CRPC/newsletters/jan93/news.tsp.html
World-Record Traveling Salesman Problem for 3038 Cities Solved

http://www.crpc.rice.edu/CRPC/newsArchive/tsp.html
CRPC Researchers Solve Traveling Salesman Problem for Record-Breaking
13,509 Cities


Oh! I just visited the "Algorithm of the Gods" site.
They're using a "simulated annealing" algorithm.
I'm not certain, but I think this is one of the "heuristic"
algorithms. I don't see how they could guarantee a
minimal cost path. But maybe I'm missing something.

Aloha,
-- "Mad" (not angry, just strange)
Kenneth Kawamura
Lansing, Michigan
USA
 
As covered in the readme file, you are correct about the simulated
annealing algorithm not necessarily producing the optimum path. However,
what is remarkable about the algorithm is that it produces a result
close to the optimum path amazingly quickly. For most practical purposes
this is more than sufficient.

Alex Balfour
 
Alex Balfour said:
[top-posting moved to bottom]
"Mad" wrote:
8 said:
Oh! I just visited the "Algorithm of the Gods" site.
They're using a "simulated annealing" algorithm.
I'm not certain, but I think this is one of the "heuristic"
algorithms. I don't see how they could guarantee a
minimal cost path. But maybe I'm missing something.
Click to expand...
Click to expand...
8 said:
As covered in the readme file, you are correct about the simulated
annealing algorithm not necessarily producing the optimum path. However,
what is remarkable about the algorithm is that it produces a result
close to the optimum path amazingly quickly. For most practical purposes
this is more than sufficient.

Alex Balfour
Click to expand...

Aloha Alex Balfour,

Thank you for those details. I'm about a quarter-
century behind the times on the TSP, I've been out
of school a long time, so I wasn't absolutely sure.

I did not download the program, nor unzip it, so I did
not see the readme file. Sorry.


I agree. I'm sure the algorithm is "amazingly quick"
and its results are "close to the optimum path" and
"more than sufficient" "for most practical purposes".


I meant no offense; only that the site did not make it
clear that the algorithm does not solve the original
problem.

As a former Mathematics student I tend to be a little
over-sensitive to "solutions" that solve a "related"
problem instead of the original problem.

And since I was replying to someone who apparently
had never heard of TSPs, I did not want him to be
misled.


Linear Programming, Non-Linear Programming,
"Simulated Annealing", "Relaxation", "Monte Carlo
Method", "Stochastic Algorithms", "Parallel
Processing" algorithms, "Genetic Programming"
(and I don't know what other newer techniques)
are wonderful. But mathematically, it is nice to know
their limitations, i.e. when they really do or don't
solve the problem, or at least whether they might
not produce a good-enough solution. Especially
since there is the temptation to use them for
life-or-death applications like atom bomb design,
weather prediction, medical applications, war and
disease simulations, ...

(I know, I'm being pessimistic.)

Aloha,
 
Mad said:
Alex Balfour said:
[top-posting moved to bottom]
"Mad" wrote:
8 said:
Oh! I just visited the "Algorithm of the Gods" site.
They're using a "simulated annealing" algorithm.
I'm not certain, but I think this is one of the "heuristic"
algorithms. I don't see how they could guarantee a
minimal cost path. But maybe I'm missing something.
Click to expand...
Click to expand...
8 said:
As covered in the readme file, you are correct about the simulated
annealing algorithm not necessarily producing the optimum path.
However, what is remarkable about the algorithm is that it produces
a result close to the optimum path amazingly quickly. For most
practical purposes this is more than sufficient.

Alex Balfour
Click to expand...

Aloha Alex Balfour,

Thank you for those details. I'm about a quarter-
century behind the times on the TSP, I've been out
of school a long time, so I wasn't absolutely sure.

I did not download the program, nor unzip it, so I did
not see the readme file. Sorry.


I agree. I'm sure the algorithm is "amazingly quick"
and its results are "close to the optimum path" and
"more than sufficient" "for most practical purposes".


I meant no offense; only that the site did not make it
clear that the algorithm does not solve the original
problem.

As a former Mathematics student I tend to be a little
over-sensitive to "solutions" that solve a "related"
problem instead of the original problem.

And since I was replying to someone who apparently
had never heard of TSPs, I did not want him to be
misled.


Linear Programming, Non-Linear Programming,
"Simulated Annealing", "Relaxation", "Monte Carlo
Method", "Stochastic Algorithms", "Parallel
Processing" algorithms, "Genetic Programming"
(and I don't know what other newer techniques)
are wonderful. But mathematically, it is nice to know
their limitations, i.e. when they really do or don't
solve the problem, or at least whether they might
not produce a good-enough solution. Especially
since there is the temptation to use them for
life-or-death applications like atom bomb design,
weather prediction, medical applications, war and
disease simulations, ...

(I know, I'm being pessimistic.)

Aloha,
Click to expand...

No offence taken!

Alex
 
----- Original Message -----
From: "John Fitzsimons"
Click to expand...

Given a finite set of cities (or locations, or
destinations) and the distances (or "costs" of travel)
between them, how do you (relatively quickly) find a
minimal length (cost) path that goes (from city to city)
thru all the cities?
Click to expand...

< snip >

Okay, thanks.
 
Back
Top