Arrival of the Fittest: Solving Evolution's Greatest Puzzle (38 page)

13
. For many examples of multiple independent innovations in nature see Vermeij (2006). While life has discovered some innovations more than once, it may have discovered others only once, but the genotypes encoding them may have diversified later beyond recognition. In some systems, for example proteins where current genotypes are extremely diverse, it is difficult to distinguish multiple independent origins from a single origin followed by diversification.

14
. See Johnson (2010), 153.

15
. These and many other examples of combinatorial innovation and reuse of existing objects and technologies can be found in Kelley and Littman (2001) and Arthur (2009).

16
. As quoted in Arkin (1998).

17
. See Gould and Vrba (1982). Gould and Vrba used the term for changes that conferred a function different from the original function, and for changes that had no utility when they first appeared.

18
. See Darwin (1872), chapter 6, page 175. The example Darwin had in mind was the transformation of the fish’s flotation bladder into the lungs of terrestrial animals.

19
. See Sumida and Brochu (2000).

20
. This and several other examples are discussed in True and Carroll (2002), who call the reuse of old parts co-option. I note that Sonic hedgehog is not a transcriptional regulator, but a molecule involved in signaling between cells. For the naming of Sonic hedgehog see Riddle et al. (1993).

21
. More precisely, I am referring to an internal combustion air-breathing turbofan engine.

22
. See Arthur (2009), 19. The book also discusses the jet engine in some detail.

23
. To my knowledge, one of the first who developed this idea for engineering applications was the German Ingo Rechenberg. See Rechenberg (1973). He pointed out that mutations need to have effects on a system’s behavior or performance that must not be too large in order for an evolutionary algorithm to be able to improve it.

24
. This algorithm of mutation and selection is actually a stochastic algorithm, where individuals can sometimes survive based on dumb luck. Such stochasticity gives rise to a process called genetic drift that is important in biological evolution. See, for example, Hartl and Clark (2007).

25
. There are many flavors of evolutionary algorithms. Two especially prominent ones are genetic programming and genetic algorithms. See Koza (1992) and Mitchell (1998).

26
. More commonly known as NP-hard. See Moore and Mertens (2011).

27
. An analysis that suggests how bumblebees might solve this problem is given in Lihoreau, Chittka, and Raine (2010).

28
. In contrast to traditional (nonevolutionary) algorithms that can solve instances of the traveling salesman problem involving millions of cities within a few percent of optimality, evolutionary algorithms are general-purpose algorithms that can provide good (if not perfect) solutions for less well studied problems, or for problems that are not as clearly posed mathematically.

29
. See Dong and Vagners (2004).

30
. For an example on engine design see Senecal, Montgomery, and Reitz (2000). One of the principal problems that evolutionary algorithms face is to find a good “genotype” representation of the features to be optimized, and to find mutation or recombination “operators”—the routines that modify the genotype—that work well. But the reason why such algorithms have not revolutionized engine design may lie deeper, in a technology that does not easily admit recombination through standardized linkage. For technologies with such linkage, choosing mutation and recombination operators may also be easier.

31
. This does not mean that they do not use recombination, far from it, but they usually recombine abstract (bit-string) representations of candidate solutions to a problem, and not elements of the solution itself, like the amino acids of proteins. More generally, I note that I use the word “recombination” here in a broader sense than prescribed by its standard definition in genetics—the swapping of DNA molecules. This more general use applies to DNA but also to any other notion of genotype, and can even apply to human innovation that is combinatorial. In this sense, even a change in one or a few amino acids of a protein amounts to a recombination of amino acids.

32
. More succinctly, new circuits consist of new combinations of interactions between regulators, interactions that may already have existed in other circuits.

33
. See the Web site of the Centro Internazionale di Studi di Architecttura Andrea Palladio (CISA) at http://www.cisapalladio.org/veneto/index.php?lingua=i&modo=nomi&ordine=alfa.

34
. Their work is described in Hersey and Freedman (1992).

35
. An algorithm could produce more than one outcome, more than one floor plan, because individual instructions in the algorithm may have a stochastic component, such as “subdivide a room into two, three, or four rooms with equal probability.” Such stochastic algorithms are widespread in computer science.

36
. Other rules include that splits are executed such that buildings are generally bilaterally symmetric around a central axis, walls are aligned whenever possible, and no rooms are allowed to be as wide or long as the entire length or width of the building.

37
. More than a century after Palladio, the Swedish inventor and industrialist Christopher Polhem invented a “mechanical alphabet” of machines that is described in Strandh (1987). The letters in this alphabet are machine components, such as levers, wedges, screws, and winches. Polhem believed that through combining these machine components, one could build any conceivable mechanical device. He intended the alphabet as a teaching tool, but some models of machines written in this language have been built. While the idea behind this alphabet is important for students of innovable technologies, it is worth pointing out that the links between machine parts are not standardized. In a similar vein, Sanchez and Mahoney point out that the automobile, aircraft, consumer electronics, and other industries build many different products by combining a limited number of “modular” components. See Sanchez and Mahoney (1996). But yet again, the links between these modules are often nonstandardized, custom-made, one-of-a-kind. This is an important shortcoming of the “design spaces” of many technologies and a major difference from the genotype spaces of living beings. For the notion of a design space see Stankiewicz (2000).

