\chapter{Evolving Cellular Information Processing Networks}
\label{evolvingACSNs}
In the previous chapter we reviewed several computational techniques for modelling chemical reaction networks. We identified agent-based approaches as suitable methods to model, analyse and simulate Cellular Information Processing Networks (CIPNs) according to the requirements of our project. Following on from this, we now present a literature review which focuses on the evolution of CIPNs \textit{in silico}. 
This review is composed of two main parts. We first examine Evolutionary Computation (EC) techniques applied to the artificial evolution of reaction networks. Secondly we present Artificial Chemistry based approaches which address the emergence and evolution of collectively autocatalytic (organisationally closed) reaction networks.

This chapter is tightly coupled with Chapter \ref{modellingCSNs} as the evolutionary methods presented here rely on modelling frameworks presented earlier. Based on both examinations conducted in the previous and current chapter, we intend to identify an adequate evolutionary simulation framework to examine closure and the evolution of artificial CIPNs. 


\section{Introduction}
At present no previous work \textit{directly} related to closure and the evolution of CIPNs has been reported in the literature. Nevertheless we distinguish two related fields of study: Evolutionary Computation (EC) \citep{fogel2007iec} and Artificial Chemistry (AC) based studies \citep{dittrich-articial}. Both EC and AC models address complementary aspects of our research: 

\begin{itemize}
	\item \textit{The EC approach}: Several investigations have been conducted on the evolution of artificial biochemical networks capable of performing computational tasks. This area of research focuses on the development of novel computational paradigms. EC techniques (e.g., Genetic Algorithms, Genetic Programming) are commonly utilised to evolve models of simplified reaction networks. The objective fitness function of these approaches is typically to mirror a computational function. Within a given reaction network, distinct arbitrary molecular species are designated as input and output signals. Properties of the reaction network (e.g., topology, kinetic rates, etc.) are subjected to mutations which ultimately affect the signal-processing and response level of output signal(s). Here the reaction network's computational function is modelled as a traditional information processing system involving an input-process-output relationship. The \textit{explicit} definition of the fitness function directs the evolutionary process of the system, which we regard as a top-down evolutionary approach. No EC-based approaches have addressed closure properties in reaction networks nor the ``cellular'' nature of CIPNs: These investigations aim at evolving reaction networks without any consideration about the container/reactor space. 

	\item \textit{The AC approach}: Another distinctive approach to the evolution of biochemical networks is addressed through the use of Artificial Chemistries (ACs). In contrast to the computation-oriented EC approaches, AC-based research focuses on the self-organisation, emergence and evolution of molecular organisations. ACs are an abstraction of chemical organisations which attempt to understand and engineer the conditions for life (as it could be) and open-ended evolutionary growth of complexity. No explicit fitness function is devised in ACs, the system's dynamics are driven by the intrinsic properties of the molecular species (e.g., enzymatic function, binding specificity). These properties may provide the system with the ability to self-sustain/maintain. These abilities are the \textit{implicit} fitness function driving an AC's (evolutionary) dynamics. Moreover, typical ACs aim at evolving minimalist molecular organisations towards networks of higher complexity where novel phenomena may occur at the system level. We thus regard ACs as a bottom-up evolutionary approach. Limited AC-based researches \citep{1268671} have been conducted towards implementing molecular computing devices compared to the EC counterpart. The computational function of ACs is modelled as a perturbation of the closed system's dynamics, without any designated input/output signals. Nevertheless, ACs have intensively focused on organisational closure, which according to our hypothesis, may be a property of CIPNs.	
\end{itemize}

We present a selection of evolutionary systems which illustrate both top-down and bottom-up approaches.

\section{Evolutionary Computation}
Evolutionary Computation techniques are non-deterministic search algorithms inspired by neo-Darwinian principles. Within the EC field, three major families of computational techniques may be identified: Genetic Algorithms (GA, \citealt{holland1992ana}), Genetic Programming (GP, \citealt{cramer1985rag}) and Evolution Strategy (ES, \citealt{rechenberg1973eot}). These techniques differ on the specification and implementation of common system properties: representation, recombination, mutation and selection. These methods have been successfully applied to a wide range of optimisation problems. Such techniques have been combined and employed in evolutionary systems applied to the evolution of biochemical networks \textit{in silico}. We review a selection of three distinct EC-based systems.
	
	\subsection{Bray and Lay}
\cite{bray1994cse} proposed the first significant investigation on evolving reaction networks through EC. A simple computational and idealised signalling pathway model (Fig. \ref{fig:bray}) was proposed to investigate the evolution of biomolecular receptors found in real cells. This model includes two cellular receptors $R_1$ and $R_2$, an extracellular ligand $L$ (the input signal), an intracellular target molecular species $T$ and a phosphorylated target species $Tp$ (the output signal). 

\begin{figure}[htbp]
	\centering
		\includegraphics[scale=1.1]{chapter3/bray.eps}
	\caption{Artificial signalling pathway model adapted from \cite{bray1994cse}.}
	\label{fig:bray}
\end{figure}

Seven chemical reactions could occur between these molecular species and are governed by mass-action kinetics:
\begin{eqnarray}
R_1 + L & \Leftrightarrow &  R_1L\\
R_1L + T & \Leftrightarrow & R_1LT\\
R_1LT & \Rightarrow & R_1L + Tp\\
R_2 + L & \Leftrightarrow & R_2L\\
R_2L + T & \Leftrightarrow & R_2LT\\
R_2LT & \Rightarrow &  R_2L + Tp	\\
Tp & \Rightarrow &  T
\end{eqnarray}

