|January 8, 1996
For Immediate Release
Revolutionary Mathematical Algorithm Replaces Conventional Trial and Error Methods
A researcher at The Johns Hopkins University Applied Physics Laboratory (APL) in Laurel, Md., has devised a breakthrough method for rapidly optimizing the performance of complex systems -- making them operate in the best and most efficient manner.
Jim Spall has developed an algorithm -- a series of mathematical steps -- that replaces current 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.
Optimization problems abound in engineering, medicine, business, and in the physical and social sciences. They can deal with such diverse issues as missile propellant mixtures, medicine dosage levels, and economic investment policies.
Currently at APL Dr. Spall's algorithm is being applied to the thorny problem of setting a network of traffic signals in an urban area to obtain the most efficient vehicle flow. Conventional methods would require making many simplifying assumptions or trying millions of different combinations of settings that consider factors such as driver response, time of day, the weather, and scores of other variables in seeking the best answer -- if, in fact, it could be found this way.
Instead of changing variables one at a time and running test after test to see how the changes affect system performance, Spall's algorithm changes every variable at the same time -- what he calls "simultaneous perturbation stochastic approximation (SPSA)" -- by an amount that is determined randomly in a special way.
The system is then run and its performance evaluated. The evaluation indicates the direction toward improved system performance so that another set of systemwide, random changes can be made and tried. The process continues until system performance -- or any selected aspect of performance -- has reached an optimum.
Spall says that the great power of the SPSA 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 current optimization techniques.
Another benefit of the algorithm is its simplicity and 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."
Spall discovered his breakthrough algorithm in 1985 as a result of a flaw in the mathematical equation he was working on for a submarine navigation problem. When he presented his new ideas, scientists in the field were skeptical because of the uncanny ability of the SPSA algorithm to obtain 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 deepened understanding of the approach, and his algorithm is now widely accepted and used by researchers around the world.
Scientists at Kansai University in Japan are using the SPSA algorithm to design advanced pattern and character recognition systems, while engineers in Italy are using it to detect faults in a power plant.
At APL it's being used or evaluated in projects to schedule fleet vehicles, manage air traffic, extract information about the ion population near the Earth from magnetospheric images, optimize battle and weapons targeting strategies, and determine optimal doses for multiple drugs in treating a patient. Recently applied to the problem of finding the most efficient way to run a wastewater treatment plant, the SPSA algorithm did the job with 160 experiments, compared to 65,920 separate trial-and-error experiments using conventional methods. This represented a huge saving in labor and fuel costs.
APL 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.
Like other breakthrough discoveries, the more the Spall algorithm is used, the more uses are found for it.
For more information, contact APL Public Information Officer Helen Worth; phone: 240-228-5113 or 410-778-5113.
The Applied Physics Laboratory is an independent division of The Johns Hopkins University. Founded in 1942, the Laboratory has for more than 50 years conducted research and development primarily for national security and for nondefense projects of national and global significance. APL is located midway between Baltimore and Washington, D.C.