38
. Even more precisely, in mathematics, a function
f
can be described as a set of ordered pairs (
a,b
), where
a
is a member of a set called the domain of the function that defines all admissible function arguments (inputs), and
b
is a member of the set of output values the function can take. One writes
b = f
(
a
)
.
Digital logic circuits compute functions of bit strings whose outputs are again bit strings.

39
. Actually it would report even more. The final version of the Köchel catalog—there are six—does end with #626, the
Requiem in D Minor,
but also includes numerous entries with variations, such as the
Church Sonata in C
(#317a) and the
Aria for Soprano in B-flat
(#317b).

40
. Some functions, such as the NOT and NOR functions, can be implemented with single transistors. The upper output bit shown in figure 22 corresponds to the lower significance binary digit. It is computed by the so-called exclusive or function (XOR). The lower-output bit is the higher-significance “carry” bit that is the result of an AND function.

41
. Integrated circuits also contain some more complex, derived logical building blocks, such as multiplexers, demultiplexers, and registers, but all of these are based on Boolean logic functions. See also Balch (2003).

42
. Such devices also come under other names, such as reconfigurable hardware or programmable logic devices. For an overview see Balch (2003). There are several classes of such devices. The research I discuss here was carried out with a specific class in mind: field-programmable gate arrays (FPGAs). Like many other integrated circuits, such arrays contain many more than just AND and OR gates. They also use more complicated units of computation, such as logic blocks, each of which may contain a full adder, several lookup tables that store truth tables in random access memory, multiplexers, and others. But the principle is still the same: They perform complex computations by networking simpler computational units.

The programming of such devices is different from more conventional software programming. A search program like the one I described earlier to search a music database is typically executed on a hardwired chip, whereas on a programmable chip a program can change the wiring of the chip itself. It amounts to creating a piece of hardware that can execute a given computation task faster than software running on a generic hardwired chip. Limitations of FPGAs include that they are slower and more expensive than application-specific integrated circuits. See also Balch (2003), 250.

43
. The field of machine learning is a well-established research field whose current focus is not programmable hardware, but methods (often implemented in software) that enable computers to extract statistical information from complex data.

44
. Once again, I am using the word “wires” not in a literal sense—flexible metal threads—but metaphorically. They are integral parts of an integrated circuit.

45
. A difference from proteins is that amino acids form a linear string, whereas the gates in a circuit have a two-dimensional arrangement.

46
. The number of functions a circuit can compute depends not only on its number of gates but also on the number of input and output bits.

47
. It also allowed us to study idealized situations, such as exploring every possible wiring change in a circuit, whereas some such changes may be prohibited in a commercial FPGA architecture. We considered circuits that could harbor OR, AND, XOR, NAND, and NOR gates, because these are the five most commonly used two-input logic gates. Each input could be wired to any of the input gates in the first column of the sixteen-gate array. Each output could be wired to any of the circuit’s output bits. Gates were wired internally in a feed-forward fashion where the input of a gate could only come from a gate to the left of it in the array. Such feed-forward connectivity is important to avoid complex dynamics, such as cyclic behavior. More details on this work, including some of the numbers I discuss, can be found in Raman and Wagner (2011).

48
. The circuits we studied had four input and four output bits, and there are 1.84 × 10
¹⁹
possible Boolean functions with this property.

49
. When I say that no two gates were identical, I mean that gates at the same position in the two circuits computed different Boolean logic functions. The maximal distance we could achieve in such a random walk depended only little on the frequency of a logic function, that is, on the number of circuits computing this logic function. There may be Boolean logic functions encoded by very few circuits that are highly similar, but those would be very hard to find in a vast circuit space. Previous work has recognized that neutral change can be important for the performance of evolutionary algorithms. See, for example, Banzhaf and Leier (2006), as well as Brameier and Banzhaf (2003), Miller and Thomson (2000), and Yu and Miller (2006). However, to my knowledge, nobody had demonstrated systematically, and in a system that can be implemented in hardware, that genotype networks and the diversity of their neighborhoods are
generic
features of a configuration space (not restricted to one or a few Boolean logic functions).

50
. This means that these functions are not likely to be found in the neighborhood of a specific circuit different from the focal circuit in whose neighborhood they occur. (But they may occur in the neighborhood of other circuits in genotype space.)

51
. A thousand wiring changes may seem like a lot, but keep in mind that programmable hardware can rewire at lightning speeds. Some useful information on the reconfiguration time of a commercial FPGA is given in Schuck, Haetzer, and Becker (2009).

52
. This holds, as usual, for phenotypes (functions) sufficiently frequent that circuits encoding them can be found through a blind search. This property of the circuit library is important, because it can minimize the amount of array reconfiguration (and thus time) needed to change from one function to another.