Emergent mating topologies in spatially structured genetic algorithms

ABSTRACT

The application of network analysis to emergent mating topologies in spatially structured genetic algorithms is presented in this preliminary study as a framework for inferring evolutionary dynamics in recombinant evolutionary search. Emergent mating topologies of populations evolving on regular, scale-free, and small-world imposed spatial topologies are analyzed. When the population evolves on a scale-free imposed spatial topology, the topology of mating interactions is also found to be scale-free. However, due to the random initial placement of individuals in the spatial topology, the scale-free mating topology lacks correlation between fitness and vertex connectivity, resulting in highly variable convergence rates. Scale-free mating topologies are also shown to emerge on regular imposed spatial topologies under high selection pressure. Since these scale-free emergent mating topologies self-organize such that the most-fit individuals are inherently located in highly connected vertices, such emergent mating topologies are shown to promote rapid convergence on the test problem considered herein. The emergent mating topologies of populations evolving on small-world imposed spatial topologies are not found to possess scale-free or small-world characteristics. However, due to the decrease in the characteristic path length of the emergent mating topology, the rate of population convergence is shown to increase as the imposed spatial topology is tuned from regular to small-world.

REFERENCES

• 1: Alba, E. & Dorronsoro, B. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Transactions on Evolutionary Computation, 9, 2, (2005), 126--142.
• 2: Albert, R., Jeong, H., & Barabáási, A. L. Diameter of the World-Wide Web. Nature, 401 (1999), 130--131.
• 3: Albert, R., Jeong, H., & Barabáási, A. L. Error and attack tolerance of complex networks. Nature, 406 (2000), 378--381.
• 4: Barabási, A. L. & Albert, R. Emergence of scaling in random networks. Science, 286 (1999), 509--512.
• 5: J. P. Cohoon , S. U. Hegde , W. N. Martin , D. Richards, Punctuated equilibria: a parallel genetic algorithm, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.148-154, October 1987, Cambridge, Massachusetts, United States
• 6: Ebel, H., Mielsch, L., & Bornholdt, S. Scale-free topology of e-mail networks. Physical Review E, 66 (2002) 035103(R).
• 7: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 8: Mario Giacobini , Marco Tomassini , Andrea Tettamanzi, Takeover time curves in random and small-world structured populations, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068224]
• 9: V. Scott Gordon , L. Darrell Whitley, Serial and Parallel Genetic Algorithms as Function Optimizers, Proceedings of the 5th International Conference on Genetic Algorithms, p.177-183, June 01, 1993
• 10: Jeong, H., Tombor, H., Albert, R., Oltavi, Z. N., & Barabáási, A. L. The large-scale organization of metabolic networks. Nature, 407 (2000), 651--654.
• 11: Jeong, H., Mason, S. P., Barabási, A. L., & Oltvai, Z. N. Lethality and centrality in protein networks. Nature, 411 (2001), 41--42.
• 12: Kuperman, M., & Abramson, G. Small-world effect in an epidemiological model. Physical Review Letters, 86 (2001), 2909--2912.
• 13: Lieberman, E., Hauert, C., & Nowak, M. A. Evolutionary dynamics on graphs. Nature, 433 (2005), 312--316.
• 14: Liljeros, F., Edling, C. R., Amaral, L. A. N., Stanely, H. E., & ÅÅberg, Y. The web of human sexual contacts. Nature, 411 (2001), 907--908.
• 15: Bernard Manderick , Piet Spiessens, Fine-Grained Parallel Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.428-433, June 01, 1989
• 16: MathWorks. 24 Prime Park Way, Natick MA 01760-1500 (2004).
• 17: Motter, A. E., de Moura, A. P. S., Lai, Y. C., & Dasgupta, P. Topology of the conceptual network of language. Physical Review E, 65 (2002), 065102(R).
• 18: Jayshree Sarma , Kenneth A. De Jong, An Analysis of the Effects of Neighborhood Size and Shape on Local Selection Algorithms, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.236-244, September 22-26, 1996
• 19: Sayama, H., Kaufman, L., & Bar-Yam, Y. Symmetry breaking and coarsening in spatially distributed evolutionary processes including sexual reproduction and disruptive selection. Physical Review E, 62 (2000), 7065--7069.
• 20: Georgos Siganos , Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, Power laws and the AS-level internet topology, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.514-524, August 2003 [doi>10.1109/TNET.2003.815300]
• 21: Stephan, K. E., Hilgetag, C., Burns, G. A. P. C., O'Neill, M. A., Young, M. P., & Köötter, R. Computational analysis of functional connectivity between areas of primate cerebral cortex. Phil. Trans. R. Soc. Lond. B, 355 (2000) 111--126.
• 22: Watts, D. J., & Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature, 393 (1998), 440--442.
• 23: Whitely, D. Cellular genetic algorithms. In Proc. 5th Int. Conf. Genetic Algorithms (Urbana-Champaign, IL, July, 1993). Morgan Kaufman, San Mateo, CA, 1993, 658.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
emergence, genetic algorithms, mating topologies, network