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

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: Enrique Alba , José M. Troya, Analyzing synchronous and asynchronous parallel distributed genetic algorithms, Future Generation Computer Systems, v.17 n.4, p.451-465, January 2001 [doi>10.1016/S0167-739X(99)00129-6]
• 4: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 5: David P. Anderson , Eric Korpela , Rom Walton, High-Performance Task Distribution for Volunteer Computing, Proceedings of the First International Conference on e-Science and Grid Computing, p.196-203, December 05-08, 2005 [doi>10.1109/E-SCIENCE.2005.51]
• 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: Travis Desell , Nathan Cole , Malik Magdon-Ismail , Heidi Newberg , Boleslaw Szymanski , Carlos Varela, Distributed and Generic Maximum Likelihood Evaluation, Proceedings of the Third IEEE International Conference on e-Science and Grid Computing, p.337-344, December 10-13, 2007 [doi>10.1109/E-SCIENCE.2007.30]
• 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: Hiroaki Imade , Ryohei Morishita , Isao Ono , Norihiko Ono , Masahiro Okamoto, A grid-oriented genetic algorithm framework for bioinformatics, New Generation Computing, v.22 n.2, p.177-186, January 2004 [doi>10.1007/BF03040956]
• 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: Dudy Lim , Yew-Soon Ong , Yaochu Jin , Bernhard Sendhoff , Bu-Sung Lee, Efficient Hierarchical Parallel Genetic Algorithms using Grid computing, Future Generation Computer Systems, v.23 n.4, p.658-670, May, 2007 [doi>10.1016/j.future.2006.10.008]
• 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: Suresh Chandra Satapathy , Jvr Murthy , P. V. G. D. Prasada Reddy , Venkatesh Katari , Satish Malireddi , V. N. K. Srujan Kollisetty, An Efficient Hybrid Algorithm for Data Clustering Using Improved Genetic Algorithm and Nelder Mead Simplex Search, Proceedings of the International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007), p.498-510, December 13-15, 2007 [doi>10.1109/ICCIMA.2007.68]
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms

Keywords:
genetic algorithms, simplex method, volunteer computing