Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2001576.2001790 | GECCO |
Keywords | Field | DocType |
good setting,parallel evolutionary algorithm,particular topology,panmictic population,exponential performance gap,increased population diversity,target island,performance drop,good diversity,migration interval,island model,vertex cover,crossover,migration,recombination,np hard problem | Mathematical optimization,Crossover,Evolutionary algorithm,Computer science,Test functions for optimization,Network topology,Vertex cover,Operator (computer programming),Artificial intelligence,Parallel running,Strongly connected component,Machine learning | Conference |
Citations | PageRank | References |
19 | 0.82 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Neumann | 1 | 1727 | 124.28 |
| Pietro Simone Oliveto | 2 | 212 | 25.56 |
| Günter Rudolph | 3 | 219 | 48.59 |
| Dirk Sudholt | 4 | 1063 | 64.62 |