Topics
features
Publications
Issue Archive
Recursive Branching Simulated Annealing Algorithm
 Created: Friday, 01 June 2012
The algorithm can be applied to a wide variety of optimization problems.
This innovation is a variation of a simulated annealing optimization algorithm that uses a recursivebranching structure to parallelize the search of a parameter space for the globally optimal solution to an objective. The algorithm has been demonstrated to be more effective at searching a parameter space than traditional simulated annealing methods for a particular problem of interest, and it can readily be applied to a wide variety of optimization problems, including those with a parameter space having both discretevalue parameters (combinatorial) and continuousvariable parameters. It can take the place of a conventional simulatedannealing, Monte Carlo, or randomwalk algorithm.
In a conventional simulatedannealing (SA) algorithm, a starting configuration is randomly selected within the parameter space. The algorithm randomly selects another configuration from the parameter space and evaluates the objective function for that configuration. If the objective function value is better than the previous value, the new configuration is adopted as the new point of interest in the parameter space. If the objective function value is worse than the previous value, the new configuration may be adopted, with a probability determined by a temperature parameter, used in analogy to annealing in metals. As the optimization continues, the region of the parameter space from which new configurations can be selected shrinks, and in conjunction with lowering the annealing temperature (and thus lowering the probability for adopting configurations in parameter space with worse objective functions), the algorithm can converge on the globally optimal configuration.
The Recursive Branching Simulated Annealing (RBSA) algorithm shares some features with the SA algorithm, notably including the basic principles that a starting configuration is randomly selected from within the parameter space, the algorithm tests other configurations with the goal of finding the globally optimal solution, and the region from which new configurations can be selected shrinks as the search continues. The key difference between these algorithms is that in the SA algorithm, a single path, or trajectory, is taken in parameter space, from the starting point to the globally optimal solution, while in the RBSA algorithm, many trajectories are taken; by exploring multiple regions of the parameter space simultaneously, the algorithm has been shown to converge on the globally optimal solution about an order of magnitude faster than when using conventional algorithms.
Novel features of the RBSA algorithm
include:
1. More efficient searching of the
parameter space due to the branching
structure, in which multiple random
configurations are generated and
multiple promising regions of the
parameter space are explored;
2. The implementation of a trust region
for each parameter in the parameter
space, which provides a natural way of
enforcing upper and lowerbound
constraints on the parameters; and
3. The optional use of a constrained gradient
search optimization, performed
on the continuous variables around
each branch’s configuration in parameter
space to improve search efficiency
by allowing for fast finetuning of the
continuous variables within the trust
region at that configuration point.
This work was done by Matthew Bolcar, J. Scott Smith, and David Aronstein of Goddard Space Flight Center. GSC159081
White Papers

