Image:Slim Films
GALAXY SEARCH was made possible by a heavenly
algorithm. 
Algorithm of the Godsby Shawn Carlson
I used to spend my days (and I do mean my days) hunting for supernovae.
The astrophysics group I worked for dusted off an old 30inch telescope,
then used only for teaching, and converted it into a fully automated
research instrument. When night arrived, this computercontrolled marvel
woke up, checked its systems and set about the business of discovery. On
clear nights it scanned hundreds of galaxies, searching for objects that
appeared as bright stars not detected in earlier images. Sometimes it
found them.
It was wonderful! And I didn't feel too guilty about not freezing all
night in a remote observatory. I had toiled in cyberhell for months
teaching the telescope's computer how to decide which galaxies to image
and in what order it should observe them. Because large excursions from
horizon to horizon sent the telescope's 40yearold drive system into
shock, it was vital that the feeble old veteran be moved as little as
possible. That meant ordering the galaxies into a sequence that, totaled
over the whole night, required the telescope to move through the smallest
possible angle. Computer aficionados will recognize my galaxy conundrum as
a variant of the classic traveling salesman problem, in which a huckster
seeks an itinerary that will let him travel the smallest possible distance
through a list of cities.
The problem of minimizing the telescope's motion appeared intractable.
There are nearly 10^{375} different ways to sort 200 galaxiesa
fairly typical evening's caseload for our telescope. (For you math types,
10375 is 200 factorial.) To find the one way of ordering the galaxies for
a search that put the absolute least strain on the telescope, we would
have had to check every possible ordering. Unfortunately, this job could
not be accomplished even by all the world's supercomputers working day and
night for sextillions of years.
For most realworld problems, a solution that comes within a few
percent of the ideal one is quite acceptable. Fortunately, computer
scientists have devised an algorithm that can find such solutions to many
seemingly impossible problems. This amazing algorithm enables ordinary
laptop computers to come up with these solutions in just a few minutes,
making it a powerful addition to any amateur scientist's tool kit.
Called simulated annealing, this algorithm is a remarkable melding of
human cleverness and natural efficiency. A mathematical physicist named
Nicholas Metropolis and his coworkers developed the procedure back in
1953, but it has only recently come into wide use. Metropolis's procedure
was later used to find useful solutions to travelingsalesmantype
problems by mimicking on a computer the natural process by which the
crystal lattices of glass or metal relax when heated. This process is
called annealing.
Although the procedure is modeled on annealing, the relevant
fundamentals are the same, and perhaps a bit more easily explained, for
crystal growth. The molecules in a solution of hot sugar water wander
about randomly. If the temperature drops quickly, the sugar molecules
solidify into a complicated jumble. But if the temperature drops slowly,
they form a highly ordered crystal that can be billions of times larger
than the individual molecules.
With each molecule not only immobile but also at its lowest possible
energy level in the crystal's lattice, this crystal is in its minimum
energy state. (It corresponds, in my problem, to the galaxy ordering that
demands the least movement from the telescope.) The system naturally
progresses toward this minimum in a rather unexpected and remarkable way.
The molecules are naturally distributed over a range of kinetic energies.
As the temperature cools, the average kinetic energy drops. But some
individual molecules remain in highenergy states, even when most are
moving slow enough to bind to the crystal. When the lowerenergy molecules
get "hung up," they often bind in states with excess energy rather than in
the lowestenergy states where they belong.
The higherenergy molecules, however, can "knock" these trapped
molecules out of these overly energetic bound states and into states of
lower energy. This energy transference from molecule to molecule allows
the molecules to redistribute themselves as the ßuid cools, thereby
nudging the growing edges of the crystal in such a way that the molecules
settling into them can find the minimum energy state. This orderly crystal
growth occurs only during a slow cooling because a lot of time is needed
for the molecules to find the lowestenergy state.
So what does all this have to do with the traveling salesman problem?
To use Metropolis's procedure, you must be able to describe your problem
as a search for a sequence. In the traveling salesman problem, for
example, the problem is to determine the best order in which to visit the
cities on a list. With a little cleverness, a great many problems can be
formulated in this way. It is also necessary for you to be able to
generate a number that tells how well any given sequence works; the better
the solution, the smaller this number must be. This number is analogous to
the energy of the crystal in the crystalgrowth example. For my supernovae
search problem, the sequence was the order of galaxies searched; the
quantity analogous to energy was the total angle through which the
telescope had to move.
The box
outlines the algorithm. It works by calculating the energy levels
represented by different sequences, or "paths." If a new sequence has a
lower energy than the previous one, the program always adopts it.
Returning to the crystalgrowth example, a lowerenergy path corresponds
to one or more molecules finding their way into a position of lower energy
in the lattice. But what about a higherenergy path? Here is where it gets
interesting. The program does not immediately reject higherenergy paths;
after all, the dislodging of a molecule trapped in a higherenergy state
in a lattice is an example of a higherenergy path, and such occurrences
are the heart of the procedure.
Yet not all higherenergy paths are likely to nudge the system into a
lowerenergy state. To determine which ones do, the procedure uses the
socalled Boltzmann probability distribution. This factor determines the
probability of finding a system, such as a molecule or a group of
molecules, with a certain energy E at a given temperature T.
When applied to simulated annealing, this probability turns out to be the
number e (a constant, equal to about 2.7183, that comes up often in
physics and other fields) raised to the power (DE/kT), where k is Boltzmann's constant, which relates temperature to
energy, and DE is the energy difference
between the two paths. A clever trick allows the list to be altered
without requiring the energy to be recalculated from scratch every time.
The alteration begins by randomly selecting some subsection of the list.
Then, either the order of the subsection's elements is reversed, or the
subsection is moved and reinserted somewhere else in the list at random.
In either case, the energy associated with the subsection does not change.
The energy changes only where the subsection joins the rest of the list.
Simulated annealing isn't the only algorithm that mimics nature to
solve complex problems. Socalled genetic algorithms simulate evolution at
the genetic level to create cyberorganisms that are themselves solutions
to research problems [see "The Amateur Scientist," July 1992]. Neural
networkswhich simulate the activity of neurons in the brain to store
information, learn from experience and do calculationsare another field
of intense research.
All this brings up a fascinating point. Nature is far more clever than
humans will ever be. Simulating on a computer nature's methods of
organizing and creating has already produced extraordinarily powerful
tools to fell some of our own most vexing computing problems. Despite
this, only a handful of nature's solutions have yet been duplicated on a
computer. There simply have to be more out there to borrow from. The
tricky part is in recognizing which systems to model and in realizing the
kinds of problems that our simulations can solve.
So keep your eyes open! Perhaps, while contemplating ripples of
turbulence in cigarette smoke, investigating how individual bees organize
themselves into a hive or studying the simultaneous turns of a flock of
birds, you will discover the next major innovation in computer problem
solving.
To download all the C code you'll need to implement the simulated
annealing algorithm, visit the Society for Amateur Scientists's World Wide Web site. For more
information about other amateur scientist projects, visit the Web site or
call (800) 8738767 or (619) 2398807.
