Katharina A. Lehmann
ABSTRACT
While the evolution of biological networks can be modeled sensefully as a series of mutation and selection, evolution of other networks such as the social network in a city or the network of streets in a country is not determined by selection since there is no alternative network with which these singular networks have to compete. Nonetheless, these singular networks do evolve due to dynamic changes of vertices and edges. In this article we present a formal, analyzable framework for the evolution of singular networks. We show that the careful design of adaptation rules can lead to the emergence of network topologies with satisfying performance in polynomial time while other adaptation rules yield exponential runtime. We further show by example how the framework could be applied to some ad-hoc communication scenarios.
- G. Box. Evolutionary operation: a method for increasing industrial productivity. Appl. Stat., 6(2):81--101, 1957.Google Scholar
Cross Ref
- P. Bremaud. Markov Chains - Gibbs Field, Monte Carlo Simulation, and Queues. Springer Verlag, 1st edition, 1999.Google Scholar
- A. Grama, G. Karypis, V. Kumar, and A. Gupta. An Introduction to Parallel Computing. Addison Wesley, 2nd edition, 2003.Google Scholar
- J. Holland. Adaptation in natural and artificial systems. Ann Arbor: The University of Michigan Press, 1975. Google ScholarDigital Library
- H. Jeong, B. Tombor, R. Albert, Z. Oltvai, and A.-L. Barabási. The large-scale organization of metabolic networks. Nature, 407:651--654, 2000.Google ScholarCross Ref
- F. Kuhn, T. Moscibroda, and R. Wattenhofer. Unit disk graph approximation. In Proc. DIALM-POMC 2004, 2004. Google ScholarDigital Library
- K. Lehmann. Why simulating evolutionary processes is just as interesting as applying them. In Proc. GECCO 2005, 2005. Google ScholarDigital Library
- S. Milgram. The small world problem. Psychology Today, 1:61--67, 1967.Google Scholar
- M. Mitchell. An introduction to genetic algorithms. The MIT Press, 1996. Google ScholarDigital Library
- I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzoog, 1973.Google Scholar
- J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modeling and Algorithms, 4(3):349--366, 2004.Google ScholarCross Ref
- A. Vázquez, A. Flammini, A. Maritan, and A. Vespignani. Modeling of protein interaction networks. Complexus, 1(1):38--44, 2003.Google ScholarCross Ref
- D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, June 1998.Google ScholarCross Ref
- C. Witt. An analysis of the (μ+1) EA on simple pseudo-boolean functions. In Genetic and Evolutionary Computation - GECCO 2004, number 3103 in LNCS, pages 761--773. Springer, 2004.Google Scholar
Index Terms
- Evolutionary algorithms for the self-organized evolution of networks
Recommendations
Stability in the Self-Organized Evolution of Networks
The modeling and analysis of large networks of autonomous agents is an important topic with applications in many different disciplines. One way of modeling the development of such networks is by means of an evolutionary process. The autonomous and ...
Neuroevolution of Controllers for Self-Organizing Mobile Ad Hoc Networks
SASO '11: Proceedings of the 2011 IEEE Fifth International Conference on Self-Adaptive and Self-Organizing SystemsThis paper describes a study in the use of neuroevolution to discover controllers for a simulated mobile ad hoc network. Neuroevolution is a technique whereby an evolutionary algorithm is used to produce artificial neural networks that solve a user-...
Stability in the self-organized evolution of networks
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computationThe modeling and analysis of large networks of autonomous agents is an important topic with applications in many different disciplines. One way of modeling the development of such networks is by means of an evolutionary process. The autonomous agents ...
Comments