Projects per year
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 language | English |
---|---|
Title of host publication | GECCO '11 Proceedings of the 13th annual conference on Genetic and evolutionary computation |
Publisher | Association for Computing Machinery |
Pages | 1587-1594 |
Number of pages | 8 |
ISBN (Print) | 978-1-4503-0557-0 |
DOIs | |
Publication status | Published - 16 Jul 2011 |
Event | Annual Conference on Genetic and Evolutionary Computation (GECCO '11), 13th - New York, United States Duration: 16 Jul 2011 → … |
Conference
Conference | Annual Conference on Genetic and Evolutionary Computation (GECCO '11), 13th |
---|---|
Country/Territory | United States |
City | New York |
Period | 16/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.Projects
- 2 Finished
-
Postdoctoral Research Fellowship - Rigorous Runtime Analysis of Nature Inspired Meta-heuristics
Oliveto, P.
Engineering & Physical Science Research Council
1/08/10 → 30/09/13
Project: Research Councils
-
SEBASE: Software Engineered By Automated SEarch
Engineering & Physical Science Research Council
29/06/06 → 28/12/11
Project: Research Councils