Modern computers allow a methodical search of possibly billions of experiments and the exploitation of interactions that are not known in advance. This enables a bottom-up process of design by assembling or configuring systems and testing the degree to which they fulfill the desired goal. We give two detailed examples of this process. One is referred to as Cartesian genetic programming and the other evolution-in-materio. In the former, evolutionary algorithms are used to exploit the interactions of software components representing mathematical, logical, or computational elements. In the latter, evolutionary algorithms are used to manipulate physical systems particularly at the electrical or electronic level. We compare and contrast both approaches and discuss possible new research directions by borrowing ideas from one and using them in the other.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Despite having no designer, natural evolution has caused the construction of “machines” of incredible sophistication and complexity. In the construction of biological organisms it has utilised countless physical properties of materials, many of which are still not fully understood. It is now possible to emulate natural evolution’s ability to utilise and exploit unknown physical and software interactions to create useful artefacts. We refer to this as computational alchemy. This process is akin to alchemy in that there is a search for a desired goal which is similar to the process of alchemy where poorly understood processes are utilised in a goal-driven, bottom-up and informal process to achieve a desired result.
A simplified and algorithmic form of natural evolution is widely used to build solutions to many computational problems. The field has two main subdivisions: genetic programming (GP) and evolutionary algorithms (EAs). The general form of an EA is shown in algorithm 1:
Advertisement
In evolutionary algorithms, fixed length encodings of potential solutions are evolved to find optima. To do this one identifies all the variables that are required to build a solution to a problem and then a vector or string of these variables is constructed. This string is usually referred to as chromosome or genotype.
GP uses EAs to evolve variable sized computational structures (Koza 1992). In this paper, we describe a form of genetic programming known as Cartesian genetic programming(CGP) (Miller 2011; Miller and Thomson 2000). CGP represents computational structures as graphs. It uses a fixed length list of genes describing the function and connections of computational nodes. It can have multiple outputs. CGP has been used to evolve electronic circuits, mathematical expressions, artificial neural networks, differential equations, data classifiers, control systems and solutions to many other types of problems. CGP exploits unknown or poorly understood interactions between known computational primitives (nodes) and often finds unusual or innovative solutions to problems.
In evolution-in-materio (EIM), EAs are used to exploit unknown interactions between unknown or poorly understood physical components to find solutions (Miller and Downing 2002; Miller et al. 2014). The main idea of EIM is that the application of some physical signals to a material (configuration variables) can cause it to alter how it responds to an applied physical input signal and how it generates a measurable physical output (see Fig. 1). Physical outputs from the material are converted to output data and a numerical fitness score is assigned depending on how close the output data (or a function of it) is to that desired. This fitness is used in an EA to attempt to find configurations that cause a material to produce a desired behaviour. In EIM, the variables optimised by evolutionary algorithms are usually the magnitudes of voltages and the positions of the electrodes to which the voltages will be applied.
Fig. 1
Concept of evolution-in-materio. There are two domains: physical and computer. In the physical domain there is a material to which physical signals can be applied or measured. These signals are either input signals, output signals or configuration instructions. A computer controls the application of physical inputs applied to the material, the reading of physical signals from the material and the application to the material of other physical inputs known as physical configurations. A genotype of numerical data is held on the computer and is transformed into configuration instructions. The genotypes are subject to an EA. Physical output signals are read from the material and converted to output data in the computer. A fitness value is obtained from the output data and supplied as a fitness of a genotype to the EA. The EA starts with a randomly generated initial population. It ends when either the used-defined number of generations has elapsed or the fitness value is satisfactory
×
The purpose of this paper is to compare and contrast these two approaches and identify new insights that might be useful to improve either technique. The underlying assumption of EIM is that utilising potentially unknown physical effects and interactions can improve evolvability. Materials that possess such properties can be thought of as physically rich. They can be more evolvable precisely because evolution has more dimensions that can be adjusted. Can such a concept be emulated in some way, in software? Miller and Hartmann suggested including a certain degree of randomness in models of logic gates and showed that this conferred a number of advantages such as fault tolerance and small circuit size (Miller and Hartmann 2001). Another possible route to enriching the basic components used in circuit evolution might be to represent the circuits at the transistor level (Greenwood and Tyrrell 2007; Trefzer and Tyrrell 2015). This would allow aspects of physics in the simulation model to be exploited. Enriching software models of components however has the drawback that it increases simulation time. On the other hand in EIM one could build arrays of evolved molecular devices, by evolving the basic components first and then allowing artificial evolution to combine them to solve computational problems.
Advertisement
The plan of the paper is as follows. Firstly, we explain CGP then in Sect. 3 we discuss three examples where unknown or poorly understood interactions between software components are exploited to create innovative solutions to various problems. In Sects. 4–6 we discuss how computer controlled evolution can utilise unknown or poorly understood physical interactions to solve computational problems. In Sect. 7 we compare and contrast the two methods and discuss future possibilities.
×
2 Cartesian genetic programming
In the original form of CGP graphs were indexed by their Cartesian coordinates, hence the term “Cartesian” (Miller and Thomson 2000). It differs from GP, which represents programs in the form of trees, in a number of ways. It uses graphs to represent solutions to computational problems which means that the outputs of the nodes in the graph can be reused multiple times rather than once as in trees. Secondly, it allows programs to have multiple-outputs which widens its applicability. It uses a simple address-based program genotype encoding which can ignore nodes if they are not referenced. The presence of explicitly inactive genes assists evolution by allowing a process of genetic drift (Miller and Smith 2006; Turner and Miller 2015a; Vassilev and Miller 2000; Yu and Miller 2001, 2006). As the upper bound on the maximum genotype size is increased an increasing proportion of genes are unexpressed this assists neutral exploration as many mutated genotypes have the same phenotype. As a result there is a strong bias in CGP for small phenotypes (Goldman and Punch 2013). This can often mean that evolved solutions are small and can be interpreted. The maximum allowed size of the genotype is highly influential (Turner and Miller 2015a) on search efficiency and often the ideal genotype length is quite large (hundreds or thousands of nodes).
Originally, CGP encoded acyclic graphs only, but it has also been extended to represent cyclic (Ryser-Welch et al. 2016) and recurrent graphs (Turner and Miller 2014b; Walker et al. 2009).
Each CGP chromosome consists of function genes (\(F_i\)), connection genes (\(C_{i,j}\)) and output genes (\(O_i\)); where i indexes each node and j indexes each nodes inputs. The function genes represent indexes in a function look-up-table and describe the functionality of each node. The connection genes describe from where each node gathers its inputs. For regular acyclic CGP, connection genes may connect a given node to any previous node in the program, or any of the program inputs. The output genes address any program input or internal node and define which are used as program outputs.
Originally CGP programs were organized with nodes arranged in rows (nodes per layer) and columns (layers); with each node indexed by its row and a column. However, here we show a generic (one row) CGP chromosome (see Equation 1), where \(\alpha\) is the arity of each node, n is the number of nodes and m is the number of program outputs.
An example CGP program is given in Fig. 2 along with its corresponding chromosome. As can be seen, all nodes are connected to previous nodes or program inputs. Not all program inputs have to be used, enabling evolution to decide which inputs are significant. CGP typically uses a simple evolutionary strategy (ES), sometimes referred to as a probabilistic hill-climber, called a \((1 + \lambda )\)-ES, where \(\lambda =4\). This is shown in Algorithm 2.
Fig. 2
Example CGP program. The program has three inputs, x, y, z and three outputs \(O_0, O_1, O_2\). The genotype is shown at the top of the figure. Underlined genes indicate node function genes. In the example there are four possible node functions, add, subtract, multiply and divide (with genes 0, 1, 2, 3). The lower schematic shows how the genotype is decoded into a graph and thence into equations. Note that program input, z is not used. The function of node 3 is add its inputs, x and y so it produces \(x+y\). The output of node 4 is not used as neither nodes or program outputs refer to it. Node 5 multiplies its inputs so it produces \((x+y)*y\). Node 6 also multiplies its inputs (which are y and the output of node 5) so it produces \((x+y)^2y\). Thus the graph represents the three equations: \(O_0=x\), \(O_1=(x+y)*y\) and \(O_2=(x+y)^2y\)
×
The integer genes in CGP are constrained to make sure all links and node functions in the graph are valid.
Algorithm 2 allows only one genotype to be selected for the next generation (called the parent), then four offspring are generated from the parent by copying the parent and then making some random alterations (mutation). Since many genes are inactive, it is often the case that the parent and offspring only genetically differ from the parent in the inactive genes. This means that the phenotype of such offspring will be identical to the parent. In situations where no offspring has a fitness greater than the parent but at least one has an equal fitness, then the the offspring is chosen as the new parent. This allows a process of genetic drift to occur.
×
3 Exploitation of unknown interactions in CGP
3.1 Digital circuits
Algorithms that optimise the number of gates used to build Boolean functions have been an active area of research for many decades (Brayton et al. 1984; Devadas 1994; Sentovich et al. 1992). However, in order to make general purpose logic mimimisation algorithms they assume rather limited choices of atomic logic gates such as AND, OR, NOT or AND, EXOR, NOT and this can lead to sub-optimum circuits (Miller et al. 2000). This is a general problem that applies to many fields. To create an automated design system very restrictive assumptions have to be made about how such systems can be represented, this is where computational alchemy can be useful. One can use representations of solutions that are much less restrictive, in the logic case this could mean allowing circuits to be built from a large collection of primitive gates e.g. all 16 two-input Boolean functions, multiplexers, universal logic modules. It is important to realise that there are no formal algorithmic methods for building circuits that use such collections of components. We give a simple example of the strangeness of solutions designed using computational alchemy in Fig. 3. The use of the two input Boolean function which is an AND gate with one input inverted is very peculiar and would not be chosen by a human designer. Bitwise multiplication follows the conventional paradigm of long multiplication. This produces the circuit shown in Fig. 3a. Allowing the use of all possible two-input Boolean functions allows bizarre circuits to arise that combine the elementary products in ways which a human designer would not consider since they do not operate according to conventional principles (Fig. 3b). It should be noted that although the total number of elementary gates used in both designs is the same, the number of transistors required may be less in the evolved design as it use ones only one XOR gate (which is relatively transistor expensive).
Fig. 3
Two-bit multipliers: conventional (a), evolved (b). Circles on inputs to gates indicate inversion. Both designs use the same number of elementary gates. The least significant input (product) bits are A0 and B0 (P0). The conventional circuit computes the output products in order: P0, P1, P2, P3. The evolved computes the outputs is a very peculiar way, P3 and P1 are produced together and P0 and P2 are produced together in two separate sub-circuits (Miller et al. 2000)
×
However, with this representational freedom comes the drawback of an enormous and intractable search space. Directly trying to evolve circuits with a reasonable number of inputs is intractable as the number of conditions is an exponential function of the number of inputs. This problem was elegantly solved in Vašíček and Sekanina (2011) where CGP is used to synthesise digital circuits with hundreds of inputs and thousands of gates (Vašíček 2015). The intractability problem was solved by using conventional algorithms to synthesize the smallest circuit and then using this circuit to provide a seed for CGP to optimise it further. However, to check whether an evolved circuit correctly implemented the chosen circuit function a SAT solver was used, this could check the equivalence of logical functions in usually polynomial time. Evolved circuits that did not correctly implement the targeted circuit were given a fitness of zero, whereas the ones that were correct were given higher fitness scores for being small. This illustrates that computational alchemy can operate successfully from human designed starting points.
3.2 Object recognition
Harding et al. (2013) and Leitner et al. (2012) used CGP to evolve very sophisticated object recognizers using conventional components. The CGP nodes were chosen from a large collection of elementary functions. The data type flowing through the CGP graph was an image. The node functions included arithmetic, mathematical, statistical and many image operations available in a well-known image processing library (OpenCV) (Bradski 2000). Harding used a set of images including the objects of interest and the aim was to produce a pixel classifier which identified whether a pixel in an image belonged to a given object or not. The training set of images included the object in different positions and lighting conditions and with the presence of other objects (not of interest). The training images included images containing the object passed through various filters such as: hue, saturation, brightness, red, green, blue, and grayscale. An example of an evolved CGP graph showing transformations of input images after various node operations is shown in Fig. 4.
Fig. 4
CGP image data flow graph (Harding et al. 2013) that can identify pixels belonging to a particular packet of tea. On the left two images of a scene containing the object of interest are used. Various image processing functions are applied resulting in a binary classification image (far right) showing where pixels are that belong to the packet of tea
×
The evolved filter program corresponding to the data flow graph is shown in Fig. 5. The first thing to note is how small the program is. This illustrates the tendency of CGP to produce compact solutions to problems. As with evolved digital circuits, evolved object recognition filters combine well-understood components in very unusual ways and there is no formal procedure that can design such programs. Although this particular image filter is hard to understand it is possible that some evolved filters could be understandable which could provide some insights in object recognition in general.
Fig. 5
Evolved object recognition program (Harding et al. 2013) that can identify pixels belonging to a packet of tea. The program can be executed in real-time on live video. This allows an object to be tracked while undergoing rotation, being partly hidden, with changed lighting and other environmental changes
CGP can encoded artificial neural networks (ANNs) (Khan et al. 2010a, b, 2013). Encoding and evolving ANNs in CGP gives immediate benefits. Turner et al. demonstrated that using heterogeneous activation functions gave improved results compared with the traditional single activation function ANNs (Turner and Miller 2014a). In addition, it has been shown that evolving ANNs with CGP produced networks whose performance was much less sensitive to topology choices than fixed topology evolved ANNs (Turner and Miller 2013). The topology of CGPANNs is unusual when compared with traditional ANNs and often cannot be described in terms of layers and nodes per layer.
Fig. 6
Unusual ANNs can be evolved using CGP
×
Figure 6 gives an example of the type of ANN which can be created using CGP. Neuron inputs are highly unconstrained; they can connect to any previous neuron in the network including input neurons. The arity of each neuron can vary. Additionally any neuron can be used as an output; including the input neurons. Neurons can have different and arbitrary activation functions, possibly even non-differentiable functions. There can also be multiple connections between the same pair of neurons (e.g. the two connections between the logistic neuron and the rectilinear neuron). CGP is capable of discovering topologies which would be unlikely to be considered by a human designer.
4 Evolution-in-materio
The concept of EIM was inspired by the work of Adrian Thompson et al. (1999) and Thompson (2001) in a sub-field of evolutionary computation called evolvable hardware (Haddow and Tyrrell 2011; Tyrrell and Trefzer 2015b). Thompson demonstrated that unconstrained evolution on a silicon chip called a Field Programmable Gate Array (FPGA) could utilize the physical properties of the chip to solve computational problems. Inspired by this, Harding and Miller showed that unconstrained evolution on a liquid crystal display could also solve a number of computational problems (Harding et al. 2004, 2015; Harding and Miller 2007; Harding et al. 2008). Indeed, it seemed to be easier to evolve computational functions with liquid crystal than it was with silicon (Harding et al. 2004). Interestingly, similar ideas, albeit without computers, were conceived in the late 1950s (particularly by Gordon Pask Cariani 1993; Pask 1958). Pask’s material was an acidified solution of Ferrous Sulphate and adjusting voltages applied to a solution grew iron threads whose form was related to the magnitude of current flow.
4.1 Travelling salesman problem
To illustrate EIM we choose a classic problem in computer science. Namely the travelling salesman problem (TSP). The aim of which, is to discover the smallest length tour of a number of cities. Small instances of TSP problems were solved using the EIM approach (Clegg et al. 2014). Single-walled carbon nanotubes (SWCNT) in PMMA polymer (Poly-methyl-methacralate) were placed on an electrode array. The material is configured by applying static voltages to electrodes. The voltages on the remaining electrodes are used to define a permutation of cities.
Figure 7 shows results using a 3 × 4 gold electrode array for a nine-city TSP problem. The particular TSP instances were generated by placing cities on a circle so that they were equidistant from one another. The genotype defined a number of real-values voltages and to which electrodes these configuration voltages would be applied. The latter was accomplished by using digitally configurable analogue cross point switches. A data acquisition card (DAQ) digitally configures the switch connections and then generates analogue configuration voltages which are applied to the electrode array. Finally, it records the voltages on the non-configuration electrodes. The number of configuration voltages deployed depends on the problem being tackled and the availability of spare electrodes on the array. The configuration voltages and electrodes to which they connect were decided by a 1+4-ES (see Sect. 2). The range of voltages values was restricted to ±3V and all connections are one to one (i.e. one configuration voltage can only go to one electrode). Configuration voltages were applied for one second and a mean value of sampled voltages from the output electrodes was calculated from the last 0.2 seconds of sampled values. This was done to exclude any “settling periods” within the material. The time required to configure the analogue switch and set up channels on the DAQ card means that testing a configuration takes several seconds. Actually further investigations revealed that signals from the SWCNT-PMMA materials have negligible noise levels after the initial 50ms so that sampling times could be substantially reduced.
Fig. 7
Top left: Array of electrodes (3 × 4) with non-uniform covering of SWCNTs (a). Note the mask fault on the third electrode. This did not appear to affect the evolutionary search when finding the shortest tour of the TSP. The fitness of the best performing genotype for each generation in an evolutionary run is shown (d). The configuration voltages defined by the best genotype are applied to the circled electrodes and the remaining electrodes provide the floating point voltage values used to determine the tour of cities. Recorded voltages which when sorted determine the order to visit cities (b). Optimum tour solution of the TSP (c)
×
The method of obtaining a tour of cities (i.e. a permutation) is as follows. A vector of voltage values with as many elements as cities is read from the electrode array. The ith element represents city i. The vector is sorted and the city indexes form a permutation, thus defining a tour (see Clegg et al. 2014 for details). The graphic at the top right of Fig. 7 shows a set of voltages read from a 3 × 4 array. Choosing the lowest voltages (y-axis) in sequence and observing which electrode corresponds to that, one obtains the permutation: 7 6 5 4 3 2 1 9 8. The results are shown in Table 1.
Table 1
9 or 10 city TSP results for different numbers of configuration voltages
Size of TSP
Number of configuration voltages
Average (median) number of generations for successful runs
9
2
158.6 (104.5)
9
3
57.36 (42.5)
9
4
118.4 (61.5)
10
2
157.95 (155.0)
10
3
79.76 (63.5)
10
4
68.03 (46.5)
Averages and medians are calculated over 30 runs of a 1+4-ES for 1500 generations
It remains to be seen how quickly larger solutions of the TSP can be evolved on larger electrode arrays. Also it would be interesting to investigate whether EIM could be used to solve general TSP problems by using an evolved device to choose which city to visit next on a given problem. In principle this could be done by inputting real-valued Cartesian coordinates (normalised) of cities and trying to use evolution to identify an output that goes high say when the next city is a good one to choose for a minimal tour.
4.2 Other problems attempted with CNTs
Within a European project called NASCENCE (Broersma et al. 2012) it was shown that many computational problems could be solved using EIM working with carbon nanotubes: classification (Mohid et al. 2014d; Vissol-Gaudin et al. 2016), bin-packing (Mohid et al. 2014b), function optimization (Mohid et al. 2014c), frequency classification (Mohid et al. 2014a), Boolean logic functions (Kotsialos et al. 2014; Massey et al. 2015; Mohid and Miller 2015b), robot control (Mohid and Miller 2015a) and graph colouring (Lykkebø and Tufte 2014). CNTs were also used in EIM as a reservoir computing device (See Sect. 6 for more details) on time series prediction, memory capacity, signal transformation and classification (Dale et al. 2016a, b, c).
5 EIM with gold nanoparticles
EIM was used to configure disordered networks of gold nanoparticles (NPs) to act as two-input Boolean gates (Bose et al. 2015). Fig. 8a, shows an atomic force micrograph (AFM) of a disordered network of gold nanoparticles (NPs) interconnected by insulating molecules (1-octanethiols) (b) over a 200nm diameter circular space surrounded by 8 radial electrodes (Ti/Au). The electrodes sit on top of a highly doped Si/SiO2 substrate, which functions as another electrode (called the back gate). At low temperatures, the charging energy of the nanoparticle is given by, \(EC = {e^2}/C\) (with e the electron charge and C the nanoparticle’s total capacitance) is larger than the thermal energy, and each NP exhibits Coulomb blockade and acts as a single electron transistor. One electron at a time can tunnel when sufficient energy is available (ON state), either by applying a voltage across the SET or by electrostatically shifting its potential. Otherwise, the transport is blocked because of the Coulomb blockade (OFF state). Two electrodes are chosen as inputs (\(V_{IN1},V_{IN2}\)) and there is one output (\(I_{OUT}\)). The remaining 5 electrodes and back gate have fixed voltages applied to them. An EA was used to arrive at suitable configuration voltages to make the device operate as a logic gate.
Fig. 8
Circular eight electrode array. The material is a disordered network of 20 nm gold nanoparticles interconnected by insulating molecules (1-octanethiols). The nanoparticles are trapped in a circular region (200 nm in diameter) between radial metal (Ti/Au) electrodes on top of a highly doped Si/SiO\(_2\) substrate. The device operates at temperatures below 1\(^{\circ }\)K (Bose et al. 2015)
×
Time dependent signals in the order of a hundred mV are applied to the input electrodes and a time dependent current in the order of a hundred pA is read from the output electrode (See Fig. 9). It was found that the EA was able to find the values of the voltages to apply to the electrodes that programmed the same device to act as any of the 16 possible two-input Boolean functions. All gates showed great stability and reproducibility. Indeed, it was found that the gates still functioned correctly when perturbations were applied to the configuration voltages. Also after raising temperatures above the operating range and then cooling again to the same temperatures at which they were evolved the gates recovered reliably their original evolved function.
Fig. 9
Digital input signals and two evolved responses. The objective is to produce an logical AND function of the two inputs P and Q. One figure (with red cross) shows a response with low fitness. The other shows a correct response which would have high fitness (green cross). (Color figure online)
×
Although the EIM work using gold nanoparticles is very promising the technique needs to be evaluated on many more computational problems. Even though it is possible to solve specific problems with EIM evolved devices, it would be more useful if general purpose computational devices could be obtained. In the next section we will see how this could potentially be accomplished.
6 Reservoir computing with carbon nanotubes
Reservoir computing (RC) is a computational paradigm which utilises a dynamical system (the reservoir) and a trainable readout mechanism (Jaeger 2001; Maass 2011; Schrauwen et al. 2007). Often reservoirs are implemented as randomly wired recurrent neural networks (Jaeger 2001). External input signals are fed into a reservoir and the internal dynamics of the reservoir maps the input into a higher dimensional space. RC uses a simple readout mechanism (weighted outputs) that is trained to read the state of the reservoir and map it to the desired output. The main benefit is that training is performed only at the readout stage and the reservoir is fixed. A reservoir functions much like a temporal kernel (Lukoševičius et al. 2012) and can represent any excitable non-linear medium provided two requirements are met (1) that it can create a high-dimensional projection of the input into observable reservoir states; and (2) that it possesses a fading memory of previous inputs and internal states. With these properties it has been shown that a reservoir can realise any non-linear filter with bounded memory, and with the aid of a trained readout approximate any function.
Dale et al. used EIM to create physical reservoir computing devices (Dale et al. 2016c, 2017). The reservoirs were electrode arrays covered with a layer of carbon nanotubes in a polymer. The RC in-materio approach provided a competitive new approach to unconventional computing. The system is depicted in Fig. 10. The advantage of using EIM to create reservoir computing devices is that evolved reservoirs could act as general purpose trainable computational devices rather than a computing device for a single application. Ultimately, implementing reservoir computing devices physically (rather than as neural networks) may offer devices that are faster and consume less power.
Fig. 10
Reservoir computing with carbon nanotube physical reservoir configured using an EA
×
It would also be interesting to replace the neural networks in reservoir computers with CGP evolved graphs or even CGPANNs. Conceptually, allowing evolution to manipulate the inner workings of the reservoir computing device would appear to offer an alternative way of arriving at reservoirs with good properties. In addition, using CGP would allow reservoir computing devices to be constructed that handle more complex data (i.e. whole images or mixed data type) so that for instance general purpose trainable image filters could be attempted.
7 Comparing and contrasting CGP with EIM
In EIM one usually has little understanding of useful physical processes in materials that could be exploited in higher-level problem solving. As a consequence one applies configuration signals to various locations in the device to cause some physical effect that affects how applied inputs are transformed into useful outputs. In CGP, the internal components are known in advance and one is trying to exploit the interactions between these components for problem solving. Comparing the two methodologies suggests that CGP would be more like EIM if the internal connectivity of the graph was not directly affected by evolution, instead one could evolve configuration signals in addition to inputs to a fixed graph (presumably randomly generated). This is quite similar to the concept of reservoir computing in which the reservoir (an analogue of a physical device) is fixed and only the external inputs and weights of output signals are adjusted. However, in CGP not allowing internal connections between primitive functions would be likely to hamper evolution as being able to manipulate internal interactions gives evolution a high degree of fine control of internal components. It would nevertheless be interesting to investigate the proposed alternative form of CGP to see how it performs in comparison with standard CGP.
Another way in which the benefits of ‘richness’ of materials that are exploited in EIM could inspire new variants of genetic programming could be to replace the primitive function set with random trees or graphs (possibly with pseudo-random constants). This would free one from deciding which primitive functions to use. Of course, the understandability of the evolved solutions would become more difficult, however the additional freedom for evolution to combine and exploit unusual interactions between components could be enhanced and it may lead to greater evolvability.
The central idea of EIM is that evolution may be able to exploit the richness of the material world for computation. The drawback is that it is not clear what kinds of materials are most evolvable and exploitable. However, recently, Dale et al. (2018) have developed a method for characterising the quality of any substrate for reservoir computing. This may lead to a better understanding of what physical systems might be most suitable. Furthermore, in the future, it might be better to create an array of different materials each of which can be configured and with evolvable connections between the different materials. Then evolution could choose which materials to use and how to connect them. This would be like an FPGA but with materials rather than engineered silicon. Indeed such a proposed device has been referred to as a Field Programmable Matter Array (FPMA) (Miller and Downing 2002). Nanoparticle based EIM appears to offer great potential particularly since, as we have seen, evolved devices have high reliability and stability. There are many variants that could be investigated in the future. Different materials could be used to keep the nanoparticles apart and also one could also use insulating as well as conducting nanoparticles. Work is also underway in attempting to build devices with smaller nanoparticles that can operate at higher temperatures. An important aspect in the evolvability and scalability of EIM is the number of electrodes. With much higher electrode densities one can potentially have much finer control of small regions of material, this ought to mean that exploitation of physical effects could be enhanced, which would lead to higher evolvability.
A key question for EIM is how to obtain general purpose computing devices rather than solutions for particular problems. We have discussed reservoir computing as one potential methodology for general problem solving. In reservoir computing the reservoir is usually a recurrent neural network which has certain statistical properties. It isn’t evolved. However, recurrent neural or recurrent CGP encoded ANNs or even recurrent non-neural CGP graphs could be used as the reservoir and evolution could be used to arrive at general purpose reservoirs.
Another step in this direction of general purpose computing from EIM devices could be to use a material in a similar way to compositional pattern producing networks (CPPNs) (Stanley 2007). CPNNs read the coordinates of pairs of artificial neurons and outputs a weight for that connection. In principle evolved material configurations could do the same. This would allow evolution to configure materials that could build arbitrary sized software ANNs.
8 Conclusion
We have discussed two forms of computational alchemy where computer-controlled search can exploit physical, mathematical, logical and software interactions to solve computational problems in unconventional ways. In CGP computational solutions are built from known components but the combinations and interactions between these components are not formally tractable while in evolution-in-materio the basic physical components are not even known in advance. Despite this, search algorithms are able to utilise these effects in problem solving. This mirrors in a small way, perhaps, the extraordinary exploitation of physics and chemistry made by natural evolution. The two techniques have not been discussed in the same article before and it is clear that comparing and contrasting the two techniques offers new insights into possible new research directions for both GP, EIM and reservoir computing.
Open AccessThis 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.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
