Novel algorithm helps optimize control strategies
“More bang for the buck” is a goal that control-system designers may be able to better aim for with a newly developed optimization strategy from researchers at Cardiff University’s Manufacturing Engineering Centre (MEC). Called the Bee Algorithm, the method adopts a strategy used in nature when honeybee colonies attempt to concentrate their honey-gathering resources to the most promising fields available at any given time. The researchers’ contribution was to apply the strategy to finding the most effective set of values for a number of automated control settings.
It’s fairly simple to determine the best setting for a single control input, but when a system includes a large number of mutually interacting inputs, optimization quickly becomes a daunting, if not impossible, task. The Bee Algorithm organizes a search over a multidimensional surface for the location that yields the absolute maximum peak optimization-parameter value—even in the presence of numerous local maxima of lower value.
The researchers studied how honey bees seek the best “bang” (that is, the most nectar) for their “buck” (collection effort). The algorithm parameters include density of nectar-bearing blossoms, quality of the nectar produced, size of the flower patch and flying distance from the nest. Convolved together, these parameters produce an optimization parameter indicating the fitness of each particular patch. The hive can maximize its honey production by sending the largest number of workers to gather in the fittest field.
The hive begins by sending out a cadre of scout bees who search randomly for promising prospect fields. These scouts then bring back reports that they communicate to the rest of the hive via the well-known “waggle dance.”
The hive then reallocates resources by sending additional scouts to assess locations surrounding the most promising locations, and fewer scouts to continue the random search. As reports continue to flood in, workers intent on gathering nectar concentrate on the most promising location.
The strategy translates directly to optimizing system controls. In the face of multiple interacting controls used to maximize system output (whether it is holding to an aircraft’s desired flight path, quality of a pharmaceutical product, or mix of fractions from an oil refinery), the optimization parameter forms a surface in a mathematical space whose dimensions are the control-input values. Such a surface typically has complex topography with numerous local peaks, valleys, ridges, etc. The optimization task is to find the very largest peak.
By swarming to the most promising locations, bees maximize their productivity given known conditions. By continuing the random search in reduced form, they provide good odds that they will eventually cover any previously overlooked good locations.
The strategy also is robust in the face of changing conditions. As, for example, workers deplete the nectar in the most promising location, that location becomes less promising. Continual reporting back at the hive automatically tracks that change. Over time, that location’s fitness erodes to below the fitness of the next most promising location. The hive automatically reallocates resources (modifies the control set points) to concentrates on what has become the most promising location.
The MEC researchers, led by Ph.D. student Afshin Ghanbarzadeh, analyzed the honey-bee strategy and developed it into a computer algorithm, which they published in a presentation as part of the University’s recent Internet-based Innovative Production and Machines Conference. The paper, entitled “The Bees Algorithm– A Novel Tool for Complex Optimisation Problems,” details the mathematics behind the algorithm and how to apply it to control optimization. The paper demonstrates using it to optimize standard test functions in two and six dimensions, and shows results for a total of eight test functionscompared to four other multidimensional optimization strategies.
Experimental results show that the algorithm succeeds in finding the absolute optimal result in all cases. That is, it always finds the location in n-space that produces the tallest local maximum of the optimization parameter without becoming trapped in a less optimal local maximum. Continuing a random-search component, of course, makes this result possible. Should the search lock onto a sub-optimal local maximum, the random component continues searching outside of that local maximum and, eventually, locates the better peak.
It is possible to find the optimal parameter set quickly. In most cases, the Bees Algorithm located the optimal maximum with orders of magnitude fewer trials. This, of course, makes the strategy useful in a real world environment where conditions continually change, requiring continual re-optimization.
There are two reasons why continual re-optimization might be needed: changing external conditions or changing system requirements. The first corresponds to the example above, where activity by the system being controlled changes the optimization-parameter surface (fitness of the fittest field). The second corresponds to a change in system output requirements.
For example, the value of a petroleum refinery’s output depends not only on the relative volumes of product fractions, but on how demand for those components changes with time. In northern-latitude spring, the mix should favor gasoline production to anticipate the summer driving season. In late summer and fall, however, the mix should shift toward more production of heating oil to anticipate the winter heating season.
The aerospace industry provides an example where both factors affect the optimal control input. Researchers at the U.S. Army’s Yuma Proving Ground have been working on a system to precision deliver materiel via high-altitude parachute drop. During the descent, the parachute passes through numerous layers of the atmosphere with different wind speeds and directions. The system pre-plans the best path for conditions at the release time and then provides corrections on the way down. Clearly, the control set points change as the parachute descends through various wind layers. Wind speeds in those layers may also change with time as well.
The Bees Algorithm lends itself to parallel processing and neural networks. Both architectures gain processing speed by solving multiple examples of a problem simultaneously. The Bees Algorithm works the same way: multiple examples (bees) explore the optimization surface simultaneously. Each “bee” evaluates a different location on the surface independently.
To view the original presentation online, click here . The presentation has excited numerous comments and follow up publications, which can be found by keying “bees algorithm” into your favorite search engine.
— Charlie Masi , Control Engineering , senior editor