title: Comparison-based algorithms are robust and randomized algorithms are anytime.
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 heuristics which use comparison based selection mechanism. The two main results are that comparison-based algorithms are the best algorithms for some robustness criteria and that introducing randomness in the choice of offspring improves the anytime behavior of the algorithm. An original Estimation of Distribution Algorithm combining both results is proposed and successfully experimented.
authors.affiliation: Equipe TAO (INRIA Futurs), LRI, UMR 8623 (CNRS - Université Paris-Sud), bat. 490 Université Paris-Sud 91405 Orsay Cedex, France. gelly@lri.fr
authors.forename: Sylvain
authors.initials: S
authors.lastname: Gelly
authors.forename: Sylvie
authors.initials: S
authors.lastname: Ruette
authors.forename: Olivier
authors.initials: O
authors.lastname: Teytaud
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical