On the Effectiveness of Crossover for Migration in Parallel Evolutionary Algorithms

F Neumann, Pietro Oliveto, GT Rudolph, Dirk Sudholt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Citations (Scopus)

Abstract

Island models are popular ways of parallelizing evolutionary algorithms as they can decrease the parallel running time at low communication costs and lead to an increased population diversity. This in particular provides a good setting for crossover as this operator relies on a good diversity between parents. We consider the effect of recombining migrants with individuals on the target island. We rigorously prove, for a test function in pseudo-Boolean optimization, exponential performance gaps between island models with strongly connected topologies and a panmictic (mu+1)-EA as long as the migration interval is not too small. We then choose vertex cover as a classical NP-hard problem. By considering instances with a clear building block structure we prove that, also in this more practical setting, island models with a particular topology drastically outperform panmictic populations. Both the theoretical and empirical results show that for strongly connected topologies, such as ring, the performance drops by decreasing the migration interval, while this is not the case for topologies connected weakly such as the single receiver model.
Original languageEnglish
Title of host publicationGECCO '11 Proceedings of the 13th annual conference on Genetic and evolutionary computation
PublisherAssociation for Computing Machinery
Pages1587-1594
Number of pages8
ISBN (Print)978-1-4503-0557-0
DOIs
Publication statusPublished - 16 Jul 2011
EventAnnual Conference on Genetic and Evolutionary Computation (GECCO '11), 13th - New York, United States
Duration: 16 Jul 2011 → …

Conference

ConferenceAnnual Conference on Genetic and Evolutionary Computation (GECCO '11), 13th
Country/TerritoryUnited States
CityNew York
Period16/07/11 → …

Fingerprint

Dive into the research topics of 'On the Effectiveness of Crossover for Migration in Parallel Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this