Genetic algorithms: bridging the convergence gap

In this paper we consider the extension of genetic algorithms (GAs) with a probabilistic Boltzmann reduction operator and prove their convergence to t he optimum. The algorithm can be seen as a hybridisation between GAs and si mulated annealing (SA), i.e. a SA-like GA. The "temperature" parameter allo ws us to control the size of the entries of the probabilistic transition ma trix of the corresponding Markov chain. In the limit case of temperature ze ro, the reduction operator becomes a kind of strong elitism. Convergence to the optimum is shown under very mild conditions for the sequence of temper atures {c(k)}. This means that the proposed algorithm is quite robust, and can be expected to perform well on practical applications. (C) 1999 Elsevie r Science B.V. All rights reserved.