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.
Go to Gazette Homepage