Skip to Main content Skip to Navigation
Journal articles

comparison-based algorithms are robust and randomized algorithms are anytime.

Sylvain Gelly 1 Sylvie Ruette 2 Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : Randomized search heuristics (e.g., evolutionary algorithms, simulated annealing etc.) are very appealing to practitioners, they are easy to implement and usually provide good performance. The theoretical analysis of these algorithms usually focuses on convergence rates. This paper presents a mathematical study of randomized search heuristicswhich use comparison based selectionmechanism. The twomain results are: (i) comparison-based algorithms are the best algorithms for some robustness criteria, (ii) introducing randomness in the choice of offspring improves the anytime behavior of the algorithm. An original Estimation of Distribution Algorithm combining (i) and (ii) is proposed and successfully experimented.
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00173221
Contributor : Olivier Teytaud <>
Submitted on : Wednesday, September 19, 2007 - 2:14:50 PM
Last modification on : Wednesday, September 16, 2020 - 4:04:52 PM
Long-term archiving on: : Friday, April 9, 2010 - 2:28:54 AM

File

lb2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00173221, version 1

Collections

Citation

Sylvain Gelly, Sylvie Ruette, Olivier Teytaud. comparison-based algorithms are robust and randomized algorithms are anytime.. Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 2007. ⟨inria-00173221⟩

Share

Metrics

Record views

573

Files downloads

386