Graph Transformation and Evolutionary Computation
Lead Research Organisation:
University of York
Department Name: Computer Science
Abstract
This research project will explore the potential of Graph Transformation as a novel approach to Evolutionary Computation in two major areas; evolution of imperative code and neuroevolution. In addition, a theory of Evolutionary Graph Programming will be developed, opening up a new sub-field of both Graph Programming and Evolutionary Computation with a wide range of applications. One impact of this project will be the extension of Evolutionary Computation with new and powerful rule-based techniques. Also, this project will provide an unexplored approach to optimization and 'black box' problem solving in graph programming.
Organisations
People |
ORCID iD |
| Timothy Atkinson (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509802/1 | 01/10/2016 | 31/03/2022 | |||
| 1789003 | Studentship | EP/N509802/1 | 01/10/2016 | 30/09/2019 | Timothy Atkinson |
| Description | Our first major development was the creation of the Probabilistic Graph Programming Language, P-GP 2, which is an extension of the existing language GP 2. This facilitates the implementation of probabilistic graph programs, which can be used to design algorithmic probabilistic manipulations of graphs (networks of nodes and connections). The main application of this, in the context of this award, is the design of mutation operators over graphs for evolutionary algorithms. However, a number of other potential applications exist, namely graph algorithms which give approximate solutions to hard graph problems. Our second development was the creation of the evolutionary algorithm Evolving Graphs by Graph Programming (EGGP). EGGP learns graphs by modifying (mutating) them and evaluating them against some measure of quality. By repeatedly applying this concept, we induce an evolutionary process which tends towards high quality solutions. Empirically, EGGP has been shown to outperform other evolutionary approaches for various digital circuit and functional program synthesis problems. EGGP's mutation operators are implemented using P-GP 2 (described above). In its published form, EGGP is a general evolutionary algorithm for finding acyclic graphs to suit a given domain and fitness function. We have since extended EGGP to facilitate new concepts unvisited by other research in evolutionary algorithms. For example, we have identified the potential to inject domain knowledge into an evolutionary process through a process we call 'Semantic Neutral Drift' (SND). SND allows the application of semantics preserving mutations to evolved graphs, changing their structure while preserving their fitness. This has empirically been shown to aid performance when searching for digital circuits. The main contribution of this line of work is the ability for other researchers to easily inject their own domain knowledge into our developed evolutionary algorithm to yield better performance in their given domain. This is an unusual and useful feature rarely seen in evolutionary algorithms. We have also investigated a new form of recombination for graphs, named 'Horizontal Gene Transfer' (inspired by the biological version), which can be used to significantly improve the performance of EGGP. We have demonstrated the usefulness of Horizontal Gene Transfer for both program synthesis and neural network training tasks. Together, these contributions amount to one of the impacts highlighted in the award abstract; the creation of evolutionary algorithms through graph programming. |
| Exploitation Route | Our evolutionary approach, EGGP, can be applied to a number of domains. Although so far we have focused on evolving digital circuits and functional programs, the approach can in principle be applied to a number of problems in computer science. For example, it could be applied to the evolution of bayesian networks, neural network topologies and quantum circuits. We expect that others would be able to apply EGGP to other domains to find effective topologies for solving difficult problems. The potential domains described have a number of potential applications external to computer science; for example, bayesian networks and artificial neural networks are used to solve machine learning problems in medicine, manufacturing and energy. |
| Sectors | Digital/Communication/Information Technologies (including Software),Electronics,Energy,Healthcare,Manufacturing, including Industrial Biotechology |