On the Convergence and Applications of Generalized Simulated Annealing

Abstract

The convergence of the generalized simulated annealing with time-inhomogeneous communication cost functions is discussed. This study is based on the use of log-Sobolev inequalities and semigroup techniques in the spirit of a previous article by one of the authors. We also propose a natural test set approach to study the global minima of the virtual energy. The second part of the paper is devoted to the application of these results. We propose two general Markovian models of genetic algorithms and we give a simple proof of the convergence toward the global minima of the fitness function. Finally we introduce a stochastic algorithm that converges to the set of the global minima of a given mean cost optimization problem.