Nothing Special   »   [go: up one dir, main page]

Skip to main content

Effects of Scale-Free and Small-World Topologies on Binary Coded Self-adaptive CEA

  • Conference paper
Evolutionary Computation in Combinatorial Optimization (EvoCOP 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3906))

Abstract

In this paper we investigate the properties of CEAs with populations structured as Watts–Strogatz small-world graphs and Albert–Barabási scale-free graphs as problem solvers, using several standard discrete optimization problems as a benchmark. The EA variants employed include self-adaptation of mutation rates. Results are compared with the corresponding classical panmictic EA showing that topology together with self-adaptation drastically influences the search.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Lehmann, E., D’Abrera, H.: Nonparametrics: Statistical Methods Based on Ranks. Prentice-Hall, Englewood Cliffs (1998)

    MATH  Google Scholar 

  2. Tomassini, M.: Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time. Springer, New York (2005)

    MATH  Google Scholar 

  3. Albert, R., Barabasi, A.-L.: Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47–97 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  4. Newman, M.E.J.: The structure and function of complex networks. SIAM Review 45, 167–256 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  5. Giacobini, M., Tomassini, M., Tettamanzi, A.: Takeover time curves in random and small-world structured populations. In: Beyer, H.-G., et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2005, pp. 1333–1340. ACM Press, New York (2005)

    Chapter  Google Scholar 

  6. Preuß, M., Lasarczyk, C.W.G.: On the importance of information speed in structured populations. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 91–100. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  7. Bäck, T.: Self-adaptation in genetic algorithms. In: Varela, F.J., Bourgine, P. (eds.) Toward a Practice of Autonomous Systems – Proc. First European Conf. Artificial Life (ECAL 1991), pp. 263–271. MIT Press, Cambridge (1992)

    Google Scholar 

  8. Beyer, H.-G., Schwefel, H.-P.: Evolution strategies: A comprehensive introduction. Natural Computing 1(1), 3–52 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. Whitley, D., Rana, S., Dzubera, J., Mathias, K.E.: Evaluating evolutionary algorithms. Artif. Intelligence 85, 245–276 (1997)

    Article  Google Scholar 

  10. Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1(1), 67–82 (1997)

    Article  Google Scholar 

  11. Goldberg, D.E., Deb, K., Horn, J.: Massively multimodality, deception and genetic algorithms. In: Männer, R., Manderick, B. (eds.) Parallel Prob. Solving from Nature II, pp. 37–46. North-Holland, Amsterdam (1992)

    Google Scholar 

  12. De Jong, K.A., Potter, M.A., Spears, W.M.: Using problem generators to explore the effects of epistasis. In: Bäck, T. (ed.) Proceedings of the Seventh ICGA, pp. 338–345. Morgan Kaufmann, San Francisco (1997)

    Google Scholar 

  13. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977)

    MATH  Google Scholar 

  14. Chen, H., Flann, N.S., Watson, D.W.: Parallel genetic simulated annealing: A massively parallel SIMD algorithm. IEEE Transactions on Parallel and Distributed Systems 9(2), 126–136 (1998)

    Article  Google Scholar 

  15. Droste, S., Jansen, T., Wegener, I.: A natural and simple function which is hard for all evolutionary algorithms. In: IEEE International Conference on Industrial Electronics, Control, and Instrumentation (IECON 2000), pp. 2704–2709. IEEE Press, Piscataway, NJ (2000)

    Google Scholar 

  16. Watts, D.J., Strogatz, S.H.: Collective dynamics of ’small-world’ networks. Nature 393, 440–442 (1998)

    Article  MATH  Google Scholar 

  17. Bartz-Beielstein, T.: New Experimentalism Applied to Evolutionary Computation. PhD thesis, University of Dortmund (April 2005)

    Google Scholar 

  18. Dorronsoro, B., Alba, E., Giacobini, M., Tomassini, M.: The influence of grid shape and asynchronicity on cellular evolutionary algorithms. In: 2004 Congress on Evolutionary Computation (CEC 2004), pp. 2152–2158. IEEE Press, Piscataway (2004)

    Google Scholar 

  19. Rudolph, G.: An evolutionary algorithm for integer programming. In: Davidor, Y., Männer, R., Schwefel, H.-P. (eds.) PPSN 1994. LNCS, vol. 866, pp. 139–148. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Giacobini, M., Preuss, M., Tomassini, M. (2006). Effects of Scale-Free and Small-World Topologies on Binary Coded Self-adaptive CEA. In: Gottlieb, J., Raidl, G.R. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2006. Lecture Notes in Computer Science, vol 3906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11730095_8

Download citation

  • DOI: https://doi.org/10.1007/11730095_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-33178-0

  • Online ISBN: 978-3-540-33179-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics