Global optimization with exploration/selection algorithms and simulated annealing

• 成果类型: Article
• 署名作者: François, O
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2002
• 页码: 248-271
• 关键词: genetic algorithms; CONVERGENCE

摘要

This article studies a stochastic model of an evolutionary algorithm that evolves a population of potential solutions to a minimization problem. The minimization process is based on two operators. First, each solution is regarded as an individual that attempts a random search on a graph, involving a probabilistic operator called exploration, The second operator is called selection. This deterministic operator creates interaction between individuals. The convergence of the evolutionary process is described within the framework of simulated annealing. It can be quantified by means of two quantities called the critical height and the optimal convergence exponent, which both measure the difficulty of the algorithm to deal with the minimization problem. This work describes the critical height for large enough population sizes. Explicit bounds are given for the optimal convergence exponent, using a few geometric quantities. As an application, this work allows comparisons of the evolutionary strategy with independent parallel runs of the simulated annealing algorithm, and it helps deciding when one method should be preferred to the other.