Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

EvAg: a scalable peer-to-peer evolutionary algorithm

  • Original Paper
  • Published:
Genetic Programming and Evolvable Machines Aims and scope Submit manuscript

Abstract

This paper studies the scalability of an Evolutionary Algorithm (EA) whose population is structured by means of a gossiping protocol and where the evolutionary operators act exclusively within the local neighborhoods. This makes the algorithm inherently suited for parallel execution in a peer-to-peer fashion which, in turn, offers great advantages when dealing with computationally expensive problems because distributed execution implies massive scalability. In this paper we show another advantage of this algorithm: We experimentally demonstrate that it scales up better than traditional alternatives even when executed in a sequential fashion. In particular, we analyze the behavior of several EAs on well-known deceptive trap functions with varying sizes and levels of deceptiveness. The results show that the new EA requires smaller optimal population sizes and fewer fitness evaluations to reach solutions. The relative advantage of the new EA is more outstanding as problem hardness and size increase. In some cases the new algorithm reduces the computational efforts of the traditional EAs by several orders of magnitude.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Originally, Ackley’s trap functions use \(z={\frac{3l} {4}}\) , however, [7] demonstrates that trap functions are fully easy under such settings.

  2. All the source code for the experiments is available from our Subversion repository at http://www.forja.rediris.es/svn/geneura/evogen published under GPL v3. Accessed on September 2009.

