Skip to Main content Skip to Navigation
Journal articles

Rigorous hitting times for binary mutations

Abstract : In the binary evolutionary optimization framework, two mutation operators are theoretically investigated. For both the standard mutation, in which all bits are flipped independently with the same probability, and the 1-bit-flip mutation, which flips exactly one bit per bitstring, the statistical distribution of the first hitting times of the target are thoroughly computed (expectation and variance) up to terms of order l (the size of the bitstrings) in two distinct situations: without any selection, or with the deterministic (1+1)-ES selection on the OneMax problem. In both cases, the 1-bit-flip mutation convergence time is smaller by a constant (in terms of l) multiplicative factor. These results extend to the case of multiple independent optimizers.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00001277
Contributor : Marc Schoenauer Connect in order to contact the contributor
Submitted on : Thursday, May 4, 2006 - 4:39:33 PM
Last modification on : Wednesday, October 20, 2021 - 12:23:58 AM
Long-term archiving on: : Saturday, April 3, 2010 - 11:18:06 PM

Files

Identifiers

  • HAL Id : inria-00001277, version 1

Collections

Citation

Josselin Garnier, L. Kallel, Marc Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 1999, 7 (2), pp.167-203. ⟨inria-00001277⟩

Share

Metrics

Les métriques sont temporairement indisponibles