Luerssen, M: Experimental Investigations into Graph Grammar

Artificial and natural instances of networks are ubiquitous, and the problem of determining the optimal topology of a network is of practical value to many domains. Evolutionary algorithms constitute a well-established optimisation method, but they scale poorly if applied to the combinatorial explosion of possible network topologies. Generative representation schemes aim to overcome this problem by facilitating the discovery and reuse of dependencies and allowing for adaptable exploration strategies. This book seeks to define a simple yet universally applicable and scalable method for evolving graphs and networks. A number of contributions are made in this regard. We establish the notion of directly evolving a graph grammar from which a population of networks can be derived. Compact cellular productions that form a hypergraph grammar are optimised by a novel multi-objective evolutionary system. A series of empirical investigations are then carried out to gain a better understanding of graph grammar evolution.