Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/71909
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | On the effectiveness of crossover for migration in parallel evolutionary algorithms |
Author: | Neumann, F. Oliveto, P. Rudolph, G. Sudholt, D. |
Citation: | GECCO'11: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, held in Dublin, Ireland, 12-16 July, 2011: pp.1587-1594 |
Publisher: | ACM Press |
Publisher Place: | New York |
Issue Date: | 2011 |
ISBN: | 9781450305570 |
Conference Name: | Genetic and Evolutionary Computation Conference (13th : 2011 : Dublin, Ireland) |
Editor: | Krasnogor, N. |
Statement of Responsibility: | Frank Neumann, Pietro S. Oliveto, Günter Rudolph and Dirk Sudholt |
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 (μ+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. |
Keywords: | Parallel evolutionary algorithms island model crossover recombination migration runtime analysis |
Rights: | Copyright 2011 ACM |
DOI: | 10.1145/2001576.2001790 |
Published version: | http://dx.doi.org/10.1145/2001576.2001790 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_71909.pdf Restricted Access | Restricted Access | 419.92 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.