Log(lambda) Modifications for Optimal Parallelism

Fabien Teytaud 1, 2 Olivier Teytaud 1, 2
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : It is usually considered that evolutionary algorithms are highly parallel. In fact, the theoretical speed-ups for parallel optimization are far better than empirical results; this suggests that evolutionary algorithms, for large numbers of processors, are not so efficient. In this paper, we show that in many cases automatic parallelization provably provides better results than the standard parallelization consisting of simply increasing the population size lambda. A corollary of these results is that logarithmic bounds on the speed-up (as a function of the number of computing units) are tight within constant factors. Importantly, we propose a simple modification, termed log(lambda)-correction, which strongly improves several important algorithms when lambda is large.
Type de document :
Communication dans un congrès
Parallel Problem Solving From Nature, Sep 2010, Krakow, Poland. 2010
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00495087
Contributeur : Fabien Teytaud <>
Soumis le : vendredi 25 juin 2010 - 09:02:21
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : lundi 27 septembre 2010 - 11:56:04

Fichier

autoparacnf.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00495087, version 1

Citation

Fabien Teytaud, Olivier Teytaud. Log(lambda) Modifications for Optimal Parallelism. Parallel Problem Solving From Nature, Sep 2010, Krakow, Poland. 2010. 〈inria-00495087〉

Partager

Métriques

Consultations de la notice

266

Téléchargements de fichiers

138