Using novelty-biased GA to sample diversity in graphs satisfying constraints

Overbury, Peter and Berthouze, Luc (2015) Using novelty-biased GA to sample diversity in graphs satisfying constraints. In: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM, New York, NY, pp. 1445-1446. ISBN 9781450334884

[img] PDF - Accepted Version
Download (1MB)

Abstract

The structure of the network underlying many complex systems, whether artificial or natural, plays a significant role in how these systems operate. As a result, much emphasis has been placed on accurately describing networks using network theoretic metrics. When it comes to generating networks with similar properties, however, the set of available techniques and properties that can be controlled for remains limited. Further, whilst it is becoming clear that some of the metrics currently used to control the generation of such networks are not very prescriptive so that networks could potentially exhibit very different higher-order structure within those constraints, network generating algorithms typically produce fairly contrived networks and lack mechanisms by which to systematically explore the space of network solutions. In this paper, we explore the potential of a multi-objective novelty-biased GA to provide a viable alternative to these algorithms. We believe our results provide the first proof of principle that (i) it is possible to use GAs to generate graphs satisfying set levels of key classical graph theoretic properties and (ii) it is possible to generate diverse solutions within these constraints. The paper is only a preliminary step, however, and we identify key avenues for further development.

Item Type: Book Section
Keywords: Network generation; degree distribution; clustering; higher- order structure; novelty search; graph diversity; coevolution- ary dynamic; multi-objective optimisation
Schools and Departments: School of Engineering and Informatics > Informatics
Subjects: Q Science > QA Mathematics > QA0075 Electronic computers. Computer science
Depositing User: Peter Overbury
Date Deposited: 30 Mar 2016 12:37
Last Modified: 08 Aug 2017 13:10
URI: http://sro.sussex.ac.uk/id/eprint/60159

View download statistics for this item

📧 Request an update