More Web Proxy on the site http://driver.im/

Article

Emergent mating topologies in spatially structured genetic algorithms

Authors:

Joshua L. Payne,

Margaret J. EppsteinAuthors Info & Claims

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Pages 207 - 214

https://doi.org/10.1145/1143997.1144032

Published: 08 July 2006 Publication History

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.

Digital Library

[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]

Cohoon, J. P., Hedge, S. U., Martin, W. N., & Richards, D. S. Punctuated Equilibria: a parallel genetic algorithm. In Proc. 2nd International Conference on Genetic Algorithms (Pittsburgh, PA, 1987). Erlbaum, Hillsdale, N.J., 1987, 148--154.

Digital Library

[6]

Ebel, H., Mielsch, L., & Bornholdt, S. Scale-free topology of e-mail networks. Physical Review E, 66 (2002) 035103(R).

[7]

Eiben, A. E. & Smith, J. E. Introduction to Evolutionary Computing. Springer-Verlag: Berlin (2003).

[8]

Giacobini, M., Tomassini, M., & Tettamanzi, A. Takeover time curves in random and small-world structured populations. In Proc. Genetic and Evolutionary Computation Conference (Washington, D.C., June 25-29, 2005). ACM Press, New York, N.Y., 2005, 1333--1340.

Digital Library

[9]

Gordon, V. & Whitely, D. Serial and parallel genetic algorithms as function optimizers. (Urbana-Champaign, IL, July, 1993). Morgan Kaufman, San Mateo, CA, 1993, 177--183.

Digital Library

[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]

Manderick, B. & Spiessens, P. Fine-grained parallel genetic algorithms. In Proc. 3rd Int. Conf. on Genetic Algorithms (Fairfax, VA, June 1989). Morgan Kaufman, San Mateo, CA, 1989, 428--433.

Digital Library

[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]

Sarma, J., & De Jong, K. An analysis of the effect of neighborhood size and shape on local selection algorithms. In Proc. Int. Conf. Parallel Prob. Solving from Nature IV (Berlin, German, September 22 - 26, 1996). Springer-Verlag, Berlin, Germany, 1996, 236--244.

Digital Library

[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]

Siganos, G, Faloutsos, M., Faloutsos, P., & Faloutsos, C. Power laws and the AS-level internet topology. IEEE/ACM Transactions on Networking, 11, 4 (2003), 514--524.

Digital Library

[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.

Cited By

Burguillo JDorronsoro BBurguillo J(2017)Optimization Models with Coalitional Cellular AutomataSelf-organizing Coalitions for Managing Complexity10.1007/978-3-319-69898-4_8(139-169)Online publication date: 14-Dec-2017
https://doi.org/10.1007/978-3-319-69898-4_8
Fernandes CLaredo JRosa A(2017)Spatially Structured Evolutionary Algorithms: Graph Degree, Population Size and Convergence SpeedIntelligent Distributed Computing XI10.1007/978-3-319-66379-1_2(15-25)Online publication date: 5-Oct-2017
https://doi.org/10.1007/978-3-319-66379-1_2
Fernandes CLaredo JMerelo JCotta CRosa A(2014)Dynamic and Partially Connected Ring Topologies for Evolutionary Algorithms with Structured PopulationsApplications of Evolutionary Computation10.1007/978-3-662-45523-4_54(665-677)Online publication date: 29-Nov-2014
https://doi.org/10.1007/978-3-662-45523-4_54
Show More Cited By

Index Terms

Emergent mating topologies in spatially structured genetic algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Self-adjusting the intensity of assortative mating in genetic algorithms

Mate selection plays a crucial role in both natural and artificial systems. While traditional Evolutionary Algorithms (EA) usually engage in random mating strategies, that is, mating chance is independent of genotypic or phenotypic distance between ...
A novel mating approach for genetic algorithms

Genetic algorithms typically use crossover, which relies on mating a set of selected parents. As part of crossover, random mating is often carried out. A novel approach to parent mating is presented in this work. Our novel approach can be applied in ...
An improved class of real-coded Genetic Algorithms for numerical optimization

Over the last few decades, many improved Evolutionary Algorithms (EAs) have been proposed to tackle different types of optimization problems. Genetic Algorithm (GA) among other canonical algorithms have not shown consistent performance over a range of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

July 2006

2004 pages

ISBN:1595931864

DOI:10.1145/1143997

General Chair:
Mike Cattolico
Tiger Mountain Scientific, Inc., USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO06

Sponsor:

GECCO06: Genetic and Evolutionary Computation Conference

July 8 - 12, 2006

Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
15
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Burguillo JDorronsoro BBurguillo J(2017)Optimization Models with Coalitional Cellular AutomataSelf-organizing Coalitions for Managing Complexity10.1007/978-3-319-69898-4_8(139-169)Online publication date: 14-Dec-2017
https://doi.org/10.1007/978-3-319-69898-4_8
Fernandes CLaredo JRosa A(2017)Spatially Structured Evolutionary Algorithms: Graph Degree, Population Size and Convergence SpeedIntelligent Distributed Computing XI10.1007/978-3-319-66379-1_2(15-25)Online publication date: 5-Oct-2017
https://doi.org/10.1007/978-3-319-66379-1_2
Fernandes CLaredo JMerelo JCotta CRosa A(2014)Dynamic and Partially Connected Ring Topologies for Evolutionary Algorithms with Structured PopulationsApplications of Evolutionary Computation10.1007/978-3-662-45523-4_54(665-677)Online publication date: 29-Nov-2014
https://doi.org/10.1007/978-3-662-45523-4_54
Fatima IFahim MLee YLee S(2013)MODMThe Journal of Supercomputing10.1007/s11227-013-0947-266:2(738-759)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1007/s11227-013-0947-2
Dorronsoro BBurguillo JPeleteiro ABouvry P(2013)Evolutionary Algorithms Based on Game Theory and Cellular Automata with CoalitionsHandbook of Optimization10.1007/978-3-642-30504-7_19(481-503)Online publication date: 2013
https://doi.org/10.1007/978-3-642-30504-7_19
Fernandes CLaredo JMerelo JCotta CRosa A(2012)Towards a 2-dimensional self-organized framework for structured population-based metaheuristics2012 IEEE International Conference on Complex Systems (ICCS)10.1109/ICoCS.2012.6458516(1-6)Online publication date: Nov-2012
https://doi.org/10.1109/ICoCS.2012.6458516
Dorronsoro BBouvry P(2012)Study of different small-world topology generation mechanisms for Genetic Algorithms2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6256543(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6256543
Dorronsoro BBouvry P(2011)Improving Classical and Decentralized Differential Evolution With New Mutation Operator and Population TopologiesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.208136915:1(67-98)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1109/TEVC.2010.2081369
Cebrian MLahiri MOliver NPentland A(2010)Measuring the Collective Potential of Populations From Dynamic Social Interaction DataIEEE Journal of Selected Topics in Signal Processing10.1109/JSTSP.2010.20530934:4(677-686)Online publication date: Aug-2010
https://doi.org/10.1109/JSTSP.2010.2053093
Echegoyen CMendiburu ASantana RLozano J(2010)Estimation of Bayesian networks algorithms in a class of complex networksIEEE Congress on Evolutionary Computation10.1109/CEC.2010.5586511(1-8)Online publication date: Jul-2010
https://doi.org/10.1109/CEC.2010.5586511
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents