Designing and Modeling a Browser-Based DistributedEvolutionary Computation System

ABSTRACT

Web browsers have scaled from simple page-rendering engines to operating systems that include most services the lower OS layer has, with the added facility that applications can be run by just visiting a web page. In this paper we will describe the front and back end of a distributed evolutionary computation system that uses the browser's capabilities of running programs written in JavaScript. We will focus on two different aspects of volunteer computing: first, the pragmatic: where to find those resources, which ones can be used, what kind of support you have to give them; and then, the theoretical: how evolutionary algorithms can be adapted to an environment in which nodes come and go, have different computing capabilities and operate in complete asynchrony of each other. We will examine the setup needed to create a simple distributed evolutionary algorithm using JavaScript, with the intention of eventually finding a model of how users react to it by collecting data from several experiments featuring a classical benchmark function.

References

1. D. Anderson. BOINC: A system for public-resource computing and storage. In Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, Pittsburgh, USA, 2004.
2. 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.
3. D. P. Anderson and G. Fedak. The computational and storage potential of volunteer computing. In Cluster Computing and the Grid, 2006. CCGRID 06. Sixth IEEE International Symposium on, volume 1, pages 73--80. IEEE, 2006.
4. S. authors. Crowdprocess. Hacker news, https://news.ycombinator.com/item?id=6744432, 2013.
5. W. Bausch. Grid computing. Technical report, nformation and Communication Systems Research Group, Institute of Information Systems, ETH Zurich, May 2000. Presentation at http://www.vs.inf.ethz.ch/edu/WS0001/UI/slides/ui_02GridComputing.pdf.
6. R. Buyya and S. Vazhkudai. Compute power market: Towards a market-oriented grid. In Cluster Computing and the Grid, 2001. Proceedings. First IEEE/ACM International Symposium on, pages 574--581. IEEE, 2001.
7. P. A. Castillo, P. García-Sánchez, M. G. Arenas, J. L. Bernier, and J. J. Merelo. Distributed evolutionary computation using SOAP and REST web services. In J. Kolodziej, S. U. Khan, and T. Burczynski, editors, Advances in Intelligent Modelling and Simulation, volume 422 of Studies in Computational Intelligence, pages 89--111. Springer Berlin Heidelberg, 2012.
8. F. S. Chong and W. B. Langdon. Java based distributed Genetic Programming on the internet. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, page 1229, Orlando, Florida, USA, 13--17 July 1999. Morgan Kaufmann. Full text in technical report CSRP-99-7.
9. T. Desell, B. Szymanski, and C. Varela. An asynchronous hybrid genetic-simplex search for modeling the Milky Way galaxy using volunteer computing. In Proceedings of the 10th annual conference on Genetic and evolutionary computation, GECCO '08, pages 921--928, New York, NY, USA, 2008. ACM.
10. J. Duda and W. Dłubacz. Distributed evolutionary computing system based on web browsers with JavaScript. In Applied Parallel and Scientific Computing, pages 183--191. Springer, 2013.
11. J. Duda and W. Dlubacz. GPU acceleration for the web browser based evolutionary computing system. In System Theory, Control and Computing (ICSTCC), 2013 17th International Conference, pages 751--756. IEEE, 2013.
12. ECMA. ECMA-262: ECMAScript Language Specification. ECMA (European Association for Standardizing Information and Communication Systems), Geneva, Switzerland, third edition, Dec. 1999.
13. C. Fernandes, J. Merelo, and A. Rosa. Using Dissortative Mating Genetic Algorithms to Track the Extrema of Dynamic Deceptive Functions. Arxiv preprint arXiv:0904.3063, 2009.
14. D. Flanagan. JavaScript: the definitive guide. O'Reilly Media, Inc., 2006.
15. D. L. Gonzalez, F. F. de Vega, L. Trujillo, G. Olague, F. C. de la O, M. Cardenas, L. Araujo, P. A. Castillo, and K. Sharman. Increasing GP computing power via volunteer computing. CoRR, abs/0801.1210, 2008.
16. D. González Lombraña, J. L. J. Laredo, F. Fernández de Vega, and J. J. Merelo Guervós. Characterizing fault-tolerance of genetic algorithms in desktop grid systems. In Evolutionary Computation in Combinatorial Optimization, pages 131--142. Springer, 2010.
17. J. J. M. Guervós, P. A. C. Valdivieso, A. M. García, A. Esparcia-Alcázar, and V. M. R. Santos. Nodeo, a multi-paradigm distributed evolutionary algorithm platform in javascript. In D. V. Arnold and E. Alba, editors, Genetic and Evolutionary Computation Conference, GECCO '14, Vancouver, BC, Canada, July 12--16, 2014, Companion Material Proceedings, pages 1155--1162. ACM, 2014.
18. B. Javadi, D. Kondo, J.-M. Vincent, and D. P. Anderson. Mining for statistical models of availability in large-scale distributed systems: An empirical study of SETI@home. In Modeling, Analysis & Simulation of Computer and Telecommunication Systems, 2009. MASCOTS'09. IEEE International Symposium on, pages 1--10. IEEE, 2009.
19. J. L. Jiménez-Laredo, P. Bouvry, D. L. González, F. F. de Vega, M. García-Arenas, J. J. Merelo-Guervós, and C. M. Fernandes. Designing robust volunteer-based evolutionary algorithms. Genetic Programming and Evolvable Machines, 15(3):221--244, 2014.
20. H. Jin, F. Luo, X. Liao, Q. Zhang, and H. Zhang. Constructing a P2P-based high performance computing platform. In 2006 International Workshop on P2P for High Performance Computational Sciences (P2P-HPCS06), volume 3994 of LECTURE NOTES IN COMPUTER SCIENCE, pages 380--387. Springer, 2006.
21. J. Klein and L. Spector. Unwitting distributed genetic programming via asynchronous JavaScript and XML. In GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 1628--1635, New York, NY, USA, 2007. ACM.
22. W. B. Langdon. Pfeiffer -- A distributed open-ended evolutionary system. In B. Edmonds, N. Gilbert, S. Gustafson, D. Hales, and N. Krasnogor, editors, AISB'05: Proceedings of the Joint Symposium on Socially Inspired Computing (METAS 2005), pages 7--13, University of Hertfordshire, Hatfield, UK, 12--15 Apr. 2005. SSAISB 2005 Convention.
23. J. Maestro-Montojo, S. Salcedo-Sanz, and J. J. M. Guervós. New solver and optimal anticipation strategies design based on evolutionary computation for the game of mastermind. Evolutionary Intelligence, 6(4):219--228, 2014.
24. J. J. Merelo. Low or no cost evolutionary computation. Figshare, 09 2014. http://dx.doi.org/10.6084/m9.figshare.1176079.
25. J. J. Merelo. Low or no cost distributed evolutionary computation. In D. Camacho, L. Braubach, S. Venticinque, and C. Badica, editors, Intelligent Distributed Computing VIII, volume 570 of Studies in Computational Intelligence, pages 3--4. Springer International Publishing, 2015.
26. J. J. Merelo, P. A. Castillo, J. L. J. Laredo, A. Mora, and A. Prieto. Asynchronous distributed genetic algorithms with JavaScript and JSON. In WCCI 2008 Proceedings, pages 1372--1379. IEEE Press, 2008.
27. J. J. Merelo, A. M. García, J. L. J. Laredo, J. Lupión, and F. Tricas. Browser-based distributed evolutionary computation: performance and scaling behavior. In GECCO '07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, pages 2851--2858, New York, NY, USA, 2007. ACM Press.
28. J. J. Merelo, A. M. Mora, P. A. Castillo, J. L. J. Laredo, L. Araujo, K. C. Sharman, A. I. Esparcia-Alcázar, E. Alfaro-Cid, and C. Cotta. Testing the intermediate disturbance hypothesis: Effect of asynchronous population incorporation on multi-deme evolutionary algorithms. In G. Rudolph, T. Jansen, S. Lucas, C. Poloni, and N. Beume, editors, Parallel Problem Solving from Nature - PPSN X, volume 5199 of LNCS, pages 266--275, Dortmund, 13--17 Sept. 2008. Springer.
29. J. J. Merelo-Guervós and P. García-Sánchez. Modeling browser-based distributed evolutionary computation systems. ArXiv e-prints, Mar. 2015. http://arxiv.org/abs/1503.06424.
30. J.-J. Merelo-Guervós, A. Mora, J. A. Cruz, and A. I. Esparcia. Pool-based distributed evolutionary algorithms using an object database. In C. di Chio et al., editor, EvoApplications 2012 Proceedings, pages 441--450, 2012.
31. A. Milani. Online genetic algorithms. Technical report, Institute of Information Theories and Applications FOI ITHEA, 2004.
32. H. Mühlenbein. Parallel genetic algorithms, population genetics and combinatorial optimization. In Parallelism, Learning, Evolution, pages 398--406. Springer, 1991.
33. J. Muszynski, S. Varrette, J. L. J. Laredo, and P. Bouvry. Analysis of the data flow in the newscast protocol for possible vulnerabilities. In Z. Kotulski, B. Ksiezopolski, and K. Mazur, editors, Cryptography and Security Systems - Third International Conference, CSS 2014, Lublin, Poland, September 22-24, 2014. Proceedings, volume 448 of Communications in Computer and Information Science, pages 89--99. Springer, 2014.
34. S. Nijssen and T. Back. An analysis of the behavior of simplified evolutionary algorithms on trap functions. Evolutionary Computation, IEEE Transactions on, 7(1):11--22, 2003.
35. R. Nogueras and C. Cotta. Studying fault-tolerance in island-based evolutionary and multimemetic algorithms. Journal of Grid Computing, pages 1--24, 2015.
36. J. G. Peñalver and J.-J. Merelo-Guervós. Optimizing web page layout using an annealed genetic algorithm as client-side script. In Proceedings PPSN, Parallel Problem Solving from Nature V, number 1967 in Lecture Notes in Computer Science, pages 1018--1027. Springer-Verlag, 1998. http://www.springerlink.com/link.asp?id=2gqqar9cv3et5nlg.
37. L. F. G. Sarmenta. Sabotage-tolerance mechanisms for volunteer computing systems. Future Generation Computer Systems, 18(4):561--572, 2002.
38. L. F. G. Sarmenta and S. Hirano. Bayanihan: building and studying Web-based volunteer computing systems using Java. Future Generation Computer Systems, 15(5-6):675--686, 1999.
39. W. J. Severin and J. W. Tankard. Communication theories: Origins, methods, and uses in the mass media. Longman, 2010.
40. D. Sherry, K. Veeramachaneni, J. McDermott, and U.-M. O'Reilly. Flex-gp: genetic programming on the cloud. In Applications of Evolutionary Computation, pages 477--486. Springer, 2012.
41. F. Soares, L. Silva, and J. Silva. How to get volunteers for web-based metacomputing. In In Proc. of the Distributed Computing on the Web (DCW98), Germany., pages 264--276. Citeseer, June 1998.
42. L. van de Wijngaert and H. Bouwman. Would you share? predicting the potential use of a new technology. Telematics and Informatics, 26(1):85--102, 2009.
43. X. Wang and S. Xu. P2HP: Construction of a cooperative server group based volunteer computing environment. In International Conference on Internet Computing in Science and Engineering, volume 0, pages 389--395, Los Alamitos, CA, USA, 2008. IEEE Computer Society.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

  • Machine learning

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming