ABSTRACT
This chapter considers the effect of two kinds of cost-function errors on the simulated annealing algorithm: errors with fixed bounds and errors with normal distributions. Binomially distributed errors can occur in asynchronous algorithms, based on the interconnectedness of the state variables and the total number of processors: in the limit, these approach the normal distribution. The chapter discusses a relationship between the equilibrium cost of an erroneous algorithm and that of an equivalent perfect algorithm, based on both bounded and Gaussian errors. It analyzes the effects of both instantaneous and accumulated errors. An accumulated error is the sum of a stream of instantaneous errors. The chapter proves a direct connection between the errors that researchers have measured, and annealing properties, including average cost. The analysis reported here should help improve asynchronous, parallel, simulated annealing algorithms in the future. The simulated annealing algorithm can approximately solve many difficult combinatorial optimization problems.
