Skip to main content
Top

2018 | OriginalPaper | Chapter

Spatially Structured Evolutionary Algorithms: Graph Degree, Population Size and Convergence Speed

Authors : Carlos M. Fernandes, Juan L. J. Laredo, Agostinho C. Rosa

Published in: Intelligent Distributed Computing XI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

An evolutionary algorithm (EA) is said to be spatially structured when its individuals are arranged in an incomplete graph and interact only with their neighbors. Previous studies argue that spatially structured EAs are less likely to converge prematurely to local optima. Furthermore, they have been initially designed for distributed computing and it is often claimed that their parallelization is simpler than the equivalent non-structured algorithm. However, most of the empirical studies on spatially structured EAs use a predefined and fixed population size, whereas the full potential of this or any other any kind of EA can only be explored if the population size is properly set. This paper investigates optimal population sizes of spatially structured EAs (cellular EAs, in particular) and the relationship between that size, convergence speed and the degree of the structuring network. EAs structured by regular graphs with different degrees have been tested on different types of fitness landscapes. We conclude that in most cases graphs with low degree require smaller populations to converge consistently to global optima. However, if the population size is properly set, EAs structured by graphs with higher degrees not only converge to global optima with high probability, but also converge faster.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)CrossRef Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)CrossRef
2.
go back to reference Alba, E., Dorronsoro, B.: The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans. Evol. Comput. 9, 126–142 (2005)CrossRef Alba, E., Dorronsoro, B.: The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans. Evol. Comput. 9, 126–142 (2005)CrossRef
3.
go back to reference Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford (1996)MATH Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford (1996)MATH
4.
go back to reference Cantú-Paz, E.: Migration policies, selection pressure, and parallel EAs. Journal of Heuristics 7(4), 311–334 (2001)CrossRefMATH Cantú-Paz, E.: Migration policies, selection pressure, and parallel EAs. Journal of Heuristics 7(4), 311–334 (2001)CrossRefMATH
5.
go back to reference Fernandes, C.M., Laredo, J.L.J., Merelo, J.J., Cotta, C., Rosa, A.C.: Dynamic and Partially Connected Ring Topologies for Evolutionary Algorithms with Structured Populations, EvoApplications 2014: Applications of Evolutionary Computation, pp. 665–677 (2014) Fernandes, C.M., Laredo, J.L.J., Merelo, J.J., Cotta, C., Rosa, A.C.: Dynamic and Partially Connected Ring Topologies for Evolutionary Algorithms with Structured Populations, EvoApplications 2014: Applications of Evolutionary Computation, pp. 665–677 (2014)
6.
go back to reference Giacobini, M., Tomassini, M., Tettamanzi, A.: Takeover time curves in random and small-world structured populations. In: Proceedings of the 7th GECCO, pp. 1333–1340 (2005) Giacobini, M., Tomassini, M., Tettamanzi, A.: Takeover time curves in random and small-world structured populations. In: Proceedings of the 7th GECCO, pp. 1333–1340 (2005)
7.
go back to reference Giacobini, M., Tomassini, M., Tettamanzi, A.G.B., Alba, E.: Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans. Evol. Comput. 9, 489–505 (2005)CrossRef Giacobini, M., Tomassini, M., Tettamanzi, A.G.B., Alba, E.: Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans. Evol. Comput. 9, 489–505 (2005)CrossRef
8.
go back to reference Laredo, J.L.J., Bouvry, P., González, D.L., Fernandéz de la Vega, F., Arenas, M.G., Merelo, J.J., Fernandes, C.M.: Designing robust volunteer-based evolutionary algorithms. Genet. Program Evol. Mach. 15(3), 221–244 (2014)CrossRef Laredo, J.L.J., Bouvry, P., González, D.L., Fernandéz de la Vega, F., Arenas, M.G., Merelo, J.J., Fernandes, C.M.: Designing robust volunteer-based evolutionary algorithms. Genet. Program Evol. Mach. 15(3), 221–244 (2014)CrossRef
9.
go back to reference Payne, J.L, Eppstein, M.J.: Emergent mating topologies in spatially structured genetic algorithms. In: Proceedings of 8th GECCO, pp. 207–214 (2006) Payne, J.L, Eppstein, M.J.: Emergent mating topologies in spatially structured genetic algorithms. In: Proceedings of 8th GECCO, pp. 207–214 (2006)
10.
go back to reference Réka, A., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–94 (2000)MathSciNetMATH Réka, A., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–94 (2000)MathSciNetMATH
11.
go back to reference Sarma J., De Jong, K.: An analysis of the effect of the neighborhood size and shape on local selection algorithms. In: Proceedings of International Conference on Parallel Problem Solving from Nature IV, LNCS 1141, pp. 236–244. Springer (1996) Sarma J., De Jong, K.: An analysis of the effect of the neighborhood size and shape on local selection algorithms. In: Proceedings of International Conference on Parallel Problem Solving from Nature IV, LNCS 1141, pp. 236–244. Springer (1996)
12.
go back to reference Sastry, K.: Evaluation-relaxation schemes for genetic and evolutionary algorithms. M.Sc. thesis, University of Illinois, Urbana, IL, USA (2001) Sastry, K.: Evaluation-relaxation schemes for genetic and evolutionary algorithms. M.Sc. thesis, University of Illinois, Urbana, IL, USA (2001)
13.
go back to reference Tomassini, M.: Spatially Structured Evolutionary Algorithms. Springer, Heidelberg (2005)MATH Tomassini, M.: Spatially Structured Evolutionary Algorithms. Springer, Heidelberg (2005)MATH
14.
go back to reference Whitacre, J.M., Sarker, R.A., Pham, Q.: The self-organization of interaction networks for nature-inspired optimization. IEEE Trans. Evol. Comput. 12, 220–230 (2008)CrossRef Whitacre, J.M., Sarker, R.A., Pham, Q.: The self-organization of interaction networks for nature-inspired optimization. IEEE Trans. Evol. Comput. 12, 220–230 (2008)CrossRef
Metadata
Title
Spatially Structured Evolutionary Algorithms: Graph Degree, Population Size and Convergence Speed
Authors
Carlos M. Fernandes
Juan L. J. Laredo
Agostinho C. Rosa
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-66379-1_2

Premium Partner