Abstract
This paper presents a study of the fault-tolerant nature of Genetic Algorithms (GAs) on a real-world Desktop Grid System, without implementing any kind of fault-tolerance mechanism. The aim is to extend to parallel GAs previous works tackling fault-tolerance characterization in Genetic Programming. The results show that GAs are able to achieve a similar quality in results in comparison with a failure-free system in three of the six scenarios under study despite the system degradation. Additionally, we show that a small increase on the initial population size is a successful method to provide resilience to system failures in five of the scenarios. Such results suggest that Paralle GAs are inherently and naturally fault-tolerant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Tomassini, M.: Spatially Structured Evolutionary Algorithms. Springer, Heidelberg (2005)
Anderson, D.: Boinc: a system for public-resource computing and storage. In: Proceedings of Fifth IEEE/ACM International Workshop on Grid Computing, 2004, pp. 4–10 (2004)
Desell, T., Szymanski, B., Varela, C.: 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, pp. 921–928. ACM, New York (2008)
Schroeder, B., Gibson, G.A.: A Large-Scale Study of Failures in High-Performance Computing Systems. In: Proc. of the International Conference on Dependable Systems, pp. 249–258 (2006)
Stutzbach, D., Rejaie, R.: Understanding churn in peer-to-peer networks. In: Proceedings of the 6th ACM SIGCOMM on Internet measurement (IMC 2006), pp. 189–202. ACM Press, New York (2006)
Gartner, F.C.: Fundamentals of fault-tolerant distributed computing in asynchronous environments. ACM Computing Surveys 31(1), 1–26 (1999)
Lombraña, D., Fernández, F.: Analyzing fault tolerance on parallel genetic programming by means of dynamic-size populations. In: Congress on Evolutionary Computation, Singapore, September 2007, vol. 1, pp. 4392–4398 (2007)
Hidalgo, I., Fernández, F., Lanchares, J., Lombraña, D.: Is the island model fault tolerant? In: Genetic and Evolutionary Computation Conference, London, England, July 2007, vol. 2, p. 1519 (2007)
González, D.L., de Vega, F.F., Casanova, H.: Characterizing fault tolerance in genetic programming. In: Workshop on Bio-Inspired Algorithms for Distributed Systems, Barcelona, Spain, pp. 1–10 (2009)
Ghosh, S.: Distributed systems: an algorithmic approach. Chapman & Hall/CRC, Boca Raton (2006)
Trujillo, L., Olague, G.: Automated Design of Image Operators that Detect Interest Points, vol. 16, pp. 483–507. MIT Press, Cambridge (2008)
Cantu-Paz, E.: A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systems Repartis 10(2), 141–171 (1998)
Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation 6(5), 443–462 (2002)
de la, O.F.C., Guisado, G.L., Lombraña, D., Fernández, F.: Una herramienta de programación genética paralela que aprovecha recursos públicos de computación. In: V Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados, Tenerife, Spain, February 2007, vol. 1, pp. 167–173 (2007)
Bill Punch, D.Z.: Lil-gp, http://garage.cse.msu.edu/software/lil-gp/index.html
Lombraña, D., Fernández, F., Trujillo, L., Olague, G., Cárdenas, M., Araujo, L., Castillo, P., Sharman, K., Silva, A.: Interpreted applications within boinc infrastructure. In: Ibergrid 2008, Porto, Portugal, May 2008, pp. 261–272 (2008)
González, D.L., de Vega, F.F., Trujillo, L., Olague, G., Araujo, L., Castillo, P., Merelo, J.J., Sharman, K.: Increasing gp computing power for free via desktop grid computing and virtualization. In: Proceedings of the 17th Euromicro Conference on Parallel, Distributed and Network-based Processing, Weimar, Germany, February 2009, pp. 419–423 (2009)
Laredo, J.L.J., Eiben, A.E., van Steen, M., Merelo, J.J.: On the run-time dynamics of a peer-to-peer evolutionary algorithm. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 236–245. Springer, Heidelberg (2008)
Laredo, J.L.J., Castillo, P.A., Mora, A.M., Merelo, J.J., Fernandes, C.: Resilience to churn of a peer-to-peer evolutionary algorithm. Int. J. High Performance Systems Architecture 1(4), 260–268 (2008)
Kondo, D., Fedak, G., Cappello, F., Chien, A., Casanova, H.: Characterizing resource availability in enterprise desktop grids, vol. 23, pp. 888–903. Elsevier, Amsterdam (2007)
Ackley, D.H.: A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers, Norwell (1987)
Deb, K., Goldberg, D.E.: Analyzing deception in trap functions. In: Whitley, L.D. (ed.) FOGA, pp. 93–108. Morgan Kaufmann, San Francisco (1992)
Thierens, D.: Scalability problems of simple genetic algorithms. Evolutionary Computation 7(4), 331–352 (1999)
Crawley, M.J.: Statistics, An Introduction using R. Wiley, Chichester (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lombraña González, D., Jiménez Laredo, J.L., Fernández de Vega, F., Merelo Guervós, J.J. (2010). Characterizing Fault-Tolerance of Genetic Algorithms in Desktop Grid Systems. In: Cowling, P., Merz, P. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2010. Lecture Notes in Computer Science, vol 6022. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12139-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-12139-5_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12138-8
Online ISBN: 978-3-642-12139-5
eBook Packages: Computer ScienceComputer Science (R0)