Representation, Graph Evolution, and the Induction of Desired Behaviours

Date

2015-07-07

Authors

Barlow, LeeAnn

Journal Title

Journal ISSN

Volume Title

Publisher

University of Guelph

Abstract

Networks and combinatorial graphs are commonly used in a wide variety of types of mathematical modelling to represent structures such as contact networks in epidemiology, road networks in urban planning, and scheduling conflicts. Many of these models also use games – such as Iterated Prisoner’s Dilemma (IPD) – played such that the graph limits interaction to those who are connected by the graph to simulate more realistic social interactions. In this dissertation, we examine the novel problem of graph evolution and develop many foundational aspects that, to date, have not been explored. To effectively evolve graphs, we first develop four new graph representations, including one that generalizes all previous effective representations, called toggle-add-delete-swap (TADS). We also introduce four new benchmark functions on which to test the various representations. One of the primary goals of our graph evolution is to determine the specific graph parameters that affect the emergence of cooperation in populations playing IPD on a graph. We find that edge density is primarily responsible but that for any given edge density, it is possible to generate graphs that promote higher or lower levels of cooperation – particularly for lower edge densities. A number of potential applications for this research are suggested, including its use in designing office layouts to promote cooperation in the workplace.

Description

Keywords

evolutionary computation, graph evolution, networks, Iterated Prisoner's Dilemma, graph-based evolutionary computation

Citation