Parallel Evolutionary Algorithms Performing Pairwise Comparisons

Abstract : We study mathematically and experimentally the conver-gence rate of differential evolution and particle swarm opti-mization for simple unimodal functions. Due to paralleliza-tion concerns, the focus is on lower bounds on the runtime, i.e upper bounds on the speed-up, as a function of the pop-ulation size. Two cases are particularly relevant: A popula-tion size of the same order of magnitude as the dimension and larger population sizes. We use the branching factor as a tool for proving bounds and get, as upper bounds, a lin-ear speed-up for a population size similar to the dimension, and a logarithmic speed-up for larger population sizes. We then propose parametrizations for differential evolution and particle swarm optimization that reach these bounds.
Type de document :
Communication dans un congrès
Jun He and Thomas Jansen and Gabriela Ochoa and Christine Zarges. Foundations of Genetic Algorithms, 2015, Aberythswyth, United Kingdom. ACM, pp.99-113 2015, Foundations of Genetic Algorithms
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01077626
Contributeur : Olivier Teytaud <>
Soumis le : lundi 3 novembre 2014 - 01:59:51
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : mercredi 4 février 2015 - 10:06:45

Fichier

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

Identifiants

  • HAL Id : hal-01077626, version 1

Citation

Marie-Liesse Cauwet, Olivier Teytaud, Shih-Yuan Chiu, Kuo-Min Lin, Shi-Jim Yen, et al.. Parallel Evolutionary Algorithms Performing Pairwise Comparisons. Jun He and Thomas Jansen and Gabriela Ochoa and Christine Zarges. Foundations of Genetic Algorithms, 2015, Aberythswyth, United Kingdom. ACM, pp.99-113 2015, Foundations of Genetic Algorithms. 〈hal-01077626〉

Partager

Métriques

Consultations de la notice

638

Téléchargements de fichiers

268