skip to main content
10.1145/1389095.1389273acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

An asynchronous hybrid genetic-simplex search for modeling the Milky Way galaxy using volunteer computing

Published: 12 July 2008 Publication History

Abstract

This paper examines the use of a probabilistic simplex operator for asynchronous genetic search on the BOINC volunteer computing framework. This algorithm is used to optimize a computationally intensive function with a continuous parameter space: finding the optimal fit of an astronomical model of the Milky Way galaxy to observed stars. The asynchronous search using a BOINC community of over 1,000 users is shown to be comparable to a synchronous continuously updated genetic search on a 1,024 processor partition of an IBM BlueGene/L supercomputer. The probabilistic simplex operator is also shown to be highly effective and the results demonstrate that increasing the parents used to generate offspring improves the convergence rate of the search. Additionally, it is shown that there is potential for improvement by refining the range of the probabilistic operator, adding more parents, and generating offspring differently for volunteered computers based on their typical speed in reporting results. The results provide a compelling argument for the use of asynchronous genetic search and volunteer computing environments, such as BOINC, for computationally intensive optimization problems and, therefore, this work opens up interesting areas of future research into asynchronous optimization methods.

References

[1]
J. e. a. Adelman-McCarthy. The 6th Sloan Digital Sky Survey Data Release, http://www.sdss.org/dr6/, July 2007. ApJS, in press, arXiv/0707.3413.
[2]
E. Alba and B. Dorronsoro. The exploration/exploitation tradeo in dynamic cellular genetic algorithms. IEEE Transactions on Evolutionary Computation, 9:126--142, April 2005.
[3]
E. Alba and J. M. Troya. Analyzing synchronous and asynchronous parallel distributed genetic algorithms. Future Generation Computer Systems, 17:451--465, January 2001.
[4]
D. P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, and D. Werthimer. SETI@home: an experiment in public-resource computing. Commun. ACM, 45(11):56--61, 2002.
[5]
D. P. Anderson, E. Korpela, and R. Walton. High-performance task distribution for volunteer computing. In e-Science, pages 196--203. IEEE Computer Society, 2005.
[6]
J. Berntsson and M. Tang. A convergence model for asynchronous parallel genetic algorithms. In IEEE Congress on Evolutionary Computation (CEC2003), volume 4, pages 2627--2634, December 2003.
[7]
E. Cantu-Paz. A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systems Repartis, 10(2):141--171, 1998.
[8]
R. Chelouah and P. Siarry. Genetic and nelder-mead algorithms hybridized for a more accurate global optimiation of continuous multiminima functions. European Journal of Operational Research, 148(2):335--348, july 2003.
[9]
T. Desell, N. Cole, M. Magdon-Ismail, H. Newberg, B. Szymanski, and C. Varela. Distributed and generic maximum likelihood evaluation. In 3rd IEEE International Conference on e-Science and Grid Computing (eScience2007), pages 337--344, Bangalore, India, December 2007.
[10]
B. Dorronsoro and E. Alba. A simple cellular genetic algorithm for continuous optimization. IEEE Congress on Evolutionary Computation (CEC2006), pages 2838--2844, July 2006.
[11]
G. Folino, A. Forestiero, and G. Spezzano. A JXTA based asynchronous peer-to-peer implementation of genetic programming. Journal of Software, 1:12--23, August 2006.
[12]
H. Imade, R. Morishita, I. Ono, N. Ono, and M. Okamoto. A grid-oriented genetic algorithm framework for bioinformatics. New Generation Computing: Grid Systems for Life Sciences, 22:177--186, January 2004.
[13]
V. Katari, S. C. Satapathy, J. Murthy, and P. P. Reddy. Hybridized improved genetic algorithm with variable length chromosome for image clustering. IJCSNS International Journal of COmputer Science and Network Security, 7(11):121--131, November 2007.
[14]
A. Lewis and D. Abramson. An evolutionary programming algorithm for multi-ob jective optimisation. In IEEE Congress on Evolutionary Computation (CEC2003), volume 3, pages 1926--1932, December 2003.
[15]
D. Lim, Y.-S. Ong, Y. Jin, B. Sendho, and B.-S. Lee. Efficient hierarchical parallel genetic algorithms using grid computing. Future Generation Computer Systems, 23:658--670, May 2007.
[16]
V. Pande et al. Atomistic protein folding simulations on the submillisecond timescale using worldwide distributed computing. Biopolymers, 68(1):91--109, 2002. Peter Kollman Memorial Issue.
[17]
J. Purnell, M. Magdon-Ismail, and H. Newberg. A probabilistic approach to finding geometric objects in spatial datasets of the Milky Way. In Proceedings of the 15th International Symposium on Methodoligies for Intelligent Systems (ISMIS 2005), pages 475--484, Saratoga Springs, NY, USA, May 2005. Springer.
[18]
J.-M. Renders and H. Bersini. Hibridizing genetic algorithms with hill-climbing methods for global optimization: two possible ways. In IEEE World Congress on Computational Intel ligence, First Conference on Evolutionary Computation, volume 1, pages 312--317, June 1994.
[19]
S. C. Satapathy, J. Murthy, P. Prasada, V. Katari, S. Malireddi, and V. S. Kollisetty. An efficient hybrid algorithm for data clustering using improved genetic algorithm and nelder mead simplex search. In International Conference on Computational Intel ligence and Multimedia Applications, volume 1, pages 498--510, December 2007.
[20]
G. Seront and H. Bersini. Simplex ga and hybrid methods. In IEEE International Conference on Evolutionary Computation, pages 845--848, May 1996.
[21]
A. Sinha and D. E. Goldberg. A survey of hybrid genetic and evolutionary algorithms. Technical Report No. 2003004, Illinois Genetic Algorithms Laboratory (IlliGAL), 2003.
[22]
B. Szymanski, T. Desell, and C. Varela. The eect of heterogeneity on asynchronous panmictic genetic search. In Proc. of the Seventh International Conference on Paral lel Processing and Applied Mathematics (PPAM'2007), LNCS, Gdansk, Poland, September 2007. To appear.
[23]
L. Wei and M. Zhao. A niche hybrid genetic algorithm for global optimization of continuous multimodal functions. Applied Mathematics and Computation, 160(3):649--661, January 2005.
[24]
J. Yen, J. C. Liao, B. Lee, and D. Randolph. A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method. IEEE Transactions on Systems, Man and Cybernetics, Part B, 29(2):173--191, April 1998.

Cited By

View all
  • (2023)Co-evolving Recurrent Neural Networks and their Hyperparameters with Simplex Hyperparameter OptimizationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596407(1639-1647)Online publication date: 15-Jul-2023
  • (2023)Efficient Neuroevolution Using Island Repopulation and Simplex Hyperparameter Optimization2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10371872(1837-1842)Online publication date: 5-Dec-2023
  • (2017)Developing a Volunteer Computing Project to Evolve Convolutional Neural Networks and Their Hyperparameters2017 IEEE 13th International Conference on e-Science (e-Science)10.1109/eScience.2017.14(19-28)Online publication date: Oct-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation
July 2008
1814 pages
ISBN:9781605581309
DOI:10.1145/1389095
  • Conference Chair:
  • Conor Ryan,
  • Editor:
  • Maarten Keijzer
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.

Check for updates

Author Tags

  1. genetic algorithms
  2. simplex method
  3. volunteer computing

Qualifiers

  • Research-article

Conference

GECCO08
Sponsor:

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 08 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Co-evolving Recurrent Neural Networks and their Hyperparameters with Simplex Hyperparameter OptimizationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596407(1639-1647)Online publication date: 15-Jul-2023
  • (2023)Efficient Neuroevolution Using Island Repopulation and Simplex Hyperparameter Optimization2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10371872(1837-1842)Online publication date: 5-Dec-2023
  • (2017)Developing a Volunteer Computing Project to Evolve Convolutional Neural Networks and Their Hyperparameters2017 IEEE 13th International Conference on e-Science (e-Science)10.1109/eScience.2017.14(19-28)Online publication date: Oct-2017
  • (2015)Designing and Modeling a Browser-Based DistributedEvolutionary Computation SystemProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768465(1117-1124)Online publication date: 11-Jul-2015
  • (2015)Evolving Deep Recurrent Neural Networks Using Ant Colony OptimizationEvolutionary Computation in Combinatorial Optimization10.1007/978-3-319-16468-7_8(86-98)Online publication date: 15-Mar-2015
  • (2014)omniClassifierProceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/2649387.2649439(514-523)Online publication date: 20-Sep-2014
  • (2014)Designing robust volunteer-based evolutionary algorithmsGenetic Programming and Evolvable Machines10.1007/s10710-014-9213-515:3(221-244)Online publication date: 1-Sep-2014
  • (2014)Evolving Neural Network Weights for Time-Series Prediction of General Aviation Flight DataParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_76(771-781)Online publication date: 2014
  • (2013)Improving volunteer computing scheduling for evolutionary algorithmsFuture Generation Computer Systems10.1016/j.future.2012.04.00229:1(1-14)Online publication date: 1-Jan-2013
  • (2012)Pool vs. Island Based Evolutionary AlgorithmsProceedings of the 2012 Seventh International Conference on P2P, Parallel, Grid, Cloud and Internet Computing10.1109/3PGCIC.2012.56(19-24)Online publication date: 12-Nov-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media