More Web Proxy on the site http://driver.im/

research-article

On the effectiveness of crossover for migration in parallel evolutionary algorithms

Authors:

Pietro Simone Oliveto,

Günter Rudolph,

Dirk SudholtAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 1587 - 1594

https://doi.org/10.1145/2001576.2001790

Published: 12 July 2011 Publication History

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.

References

[1]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.

Digital Library

[2]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

[3]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617--633, 2010.

Digital Library

[4]

T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt. Analysis of diversity-preserving mechanisms for global exploration. Evolutionary Computation, 17(4):455--476, 2009.

Digital Library

[5]

J. Lassig and D. Sudholt. The benefit of migration in parallel evolutionary algorithms. In Proc. of GECCO '10, pages 1105--1112, 2010.

Digital Library

[6]

J. Lassig and D. Sudholt. General scheme for analyzing running times of parallel evolutionary algorithms. In PPSN '10, pages 234--243. Springer, 2010.

Digital Library

[7]

J. Lassig and D. Sudholt. Adaptive population models for offspring populations and parallel evolutionary algorithms. In Proc. of FOGA '11, pages 181--192. ACM Press, 2011.

Digital Library

[8]

N. Nedjah, L. de Macedo Mourelle, and E. Alba. Parallel Evolutionary Computations. Springer, 2006.

Digital Library

[9]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[10]

P. S. Oliveto, J. He, and X. Yao. Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Trans. Evolutionary Computation, 13(5):1006--1029, 2009.

Digital Library

[11]

G. Rudolph. Global optimization by means of distributed evolution strategies. In Parallel Problem Solving from Nature, pages 209--213. Springer, Berlin and Heidelberg, 1991.

Digital Library

[12]

G. Rudolph. Takeover time in parallel populations with migration. In BIOMA 2006, pages 63--72, 2006.

[13]

Z. Skolicki. An Analysis of Island Models in Evolutionary Computation. PhD thesis, George Mason University, 2007.

Digital Library

[14]

Z. Skolicki and K. A. De Jong. The influence of migration sizes and intervals on island models. In Proc. of GECCO '05, pages 1295--1302. ACM, 2005.

Digital Library

[15]

M. Tomassini. Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time. Springer, 2005.

Digital Library

[16]

R. Watson and T. Jansen. A building-block royal road where crossover is provably essential. In Proc. of GECCO '07, pages 1452--1459. ACM, 2007.

Digital Library

[17]

C. Witt. Runtime analysis of the (μ+1) EA on simple pseudo-Boolean functions. Evolutionary Computation, 14(1):65--86, 2006.

Digital Library

Cited By

Duan QShao CZhou GZhang MZhao QShi Y(2024)Distributed Evolution Strategies With Multi-Level Learning for Large-Scale Black-Box OptimizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.343768835:11(2087-2101)Online publication date: Nov-2024
https://doi.org/10.1109/TPDS.2024.3437688
Cerf SLengler J(2024)How Population Diversity Influences the Efficiency of CrossoverParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_7(102-116)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_7
Aboutaib BSutton A(2023)The Influence of Noise on Multi-parent Crossover for an Island Model Genetic AlgorithmACM Transactions on Evolutionary Learning and Optimization10.1145/36306384:2(1-28)Online publication date: 9-Nov-2023
https://dl.acm.org/doi/10.1145/3630638
Show More Cited By

Index Terms

On the effectiveness of crossover for migration in parallel evolutionary algorithms
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The benefit of migration in parallel evolutionary algorithms
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Parallelization is becoming a more and more important issue for solving difficult optimization problems. Various implementations of parallel evolutionary algorithms (EAs) have been applied in the past decades. Island models combine phases of independent ...
Design and analysis of migration in parallel evolutionary algorithms

Parallelization is becoming a more important issue for solving difficult optimization problems. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbored islands. This can lead to an ...
Analysis of speedups in parallel evolutionary algorithms and ( 1 + λ ) EAs for combinatorial optimization

Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Duan QShao CZhou GZhang MZhao QShi Y(2024)Distributed Evolution Strategies With Multi-Level Learning for Large-Scale Black-Box OptimizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.343768835:11(2087-2101)Online publication date: Nov-2024
https://doi.org/10.1109/TPDS.2024.3437688
Cerf SLengler J(2024)How Population Diversity Influences the Efficiency of CrossoverParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_7(102-116)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_7
Aboutaib BSutton A(2023)The Influence of Noise on Multi-parent Crossover for an Island Model Genetic AlgorithmACM Transactions on Evolutionary Learning and Optimization10.1145/36306384:2(1-28)Online publication date: 9-Nov-2023
https://dl.acm.org/doi/10.1145/3630638
Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger S(2023)Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/36036293:2(1-32)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3603629
Aboutaib BSutton AWagner M(2022)The influence of noise on multi-parent crossover for an island model GAProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528854(666-674)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528854
Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger SWagner M(2022)Crossover for cardinality constrained optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528713(1399-1407)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528713
Chu JYu XYang SQiu JWang Q(2022)Architecture entropy sampling-based evolutionary neural architecture search and its application in osteoporosis diagnosisComplex & Intelligent Systems10.1007/s40747-022-00794-79:1(213-231)Online publication date: 25-Jun-2022
https://doi.org/10.1007/s40747-022-00794-7
Oliveto PSudholt DWitt C(2021)Tight Bounds on the Expected Runtime of a Standard Steady State Genetic AlgorithmAlgorithmica10.1007/s00453-021-00893-w84:6(1603-1658)Online publication date: 23-Dec-2021
https://doi.org/10.1007/s00453-021-00893-w
Oliveto PSudholt DWitt CCoello Coello C(2020)A tight lower bound on the expected runtime of standard steady state genetic algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390212(1323-1331)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390212
Nguyen PSudholt D(2020)Memetic algorithms outperform evolutionary algorithms in multimodal optimisationArtificial Intelligence10.1016/j.artint.2020.103345(103345)Online publication date: Jun-2020
https://doi.org/10.1016/j.artint.2020.103345
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents