Foundations of Genetic Algorithms 2001 (FOGA 6)

Mutation-Selection Algorithm: a Large Deviation Approach

Paul Albuquerque; Christian Mazza    Dept. of Computer Science, University of Geneva, 24 rue Général–Dufour, CH-1211 Geneva 4, SwitzerlandLaboratoire de Probabilités, Université Claude Bernard Lyon-I, 43 Bd du 11–Novembre-1918, 69622 Villeurbanne Cedex, France

Abstract

We consider a two-operator mutation–selection algorithm designed to optimize a fitness function on the space of fixed length binary strings. Mutation acts as in classical genetic algorithms, while the fitness-based selection operates through a Gibbs measure (Boltzmann selection). The selective pressure is controlled by a temperature parameter. We provide a mathematical analysis of the convergence of the algorithm, based on the ...