The principle of multi-path simulated annealing global optimization algorithm

Multi-path simulated annealing (mpsa) optimization algorithm was developed to search the global minimum for a given object function varied with different configurations. Conventional simulated annealing (SA), a powerful global optimization algorithm, requires very slow temperature-reducing scheme and takes a very long time. In certain cases, the solution can be very easily trapped in global minima within an affordable period of time.

The animation above illustrates how mpsa works. The 4 balls represent 4 different annealing paths, each of which can be treated as a conventional SA. However, the different paths are not completely independent since they interact with each other during the course of annealing. For a given period of time, each ball's location (a point on the paths) represents a configuration (solution, i.e. a set of values for different variables that can be referred as center and orientation in the context of cryoEM image processing). The optimization starts simultaneously with different configurations, the time variations of which will form 4 different paths. Within the paths, multi-path simulated annealing can be divided into three different stages based on annealing temperatures, path update schemes, and numbers of trials.

In the first stage, the annealing cycles begin at high temperatures with large step sizes. Each one of the current configurations (all paths) travels globally through the entire search space, updating itself by a trial solution/configuration as in conventional SA. As a result of high temperature annealing, most of the trial solutions will be accepted. At the end of this stage, the solutions in the best solution list (including the best one from each path) are expected to be evenly distributed among the whole orientation space and will be taken as the starting solutions for the second stage.

The second stage is performed at lower temperatures with relative smaller step sizes. The step sizes of both the center and orientation changes are gradually reduced to a few pixels and degrees. While it remains a global search, the search range is relatively limited since this step is done at a lower temperature (i.e. searching more locally around each of the starting points). This stage is the most computationally expensive step among the three stages. With multiple starting paths, it is expected that at least one of the paths will be close to the global minimum. These "best solutions" are used as the starting solutions for the third stage. Again, each of the current solutions will be updated independently for each path.

The third stage that runs at very low temperature with small step size utilizes a different path-updating scheme. To precisely determine the final solution, the step sizes are gradually reduced to very small values depending on the size of the particle and the desired accuracy. For all the paths to converge to the global minimum, the worst solution in the current solution list will be replaced by a new trial solution that has better residual from any of the paths. The small step sizes, low temperature, and the cross-path update scheme facilitate the identification of the deepest minimum among the candidate solutions from the second stage. If one of the best solutions from the second stage is near the actual global minimum, it will be captured in the third stage and refined with very high precision.