Complex equation may simplify complex systems...
Improving Upon Trial and Error

Ben Walker
---------------------------------------
Applied Physics Laboratory


algorithm//a step-by-step procedure for solving a problem.


     Stuck in traffic as you creep home after a hard day, you sit
shivering in the cold darkness of your car at yet another in a
seemingly endless series of red lights. To stay warm, you stew,
wondering what bureaucrat rigged the traffic light pattern, which
obviously is to blame for the rush hour traffic jam.

     But what seems so simple to a driver stuck in traffic is,
for urban traffic planners, something of a nightmare as they seek
the best overall signal pattern. These planners are faced with a
dizzying grid of main roads and side streets and highway ramps
and school zones. They try--largely through trial and error--
millions of different combinations of signal settings, taking
into account a wide range of variables, from driver response to
time of day to the weather to neighborhood peculiarities. It
takes long, frustrating hours, weeks, months.

     But APL's Jim Spall has devised an algorithm that is a
breakthrough method for rapidly solving just such extremely
complex systems. His algorithm replaces trial-and-error
techniques with a radical approach that dramatically slashes the
time to find a solution by factors of 1,000 or more in many
practical problems, and makes it possible to tackle some problems
that up to now have been out of reach.

     Currently, most multivariable systems are figured out by
changing each variable one at a time and running test after test
to see how the changes affect system performance. Spall's
computer-driven algorithm changes every system variable at the
same time--what he calls "simultaneous perturbation"--by an
amount that is determined randomly in a particular way. 

     The system is then run, and its performance evaluated. The
evaluation indicates the direction toward improved system
performance so that another set of randomly determined,
systemwide changes can be made and tried. The process continues
until system performance--or any selected aspect of performance--
is operating as efficiently as it can.

     Spall, of the Strategic Systems Department, says the
algorithm works because the randomness factor tends to accentuate
the direction that gives the greatest improvement. Putting it
mathematically, he says that changing all the variables at once
by a random factor creates a direction vector that on average
points the way toward improvement, and then subsequent iterations
continuously improve the performance until you've reached optimal
performance for the system parameters you've chosen.

     The great power of the algorithm comes from the fact that
one carefully chosen, simultaneous random change of all variables
in a problem contains as much information for optimization as a
full set of one-at-a-time changes of each of the variables--the
approach used in conventional optimization techniques. Another
benefit of the algorithm is the ease with which it can be
implemented. Spall says, "There's no need to build a detailed,
mathematical model of the system you're working on in order to
apply the procedure."


Accidental discovery

     Spall's discovery of the algorithm was something of a random
event itself. Working on a submarine navigation problem in 1985,
he wrote a mathematical expression on the blackboard that turned
out to be flawed for the problem being considered. But when he
looked at the expression several days later, he suddenly realized
that with a few changes it might have profound implications for
solving far wider and even more complex problems than submarine
navigation. 

     The algorithm spreads across six pages. Not exactly e=mc2,
but it works.

     When Spall first presented and published his ideas in 1987,
scientists in the field were skeptical because of the uncanny
ability of the approach to secure remarkable benefits despite its
inherent simplicity and because it seemed to offer "something for
nothing."

     Since then, Spall and others have published a steady stream
of  technical papers that deepen understanding of the approach,
and his algorithm is now widely acclaimed by researchers around
the world who are using it to solve complex optimization
problems.

     Others at APL, notably Dan Chin and John Cristion, have also
made significant contributions to the development of the method.  

     Like other breakthrough discoveries, the more the Spall
algorithm is used, the more uses are being found for it.

     The laboratory is also using the algorithm in a joint
project with scientists from Denmark to find the optimal
placement of sensors that monitor the structural condition of a
bridge. Scientists at Kansai University in Japan are using the
Spall algorithm to design advanced pattern and character
recognition systems, while engineers in Italy are using it to
detect faults in a power plant. The Ford Motor Company is
evaluating the algorithm for use in regulating vehicle engine
temperature.

     Applied to the problem of finding the most efficient way to
run a wastewater treatment plant, the algorithm did the job with
160 experiments, compared to 65,920 separate trial-and-error
experiments using conventional methods. This represents a huge
savings in labor and fuel costs.

     At APL, it's being evaluated or used in projects designed to
schedule fleet vehicles, manage air traffic, extract information
about the ion population near the Earth from magnetospheric
images, optimize battle strategies and determine optimal doses
for multiple drugs in treating a patient.

     And it also is being used at APL to time traffic signal
lights in a simulated urban area. So while Jim Spall's algorithm
may not help you get home from work faster, you could run through
it in your head as you remained jammed up in rush hour traffic.
Just to pass the time.