Image:Slim Films GALAXY SEARCH was made possible by a heavenly algorithm.

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 30-inch telescope, then used only for teaching, and converted it into a fully automated research instrument. When night arrived, this computer-controlled 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 40-year-old 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³⁷⁵ different ways to sort 200 galaxies-a 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 real-world 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 co-workers 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 traveling-salesman-type 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 high-energy states, even when most are moving slow enough to bind to the crystal. When the lower-energy molecules get "hung up," they often bind in states with excess energy rather than in the lowest-energy states where they belong.

The higher-energy 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 lowest-energy 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 crystal-growth 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 crystal-growth example, a lower-energy path corresponds to one or more molecules finding their way into a position of lower energy in the lattice. But what about a higher-energy path? Here is where it gets interesting. The program does not immediately reject higher-energy paths; after all, the dislodging of a molecule trapped in a higher-energy state in a lattice is an example of a higher-energy path, and such occurrences are the heart of the procedure.

Yet not all higher-energy paths are likely to nudge the system into a lower-energy state. To determine which ones do, the procedure uses the so-called 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. So-called 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 networks-which simulate the activity of neurons in the brain to store information, learn from experience and do calculations-are 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.