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

research-article

Opportunistic evolution: efficient evolutionary computation on large-scale computational grids

Authors:

Keith Sullivan,

Steven ArmentroutAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Pages 2227 - 2232

https://doi.org/10.1145/1388969.1389050

Published: 12 July 2008 Publication History

Abstract

We examine opportunistic evolution, a variation of master-slave distributed evaluation designed for deployment of evolutionary computation to very large grid computing architectures with limited communications, severe evaluation overhead, and wide variance in evaluation node speed. In opportunistic evolution, slaves receive some N individuals at a time, evaluate them, and then run those individuals through their own mini evolutionary loop until some fixed wall clock time has been exceeded. Our implementation of opportunistic evolution may be used in conjunction with either a generational or, for maximum throughput, an asynchronous steady-state evolutionary model in the master. Opportunistic evolution is strongly exploitative. We perform initial experiments comparing the technique with a traditional master/slave model, and suggest possible classes of problems for which it might be apropos.

References

[1]

R. Bianchini and C. Brown. Parallel genetic algorithms on distributed-memory architectures. Revised Version 436, Computer Science Department, University of Rochester, Rochester, NY 14627, 1993.

Digital Library

[2]

R. Bradwell and K. Brown. Parallel asynchronous memetic algorithms. In E. Canú-Paz and B. Punch, editors, Evolutionary Computation and Parallel Processing, pages 157---159, 1999.

[3]

A. E. Calaor, A. Y. Hermosilla, and B. O. C. Jr. Parallel hybrid adventures with simulated annealing and genetic algorithms. In Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks, 2002.

Digital Library

[4]

E. Cantú-Paz. A survey of parallel genetic algorithms. Technical Report 97003, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 117 Transportation Building, 104 S. Mathews Ave., Urbana, IL 61801, 1997.

[5]

E. Cantú-Paz. Designing Efficient and Accurate Parallel Genetic Algorithms. PhD thesis, University of Illinois, 1999.

[6]

J. Digilakis and K. Margaritis. Performance comparison of memetic algorithms. Journal of Applied Mathematics and Computation, 158:237--252, October 2004.

Digital Library

[7]

J. Grefenstette. Parallel adaptive algorithms for function optimization. Technical Report CS-81-19, Computer Science Department, Vanderbilt Univesity, P.o. Box 1679, Station B, Nashville, TN 37235, 1981.

[8]

J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994.

Digital Library

[9]

S. Luke, L. Panait, G. Balan, S. Paus, Z. Skolicki, E. Popovici, J. Harrison, J. Bassett, R. Hubley, and A. Chircop. ECJ: A Java-based evolutionary computation research system. http://cs.gmu.edu/$\sim$eclab/projects/ecj/, 2007.

[10]

M. Mitchell, S. Forest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In Proceedings of the First European Conference on Artifical Life, 1992.

[11]

M. Nowostawski and R. Poli. Parallel genetic algorithm taxonomy. In Knowledge-Based Intelligent Information Engineering Systems, pages 88--92, 1999.

[12]

ORIGIN: Evolutionary SDK. http://www.parabon.com/developers/origin.jsp, 2008.

[13]

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

Digital Library

[14]

J. Tang, M. H. Lim, Y. S. Ong, and M. J. Er. Parallel memetic algoithm with selective local search for large scale quadratic assignment problems. International Journal of Innovative Computing, Information and Control, 2(6):1399--1416, 2006.

[15]

R. A. Watson. Composition Evolution: Interdisciplinary Investigations in Evolvability, Modularity, and Symbiosis. PhD thesis, Brandeis University, 2002.

Digital Library

[16]

R. A. Watson, G. S. Hornby, and J. B. Pollack. Modeling building-block interdependency. In Proceedings of Parallel Problem Solving from Nature, 1998.

Digital Library

Cited By

Hermes SCady JArmentrout SO’Connor JHoldaway SCruchaga CWingo TGreytak E(2024)Epistatic Features and Machine Learning Improve Alzheimer’s Disease Risk Prediction Over Polygenic Risk ScoresJournal of Alzheimer’s Disease10.3233/JAD-23023699:4(1425-1440)Online publication date: 23-May-2024
https://doi.org/10.3233/JAD-230236
Del Pozo Durango RT SDíaz ETrejo JGallegos LArellano MRosillo VHifong M(2023)Analysis of Information Security Management Applying International Standards to Mitigate Risks2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE)10.1109/CSCE60160.2023.00114(669-674)Online publication date: 24-Jul-2023
https://doi.org/10.1109/CSCE60160.2023.00114
Jakobović DGolub MČupić M(2018)Asynchronous and implicitly parallel evolutionary computation modelsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-013-1140-518:6(1225-1236)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-013-1140-5
Show More Cited By

Index Terms

Opportunistic evolution: efficient evolutionary computation on large-scale computational grids

Recommendations

Distributed evolutionary algorithms and their models

Graphical abstractDisplay Omitted HighlightsProvide an updated and systematic review of distributed evolutionary algorithms.Classify the models into population and dimension-distributed groups semantically.Analyze the parallelism, search behaviors, ...
Opportunistic MANETs: mobility can make up for low transmission power

Opportunistic mobile ad hoc networks (MANETs) are a special class of sparse and disconnected MANETs where data communication exploits sporadic contact opportunities among nodes. We consider opportunistic MANETs where nodes move independently at random ...
An Opportunistic Network Coding Routing for Opportunistic Networks

In opportunistic networks (OppNets), instead of assuming a complete path, messages are exchanged opportunistically when two nodes encounter. To support efficient and reliable end-to-end messaging in OppNets, a number of routing protocols based on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

July 2008

1182 pages

ISBN:9781605581316

DOI:10.1145/1388969

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

distributed evolutionary computation

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
179
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hermes SCady JArmentrout SO’Connor JHoldaway SCruchaga CWingo TGreytak E(2024)Epistatic Features and Machine Learning Improve Alzheimer’s Disease Risk Prediction Over Polygenic Risk ScoresJournal of Alzheimer’s Disease10.3233/JAD-23023699:4(1425-1440)Online publication date: 23-May-2024
https://doi.org/10.3233/JAD-230236
Del Pozo Durango RT SDíaz ETrejo JGallegos LArellano MRosillo VHifong M(2023)Analysis of Information Security Management Applying International Standards to Mitigate Risks2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE)10.1109/CSCE60160.2023.00114(669-674)Online publication date: 24-Jul-2023
https://doi.org/10.1109/CSCE60160.2023.00114
Jakobović DGolub MČupić M(2018)Asynchronous and implicitly parallel evolutionary computation modelsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-013-1140-518:6(1225-1236)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-013-1140-5
Moore JAndrews POlson RCarlson SLarock CBulhoes MO’Connor JGreytak EArmentrout S(2017)Grid-based stochastic search for hierarchical gene-gene interactions in population-based genetic studies of common human diseasesBioData Mining10.1186/s13040-017-0139-310:1Online publication date: 30-May-2017
https://doi.org/10.1186/s13040-017-0139-3
Luke STalukder AAlba E(2013)Is the meta-EA a viable optimization method?Proceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2465806(1533-1540)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2465806
Lemnaru CCuibus MBona AAlic APotolea R(2012)A Distributed Methodology for Imbalanced Classification ProblemsProceedings of the 2012 11th International Symposium on Parallel and Distributed Computing10.1109/ISPDC.2012.30(164-171)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1109/ISPDC.2012.30

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