HAL: inria-00173221, version 1

See detailed view

BibTeX,EndNote,... BibTeX - EndNote - TEI - RefWorks -

Evolutionary Computation Journal (2007)

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

Sylvain Gelly 1, Sylvie Ruette 2, Olivier Teytaud 1

(2007)

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.

1:	TAO (INRIA Futurs)
	INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
2:	Laboratoire de Mathématiques d'Orsay (LM-Orsay)
	CNRS : UMR8628 – Université Paris XI - Paris Sud

Domain

:

Mathematics/Optimization and Control

Keywords: Anytime optimization – non-linear optimization – comparison-based algorithms – complexity – theory – randomized search heuristics

inria-00173221, version 1

http://hal.inria.fr/inria-00173221

oai:hal.inria.fr:inria-00173221

From: Olivier Teytaud <>

Submitted on: Wednesday, 19 September 2007 14:14:50

Updated on: Wednesday, 19 September 2007 14:20:54