The model was trained to exhibit a specified response to pulses of stimulus species $L$. The topology of the reaction network was fixed, i.e., no creation or removal of reactions could occur. An ES approach was employed in which mutations were applied upon the seven variable reaction rates. This mutation operator was utilised to generate offspring of the unique, initial seed reaction network (where initial reaction rates are equal and set arbitrarily). Selection was conducted as follows: 

\begin{itemize}
	\item The numerical integration of the differential equations (i.e., the network's genotype) generated from the above reactions was carried-out. 
  \item The results of this integration (i.e., the network's phenotype) provided the time course and concentration level of output signal. This information was used to determine the network's fitness value. 
  \item The fittest offspring network (i.e., which best exhibited the specified and desired behaviour) was selected	and used for the next iterative generation.
\end{itemize}

Using the above ES algorithm, Bray and Lay successfully trained this model to exhibit a specified response, see Fig. \ref{fig:brayResponse} .

\begin{figure}[htbp]
	\centering
		\includegraphics[scale=0.7]{chapter3/brayResponse.eps}
	\caption{Results of an example simulation, taken from \cite{bray1994cse}, in which the network was trained to exhibit a specified time course and concentration level of $Tp$ (this target response is here represented by the shaded gray area). Each individual curve depicts the concentration of $Tp$ produced in response to a squarewave pulse of stimulus $L$, applied for 40 seconds. The response of the network evolved from a square wave pulse that matches the stimulus level, to one that remains elevated for a longer period after the stimulus was applied, thus matching the pre-specified target response. This evolved reaction network behaves as an ``ON switch''.}
	\label{fig:brayResponse}
\end{figure}

In this approach, mutation and structural effects were limited, only the kinetic parameters were subjected to variations. The evolutionary process led to the adaptation of the given model to mirror a specified behaviour. Bray and Lay demonstrated that under an evolutionary regime, it was possible to evolve an artificial reaction network to perform a simple computational task (i.e., a switch). However it was also reported that the current model could not be evolved to perform other computational functions such as a sigmoidal or first derivative function. Following this work, \cite{bray1995pmc} later discussed the analogy of molecular species as computational units occurring in living cells. 
Such \textit{in-silico} evolutionary experiments, aiming at realising computational functions in chemical networks, have to date not been reported to be conducted/validated in wet lab conditions.

	\subsection{Lakhesis}
The computational capabilities of Bray and Lay's approach were limited with regards to performing mathematical operations. However this work was extended and involved more elaborated EC techniques. \cite{citeulike:96164} proposed the Lakhesis system as a modelling and evolutionary simulation platform. The motivation to this work was to investigate computational properties and capabilities of biochemical reaction networks. 
	
Similarly to Bray and Lay's system, chemical reactions are governed by mass-action kinetics and are modelled as differential equations. Input and output molecular species were identified and fixed within reaction networks modelled with Lakhesis.

However, a number of EC related specifications differ between Lakhesis and Bray and Lay's system:
\begin{itemize}
	\item The initial population contains a multitude of randomly generated reaction networks (where the initial number of molecular species and associated reactions are set at random). In each of these networks, input and output signal(s) are designated and fixed.
	\item The number of molecular species $n$ may vary throughout the initial reaction networks. However within a given reaction network, this number is fixed and may not vary through mutational changes.
	\item The number of chemical reactions $r$ within a reaction network is subjected to variation. However a reaction network may not contain more than $r_{max}$ reactions.
	\item The networks' fitness values are obtained by computing the steady state solution of the systems' set of ODEs. Networks that exhibit steady states and the least deviant behaviour (according to the objective function) are the fittest.
	\item During each iteration, the subset containing the fittest network candidates is selected and remains within the population for the next iteration. The unselected reaction networks are removed from the population.
	\item Mutation operators are devised and introduce variations upon the network's topology \textit{and} reaction rates, see Fig. \ref{fig:deckardMut}.
\end{itemize}

\begin{figure}[htbp]
	\centering
		\includegraphics[scale=0.8]{chapter3/deckardMut.eps}
	\caption{Mutation operators in Lakhesis adapted from \cite{citeulike:96164}. A: Change of reaction rate, B: addition/removal of reaction, C: new reaction type. These mutations occur with different probabilities, A mutations occurring the most often as their effects are less disruptive than B and C mutations.}
		\label{fig:deckardMut}
\end{figure}

The above EC approach extends Bray and Lay's work by introducing richer mutation operators. As a result, a greater variety of reaction networks could be evaluated during the evolutionary process. 

Using this system, Deckard and Sauro successfully evolved reaction networks to perform a range of mathematical functions such as: multiplication by constants, square roots, cube roots and natural logarithms. Such computations could not be evolved using Bray and Lay's approach which appeared to be limited due to the  restricted number of signalling molecular species and lack of feedback loops \citep{bray1994cse}.

Moreover, in particular reaction networks capable of performing the square root function, a subpart or \textit{module} of the network was identified as being able to solve quadratic equations. Such a modular structure is of interest as it is a common feature of CIPNs. This work may thus provide further insights on the evolution of modularity in CIPNs.

Deckard and Sauro's approach was recently adopted and developed by \cite{lenser2007ten}. A multi-level Evolutionary Algorithm (EA) was proposed to conduct similar studies on the evolution of reaction networks capable of signal-processing functions. 

	\subsection{Learning Classifier Systems}
	\label{subsec:LCSagentBased}
In previous top-down evolutionary approaches, molecular species were treated in an aggregate manner at the system level. The internal structure and intrinsic properties of molecular species were not specified and did not affect the reaction network's topology nor dynamics. 

We present an alternative top-down approach in which the individual behaviour of molecules is considered. As previously presented in Section \ref{subsec:ABLCS}, \cite{holland2001eec} proposed an agent-based model where the agents' behaviour and adaptation are determined through the use of Learning Classifier Systems. Holland suggested this ABM as a suitable modelling framework for the study of CIPNs. The modelling of CIPNs was conducted in a top-down fashion, where an iterative refinement process was employed to specify the different levels of CIPN interactions. No implementation of this system was performed, nevertheless Holland proposed a toy model to illustrate this evolutionary approach. This toy model provided an existence proof that his system could be used to evolve a simple repertoire of condition-action rules to a more complex goal directed set of rules. We describe the application of this ABM approach to evolve CIPNs.

Cells are autonomous agents which possess five principle components:
\begin{enumerate}
	\item \textit{A set of detectors}: Cellular agents are situated in space and may probe their surrounding environment to detect input messages (e.g., nutrients, hormone molecules, toxic molecules). This sensor apparatus (i.e., cellular receptor) constrains the agent to only interact with its local environment. Detected messages are stored in the list of messages.
	\item \textit{A list of messages}: Messages (i.e., input signals or stimuli molecules) are received from the environment as binary encoded data. Input signals are then stored in an internal data structure termed the \textit{message list}. 
	\item \textit{A list of classifiers}: Enzymatic operations are addressed with classifiers which are strings formed over the ternary alphabet \{0,1,\#\}. Classifiers are condition/action rules. The condition statement refers to the ``binding'' conditions where input messages are evaluated. This binding condition (a pattern matching expression) determines the network's topology, i.e., the reactions/connections between the molecular species.	The action statement describes the enzymatic/computational function which results in the production of an output signal (i.e., intra-cellular signalling molecule). The latter may interact with the agent's effectors (see below). When the character \# occurs in the condition part of a classifier, \# acts as a single character wildcard which allows for the potential matching of a greater number of input strings, e.g., the string 10\# can match both inputs 100 or 101. When occurring in the action part of a classifier, \# may also copy the matched character into the output signal, e.g., let us consider the rule IF 1\#0 THEN 00\# and the input 110, the condition 1\#0 is satisfied by 110, the \# occurring in the action part 00\# is here equal to the third character of 110, as a result the product molecule 000 is generated. This character may thus provide for string/signal processing capabilities.	
	
	\item \textit{A set of effectors}: Similarly to classifiers, effectors are conditional rules. When effectors (e.g., flagella) are satisfied by output messages generated by classifiers, an action causing some changes to the environment is performed (e.g., move, produce inter-cellular signalling molecules). 
	\item \textit{A set of reservoirs}: When a classifier evaluates a binding input signal, an appropriate response is determined. This response is indicated by the classifier's action expression. If this action exhibits a specified desired behaviour then a reward mechanism is implemented through the use of a scalar reinforcement algorithm. Each classifier has an associated fitness measure, quantifying the \textit{usefulness} of the rule in attracting external reward. The rewards are resources which fill the reservoir. These resources, which deplete over time, are needed by the cell to persist in its environment. 
\end{enumerate}

Fig. \ref{fig:lcs} provides a schematic view of Holland's system where a cellular agent is depicted.
\begin{figure}[htbp]
   \centering
   \includegraphics[scale=1.1]{chapter3/lcs}
   \caption{Schematic of Holland's agent-based Learning Classifier System}
   \label{fig:lcs}
 \end{figure}

A credit assignment algorithm (such as the bucket brigade algorithm) is employed to reward and strengthen efficient classifiers/rules. Moreover a rule discovery mechanism is specified which is responsible for generating \textit{potentially} more efficient rules. GAs are employed to generate new classifiers where selection is carried out upon the classifiers' fitness measure. Both algorithms are pre-specified and do not evolve. Similarly to Bray and Deckard's approach, these explicit fitness functions are used to drive the evolution of the agent. This ABM is therefore a top-down evolutionary approach.
 
Although Holland addressed the inner structure and behaviour of individual molecules through the use of messages and classifiers, Holland distinguished a demarcation between substrate/signalling molecules (messages) and enzymatic molecules (classifiers). However, molecular species are \textit{reflexive} by nature and may act as both substrates and enzymes.

Nevertheless, in contrast to Bray and Deckard, Holland addressed certain distinctive features of CIPNs:
\begin{itemize}
	\item CIPNs are reaction networks capable of signal-processing which are contained within a cellular structure. The cellular membrane marks the distinction between the environment and the intra-cellular milieu in which CIPNs occur.
	\item The network's topology is determined by the intrinsic properties of molecular species, here modelled as pattern matching expressions.
	\item The hierarchical organisation of the cell/CIPN couple is considered. CIPNs do not directly interact with the environment but only operate within the cell. Whereas the cell may interact with the environment through the use of detectors (e.g., membrane receptors) and effectors (e.g., flagella). Two levels of interaction, i.e., molecular and cellular are identified which characterise CIPNs/cells. 
\end{itemize}

Holland's proposal complements Bray and Deckard's approaches by introducing characteristic features of CIPNs. However some aspects of CIPNs are still not considered in this approach, e.g., reflexive nature of molecular species, cellular division and a potential mechanism enabling the (self)-maintenance of CIPNs.


\section{Artificial Chemistries}
The above EC-based research did not address closure dynamics in reaction networks. We present Artificial Chemistry based  investigations which consider both closure dynamics and individual behaviour of molecular species. Artificial Chemistries (AC) are an abstraction of real chemical processes which aim at understanding the dynamics of complex molecular organisations \citep{dittrich-articial}. An AC typically consists of a set of computational ``molecules'' and of a set of rules. The rules describe the reactions that may occur between the simulated molecules. The rules are applied according to an AC-specific algorithm which also characterises the reaction space. Artificial reactions lead to the production, modification or destruction of molecules.

During an AC simulation, several phenomena of interest may arise such as the emergence and evolution of closed biochemical organisations. Although most ACs have been employed to investigate artificial/simplified models of chemical reaction networks, some AC systems have been specifically devised to study chemical reaction networks from a more biologically realistic perspective \citep{1480452,1480454}. 

Nevertheless there is, to our knowledge, no ACs which were specifically developed to examine closure and the evolution of CIPNs. We review a number of selected and related ACs in which the spontaneous emergence and evolution of organisationally closed reaction networks were examined.

\subsection{Alchemy}
\label{subsec:reviewAlchemy}
\cite{fontana1994aft, fontana1994wci} developed Alchemy to study the emergence of self-maintaining organisations in biochemical systems. Alchemy employs the $\lambda$-calculus \citep{church1932spf} formalism to specify molecular species and reactions. 

Molecules are specified as $\lambda$-expressions which upon reacting with each other may generate product molecules. Reactions occur in a well-stirred flow reactor where molecules may collide with each other at random. A collision between the molecules $A$ and $B$ generates a function $A(B)$ which is then subjected to a reduction process. The latter produces the normal form $C$ of $A(B)$, $C$ is the product molecule. The reduction process involves a number of necessary reduction steps. If the normal form is not obtained after $k$ reduction steps then the reaction is elastic, i.e, no product molecules are generated. This reduction to normal form determines the possible reactions between the molecular species. Therefore, as in LCS, the intrinsic properties of molecular species identify the reaction network's topology.

Elastic reactions may also occur when the following condition is satisfied: Let us consider the molecular species $X$ and $B$, if the normal form $X(B)$ is directly obtained without any reduction steps, then the reaction $X(B)$ is elastic. In other words, molecular species which are not capable of enzymatic/computational transformations are not allowed in Alchemy. This filter applies when molecules are randomly generated in Alchemy simulations.

As no mutations may occur in Alchemy, the molecular diversity is determined by the initial randomly generated molecular population and subsequent catalytic reactions that may occur between the molecules. 

Moreover, in contrast to EC-based systems, no explicit fitness function is defined. The dynamics of the system are only driven by the individual behaviour of the molecular species.

A series of experiments was conducted in which different forms and levels of organisation could be distinguished: \begin{enumerate}
	\item \textit{Level 0 organisations}: At the simplest level, the system is initialised with random and unique molecular species. When executed, this system quasi-deterministically converges to a state where a single autocatalytic molecular species dominates the whole population. These molecules can self-replicate when colliding with a copy of themselves, i.e., if we consider two instances (molecules) $A_1$ and $A_2$ of species $A$, we have $A_1(A_2)=A_3$. This phenomenology where molecular species can replicate themselves is referred to as \textit{level 0} ($L0$). The self-replicase species are called $L0$-objects. An example $L0$-object is $\lambda x.x$. $L0$-organisations have the form of hypercycles which were introduced by \cite{eigen1971sma, eigen1977pns}. A three-element hypercycle is presented in Fig.~\ref{fig:alchemy}. Under perturbation/mutation effects (e.g., addition/removal of molecules), such organisations are known to be \textit{fragile} and collapse to a single replicase molecular species (i.e., a single-element hypercycle).
	
	
	\item \textit{Level 1 organisations}: At the next level, an additional filter is defined to prevent self-replication reactions (where the product molecule is syntactically identical to the substrate and/or enzyme molecules) from occurring. When this filter is applied in Alchemy simulations, the emergence of a novel form of organisation can be observed: a collectively autocatalyctic set of molecular species. This form of organisation is referred to as an $L1$-organisation. In this type of reaction network, a distinct molecular species is not capable of self-replicating, but is capable of catalysing the production of another species. A closed cycle of complementary productions enables the maintenance of each molecular species present in the reaction network. Each molecular species is thus necessary for the production of another species and ultimately responsible for the maintenance of this \textit{virtuous} self-maintaining cycle. An example $L1$-organisation is depicted in Fig.~\ref{fig:alchemy}. In contrast to $L0$-organisations, it has been reported that $L1$ sets are relatively more robust to perturbations, having the ability to self-repair. $L1$-organisations are examples of autocatalytic sets \citep{kauffman1993oos}, i.e., $L1$-sets are no longer hypercycles but collectively autocatalytic (organisationally closed) reaction networks.
	
	\item \textit{Level 2 organisations}: In the last series of experiments, the system is seeded with two distinct $L1$ organisations (obtained from previous independent $L1$ experiments) in which two phenomena may be observed: 
\begin{itemize}
	\item If no molecular species may interact between both $L1$ sets then one of the two $L1$ organisations displaces the other one. 
	\item If some molecular interactions occur between both $L1$ sets then a \textit{level 2} organisation emerges. An $L2$ set is a metaorganisation which contains both $L1$ organisations as subnetworks (i.e., modules). In addition a set of molecular species is generated as a result of the molecular interactions occurring between the $L1$ sets. These molecular species do not belong to the closed cycles of both $L1$ sets. Moreover, these species do not form a closed cycle and thus cannot self-maintain. However the metaorganisation containing both $L1$ sets and these extra molecular species is closed. The $L2$ set is therefore able to maintain \textit{all} molecular species present in the network. These molecular species, occurring outside the $L1$ sets, enabled the stabilisation and integration of both $L1$ sets into a higher order $L2$ organisation. 
\end{itemize}
\end{enumerate}

\begin{figure}[htbp]
	\centering
		\includegraphics{chapter3/alchemy.eps}
	\caption{A: Level 0 organisation (a three-element hypercycle). B: Level 1 organisation. C: Level 2 organisation containing two Level 1 organisations}
	\label{fig:alchemy}
\end{figure}

The above phenomena resulted only from self-organisation dynamics. Contrary to EC-based research, this work did not attempt to perform or investigate computation in reaction networks. Nevertheless some CIPN aspects can be identified in this investigation:

\begin{itemize}
	\item The $L2$ experiments exhibited reaction networks where a modular structure can be observed. Modules (i.e., $L1$ sets) can be identified and are contained within a higher structure or metamodule. This hierarchical organisation is characteristic of CIPNs where each module may possess a distinctive function. 
	\item The signalling pathway formed by the``glue'' molecular species (which resulted from the molecular interactions occurring between the $L1$ sets) may be acting as a \textit{control} or \textit{regulation} function. These molecular species prevent the $L1$ sets from displacing each other by regulating the reactions occurring in each $L1$ set. For example let us consider the $L2$ set $C$, $A$ and $B$ are $L1$ sets, and $G$ the set of glue molecules so that $A\cup B\cup G=C$. If $A$ grow faster than $B$ then this has an affect on $G$ which would subsequently grows faster. However if $G$ grows faster then $B$ would also benefit from this growth. As a result, $A$ and $B$ are stabilised.
\end{itemize}

In this approach, only catalytic molecular species are allowed. Fontana and Buss reported that if molecular species acting only as substrate molecules are not filtered out then no spontaneous emergence of closed organisations could be obtained. When allowed, an accumulation of such inert molecular species is observed. These molecular species being inert, cannot contribute to the production of other molecular species. Fontana and Buss argued that this accumulation of ``waste'' molecular species disrupts the metabolic processes and prevents self-maintaining metabolic cycles from emerging.

Although the Alchemy system presented significant results related to closure in reaction networks. The introduction of non-catalytic  molecular species prevents autocatalytic closure from emerging. However CIPNs typically involve such molecular species during signal transduction. Finally no random variations at the molecular level were devised in Alchemy. Fontana and Buss's work did not address the evolution but the emergence of self-maintaining organisations in initially unorganised reaction networks. The Alchemy approach may thus not be directly applicable to the study of closure and the evolution of CIPNs.
 
	\subsection{\texorpdfstring{$\alpha$}{alpha}-universes}
$\alpha$-universes are a class of AC which were proposed by \cite{holland1976sse} to investigate the spontaneous emergence of life. Holland aimed at demonstrating that emergence of self-replicating systems  was possible given an initial unorganised system state. This investigation was addressed through a quantitative analysis of the emergence time of autocatalytic systems/reaction networks. In this investigation, a specific $\alpha$-universe was described by Holland and is presented in the remainder of this section.

The model is specified as a one dimensional and circular linear string of ``nodes''. The latter may be empty or contain an ``atom'' from the set $\{0,1,:,N_0,N_1\}$. This instance of $\alpha$-universe is a mass conservation model, i.e., the number of existing atoms is fixed, atoms cannot be created or removed, they are simply rearranged in space.

Adjacent atoms may be bonded to constitute structures (i.e., molecules) which are separated from each other by empty nodes. Each atom is associated with a level of bonding (i.e., weak or strong) to the adjacent atom, if any, at its right. A bond between an atom and an empty node is weak by convention.

Two classes of operator, respectively  called ``primitive'' and ``emergent'', are distinguished and operate stochastically:

\begin{enumerate}
	\item Two primitive operators are devised allowing the spontaneous stochastic recombination of the molecules' structures: the \ttfamily EXCHANGE \normalfont operator produces diffusion-like movements of atoms whereas the \ttfamily BOND-MODIFICATION \normalfont  operator causes random changes in the strength of bonding between atoms. These operators are context-insensitive and allow for random variations to occur at the molecular level (i.e., acting like mutation operators). A feature which was not devised in Alchemy.
	
	\item Two emergent operators are defined and are sequences over $\{0,1,:\}$. The latter are regarded as functional elements whereas $\{N_0,N_1\}$ are viewed as ``nucleotides''.  The colon symbol is employed to separate the sequences into the operator's arguments. The latter designate the type of the operator (i.e., \ttfamily COPY \normalfont or \ttfamily DECODE\normalfont) and the prefix of the ``substrate molecule''. These operators are context-sensitive, i.e., these operators/functional molecules ``emerge'' according to the specific arrangement of atoms in the sequences. The \ttfamily DECODE \normalfont operator translates sequences over $\{N_0,N_1\}$ into sequences in the alphabet $\{0,1,:\}$ through the use of a mapping table. The \ttfamily COPY \normalfont produces copies of sequences over $\{N_0,N_1\}$.
\end{enumerate}

A distinction is thus made between molecules that can only act as substrates and those which possess functional capabilities. Non-functional molecules were not present in Alchemy as it would have prevented the emergence of self-maintaining organisations (Section \ref{subsec:reviewAlchemy}).

The molecular computational operations can be viewed as a simplification of Learning Classifier Systems (i.e., production rules). As in the agent-based LCS approach, the network's topology is determined by the binding/pattern matching conditions of the functional molecules. However the collision rule differs and accounts for space (favouring collisions between molecules that are nearest to each other). A reaction occurs if the functional molecule's binding condition (as devised in the molecule/operator's arguments) is satisfied by the structure of the substrate molecule.

As proposed, this system does not allow for the implementation of individually  autocatalytic/self-replicating molecular species. However Holland argued that an infinite class of collectively autocatalytic reaction networks could be identified in $\alpha$-universes. Although no experiments were conducted, Holland presented a theoretical analysis of the expected emergence time of such closed reaction networks. 

Actual experiments \citep{mcmullin1992halphau} demonstrated that closed reaction networks could not self-maintain due to side reactions not predicted by Holland. It was also observed that necessary ``food molecules'' (i.e., nutrients) would rapidly deplete and prevent any further reactions from occurring. It has however been suggested that under flow conditions (providing an inflow of nutrients), it could be envisaged to obtain such closed reaction networks to self-maintain \citep{mcmullin2000raa}.

\subsection{Tierra}
\label{subsec:tierra}
Alchemy and $\alpha$-universes focused on the spontaneous emergence of organisations given an initial unorganised system. In contrast to these approaches, \cite{ray1991asl} did not focus on prebiotic conditions but on the requirements allowing for the spontaneous evolutionary process of increasing diversity and complexity of organisms. To assist this research, Ray proposed Tierra and intended to explore open-ended evolution using this system. 

In the Tierra metaphor, a virtual computer is employed to represent the universe. The computer memory designates the universe's one-dimensional space. Within the virtual computer memory, we may distinguish patterns of computer codes which identify the digital organisms/agents. The latter are represented as concurrent computer programs which compete with each other for CPU time (energy) and access to memory (nutrients). Interactions between these computer processes may lead to the creation, modification or destruction of processes. These evolvable digital organisms/processes can be regarded as molecules which may interact/react with each other leading to the production/destruction of molecules/computer processes. These reactions occur under flow conditions. The molecular computational processes also follow the virtual computer metaphor and consist of computer instruction operators (32 distinct operators/atomic elements are devised). The agents are evolvable in the sense that they can be modified through the use of stochastic operators (e.g. error-prone replications, spontaneous mutations). 

Parallelism is simulated in the Tierra virtual computer where the number of CPUs is equal to the number of existing agents. Each of these CPUs execute a small time slice in turn as devised by the time-slicing algorithm. CPUs perpetually carry out a ``fetch, decode, execute, increment instruction pointer'' cycle where the instruction pointer indicates a memory address in the virtual computer memory.

When an agent is interpreted for computation, specific operators may be employed to point at specific regions of the computer memory. In particular cases these pointers may jump to memory areas where another agent (or raw material) is already present. In such cases, interactions (i.e., chemical reactions) between the enzyme and substrate species may occur. These instruction pointer mechanisms identify the reactions that may occur between species, and therefore determine the reaction network's topology.

In the Tierra system, it was necessary to construct and feed the system with at least a single autocatalytic/self-replicator molecule called the ``ancestor". This introduction of an ancestor species was necessary as no spontaneous emergence of such species could be observed (a variant of the Tierra system called Amoeba was specifically developed by \citealp{DBLP:journals/alife/Pargellis01} to address this issue). 

The reaction space's size is fixed and may contain up to 60000 instructions. When 80\% of the space if filled up, then a reaper is activated and kills molecules (by deallocating their memory) in a particular order specified in the reaper's queue. This mechanism introduces mortality and prevents the saturation of the reaction space, in which case no further reactions could occur.

Example evolutionary dynamics observed when a single ancestor molecule (which contains 80 instructions) is inserted in this reaction space are as follows:

\begin{itemize}
	\item The self-replicator species would rapidly fill up the reaction space. Then through mutations, mutants of the self-replicator species would emerge and were potentially more efficient (having a faster reaction speed) than the ancestor molecules. In such cases, the mutants possessed a selective advantage and displaced the original ancestor molecular species. Series of such selective displacements involving mutant species could be observed.
	
	\item A second more complex phenomenon includes the emergence of pseudo-collectively autocatalytic sets of molecules. This phenomenon was due to the emergence of mutant species which were acting as ``parasites''. These parasites were not able to self-replicate, but relied on ``host'' species to be replicated. Thus the replication of each molecular species, including both the parasitic and the self-replicator species, was possible in such reaction networks. The latter can therefore be considered as organisationally closed. However as autocatalytic species are still present, the term \textit{collectively} autocatalytic cannot be rigorously applied here.
	
	\item Another dynamic of interest is distinguished with the emergence of ``social hyper-parasites''. In reaction networks composed of such entities, no autocatalytic molecular species were present. An aggregation of molecules was observed in which each of them supported the production of another molecule in this set. Therefore these social hyper-parasite species constituted a collectively autocatalytic reaction network. It has been reported that such organisations possessed a selective advantage which would drive the extinctions of self-replicators, parasistes and hyper-parasites. The latter are not described here, \cite{ray1992eea} provides further details about these species.
\end{itemize}

Other emerging phenomena were observed such as the emergence of immunity to parasitism, circumvention of immunity to parasitism, hyper-parasitism, Lotka-Volterra cycles and cheaters with hyper-hyper-parasites. This set of behaviour demonstrates the capability of Tierra to exhibit intricate evolutionary dynamics and phenomena. An increase in complexity and diversity was observed, which was potentially facilitated by the mutation operators and the rich set of enzymatic/computational operators.

On top of exhibiting the emergence of closed reaction networks, this work is of interest to the evolution of CIPNs as it demonstrates that under an evolutionary regime, complex behaviours at the macroscopic level, e.g., emergence of ecologies, exhibition of punctuated equilibrium dynamics \citep{gould2002set}, may emerge. Similarly to the Tierran societies, cells may exhibit complex behaviours that are not predictable.

Nevertheless we may also argue that the set (and nature) of the instruction operators is already \textit{quite} complex. Indeed machine instructions that are equivalent to the Tierra operators are capable of universal computation. However the set of enzymatic operators occurring in CIPNs \textit{may not} share such a level of computational capability.

\section{Other systems}
Our review of evolutionary approaches applied to biochemical networks is far from exhaustive. Many other systems have been developed and address various aspects of the emergence, self-organisation, self-maintenance and evolution of biochemical organisations. Examples of related studies include:
\begin{itemize}

	\item \cite{stuart1986kas,farmer1986arp} conducted an early study on the spontaneous emergence of autocatalytic sets. A simplified protein-network model was proposed in which only cleavage and condensation reactions could occur. This work focused on the reaction graph's connectivity as the key feature enabling the emergence of autocatalytic sets. Given a well-stirred prebiotic soup containing such simplified proteins generated from the random assembly of monomers, Kauffman et al. demonstrated that as the diversity of molecular species increases (which indirectly affects the reaction network's level of connectivity), the probability of an autocatalytic set to spontaneously emerge increases accordingly. Kauffman's work thus suggests that the emergence of such autocatalytic sets is feasible under relatively reasonable conditions.

	\item Typogenetics is a simplified model of DNA replication presented as a typographical formal system \citep{hofstadter1979geb}. The novelty of this system relied on the introduction of a primary/informational and secondary/functional structures. Codons of ``nucleotides'' would code for specific functional operators though the use of a mapping table. It was proposed that Typogenetics was a suitable approach to investigate Artificial Life \citep{morris1987tla}. Studies on self-replicators and hypercycles were also conducted using this system \citep{kvasnicka2001aah,wee2005eav,gwak2007cht}
	
	\item Avida \citep{adami1994ela} is a popular variant of the Tierra system. In contrast to Ray's system, the update rules (as devised by the time-slicing algorithm) are not fixed and may vary according to the nature of the organisms' genomes. Avida agents are executed on individual virtual CPUs whose ``speed'' may vary from one another.	As Tierra, Avida was also employed to investigate open-ended evolution \citep{lenski1999gcr, lenski2003eoc}.
	
	\item Echo \citep{holland1990eee, holland1994eeo, holland1996hoa} is an agent-based system proposed to investigate the abstract class of Complex Adaptive Agents (which may be applied to a wide variety of artificial and natural systems). Echo employs simplified LCS-like rules to determine the agents' behaviour. This model was inspired by ecological research in which typical agent interactions include combat, trade and mating. 
	
	\item \cite{farmer1986isa} proposed a dynamic network model of Artificial Immune Systems (AIS) based on the network theory of \cite{jerne1974tnt}. Farmer et al. demonstrated a strong analogy between their proposed model and Holland's LCS in which molecular (antibody) species are classifiers, the latter's conditions and actions are respectively epitopes and paratopes, finally the classifiers' fitness/strength designate the molecular species' concentration. This work on adaptable/evolvable biochemical networks differs from other LCS-based investigations by explicitly addressing the molecular species' concentration with the classifiers' fitness as devised by the credit assignment algorithm (Section \ref{subsec:LCSagentBased}). This algorithm (e.g., the bucket brigade algorithm) governs the changes in concentration of the different molecular species and can be thus regarded as the reactor model. However, in contrast with above presented systems, AIS-based research has focused on problem-solving applications using AIS as adaptive machine learning techniques \citep{bersini1990hap,DBLP:conf/icaris/2006}. 
	
	%\item Constrained generating procedures \citep{holland1998eco}
\end{itemize}
Although the specification and implementation of the above models may vary significantly compared to selected reviewed EC and AC models, the observed evolutionary dynamics are essentially equivalent (e.g., emergence of closed networks, increase in diversity and complexity of species, emergence of complex behaviours at the molecular population level). However the evolution of reaction networks using these systems would always plateau (where no further increase in complexity nor emerging behaviour would be observed) during long term evolution. To date, no evolutionary system has managed to demonstrate an open-ended evolutionary growth of complexity.

In the following section we evaluate the strengths and weaknesses of EC/top-down and AC/bottom up evolutionary approaches. 
\section{Top-down versus bottom-up approaches}
\label{sec:topDown}
We discuss the pros and cons of the above top-down and bottom-up evolutionary approaches. We distinguish several evaluation criteria that are related to closure and the evolution of CIPNs:

\begin{itemize}	
\item \textit{Granularity}: EC models (excluding Holland's agent-based LCS) consider molecular species in an aggregate manner at the system level. Bray and Deckard's approaches employed differential equations to model the artificial reaction networks. As reviewed in Chapter \ref{modellingCSNs}, these modelling techniques do not allow for the examination of the individual behaviour of molecular species. However examining closure and the evolution of CIPNs requires the ability to trace the behaviour (subjected to an evolutionary process) of distinct species. Presented AC models rely on modelling techniques which address the individual and inner structure (including submolecular elements and/or reflexive nature) of molecular species.

	\item \textit{Cell-level interactions}: Bray and Deckard's approaches evolved reaction networks in which the nature of the container (e.g., a cell) was not considered. By contrast, Holland's approaches considered cell-level properties leading to systems possessing two distinct levels of interaction. However further key properties of cells were still not addressed. For example no systems implemented cellular division where molecular species are randomly selected and distributed to offspring cells. This stochastic process may therefore dramatically affect the behaviour/performance of offspring cells/agents. EC models did not attempt to examine self-maintenance properties of biochemical networks. 
	On the other hand, ACs addressed the self-organisation and self-maintenance properties of reaction networks. However the potential functions of the system itself (i.e., the cell) and cell-level interactions were not investigated. 

	\item \textit{Computation}: In terms of traditional computational/signal processing functions, EC models were successfully employed to evolve a range of mathematical functions (e.g., square/cubic root, normal logarithm, etc.). Artificial reaction networks were also evolved with success to solve quadratic equations. Such results have not been obtained using ACs. Evolving mathematical functions in EC models is facilitated by the explicit definition of an objective function. The latter allows one to specify precise computational functions to be mirrored. 
	
No ACs have to date been devised to evolve reaction networks capable of distinct signal-processing functions. ACs are mainly employed to investigate the emergence and evolution of behaviours exhibited by living systems. However these targeted natural behaviours exclude signal-processing functions that some natural systems are capable of (e.g., CIPNs, neural networks).
	
Nevertheless some AC models are computational universal, therefore such ACs should be able to generate computational functions of any complexity. Although the evolution of computational functions using ACs has not been investigated, the modelling of molecular computing devices using ACs has been addressed \citep{1268671}. This work supports the suggested ability of AC systems to perform computational functions.

\item \textit{Closure}: 
According to \cite{kauffman1993oos}, the network's topology is a critical property which may allow or not the spontaneous emergence of collectively autocatalytic reaction networks. Given a randomly generated reaction network, a level of connectivity/reactions between the molecular species is necessary to obtain spontaneously a collectively autocatalytic reaction network.

In ACs, the inner structure (binding rules) of molecular species determines the reaction network's topology. As the structure of species is dynamic, the network's topology may also change over time. Varying these properties dynamically allows ACs to exhibit such spontaneous phenomena involving closure in reaction networks.

Although in some EC models, the network's topology may be dynamic, no consideration for organisational closure was given. However this could have been addressed in these models where the objective fitness function could be modified to account for closure properties. This engineered top-down trick remains hypothetical as further examinations would be necessary.

	\item \textit{Evolution}: In EC models, the evolutionary process is driven by explicitly devised fitness functions. These fitness functions are pre-specified and do not evolve. As discussed by \cite{860359}, these attributes may stifle the occurrence of ``perpetual novelty'' during evolution. Therefore the performance of the system (as defined by the fitness function) may be limited during long term evolution. 

An alternative would be to define a meta Evolutionary Algorithm (EA) that would evolve these mechanisms, however this would present one with yet another problem: how to specify the EA fitness function? The latter is fixed and is potentially another point where novelty may be stifled, recreating this credit assignment problem. 

To avoid this infinitely recursive problem, ACs rely on implicit fitness functions that the agents devise themselves. Nevertheless, in any given ACs, the evolution of complexity appears to plateau during long-term evolution. Although the use of implicit fitness functions seems more appropriate, further   conditions for open-ended evolution exist. The identification and understanding of these conditions remain, to date, critical and challenging problems in both artificial and natural systems \citep{Gershenson2008}.
\end{itemize}

Based on the above evaluation, we do not identify a clear suitable evolutionary framework to investigate closure and the evolution of CIPNs. However complementary desired features are present in these systems. AC-based/bottom-up evolutionary frameworks appeared to present essential features with regards to granularity, evolution and closure. 

Moreover ACs that are modelled as agent-based systems, and implemented using an object-oriented programming environment \citep{bersini1999dpo,borsini2000rmo}, offer flexibility. The latter allows us to propose a novel AC which would also account for CIPN-specific properties and information processing capabilities. This novel AC is described in the next concluding section.

\section{Conclusion}
We reviewed a selection of top-down and bottom-up evolutionary systems which addressed complementary aspects with regards to computational abilities, emergence, self-organisations, self-maintenance and evolution of CIPNs. However, this review revealed that no existing evolutionary frameworks can be directly applied to investigate closure and the evolution of CIPNs. 

Nevertheless we identified agent-based ACs as a relatively more promising and flexible evolutionary approach. We thus propose the development of a novel agent-based AC which is inspired by, and combines features of, the ACs previously evaluated. This AC will incorporate the following features:
\begin{itemize}
	\item This AC will be modelled through the use of an algebraic/agent-based approach. The inner structure of molecular species will be thus specified. This modelling approach will allow for the examination of individual behaviour of molecular species.
	\item A production rule (i.e., condition/action rules) formalism will be adopted to implement the molecular computational processes (binding conditions and enzymatic operations). However no demarcation between operands and operators will be distinguished addressing the reflexive nature of molecular species. 
	\item The set of primitive computational operators will be constructed in a minimalist fashion (\textit{a contrario} to Tierra which involved computer-like instructions). This will allow us to minimise the initial complexity of the model, and potentially not bias emerging phenomena that may occur.
	\item Reactions will occur in a well stirred reactor. 
	\item Molecular collisions and enzymatic/computational operations will involve stochastic elements resulting in a stochastic behaviour at the system level.
	\item In accordance with traditional ACs, we will examine CIPNs from a bottom-up approach in which no explicit fitness function will be devised.
	\item Molecular species will be subjected to random changes (mutations) introducing greater genotypic/phenotypic diversity during evolution.
	\item Mutations will affect the binding conditions/structures of molecular species. As a result the reaction network's topology will be dynamic which may facilitate the emergence of closed reaction networks.
  \item Molecular species will be contained within a single reactor which will ultimately be evolved to carry-out signal-processing functions. This single reactor model is presented and evaluated in Chapter \ref{TheAC} and \ref{emerSelfMainClosedRN} respectively.
  \item Compartmentalised containers will be introduced. Diffusion/exchange of molecules between these multiple compartments will be devised. This static reactors model with molecular diffusion is investigated in Chapter \ref{chap:evoStab}.
  \item Similarly to biological cells, compartmentalised containers (i.e., cells) will be able to ``grow and divide''. This cellular model is also examined in Chapter \ref{chap:evoStab}.
\end{itemize}

In the next chapter, we present in detail our novel proposed AC, called the Molecular Classifier Systems (\MCS), specifically devised to address closure and the evolution of CIPNs.
