Projects per year
Abstract
Studying coevolutionary systems in the context of simplified models (i.e. games
with pairwise interactions between coevolving solutions modelled as self plays) remains an open challenge since the rich underlying structures associated with pairwisecomparisonbased fitness measures are often not taken fully into account. Although cyclic dynamics have been demonstrated in several contexts (such as intransitivity in coevolutionary problems), there is no complete characterization of cycle structures and their effects on coevolutionary search. We develop a new framework to address this issue. At the core of our approach is the directed graph (digraph) representation of coevolutionary problem that fully captures structures in the relations between candidate solutions. Coevolutionary processes are modelled as a specific type of Markov chains  random walks on digraphs. Using this framework, we show that coevolutionary problems admit a qualitative characterization: a coevolutionary problem is
either solvable (there is a subset of solutions that dominates the remaining candidate solutions) or not. This has an implication on coevolutionary search. We further develop our framework that provide the means to construct quantitative tools for analysis of coevolutionary processes and demonstrate their applications through case studies. We show that coevolution of solvable problems corresponds to an absorbing Markov chain for which we can compute the expected hitting time of the absorbing class. Otherwise, coevolution will cycle indefinitely and the quantity of interest will be the limiting invariant distribution of the Markov chain. We also provide an index for characterizing complexity in coevolutionary problems and show how they can be generated in a controlled manner.
with pairwise interactions between coevolving solutions modelled as self plays) remains an open challenge since the rich underlying structures associated with pairwisecomparisonbased fitness measures are often not taken fully into account. Although cyclic dynamics have been demonstrated in several contexts (such as intransitivity in coevolutionary problems), there is no complete characterization of cycle structures and their effects on coevolutionary search. We develop a new framework to address this issue. At the core of our approach is the directed graph (digraph) representation of coevolutionary problem that fully captures structures in the relations between candidate solutions. Coevolutionary processes are modelled as a specific type of Markov chains  random walks on digraphs. Using this framework, we show that coevolutionary problems admit a qualitative characterization: a coevolutionary problem is
either solvable (there is a subset of solutions that dominates the remaining candidate solutions) or not. This has an implication on coevolutionary search. We further develop our framework that provide the means to construct quantitative tools for analysis of coevolutionary processes and demonstrate their applications through case studies. We show that coevolution of solvable problems corresponds to an absorbing Markov chain for which we can compute the expected hitting time of the absorbing class. Otherwise, coevolution will cycle indefinitely and the quantity of interest will be the limiting invariant distribution of the Markov chain. We also provide an index for characterizing complexity in coevolutionary problems and show how they can be generated in a controlled manner.
Original language  English 

Number of pages  33 
Journal  Evolutionary Computation 
Early online date  20 Nov 2017 
DOIs  
Publication status  Epub ahead of print  20 Nov 2017 
Keywords
 Coevolution
 Directed graphs
 Markov chains
 Evolutionary Computation
 Self play
Fingerprint
Dive into the research topics of 'A New Framework for Analysis of Coevolutionary Systems  Directed Graph Representation and Random Walks'. Together they form a unique fingerprint.Projects
 1 Finished

Personalised Medicine through Learning in the Model Space
Engineering & Physical Science Research Council
1/10/13 → 31/03/17
Project: Research Councils