References

  1. D.H. Ackley, A Connectionist Machine for Genetic Hillclimbing. (Kluwer, Norwell, MA, 1987)

    Google Scholar 

  2. E. Alba, M. Tomassini, Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)

    Article  Google Scholar 

  3. M. Arenas, P. Collet, A.E. Eiben, M. Jelasity, J.J. Merelo, B. Paechter, M. Preuss, M. Schoenauer, A framework for distributed evolutionary algorithms. In Parallel Problem Solving from Nature—PPSN VII, Granada, Spain, No. 2439 in Lecture Notes in Computer Science, LNCS. (Springer, 2002), pp. 665–675

  4. B. Bánhelyi, M. Biazzini, A. Montresor, M. Jelasity, Peer-to-peer optimization in large unreliable networks with branch-and-bound and particle swarms. In Applications of Evolutionary Computing, Lecture Notes in Computer Science, ed. by M. Giacobini, A. Brabazon, S. Cagnoni, G.A.D. Caro, A. Ekárt, A.I. Esparcia-Alcázar, M. Farooq, A. Fink, P. Machado (Springer, 2009), pp. 87–92

  5. J. Berntsson, G2DGA: an adaptive framework for internet-based distributed genetic algorithms. In GECCO ’05: Proceedings of the 2005 workshops on Genetic and evolutionary computation, pp. 346–349

  6. E. Cantú-Paz, Efficient and Accurate Parallel Genetic Algorithms. (Kluwer, Norwell, MA, 2000)

    MATH  Google Scholar 

  7. K. Deb, D.E. Goldberg, Analyzing deception in trap functions. In Foundations of Genetic Algorithms. (Morgan Kaufmann, 1991), pp. 93–108

  8. A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing. (Springer, Berlin, 2003)

    MATH  Google Scholar 

  9. A.E. Eiben, A.R. Griffioen, E. Haasdijk, Population-based adaptive systems: concepts, issues, and the platform NEW TIES. In Proceedings of European Conference on Complex Systems, Dresden, Germany, http://www.cs.vu.nl/~gusz/papers/2007-ECCS-PAS.pdf

  10. G. Folino, G. Spezzano, P-cage: an environment for evolutionary computation in peer-to-peer systems. In EuroGP, Lecture Notes in Computer Science, vol. 3905, ed. by P. Collet, M. Tomassini, M. Ebner, S. Gustafson, A. Ekárt (Springer, 2006), pp. 341–350

  11. M. Giacobini, E. Alba, A. Tettamanzi, M. Tomassini, Modeling selection intensity for toroidal cellular evolutionary algorithms. In GECCO ’04: Proceedings of the 2004 conference on Genetic and Evolutionary Computation (Springer, Berlin/Heidelberg, LNCS, 2004), pp. 1138–1149

  12. M. Giacobini, M. Tomassini, A. Tettamanzi, Takeover time curves in random and small-world structured populations. In GECCO ’05: Proceedings of the 2005 conference on Genetic and evolutionary computation (ACM, New York, NY, 2005a), pp. 1333–1340. http://www.doi.acm.org/10.1145/1068009.1068224

  13. M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans. Evol. Comput. 9(5), 489–505 (2005b)

    Article  Google Scholar 

  14. M. Giacobini, M. Preuss, M. Tomassini, Effects of scale-free and small-world topologies on binary coded self-adaptive CEA. In Evolutionary Computation in Combinatorial Optimization—EvoCOP 2006, vol. 3906, ed. by J. Gottlieb, G.R. Raidl (Springer, Budapest, LNCS, 2006), pp. 85–96

  15. D.E. Goldberg, The Design of Innovation—Lessons from and for Competent Genetic Algorithms (Kluwer, Norwell, MA, 2002)

    MATH  Google Scholar 

  16. D.E. Goldberg, K. Deb, A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of Genetic Algorithms (Morgan Kaufmann, 1991), pp. 69–93

  17. G. Harik, E. Cantú-Paz, D. Goldberg, B. Miller, The Gambler’s ruin problem, genetic algorithms, and the sizing of populations. Evol. Comput. 7(3), 231–253 (1999)

    Article  Google Scholar 

  18. I. Hidalgo, F. Fernández, Balancing the computation effort in genetic algorithms. In The 2005 IEEE Congress on Evolutionary Computation, vol. 2 (IEEE Press, 2005), pp. 1645–1652. doi:10.1109/CEC.2005.1554886

  19. M. Jelasity, M. van Steen, Large-scale Newscast Computing on the Internet. Tech. Rep. IR-503 (Vrije Universiteit Amsterdam, Department of Computer Science, Amsterdam, The Netherlands). http://www.cs.vu.nl/pub/papers/globe/IR-503.02.pdf

  20. M. Jelasity, A. Montresor, O. Babaoglu, Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst. 23(3), 219–252 (2005)

    Article  Google Scholar 

  21. J.L.J. Laredo, P.A. Castillo, B. Paechter, A.M. Mora, E. Alfaro-Cid, A. Esparcia-Alcázar, J.J. Merelo, Empirical validation of a gossiping communication mechanism for parallel EAs. In EvoWorkshops, Lecture Notes in Computer Science, vol. 4448 (Springer, 2007), pp. 129–136

  22. J.L.J. Laredo, P.A. Castillo, A.M. Mora, J.J. Merelo, Exploring population structures for locally concurrent and massively parallel evolutionary algorithms. In IEEE Congress on Evolutionary Computation (CEC2008), WCCI2008 Proceedings (IEEE Press, Hong Kong, 2008a), pp. 2610–2617

  23. J.L.J. Laredo, P.A. Castillo, A.M. Mora, J.J. Merelo, C. Fernandes, Resilience to churn of a peer-to-peer evolutionary algorithm. Int. J. High Perform. Syst. Archit. 1(4), 260–268 (2008b). http://www.dx.doi.org/10.1504/IJHPSA.2008.024210

  24. J.L.J. Laredo, A.E. Eiben, M. van Steen, J.J. Merelo, On the run-time dynamics of a peer-to-peer evolutionary algorithm. In Proceedings of the 10th international conference on Parallel Problem Solving from Nature (Springer, Berlin, Heidelberg, 2008c), pp. 236–245. http://www.dx.doi.org/10.1007/978-3-540-87700-4_24

  25. J.L.J. Laredo, P.A. Castillo, A.M. Mora, J.J. Merelo, Evolvable agents, a fine grained approach for distributed evolutionary computing: walking towards the peer-to-peer computing frontiers. Soft Comput. Fusion Found. Methodol. Appl. 12(12), 1145–1156 (2008d)

    MATH  Google Scholar 

  26. J.L.J. Laredo, C. Fernandes, A. Mora, P.A. Castillo, P. Garcia-Sanchez, J.J. Merelo, Studying the Cache Size in a Gossip-based Evolutionary Algorithm. In 3rd International Symposium on Intelligent Distributed Computing (Springer, Berlin/Heidelberg, 2009), pp. 131–140

  27. W.P. Lee, Parallelizing evolutionary computation: a mobile agent-based approach. Expert Syst. Appl. 32(2), 318–328 (2007)

    Article  Google Scholar 

  28. F.G. Lobo, C.F. Lima, Adaptive population sizing schemes in genetic algorithms. In Parameter Setting in Evolutionary Algorithms, Studies in Computational Intelligence (Springer, Berlin/Heidelberg, 2007), pp. 185–204

  29. J.J. Merelo, P.A. Castillo, J.L.J. Laredo, A.M. Mora, A. Prieto, Asynchronous distributed genetic algorithms with Javascript and JSON. In IEEE Congress on Evolutionary Computation (CEC2008), WCCI2008 Proceedings (IEEE Press, Hong Kong, 2008), pp. 1372–1379

  30. N. Nedjah, L. de Macedo Mourelle, E. Alba (eds.), Parallel Evolutionary Computations, Studies in Computational Intelligence, vol. 22. (Springer, 2006)

  31. M. Preuss, C. Lasarczyk, On the importance of information speed in structured populations. In PPSN, vol. 3242 (Springer, 2004), pp. 91–100

  32. K. Sastry, Evaluation-relaxation Schemes for Genetic and Evolutionary Algorithms. Tech. Rep. 2002004 (University of Illinois at Urbana-Champaign, Urbana, IL, 2001)

  33. R. Steinmetz, K. Wehrle, What is this peer-to-peer about? In Peer-to-Peer Systems and Applications, Lecture Notes in Computer Science, vol. 3485, ed. by R. Steinmetz, K. Wehrle (Springer, 2005), pp 9–16

  34. D. Thierens, Scalability problems of simple genetic algorithms. Evol. Comput. 7(4), 331–352 (2005)

    Article  Google Scholar 

  35. M. Tomassini, Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Natural Computing Series) (Springer New York, Inc., Secaucus, NJ, 2005)

    MATH  Google Scholar 

  36. S. Voulgaris, M. Jelasity, M. van Steen, A Robust and Scalable Peer-to-Peer Gossiping Protocol, Lecture Notes in Computer Science (LNCS), vol. 2872 (Springer, Berlin/Heidelberg, 2004), pp. 47–58. doi:10.1007/b104265

  37. D. Watts, S. Strogatz, Collective dynamics of “small-world” networks. Nature 393, 440–442 (1998). http://www.dx.doi.org/10.1038/30918

    Google Scholar 

  38. J. Whitacre, R. Sarker, Q. Pham, The self-organization of interaction networks for nature-inspired optimization. IEEE Trans. Evol. Comput. 12(2), 220–230 (2008). doi:10.1109/TEVC.2007.900327

    Google Scholar 

  39. W.R.M.U.K. Wickramasinghe, M. van Steen, A.E. Eiben, Peer-to-peer evolutionary algorithms with adaptive autonomous selection. In GECCO ’07 (ACM Press, New York, NY, 2007), pp. 1460–1467, http://www.doi.acm.org/10.1145/1276958.1277225

Download references

Acknowledgments

This work has been supported by the Spanish MICYT project TIN2007-68083-C02-01, the Junta de Andalucia CICE project P06-TIC-02025 and the Granada University PIUGR 9/11/06 project.

Author information

Authors and Affiliations

  1. University of Granada, ATC-ETSIT, C. Periodista Daniel Saucedo Aranda, 18071, Granada, Spain

    J. L. J. Laredo & J. J. Merelo

  2. Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

    A. E. Eiben & M. van Steen

Authors
  1. J. L. J. Laredo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. E. Eiben
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. van Steen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. J. J. Merelo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. L. J. Laredo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laredo, J.L.J., Eiben, A.E., van Steen, M. et al. EvAg: a scalable peer-to-peer evolutionary algorithm. Genet Program Evolvable Mach 11, 227–246 (2010). https://doi.org/10.1007/s10710-009-9096-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10710-009-9096-z

Keywords

Search

Navigation