Evolutionary dynamics on multiple scales: a quantitative analysis of the interplay between genotype, phenotype, and fitness in linear genetic programming

Abstract

Redundancy is a ubiquitous feature of genetic programming (GP), with many-to-one mappings commonly observed between genotype and phenotype, and between phenotype and fitness. If a representation is redundant, then neutral mutations are possible. A mutation is phenotypically-neutral if its application to a genotype does not lead to a change in phenotype. A mutation is fitness-neutral if its application to a genotype does not lead to a change in fitness. Whether such neutrality has any benefit for GP remains a contentious topic, with reported experimental results supporting both sides of the debate. Most existing studies use performance statistics, such as success rate or search efficiency, to investigate the utility of neutrality in GP. Here, we take a different tack and use a measure of robustness to quantify the neutrality associated with each genotype, phenotype, and fitness value. We argue that understanding the influence of neutrality on GP requires an understanding of the distributions of robustness at these three levels, and of the interplay between robustness, evolvability, and accessibility amongst genotypes, phenotypes, and fitness values. As a concrete example, we consider a simple linear genetic programming system that is amenable to exhaustive enumeration and allows for the full characterization of these quantities, which we then relate to the dynamical properties of simple mutation-based evolutionary processes. Our results demonstrate that it is not only the distribution of robustness amongst phenotypes that affects evolutionary search, but also (1) the distributions of robustness at the genotypic and fitness levels and (2) the mutational biases that exist amongst genotypes, phenotypes, and fitness values. Of crucial importance is the relationship between the robustness of a genotype and its mutational bias toward other phenotypes.

Appendices

Appendices

In the appendix, we lay out the details of our analytical treatment, which is based on the techniques described in [3, 17]. Both texts provide exceptionally lucid expositions of absorbing Markov chains and their applications.

1.1 Appendix 1: Markov chains to determine the mean first passage time

The mean waiting time and mean adaptation time can be obtained analytically with absorbing Markov chains [17], using the stochastic transition matrix P whose elements

$$ p_{x^{\rm p}y^{\rm p}} = \left\{\begin{array}{ll}\frac{| \Upomega^{x^{\rm p},y^{\rm p}} |} {|\Uptheta^{x^{\rm p}}|+\sum_{z\ne y}| \Upomega^{x^{\rm p},z^{\rm p}} |}, & \hbox{if}\,x^{\rm p} \ne y^{\rm p} \\ \frac{|\Uptheta^{x^{\rm p}}|} {|\Uptheta^{x^{\rm p}}|+\sum_{z\ne y}| \Upomega^{x^{\rm p},z^{\rm p}} |}, & \hbox{if}\,x^{\rm p} = y^{\rm p} \end{array}\right. $$

(15)

denote the probability of a transition from phenotype x ^p to phenotype y ^p.

The target phenotype t ^p is the absorbing state of the Markov chain; all other phenotypes are transient. The row corresponding to phenotype t ^p is therefore modified such that $p_{t^{\rm p}t^{\rm p}} = 1$ and $p_{t^{\rm p}x^{\rm p}} = 0 \forall x^{\rm p}\ne t^{\rm p}$. Placing P in canonical form, we have

$$ {\bf P} = \left(\begin{array}{llll} p_{11}& p_{12}& \ldots & p_{1t^{\rm p}} \\ p_{21} & p_{22} & \ldots & p_{2t^{\rm p}} \\ \vdots & \vdots & \ddots & \vdots \\ p_{t^{\rm p}1} & p_{t^{\rm p}2} & \ldots & p_{t^{\rm p}t^{\rm p}} \end{array}\right) = \left(\begin{array}{llll} p_{11} & p_{12} & \ldots & p_{1t^{\rm p}} \\ p_{21} & p_{22} & \ldots & p_{2t^{\rm p}} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{array}\right) = \left(\begin{array}{ll} {\bf Q} & {\bf R} \\ \hline {\bf 0} & 1 \end{array}\right), $$

(16)

where Q is a $(|\Upphi^{\rm p}|-1)\times (|\Upphi^{\rm p}|-1)$ matrix, R is a $(|\Upphi^{\rm p}|-1)\times 1$ column vector, and 0 is a $1\times (|\Upphi^{\rm p}|-1)$ row vector. To obtain the mean waiting time, we use Q to calculate the fundamental matrix

$$ {\bf N}=({\bf I}-{\bf Q)^{-1}}, $$

(17)

where I is the identity matrix and entry $n_{x^{\rm p}y^{\rm p}}$ is the expected time spent in transient phenotype x ^p, given that the random walk started in the transient phenotype y ^p. The fundamental matrix is then used to calculate

$$ {\bf \tau}={\bf N}{\bf e}, $$

(18)

where e is a column vector of ones and $\tau_{x^{\rm p}}$ is the mean waiting time to reach phenotype t ^p from phenotype x ^p.

1.2 Appendix 2: Markov chains to determine the most common path

Absorbing Markov chains can also be used to determine the most common path from a transient phenotype s ^p to a target phenotype t ^p. Since the most common path must visit each phenotype at most once, the length of the path must be less than or equal to the total number of phenotypes $|\Upphi^{\rm p}|$. Every path has an associated probability, which can be calculated using the entries of the transition matrix P. For example, the path $s^{\rm p}\rightarrow x^{\rm p}\rightarrow y^{\rm p} \rightarrow t^{\rm p}$ has probability $p_{s^{\rm p}x^{\rm p}} p_{x^{\rm p}y^{\rm p}} p_{y^{\rm p}t^{\rm p}}$. The most common path is the one with the highest such joint probability, which can be determined efficiently using the message passing approach described in [3].