Simulated Annealing Applied to a Problem in Combinatorial Optimization

摘要

This thesis considers the application of simulated annealing to combinatorial optimization problems resulting from a spin glass model of a folding protein. An algorithm is developed which is non-adaptive and executes a number of iterations determined by the problem itself and three parameters: an initial temperature, a final temperature, and a parameter which controls the rate of decrease of the temperature. The number of iterations is fairly insensitive to the initial temperature which can be computed adaptively with little cost. An optimal value for the final temperature can be determined by experimenting with smaller problems. The number of iterations, and, consequently, the solution quality is then determined by the third parameter. The solution quality may be improved somewhat, given a fixed amount of time, by performing several trials and using the best result. In addition, in concurrent environments, this practice may become more advantageous, particularly if a substantial portion of the computations within a trial must be performed sequentially. (ERA citation 12:034419)