Comparison-based algorithms are robust and randomized algorithms are anytime
Evolutionary
Computation, 15, No. 4 (special issue Bridging the
gap between theory and practice), 411-434, 2007.
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.
Paper