Abstract
Cartesian genetic programming, a well-established method of genetic programming, is approximately 20 years old. It represents solutions to computational problems as graphs. Its genetic encoding includes explicitly redundant genes which are well-known to assist in effective evolutionary search. In this article, we review and compare many of the important aspects of the method and findings discussed since its inception. In the process, we make many suggestions for further work which could improve the efficiency of the CGP for solving computational problems.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The term “Cartesian genetic programming” (CGP)Footnote 1 first appeared in 1999 [65]. Although, it was a generalisation of a method of encoding and evolving electronic circuits that was first described in 1997 [71]. In 2000, it became established as a new form of genetic programming [70]. Since that time CGP has been adopted by many researchers, adapted by others and applied to many applications areas. This article provides an extensive review of the different variants of CGP, and an analysis of many important aspects of CGP. It discusses numerous open issues and questions. The article contains many suggestions for further work which could lead to improvements in the efficiency of the CGP for solving computational problems.
In contrast to tree-based genetic programming [53, 80], CGP encodes computational structures as directed graphs. Its invention was heavily influenced by earlier work on creating and evolving genetic representations of circuits. These are most naturally encoded as graphs and can be described using structures called netlists. CGP uses a netlist-inspired address-based genotype consisting of integers pointers to an either an array of primitive functions or data locations. Encoding graphs, rather than trees has advantages in that nodes can be multiply used and graphs can have multiple outputs. It is a very adaptable representation as it can easily represent many types of computational structures, such as systems of equations, state-machines, neural networks, algorithms and electronic circuits. Another defining characteristic of CGP is that the genotype can include non-coding genes. The genotype is recursively decoded from program outputs to inputs and in so doing nodes can be ignored, these are non-coding. As we shall the presence of non-coding genes has strongly influenced the choice of search algorithm that is most suitable for CGP (see Sect. 2).
In the article, we discuss many variants of CGP that have been proposed. We begin with a graph-based form of GP called parallel distributed GP (PDGP) which was developed by Poli prior to CGP [77, 78]. This has many similarities with CGP but also uses various graph-based crossover and mutation operators and restricted graph connectivity. Modular CGP (MCGP) is based on standard CGP but has additional mutation operators which allow CGP-encoded sub-functions (called modules) to be captured, re-used or modified. This was motivated by Koza’s work on automatically defined functions in tree-based GP [54]. In real-valued CGP (RVCGP) all genes are real-valued and a decoding step translates these into standard CGP genes. This is attractive as it allows many methods for evolving genotypes used in evolutionary algorithms work to be used to evolve programs (e.g. “flat” crossover see Sect. 5).
Implicit-context CGP (ICCGP) removed the positional dependence of genes in CGP by representing components by evolved entities called enzymes which are self-assembled to form CGP-like phenotypes. Self-modifying CGP (SMCGP) extended CGP by introducing new kinds of primitive functions (self-modifying) which carried out transformations of the phenotype, this allowed sequences of phenotypes to be evolved from a single genotype. It also required genes in CGP to use relative addressing (also used in PDGP). Mixed-type CGP (MTCGP) borrowed some features from SMCGP and also allowed CGP to handle different data types (i.e. scalar and vector). Recurrent CGP (RCGP) is a simple extension to standard CGP which allowed connections between primitive functions to be both feed-forward or feedback (i.e. breaking acyclicity). Iterative CGP (ICGP) introduced conditional loop-genes into CGP which allowed CGP to encode algorithms.
Differentiable CGP (DCGP) is a form of CGP in which phenotypes are differentiable. Primitive functions are truncated Taylor’s series and graph connections are weighted. This allows gradient descent to be used to arrive at highly-tuned graphs. We also discuss a recently developed form of graph-based GP called evolving graphs by graph programming (EGGP) in which phenotypes are encoded using a graph description language. This allows graphs to be manipulated more freely than is possible in the standard form of CGP. We also discuss the recently proposed positional CGP (PCGP). This a real-valued form of CGP form in which graph nodes have evolvable positions, and connections are made to the nearest node.
We also discuss in depth various promising forms of crossover, mutation and search algorithms that have been suggested in the literature of CGP. It should be noted that very recently, another review of CGP has appeared. It discusses CGP and its variants and focuses in detail on their representational differences and evolutionary operators [62].
The plan of the article is as follows. First we review CGP-encoded representations of programs that have been suggested in the literature (Sect. 3). We follow this with a discussion of work done in mutation (Sect. 4) and crossover (Sect. 5). Section 6 discusses various search algorithms that have been investigated for CGP. In Sect. 7 we examine ways in which CGP can be made faster by using hardware. Section 8 discusses major applications of CGP including CGP encoded artificial neural networks. In Sect. 9 we discuss the relatively high comprehensibility of CGP programs. We give comparisons of the efficiency and human-competitiveness of CGP to other machine learning techniques in Sect. 10. The growing amount of publicly available software for CGP is reviewed in Sect. 11. We close with sections on open questions and suggestions for further investigation (Sect. 12) and conclusions. For reference and completeness we begin with a description of the standard form of CGP.
2 Aspects of standard CGP
2.1 Representation
In its standard form CGP programs are representations of directed acyclic graphs. These graphs are represented using a two-dimensional grid of computational nodes. Hence the term “Cartesian”.
Each node in the directed graph represents a particular function and is encoded by a number of integer genes. Each node has a function gene which is the address of the computational function of the node in a user-defined look-up table of functions. The remaining node genes are connection genes and say where the node gets its data from. These genes represent addresses in a data structure (typically an array). Nodes take their inputs from either the output of a node (in acyclic CGP, from a previous column) or from a program input. The number of connection genes a node has is chosen to be the maximum number of inputs that any function in the function look-up table has. If any node function requires less inputs, the remaining connection genes are ignored. The program data inputs are given the absolute data addresses 0 to \(n_i-1\) where \(n_i\) is the number of program inputs. The data outputs of nodes in the genotype are given addresses sequentially, column by column, starting from \(n_i\) to \(n_i+n_n-1\), where \(n_n\) is the user-determined upper bound on the number of nodes. A schematic is shown in Fig. 1.
If the problem requires \(n_o\) program outputs, the genotype is augmented with a number of output genes (\(O_i=n_o\)). Each of these is an address of a node where the program output data is taken from. Nodes in columns cannot be connected to each other. In its standard form the graph in CGP is directed and feed-forward; this means that a node may only have its inputs connected to either input data or the output of a node in a previous column. However, as we will see in Sects. 3.7 and 3.8, this restriction can be relaxed to allow recurrent or cyclic graphs. A schematic of the genotype is shown in Fig. 1.
CGP has three user-selectable graph parameters that define the dimensionality and connectivity of the encoded graphs. These are the number of columns, the number of rows and levels-back. These are denoted by \(n_c\), \(n_r\) and l, respectively. The product of the first two parameters determine the maximum number of computational nodes allowed: \(n_n = n_c n_r\). The parameter l, called levels-back, controls the connectivity of the graph encoded. Levels-back constrains which columns a node can get its inputs from. If \(l=1\), a node can get its inputs only from a node in the column on its immediate left or from a primary input. If \(l=2\), a node can have its inputs connected to the outputs of any nodes in the immediate left two columns of nodes or a primary input. If one wishes to allow nodes to connect to any nodes on their left, then \(l=n_c\). Varying these parameters can result in various kinds of graph topology. An important special case of these three parameters occurs when the number of rows is chosen to be one and levels-back is set to be the number of columns (one dimensional topology). In this case the genotype can represent any bounded directed graph where the upper bound is determined by the number of columns. The length of a CGP genotype is given by \(L_{cgp} = n_n (a+1) + n_o\).
2.2 Search algorithm
Standard CGP uses a search algorithm (Algorithm 1) that is inspired by the \(1+\lambda\) evolutionary strategy [83] in which a single parent genotype is mutated to create \(\lambda\) offspring. An offspring that has a fitness better or equal to the parent becomes the new parent for the next generation. This is still the most widely used search algorithm for CGP. We discuss work suggesting other search algorithms in Sect. 6.
2.3 Non-coding genes
The reason that such a simple search strategy operating on such a small population is effective is strongly connected with the presence of non-coding genes in the genotype. Non-coding genes arise in CGP when the outputs of nodes are not referenced in the flow of data from program inputs to program outputs. It is this which leads to both variable length phenotypes and evolutionary neutral drift in the genotype. It should be noted that the genotype-phenotype map** process in CGP incurs very little computational overhead as it is only carried out once per genotype. The \(1+\lambda\)-inspired algorithm promotes neutral drift since often mutational offspring differ only in inactive genes and so have equal fitness to their parent [69, 110, 119, 128, 129]. Such identical offspring can be detected before fitness evaluation so incurring no fitness calculation. Thus, even when it appears that the algorithm is stuck on a local optimum fitness value the search algorithm is exploring many possible different solutions by mutating different genotypes. The maximum allowed size of the genotype is highly influential here and Turner et al. investigated the relationship between it and performance on a suite of hard benchmarks [110]. They found that the relationship was approximately quadratic with a clear optimum value for \(n_n\). Often the optimum number of nodes was quite large (hundreds or thousands of nodes).
2.4 Absence of bloat
CGP does not suffer from a phenomenon called bloat [105], in which over evolutionary time, programs become larger [91]. Bloat has been described as “program growth without (significant) return in terms of fitness” [80]. It was thought that the lack of bloat in CGP was caused by either neutral genetic drift (NGD) [66] or length bias (LB) [18]. The former argued that since NGD is beneficial to search, it is beneficial to maintain a large number of inactive genes. This provides a pressure to limit the number of active genes. LB argues that the lack of bloat is a consequence of the genotype representation which has the property that nodes closer to the program inputs are much more likely to be active since they can be connected to by many nodes on their right. This causes a strong bias towards small program sizes. Interestingly, both these hypotheses for the lack of bloat in CGP have been disproved [105] where it was shown that when NGD is disallowed in CGP bloat still does not occur. LB cannot be the reason why there is no bloat since Recurrent CGP (see Sect. 3.7) has no length bias and yet it too does not exhibit bloat. Thus the cause of lack of bloat in CGP is still an open question.
3 Alternative genotype representations
3.1 Parallel distributed genetic programming
For completeness, and because of later discussion, we include a brief discussion of a form of graph-based genetic programming that has a representation that is similar to CGP. It is called parallel distributed GP. Poli proposed this in 1996 [77, 79]. Like CGP, PDGP represented graphs using a Cartesian grid of nodes. Connection to nodes were restricted to the previous layer (i.e. in CGP terms, with levels-back equal to 1) and the connection genes were relative (as in SMCGP see Sect. 3.5) and counted back from a node position to the source of node input. A pass-through (or wire) function was allowed so that nodes could be connected to deeper layers. Poli devised various crossover operators. They are all based around the idea of swap** sub-graphs defined by selecting random crossover points in the parents to create offspring. One can choose the first crossover point at random and the other must respect the limitation that the graphs have a maximum depth (in CGP terms, a maximum number of columns). By choosing crossover points either in either active or inactive nodes or both, he described a number of types of crossover. He also discussed two forms of mutation, one he called global in which a random sub-graph is generated and replaces an existing sub-graph. Actually, he states that global mutation was implemented by crossing over an individual with a randomly generated new individual [79]. The second mutation operator he called link which is the same as point mutation in CGP. Using an evolutionary algorithm with population sizes of around 1000 and tournament selection with crossover and both types of mutation Poli showed that PDGP was markedly more efficient at solving problems than standard tree-based GP (even with ADFs) and often the evolutionary algorithm was most efficient with small grid sizes. PDGP was also used to evolve artificial neural networks [81].
3.2 Modular
Koza demonstrated the usefulness of automatically-defined functions (ADFs) in tree-based GP [54]. Walker and Miller introduced an equivalent to ADFs for CGP called modules [122, 123]. In modular CGP sub-functions or modules can be captured or destroyed by mutation operators. Capture or acquisition happens via two random positions in the genotype. The genotype is extracted and placed in a module list and the removal site replaced by a module containing the re-labelled sub-genotype so that the meaning of the genotype is identical to the original genotype before module acquisition. Empirical comparisons of results with and without ADFs were made on a number of benchmarks and appeared to show that CGP with module acquisition and evolution obtained solutions in much fewer numbers of evaluations that standard CGP, particularly on hard problems. However, it should be noted that the comparisons with CGP were unfair in the sense that the total size of allowed genotype in nodes with modules was much greater than the number allowed in standard CGP. Thus, it still remains an open question as to whether module acquisition is beneficial.
Noting that in modular CGP modules were acquired or destroyed randomly (i.e. via mutation), Kaufmann and Platzner introduced some new techniques for creating modules: age-based and cone-based [38]. The age-based module creation operator identifies primitives nodes that have remained unchanged for a number of generations and places these into modules (only primitive nodes can reside in a module). The module is given an age that is the average of the ages of the primitive nodes within it. Two candidates are generated using this operator and the one that is older is chosen. In contrast to standard or age-based module creation, cone-based module acquisition (MA) aggregates only primitive nodes that are within a structure called cone (see [38] for details). Cones are a widely-used concept in circuit synthesis. They compare the computational effort (as defined in [53]) of the original modular CGP with versions that allow either age-based or cone-based MA on circuit synthesis and classification problems. They found that in almost all cases the age-based technique was superior to the original MA. However, cone-based MA largely proved superior only on circuit problems.
3.3 Real-valued
Clegg et al. devised a genotype representation for CGP in which all genes are floating point numbers in the interval [0.0, 1.0] [10]. We refer to this as a real-valued CGP representation (RVCGP). The motivation for devising this representation was that crossover in CGP might be more effective using a real-valued representation. We will discuss this in more detail in Sect. 5. Real-valued CGP has an additional decoding step in which a standard CGP genotype is obtained from the real-valued genotype. The real-valued genotype still has genes grouped by nodes consisting of a function gene and a number of connection genes.
Assume that the node function look-up table has \(n_f\) functions. Standard CGP node function integer genes, \(ig_f\) are obtained from the floating point gene, \(rg_f\), by examining which of \(n_f\) segments of the interval [0.0, 1.0], \(rg_f\) lies within. This is accomplished with Eq. 2.
For instance assume there are four node functions. Then if \(rg_f\) is less than 0.25 then \(ig_f = 0\) while if \(rg_f\) is greater than 0.25 and less than 0.5, \(ig_f=1\), and so on.
Real-valued connection genes, \(rg_c\) corresponding to node address, \(n_p\) are decoded to standard integer connection genes, \(ig_c\) by dividing the unit interval into \(n_p\) segments. The equation that accomplishes this given in Eq. 3.
For instance, suppose that \(n_p=6\), and there are two program inputs and four nodes. Then the unit interval is divided into as many segments as the node address (i.e. 6). If \(rg_c\) is between 0 and 1/6 then \(ig_c=0\), so that the first input to node 6 is the first program input (whose address is 0), if \(rg_c\) is between 5/6 and 1 then \(ig_c=5\) and the first input of node 6 is connected to the output of node 5 (the previous node). Output genes are decoded in the same way as the connection genes corresponding to node address of one more than the highest node address.
Using floating point values as genes for CGP has the potential to make the genotype more evolvable since when small changes are made to the genes the gene can move gradually to a value which will result in genotype change (assuming Gaussian mutation), whereas in standard CGP random mutations either abruptly moves a node input connection to an entirely different node, or changes the function of the node. Also, another motivation was to transform the discrete nature of CGP genotypes to smooth functions of n variables [10]. Finally, it allowed the prospect that much of the research into the optimization of real-valued vectors using evolutionary algorithms could be applied to CGP and hence the evolution of programs or other computational structures. Indeed, Clegg (see Sect. 5) used a form of crossover showing it appeared to be beneficial for symbolic regression problems. However, in his master’s thesis, Turner [101] examined RVCGP on three additional classes of computational problems, digital circuit synthesis, function optimisation and agent-based wall avoidance. On these problems, it was found that RVCGP together with the crossover operation performed worse than standard CGP. However, he found that implementing the RVCGP representation but with the same selection and mutation methods as CGP gave equivalent performance to CGP.
Meier et al. interpreted the RVCGP genes as mean values in a multivariate Gaussian distribution [63]. From these distributions new genotypes can be sampled. They defined an operator called forking which decides whether a genotype should be interpreted either as a point or as a distribution in genotype space. The decision to fork uses population statistics based on an analysis of phenotypes (called fingerprints). Early in evolution an individual’s phenotype is likely to be rare in the population, in which case the forking operator is more likely to interpret the individual as a point. As evolution progresses, individuals focus on fewer regions so that the current individual’s phenotype may be shared by other individuals. In this case, its phenotype fingerprint frequency increases and the forking operator will be more likely to interpret the current individual as a distribution, so that sampling happens more frequently. They evaluated their approach on four symbolic regression problems and found the forking operator reduced the number of generations to converge to high fitness and the computation time per run, as compared with standard RVCGP.
Walker et al. modified the RVCGP representation to encode transistor circuits [121]. Six floating point genes were used to specify each CGP node. Four genes defined the transistor characteristics while two specify the node inputs. A three-stage genotype to phenotype map** was employed to obtain a valid circuit simulator netlists that could be simulated using the SPICE simulator.
Wilson et al. used a recursive variant of the real-valued representation to evolve highly effective Atari game playing agents in [125]. In addition, each node also had a parameter gene which used used by some node functions and was also used to weight the node output (as used in [52]).
3.4 Implicit context
In the Sect. 2 we saw that in CGP all nodes and inputs have an address which expresses where they are positioned in the genotype. Lones created a form of GP called enzyme GP in which the structure of a program is not given explicitly (as in most forms of GP) but is derived from connection choices made by each component of the program in a bottom-up fashion. He argued that in biological genomes the location of genes is relatively unimportant and criticized GP systems for being positionally dependent [60]. However, this point of view is at best debatable since some biological studies indicate that genes are located in positional neighbourhoods [12]. Furthermore, it has been discovered that a gene’s location in a chromosome does play a significant role in sha** how an organism’s traits vary and evolve [84].
Smith et al. [95] adopted many aspects of Enzyme GP and proposed a new representation of CGP called implicit context CGP (ICCGP). In enzyme GP and ICCGP program nodes are called enzymes. Each enzyme has a type (referred as ‘activity’), a number of binding vectors (\(\underline{b_1}\), \(\underline{b_2}\)), an output vector called a shape, \(\underline{s}\) and a function gene (see Fig. 2). The elements of the vectors are integers in the range 0 to 255 (though in some implementations real numbers between 0 and 1 are used). Type merely indicates whether the enzyme is a program input, computational node or a program output. The number of elements that a binding or shape vector have is given by the sum of the number of external program inputs, \(n_i\) and the number of possible computational functions in the function look-up table, \(n_f\).
As with CGP, the number of bindings (inputs) an enzyme has, is defined by the the arity of the enzyme function. Enzyme’s of type 0 have only a shape as these represent external inputs and enzyme’s of type 2 only have a single binding vector as these represent external outputs. An enzyme’s shape is defined as:
where \(\underline{f}\) is a vector of the same length as the binding vectors, but whose only non-zero element is 255 at position \(n_i+f\) where f is the enzyme’s function gene. The multiplying constants ensure that the elements of the shape vector are in the range 0 to 255. The idea behind shape is that it represents the affinity that a component has to form connections with other components.
Genes are initialised randomly. An assembly process creates the phenotype. It starts at the type 2 enzymes (i.e. outputs). These bind to other enzymes (types 0 or 1). Binding is how connections between computational nodes occur. The binding vectors define whether and how strongly an enzyme can bind to another enzyme’s shape. This is determined by the degree of matching between the binding of one enzyme with the shape of another. Input enzymes have a shape, outputs a single input binding. Connections between enzymes, inputs and outputs are determined by which bindings form the strongest match with shapes. The smallest difference between the elements of the binding vector and shape indicates the strongest match. Construction of the phenotype is similar to standard CGP. It begins with outputs binding to component or input shapes. Then these components bind and so on, until all enzyme’s are bound. At this point a CGP-like phenotype can be obtained. The genotype has \(L_{iccgp}=(n_i+n_n+n_o)(n_i+n_f)\) elements. Genotypes are mutated via point mutation and bindings and enzyme functions can be mutated at different rates.
The length of the genotype representation in ICCGP is much greater than in CGP as each enzyme has \((n_i+n_f)\) elements compared with \(n_a+1\) in CGP. For instance, suppose we choose 100 nodes or enzymes (a modest figure in CGP). Assume also that the problems we are trying to solve have many inputs (e.g. Boolean circuits with say 50 inputs and five outputs) and there are many possible node functions (say 16) then the genotype length would be \((50+100+5)(50+16) = 10{,}230\) genes compared with 305 in standard GP! As a consequence, ICCGP has only been applied with a very modest numbers of enzymes.
To date, as far as the author is aware, there has been only a single comparison of the computational efficiency of ICCGP with CGP and this was in the very limited context of the three input parity function over a range of rectangular topology parameters [8]. Thus, it remains unclear whether ICCGP offers any computational benefits. Despite this ICCGP has been extensively and successfully applied to various problems in medical diagnostics [56, 58, 59, 93, 94, 96,97,98].
3.5 Self-modifying
Self-modifying CGP introduced another type of node, a self-modifying (SM) node, one that refers to the code itself [26, 28, 29]. Such nodes modify the phenotype. For instance, a node may be a deletion operation, which deletes CGP nodes between two positions in the phenotype. Such operations imply that the phenotype is iterated in something akin to a developmental process. The process is as follows. The genotype is first duplicated to create the first phenotype. So here phenotypes mean genotype-like strings of numbers in the same format as CGP. The active self-modification nodes in the phenotype are applied one after the other to produce a new phenotype. This process defines one iteration. This is repeated until either there are no SM nodes in a phenotype or until a user-defined limit on the number of iterations is reached.
The presence of SM nodes makes it more appropriate to replace absolute node addressing as in standard CGP with relative addressing. The latter is where connection genes count back from the node position. In addition, functions were introduced that provided external inputs (via a circular register) or wrote calculations to external outputs. This was done so that SM operations could change the number of inputs and outputs. SM nodes also require parameters which dictate where they operate in the phenotype (i.e. copy nodes between n and m and insert them at position p).
SMCGP can produce a sequence of phenotypes, each of which could solve a different computational problem (e.g. produce a series of parity functions of increasing number of inputs). This allows SMCGP to be applied to classes of problems that non-developmental encodings can not solve. Indeed, it has been shown that SMCGP could find provably general solutions to certain classes of problems: parity, binary addition [26], computation of \(\pi\) and e [27]
It is interesting to note that even without the presence of SM nodes, SMCGP introduced a possible modification of the standard CGP genotype representation (relative addressing and input/output functions). This was actually used in place of CGP in a number of papers [23, 24, 55]. However, to date, there has been no quantitative comparative studies of the two CGP representations and their efficacy.
3.6 Mixed-type
Harding et al. [23] introduced a form of CGP called mixed-type CGP (MTCGP) in which the data which flowed through the CGP graphs could have different types. In MTCGP node functions inspect the types of the input values being passed to it, and determine the most suitable operation to perform. This in turn determines the output type of the function. Node functions return a default value in cases where there is no suitable operation for the types being passed to the function. In MTCGP inputs can be variable length vectors of reals or individual values. Since MTCGP can handle multiple and mixed data types it allows a much wider range of node functions to be used. They used relative addressing and input gathering and output producing functions (as in SMCGP).
MTCGP was applied to a number of classification tasks in the UCI Machine learning repository: Wisconsin breast cancer, phoneme, diabetes, and heart datasets. For each of the classification tasks, the inputs presented to the program were both the entire attribute vector as well as the individual attribute values of the vector. They used a large set of primitive functions ranging over list processing, mathematical and statistical and compared results with a suite of well-known classification methods producing highly respectable results. Often also, the evolved CGP programs were very small and readable.
Wilson et al. in their work on evolving human-readable Atari game playing programs, extended multiple data types handling node functions to include also a matrix type [125].
3.7 Recurrent
CGP is usually described as a representation of acyclic graphs. However, it is straightforward to extend it to recurrent or cyclic graphs [108, 109]. To do this, the restriction that connection genes of a node must have values less than its position is lifted, so that it can connect to itself and any other node. The genotype is decoded in a very similar way to standard CGP to produce a list of active nodes. First the active nodes need to be determined. This can be done recursively from output to inputs in the usual way for CGP except that one only adds new nodes to the active list, not ones already present (this breaks cycles). After this the following steps are carried out
- 1.
set all active nodes to output zero
- 2.
apply the next set of program inputs
- 3.
update all active nodes once from program inputs to program outputs
- 4.
read the program outputs
- 5.
repeat from 2 until all program input sets have been applied.
Of course, in step 3 one could choose to update active nodes more than once and use some function of the output values (i.e. the average). However, there would always be the issue of when to stop.
To control the numbers of recurrent versus non-recurrent connections, Turner et al. introduced a additional parameter called recurrent connection probability which controlled the likelihood of recurrent and non-recurrent connections. The performance of RCGP was compared with CGP on a number of benchmarks [108], the Artificial Ant, Sunspot prediction and a number of integer sequences [109]. In all cases RCGP outperformed CGP significantly. In addition RCGP outperformed various published methods for the Fibonacci sequence. RCGP should be regarded as “standard” CGP in that when the recurrent connection probability is zero it becomes the original form of CGP.
3.8 Iterative
In iterative CGP (ICGP) conditional cyclic loops can be represented [86]. To accomplish this a linear CGP geometry is assumed (i.e. one row and multiple columns) with levels-back set to be the number of columns. All nodes have four genes. The first gene is a node function gene, the next two are connection genes and the last gene represents a Boolean condition which determines whether a loop should be continued or terminated. The first connection of a node always refers to a node previous to the node (i.e. a standard feed-forward CGP connection). The second connection gene is either ignored or represents a cycle. The gene is ignored if it refers to a previous node or input. However, it may refer to a subsequent node (or itself) in which case it defines a loop. The nodes between the position of the calling node and the forward connection are then in a cycle. The condition gene is an address in a look-up table of possible loop exit conditions. If it exits then the next instruction is decided by the node immediately after the end of the loop, if it does not exit it executes the instruction in the next node on the right. There is a single output gene (\(O_A\)) which points to the last executed node (10). An example genotype is shown in Fig. 3.
In the example, the nodes are executed in the following order: 1, 2, 3, 6, 7, 2, 8, 1, 9, 10. We have assumed that on the second call of node 2, condition 1 is met, so execution passes to the next node after the loop (node 8) and thence to 1. We also have assumed in this example that loop condition of node 1 (2) is also met thus causing program execution to move to the next node (9) after the loop terminates at node (8). There are some rules required to enforce valid loops:
- 1.
For any nodes inside an existing loop, branching genes can only connect to either any previous node or input (acyclic) or a node with a higher index that is inside the current loop (cyclic). For instance, in Fig. 3, the branching gene of nodes 3–6 can be valid if its value is lower than 7. However, any branching genes greater than the node label would create loops within the already existing loop starting at node 2 and ending at node 7.
- 2.
For any nodes outside an existing loop, their branching genes can only connect to a node that is outside any existing loops. For instance, because the nodes 2–7 are already in a loop, the branching gene of node 1 can only point to either the input or nodes 8, 9, or 10.
Ryser-Welch applied iterative CGP to three classes of problems: travelling salesman, mimicry and nurse-rostering [85, 86]. For these problems, the node operations were very sophisticated and applied existing heuristic algorithms rather than merely a mathematical function of input data. In this way it was shown that new human-readable, standalone problem-solving algorithms could be produced.
3.9 Differentiable CGP
Genetic programming is normally considered as a derivative-free method, however in an impressive paper Izzo et al. [33] show how it is possible to obtain a complete representation of the differential properties of a program encoded by a genetic programming expression. They applied this to CGP creating a new form of it called called differentiable CGP (dCGP). In dCGP all connections have weights (like artificial neural networks) and node functions are represented as truncated Taylor expansions of a given order. They show that this allows arithmetic operators +, −, *, / to be extended to operate on truncated Taylor expansions. For instance, using this idea they show that a CGP encoded function \(O_0 =sigmoid(yz+1)/x\) can be written also as second order Taylor expansion of differentials,
The dCGP approach means that not only can the output function of a CGP program be computed at a given point but also all its derivatives up to a given order. Their approach makes it possible to apply concepts such a back propagation to CGP encoded programs.
They evaluate the dCGP technique on a suite of varied symbolic regression problems in which \(\pi\) and e appear. Newton’s method was used to back-propagate the errors on ephemeral constants in evolved expressions to determine the constants in the Taylor expansions. The fitness is the final error. They showed that they could evolve the target formulae exactly (with all weights set to 1). However, they note a drawback to this method: the number of ephemeral constants used as additional terminals needs to be pre-determined. However, by associating weights to every edge of the graph, the differential properties of the error with respect to weights can be determined. This allows symbolic regression to be carried out with no extra terminal inputs but the values for all the weights has to be determined. Since there can be many weights, the dCGP method selects random weights and then iteratively back-propagates the errors. They used a \(1+4\) evolutionary strategy to evolve the dCGP expression and interestingly, each offspring, \(i = 1\) to 4 received i mutations. They also showed that dCGP could be applied to solve partial, ordinary differential equations and to search for expressions that are prime integrals of sets of differential equations
3.10 Graph programming
Recently, an interesting new method of evolving graphs has been proposed. It is called evolving graphs by graph programming (EGGP) [7]. This method evolves graphs directly rather than using linear or grid-based genotypes. Using a probabilistic extension to the graph programming language, GP2, Atkinson et al. are able to evolve graphs. They show firstly that any CGP individual can be represented as an EGGP individual, whereas the converse may not always hold when the number of rows in a CGP individual is greater than one. Secondly they note that some feed-forward preserving mutations in EGGP are not possible in the standard form of CGP. Figure 4 shows how an allowable mutation in EGGP is not allowed in CGP. The EGGP approach is shown to significantly out-perform CGP on a collection of circuit benchmarks (particularly the harder benchmarks).
However, it should be noted that since recurrent CGP allows both feedforward and feedback connections the mutations which are illegal in standard CGP but possible in EGGP are also legal in recurrent GP. It may also be possible to introduce a new mutation operator to make these currently illegal mutations possible in standard CGP.
3.11 Positional CGP
Positional CGP [\(i_n\) but are constrained to the interval \([-1, 0]\). Output genes do not have positions and take values in the interval [0, 1]. A small example of the PCGP representation is shown in Fig. 5.
Notes
Berkley Logic Synthesis and Verification Group: ABC: A System for Sequential Synthesis and verification. http://www.eecs.berkeley.edu/*alanmi/abc/.
This was a competition at the 2012 International Conference on Pattern Recognition (ICPR).
caret: Classification and Regression Training, 2014. R package version 6.0-37.
To obtain a permutation from an indexed vector of real-numbers one merely has to sort the numbers and the re-arranged indexes form a permutation.
References
A.M. Ahmad, G.M. Khan, Bio-signal processing using Cartesian genetic programming evolved artificial neural network (CGPANN), in 2012 10th International Conference on Frontiers of Information Technology (FIT) (IEEE, 2012), pp. 261–268
A.M. Ahmad, G.M. Khan, S.A. Mahmud, Classification of arrhythmia types using Cartesian genetic programming evolved artificial neural networks, in Engineering Applications of Neural Networks, ed. by L. Iliadis, C. Jayne (Springer, Berlin, 2013), pp. 282–291
A.M. Ahmad, G.M. Khan, S.A. Mahmud, Classification of mammograms using Cartesian genetic programming evolved artificial neural networks, in AIAI, IFIP Advances in Information and Communication Technology, vol. 436 (Springer, 2014), pp. 203–213
A.M. Ahmad, G.M. Khan, S.A. Mahmud, J.F. Miller, Breast cancer detection using Cartesian genetic programming evolved artificial neural networks, in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (2012), pp. 1031–1038
J. Ali, F. Zafari, G.M. Khan, S.A. Mahmud, Future clients’ requests estimation for dynamic resource allocation in cloud data center using CGPANN, in 2013 12th International Conference on Machine Learning and Applications (ICMLA), vol. 2 (IEEE, 2013), pp. 331–334
H. Alyasiri, J. Clark, D. Kudenko, Applying Cartesian genetic programming to evolve rules for intrusion detection system, in Proceedings of the 10th International Joint Conference on Computational Intelligence—Volume 1: IJCCI (SciTePress, 2018), pp. 176–183
T. Atkinson, D. Plump, S. Stepney, Evolving graphs by graph programming, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 10781 (2018), pp. 35–51
X. Cai, S.L. Smith, A.M. Tyrrell, Positional independence and recombination in Cartesian Genetic programming, in European Conference on Genetic Programming, LNCS, vol. 3905 (2006), pp. 351–360
M. Češka, J. Matyáš, V. Mrazek, L. Sekanina, Z. Vašíček, T. Vojnar, Approximating complex arithmetic circuits with formal error guarantees: 32-bit multipliers accomplished, in Proceedings of the 36th International Conference on Computer-Aided Design, ICCAD ’17 (IEEE Press, 2017), pp. 416–423
J. Clegg, J.A. Walker, J.F. Miller, A new crossover technique for Cartesian genetic programming, in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (ACM, 2007), pp. 1580–1587
K.D. Clegg, J.F. Miller, K. Massey, M. Petty, Travelling salesman problem solved ‘in materio’ by evolved carbon nanotube device, in Parallel Problem Solving from Nature—PPSN XIII (Springer, 2014), pp. 692–701
S. De, M. Babu, Genomic neighbourhood and the regulation of gene expression. Curr. Opin. Cell Biol. 22, 326–333 (2010)
K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, in Parallel Problem Solving from Nature PPSN VI, LNCS, vol. 1917 (2000), pp. 849–858
M. Drahošová, L. Sekanina, M. Wiglasz, Adaptive fitness predictors in coevolutionary Cartesian genetic programming. Evolut. Comput. 26(4), 1–27 (2018)
I. Dzalbs, T. Kalganova, Multi-step ahead forecasting using Cartesian genetic programming, in Inspired by Nature: Essays PresInspired by Nature: Essays Presented to Julian F. Miller on the Occasion of his 60th Birthday, ed. by S. Stepney, A. Adamatzky (Springer, Berlin, 2018), pp. 235–246
Z. Gajda, L. Sekanina, An efficient selection strategy for digital circuit evolution, in Evolvable Systems: From Biology to Hardware, LNCS, vol. 6274 (2010), pp. 13–24
A.B. Garmendia-Doval, J.F. Miller, S.D. Morley, Cartesian genetic programming and the post docking filtering problem, in Genetic Programming Theory and Practice II, ed. by U.M. O’Reilly, T. Yu, R. Riolo, B. Worzel (Springer, New York, 2005), pp. 225–244
B.W. Goldman, W.F. Punch, Length bias and search limitations in Cartesian genetic programming, in Proceeding of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference (ACM, 2013), pp. 933–940
B.W. Goldman, W.F. Punch, Reducing wasted evaluations in Cartesian genetic programming, in Proceedings of the European Conference on Genetic Programming, vol. 7831 (Springer, 2013), pp. 61–72
B.W. Goldman, W.F. Punch, Analysis of Cartesian genetic programming’s evolutionary mechanisms. IEEE Trans. Evolut. Comput. 19(3), 359–373 (2015)
N. Hansen, A. Ostermeier, Completely derandomized self-adaptation in evolution strategies. Evolut. Comput. 9(2), 159–195 (2001)
S. Harding, W. Banzhaf, Fast genetic programming on GPUS, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 4445 (2007), pp. 90–101
S. Harding, V. Graziano, J. Leitner, J. Schmidhuber, MT-CGP: mixed type Cartesian genetic programming, in Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference (ACM, 2012), pp. 751–758
S. Harding, J. Leitner, J. Schmidhuber, Genetic Programming Theory and Practice X. Cartesian Genetic Programming for Image Processing (Springer, Berlin, 2013), pp. 31–44
S. Harding, J.F. Miller, Cartesian Genetic Programming on the GPU (Springer, Berlin, 2013), pp. 249–266
S. Harding, J.F. Miller, W. Banzhaf, Developments in Cartesian genetic programming: self-modifying CGP. Genet. Program. Evolvable Mach. 11(3–4), 397–439 (2010)
S. Harding, J.F. Miller, W. Banzhaf, Self modifying Cartesian genetic programming: finding algorithms that calculate pi and e to arbitrary precision, in Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (ACM, 2010), pp. 579–586
S.L. Harding, J.F. Miller, W. Banzhaf, Self-modifying Cartesian genetic programming, in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO ’07 (2007), pp. 1021–1028
S.L. Harding, J.F. Miller, W. Banzhaf, Self-Modifying Cartesian Genetic Programming (Springer, Berlin, 2011), pp. 101–124
R. Hrbacek, V. Dvorak, Bent function synthesis by means of Cartesian genetic programming, in Parallel Problem Solving from Nature—PPSN XIII, ed. by T. Bartz-Beielstein, J. Branke, B. Filipič, J. Smith (Springer, Berlin, 2014), pp. 414–423
R. Hrbacek, M. Šikulová, Coevolutionary Cartesian genetic programming in FPGA, in Proceedings of the Conference on Artificial Life (2013), pp. 431–438
J. Husa, R. Kalkreuth, A comparative study on crossover in Cartesian genetic programming, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 10781 (2018), pp. 203–219
D. Izzo, F. Biscani, A. Mereta, Differentiable genetic programming, in Proceedings of the European Conference on Genetic Programming, Lecture Notes in Computer Science, vol. 10196 (2017), pp. 35–51
R. Kalkreuth, Towards Advanced Phenotypic Mutations in Cartesian Genetic Programming (2018). CoRR ar**v:abs/1803.06127
R. Kalkreuth, G. Rudolph, A. Droschinsky, A new subgraph crossover for Cartesian genetic programming, in Proceedings of the European Conference Genetic Programming, LNCS, vol. 10196 (2017), pp. 294–310
R. Kalkreuth, G. Rudolph, J. Krone, Improving convergence in Cartesian genetic programming using adaptive crossover, mutation and selection, in 2015 IEEE Symposium Series on Computational Intelligence (2015), pp. 1415–1422
P. Kaufmann, R. Kalkreuth, Parametrizing Cartesian genetic programming: an empirical study, in KI 2017: Advances in Artificial Intelligence, LNCS, vol. 10505 (2017), pp. 316–322
P. Kaufmann, M. Platzner, Advanced techniques for the creation and propagation of modules in Cartesian genetic programming, in Proceedings of the Conference on Genetic and Evolutionary Computation (2008), pp. 1219–1226
P. Kaufmann, M. Platzner, Combining local and global search: a multi-objective evolutionary algorithm for Cartesian genetic programming, in Inspired by Nature: Essays Presented to Julian F. Miller on the Occasion of his 60th Birthday, ed. by S. Stepney, A. Adamatzky (Springer, Berlin, 2018), pp. 175–194
G.M. Khan, Evolution of Artificial Neural Development—In Search of Learning Genes, Studies in Computational Intelligence, vol. 725 (Springer, Berlin, 2018)
G.M. Khan, S. Khan, F. Ullah, Short-term daily peak load forecasting using fast learning neural network, in 2011 11th International Conference on Intelligent Systems Design and Applications (ISDA) (IEEE, 2011), pp. 843–848
G.M. Khan, A.R. Khattak, F. Zafari, S.A. Mahmud, Electrical load forecasting using fast learning recurrent neural networks, in The 2013 International Joint Conference on Neural Networks (IJCNN) (IEEE, 2013), pp. 1–6
G.M. Khan, J.F. Miller, D.M. Halliday, Evolution of Cartesian genetic programs for development of learning neural architecture. Evolut. Comput. 19(3), 469–523 (2011)
G.M. Khan, F. Ullah, S.A. Mahmud, MPEG-4 internet traffic estimation using recurrent CGPANN, in Engineering Applications of Neural Networks, ed. by L. Iliadis, H. Papadopoulos, C. Jayne (Springer, Berlin, 2013), pp. 22–31
G.M. Khan, F. Zafari, S.A. Mahmud, Very short term load forecasting using Cartesian genetic programming evolved recurrent neural networks (CGPRNN), in 2013 12th International Conference on Machine Learning and Applications (ICMLA), vol. 2 (IEEE, 2013), pp. 152–155
M.M. Khan, A.M. Ahmad, G.M. Khan, J.F. Miller, Fast learning neural networks using Cartesian genetic programming. Neurocomputing 121, 274–289 (2013)
M.M. Khan, S.K. Chalup, A. Mendes, Parkinson’s disease data classification using evolvable wavelet neural networks, in Proceedings of Second Australasian Conference on Artificial Life and Computational Intelligence (2016), pp. 113–124
M.M. Khan, G.M. Khan, J.F. Miller, Evolution of neural networks using Cartesian genetic programming, in Proceedings of the IEEE Congress on Evolutionary Computation, CEC (2010), pp. 1–8
M.M. Khan, G.M. Khan, J.F. Miller, Evolution of optimal ANNs for non-linear control problems using Cartesian genetic programming, in Proceedings of the 2010 International Conference on Artificial Intelligence (2010), pp. 339–346
M.M. Khan, A. Mendes, P. Zhang, S.K. Chalup, Evolving multi-dimensional wavelet neural networks for classification using Cartesian genetic programming. Neurocomputing 247, 39–58 (2017)
N.M. Khan, G.M. Khan, Audio signal reconstruction using Cartesian genetic programming evolved artificial neural network (CGPANN), in ICMLA (IEEE, 2017), pp. 568–573
K. Knezevic, S. Picek, J.F. Miller, Amplitude-oriented mixed-type CGP classification, in Proceedings of the Genetic and Evolutionary Computation Conference Companion (2017), pp. 1415–1418
J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, Cambridge, 1992)
J.R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs (MIT Press, Cambridge, 1994)
J. Leitner, S. Harding, A. Förster, J. Schmidhuber, Mars terrain image classification using Cartesian genetic programming, in 11th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS) (2012)
M. Lones, J.E. Alty, P. Duggan-Carter, A.J. Turner, D.R. Jamieson, S.L. Smith, Classification and characterisation of movement patterns during levodopa therapy for Parkinson’s disease, in Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO Comp ’14 (2014), pp. 1321–1328
M.A. Lones, J.E. Alty, J. Cosgrove, P. Duggan-Carter, S. Jamieson, R.F. Naylor, A.J. Turner, S.L. Smith, A new evolutionary algorithm-based home monitoring device for Parkinson’s dyskinesia. J. Med. Syst. 41(11), 176 (2017)
M.A. Lones, S.L. Smith, J.E. Alty, S.E. Lacy, K.L. Possin, D.S. Jamieson, A.M. Tyrrell, Evolving classifiers to recognize the movement characteristics of Parkinson’s disease patients. IEEE Trans. Evolut. Comput. 18(4), 559–576 (2014)
M.A. Lones, S.L. Smith, A.T. Harris, A.S. High, S.E. Fisher, D.A. Smith, J. Kirkham, Discriminating normal and cancerous thyroid cell lines using implicit context representation Cartesian genetic programming, in IEEE Congress on Evolutionary Computation (2010), pp. 1–6
M.A. Lones, A.M. Tyrrell, Biomimetic representation with enzyme genetic programming. Genet. Program. Evolvable Mach. 3(3), 315–315 (2002)
M. Lopez-Ibanez, J. Dubois-Lacoste, L.P. Cáceres, M. Birattari, T. Stützle, The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016)
A. Manazir, K. Raza, Recent developments in Cartesian genetic programming and its variants. ACM Comput. Surv. 51(6), 122:1–122:29 (2019)
A. Meier, M. Gonter, R. Kruse, Accelerating convergence in Cartesian genetic programming by using a new genetic operator, in Proceeding of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference (ACM, 2013), pp. 981–988
N. Milano, P. Pagliuca, S. Nolfi, Robustness, Evolvability and Phenotypic Complexity: Insights from Evolving Digital Circuits (2017). ar**v:1712.04254
J.F. Miller, An empirical study of the efficiency of learning Boolean functions using a Cartesian genetic programming approach, in Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2 (1999), pp. 1135–1142
J.F. Miller, What bloat? Cartesian genetic programming on Boolean problems, in 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers (2001), pp. 295–302
J.F. Miller, Chapter 8: Neuro-centric and holocentric approaches to the evolution of developmental neural networks, in Growing Adaptive Machines: Combining Development and Learning in Artificial Neural Networks, ed. by T. Kowaliw, N. Bredeche, R. Doursat (Springer, Berlin, 2014), pp. 227–249
J.F. Miller, M. Mohid, Function optimization using Cartesian genetic programming, in Proceeding of the fifteenth annual conference companion on Genetic and evolutionary computation conference companion (ACM, 2013), pp. 147–148
J.F. Miller, S. Smith, Redundancy and computational efficiency in Cartesian genetic programming. IEEE Trans Evolut. Comput. 10(2), 167–174 (2006)
J.F. Miller, P. Thomson, Cartesian genetic programming, in Proceedings of the European Conference on Genetic Programming, vol. 1820 (Springer, 2000), pp. 121–132
J.F. Miller, P. Thomson, T. Fogarty, Chapter 6: Designing electronic circuits using evolutionary algorithms. Arithmetic circuits: a case study, in Genetic Algorithms and Evolution Strategies in Engineering and Computer Science: Recent Advancements and Industrial Applications, ed. by D. Quagliarella, J. Periaux, C. Poloni, G. Winter (Wiley, Hoboken, 1997)
J.F. Miller, D.G. Wilson, S. Cussat-Blanc, Chapter 8: Evolving developmental programs that build neural networks for solving multiple problems, in Genetic Programming Theory and Practice XVI, ed. by W. Banzhaf, L. Spector, L. Sheneman (Springer, Berlin, 2019), pp. 137–176
R. Miragaia, G. Reis, F. Fernandéz, T. Inácio, C. Grilo, CGP4Matlab—a Cartesian genetic programming MATLAB toolbox for audio and image processing, in Applications of Evolutionary Computation, LNCS, vol. 10784 (Springer, 2018), pp. 455–471
P.C.D. Paris, E.C. Pedrino, M.C. Nicoletti, Automatic learning of image filters using Cartesian genetic programming. Integr. Comput. Aided Eng. 22(2), 135–151 (2015)
S. Picek, C. Carlet, S. Guilley, J.F. Miller, D. Jakobovic, Evolutionary algorithms for Boolean functions in diverse domains of cryptography. Evolut. Comput. 24(4), 667–694 (2016)
S. Picek, D. Jakobovic, J.F. Miller, L. Batina, M. Cupic, Cryptographic Boolean functions. Appl. Soft Comput. 40(C), 635–653 (2016)
R. Poli, Parallel distributed genetic programming. Technical Report CSRP-96-15, Department of Computer Science, University of Birmingham, UK (1996)
R. Poli, Some steps towards a form of parallel distributed genetic programming, in Proceedings of the First On-line Workshop on Soft Computing (1996), pp. 290–295
R. Poli, Parallel distributed genetic programming, in New Ideas in Optimization, ed. by M. Dorigo, D. Corne, F.W. Glover (McGraw-Hill Ltd., London, 1999), pp. 403–432
R. Poli, W.B. Langdon, McN.F. Phee, A field guide to genetic programming (2008). Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk. Accessed Apr 2019
J. Pujol, R. Poli, Evolving the topology and the weights of neural networks using a dual representation. Appl. Intell. 8(1), 73–84 (1998)
N.J. Radcliffe, Equivalence class analysis of genetic algorithms. Complex Syst. 5, 183–205 (1991)
I. Rechenberg, Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Ph.D. Thesis, Technical University of Berlin, Germany (1971)
M.V. Rockman, S.S. Skrovanek, L. Kruglyak, Selection at linked sites shapes heritable phenotypic variation in C. elegans. Science 330(6002), 372–376 (2010)
P. Ryser-Welch, Evolving comprehensible and scalable solvers using CGP for solving some real-world inspired problems. Ph.D. Thesis, Department of Electronic Engineering, University of York (2017). http://etheses.whiterose.ac.uk/19011/1/finalThesisv3.pdf. Accessed Apr 2019
P. Ryser-Welch, J.F. Miller, J. Swan, M.A. Trefzer, Iterative Cartesian genetic programming: creating general algorithms for solving travelling salesman problems, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 9594 (2016), pp. 294–310
L. Sekanina, Image filter design with evolvable hardware, in Applications of Evolutionary Computing, LNCS, vol. 2279, ed. by S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G.R. Raidl (Springer, Berlin, 2002), pp. 255–266
L. Sekanina, S.L. Harding, W. Banzhaf, T. Kowaliw, Image Processing and CGP (Springer, Berlin, 2011), pp. 181–215
M. Shafique, R. Hafiz, M.U. Javed, S. Abbas, L. Sekanina, Z. Vašíček, V. Mrazek, Adaptive and energy-efficient architectures for machine learning: challenges, opportunities, and research roadmap, in 2017 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) (2017), pp. 627–632
M. Šikulová, L. Sekanina, Coevolution in Cartesian genetic programming, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 7244 (2012), pp. 182–193
S. Silva, E. Costa, Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories. Genet. Program. Evolvable Mach. 10(2), 141–179 (2009)
D. Simon, Biogeography-based optimization. IEEE Trans. Evolut. Comput. 12, 702–713 (2008)
S.L. Smith, Cartesian genetic programming and its application to medical diagnosis. IEEE Comput. Intell. Mag. 6(4), 56–67 (2011)
S.L. Smith, P. Gaughan, D.M. Halliday, Q. Ju, N.M. Aly, J.R. Playfer, Diagnosis of Parkinson’s disease using evolutionary algorithms. Genet. Program. Evolvable Mach. 8(4), 433–447 (2007)
S.L. Smith, S. Leggett, A.M. Tyrrell, An implicit context representation for evolving image processing filters. Appl. Evolut. Comput. 3449, 407–416 (2005)
S.L. Smith, M.A. Lones, Medical applications of Cartesian genetic programming, in Inspired by Nature: Essays Presented to Julian F. Miller on the Occasion of his 60th Birthday, ed. by S. Stepney, A. Adamatzky (Springer, Berlin, 2018), pp. 247–266
S.L. Smith, M.A. Lones, M. Bedder, J.E. Alty, R. Cosgrove, R.J. Maguire, M.E. Pownall, D. Ivanoiu, C. Lyle, A. Cording, C.J. Elliott, Computational approaches for understanding the diagnosis and treatment of Parkinson’s disease. IET Syst. Biol. 9(6), 226–23 (2015)
S.L. Smith, J.A. Walker, J.F. Miller, Medical Applications of Cartesian Genetic Programming (Springer, Berlin, 2011), pp. 309–336
M. Suganuma, S. Shirakawa, T. Nagao, A genetic programming approach to designing convolutional neural network architectures, in Proceedings of the Genetic and Evolutionary Computation Conference (2017), pp. 497–504
H. Tizhoosh, Opposition-based learning: a new scheme for machine intelligence, in Proceedings of International Conference on Computational Intelligence for Modeling Control and Automation, vol. 1 (2005), pp. 695–701
A.J. Turner, Improving crossover techniques in a genetic program. Masters Thesis, Department of Electronics, University of York (2012). http://www.andrewjamesturner.co.uk. Accessed Apr 2019
A.J. Turner, Evolving artificial neural networks using Cartesian genetic programming. Ph.D. Thesis, Department of Electronic Engineering, University of York (2017). http://etheses.whiterose.ac.uk/12035/. Accessed Apr 2019
A.J. Turner, J.F. Miller, Cartesian genetic programming encoded artificial neural networks: a comparison using three benchmarks, in Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO-13) (2013), pp. 1005–1012
A.J. Turner, J.F. Miller, The importance of topology evolution in neuroevolution: a case study using Cartesian genetic programming of artificial neural networks, in Research and Development in Intelligent Systems XXX, ed. by M. Bramer, M. Petridis (Springer, Berlin, 2013), pp. 213–226
A.J. Turner, J.F. Miller, Cartesian genetic programming: Why no bloat?, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 8599 (2014), pp. 193–204
A.J. Turner, J.F. Miller, Introducing a cross platform open source Cartesian genetic programming library. Genet. Program. Evolvable Mach. 16(1), 83–91 (2014)
A.J. Turner, J.F. Miller, NeuroEvolution: the importance of transfer function evolution and heterogeneous networks, in Proceedings of the 50th Anniversary Convention of the AISB (2014), pp. 158–165
A.J. Turner, J.F. Miller, Recurrent Cartesian genetic programming, in 13th International Conference on Parallel Problem Solving from Nature (PPSN 2014), LNCS, vol. 8672 (2014), pp. 476–486
A.J. Turner, J.F. Miller, Recurrent Cartesian genetic programming applied to famous mathematical sequences, in Proceedings of the Seventh York Doctoral Symposium on Computer Science & Electronics (2014), pp. 37–46
A.J. Turner, J.F. Miller, Neutral genetic drift: an investigation using Cartesian genetic programming. Genet. Program. Evolvable Mach. 16(4), 531–558 (2015)
A.J. Turner, J.F. Miller, Recurrent Cartesian genetic programming of artificial neural networks. Genet. Program. Evolvable Mach. 18(2), 185–212 (2017)
Z. Vašíček, Bridging the gap between evolvable hardware and industry using Cartesian genetic programming, in Inspired by Nature: Essays Presented to Julian F. Miller on the Occasion of his 60th Birthday, ed. by S. Stepney, A. Adamatzky (Springer, Berlin, 2018), pp. 39–55
Z. Vašíček, L. Sekanina, Hardware accelerators for Cartesian genetic programming, in Proceedings of the European Conference on Genetic Programming, LNCS, vol. 4971 (2008), pp. 230–241
Z. Vašíček, L. Sekanina, Hardware accelerator of Cartesian genetic programming with multiple fitness units. Comput. Inform. 29, 1359–1371 (2010)
Z. Vašíček, L. Sekanina, Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware. Genet. Program. Evolvable Mach. 12(3), 305–327 (2011)
Z. Vašíček, L. Sekanina, Evolutionary approach to approximate digital circuits design. IEEE Trans. Evolut. Comput. 19(3), 432–444 (2015)
Z. Vašíček, L. Sekanina, Evolutionary design of complex approximate combinational circuits. Genet. Program. Evolvable Mach. 17(2), 169–192 (2016)
V.K. Vassilev, J.F. Miller, Embedding landscape neutrality to build a bridge from the conventional to a more efficient three-bit multiplier circuit, in Proceedings of the Genetic and Evolutionary Computation Conference (2000), p. 539. http://cartesiangp.com/julian-miller. Accessed Apr 2019
V.K. Vassilev, J.F. Miller, The advantages of landscape neutrality in digital circuit evolution, in Proceedings of International Conference on Evolvable Systems, LNCS, vol. 1801 (Springer, 2000), pp. 252–263
Z. Vašíček, Cartesian GP in optimization of combinational circuits with hundreds of inputs and thousands of gates, in Proceedings of European Conference on Genetic Programming, LNCS, vol. 9025 (2015), pp. 139–150
J.A. Walker, J.A. Hilder, A.M. Tyrrell, Evolving variability-tolerant CMOS designs, in Evolvable Systems: From Biology to Hardware, LNCS, vol. 5216, ed. by M. Sipper, D. Mange, A. Pérez-Uribe (Springer, Berlin, 2008), pp. 308–319
J.A. Walker, J.F. Miller, Evolution and acquisition of modules in Cartesian genetic programming, in Proceedings of European Conference on Genetic Programming, vol. 3003 (2004), pp. 187–197
J.A. Walker, J.F. Miller, The automatic acquisition, evolution and reuse of modules in Cartesian genetic programming. IEEE Trans. Evolut. Comput. 12(4), 397–417 (2008)
J.A. Walker, K. Völk, S.L. Smith, J.F. Miller, Parallel evolution using multi-chromosome Cartesian genetic programming. Genet. Program. Evolvable Mach. 10(4), 417–445 (2009)
D.G. Wilson, S. Cussat-Blanc, H. Luga, J.F. Miller, Evolving simple programs for playing Atari games, in Proceedings of the Genetic and Evolutionary Computation Conference (2018), pp. 229–236
D.G. Wilson, J.F. Miller, S. Cussat-Blanc, H. Luga, Positional Cartesian Genetic Programming (2018). ar**v:1810.04119
S. Yazdani, J. Shanbehzadeh, Balanced Cartesian genetic programming via migration and opposition-based learning: application to symbolic regression. Genet. Program. Evolvable Mach. 16(2), 133–150 (2015)
T. Yu, J. Miller, Neutrality and the evolvability of Boolean function landscape, in Genetic Programming, Lecture Notes in Computer Science, vol. 2038, ed. by L. Sekanina, T. Hu, N. Lourenço, H. Richter, P. García-Sánchez (Springer, Berlin, 2001), pp. 204–217
T. Yu, J.F. Miller, Through the interaction of neutral and adaptive mutations, evolutionary search finds a way. Artif. Life 12(4), 525–551 (2006)
F. Zafari, G.M. Khan, M. Rehman, S.A. Mahmud, Evolving recurrent neural network using Cartesian genetic programming to predict the trend in foreign currency exchange rates. Appl. Artif. Intell. 28(6), 597–628 (2014)
E. Zitzler, M. Laumanns, L. Thiele, SPEA2: improving the strength Pareto evolutionary algorithm. Technical Report 103, ETH Zurich (2001)
Acknowledgements
Thanks to the anonymous reviewers and to Dennis Wilson for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Miller, J.F. Cartesian genetic programming: its status and future. Genet Program Evolvable Mach 21, 129–168 (2020). https://doi.org/10.1007/s10710-019-09360-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10710-019-09360-6