3. See Chapter 2 of Cook (2012) for an overview of the problem’s history. The term traveling salesman problem was not used until the middle of the twentieth century. The problem itself is often associated with the Irish mathematician Sir William Rowan Hamilton, who studied a special mathematical instance of the problem, namely how to visit all twenty vertices of a dodecahedron in a continuous path along the dodecahedron’s edges. His name is attached to the notion of a Hamiltonian circuit, the problem of finding a circuit through a network (a graph in mathematical language) that visits each of the network’s nodes exactly once. Solving the TSP is tantamount to finding a shortest Hamiltonian circuit through such a graph.
The many solutions for problems like these are not the only reason they are hard. There are other problems that have many solutions and that are easy to solve, because the best solution is easy to find among all solutions. The reason is that the landscape describing these solutions is simple. Among such easy problems is the minimum spanning tree problem. See Chapter 3 of Moore and Mertens (2011). More generally, in computer science, hard problems are also referred to as NP (“non-deterministic polynomial-time”)-hard, a term that refers to how the amount of time needed to solve a problem scales with problem size and distinguishes these problems from easier ones that are solvable in an amount of time that scales polynomially with problem size. Harder problems are those with more rugged solution landscapes. I note that the question of how to distinguish rigorously between easy and hard problems is itself one of the deepest open problems in computer science and mathematics. See, for example, Chapter 6 of Moore and Mertens (2011).
4. See Matai et al. (2010), Chapter 3 of Cook (2012), as well as Chapter 4 of Rhodes (1999).
5. For an algorithm specifically aimed at minimizing the carbon footprint of a vehicle route, see Liu et al. (2014).
6. This is only one among multiple kinds of moves that are possible in the solution landscape. Another one, also referred to as 2-opt, cuts two parts of a route that cross each other and then swaps these parts between the two customers they serve. 2-opt helps avoid self-crossing routes, which are inefficient. See Section 9.10 of Moore and Mertens (2011).
7. More precisely, a greedy algorithm is one that always chooses the best among a (limited) number of options. The two options here are the original and the swapped customer order, and the algorithm chooses the one that creates the better solution. In the context of landscape search, algorithms are often referred to as greedy if they ascend the steepest slope to a peak, but this definition presupposes that the algorithm can evaluate all possible next steps, which can require a lot of computation if there are many such steps. I also note that there can be multiple greedy algorithms for any one problem. A better-known greedy algorithm for the vehicle routing problem first visits the customer closest to the depot, travels from there to the closest customer, and so on. It needs to evaluate the distance to all possible customers. In the traveling salesman problem, a specific algorithm that grows many sub-paths simultaneously is known as the greedy algorithm, even though it is only one among many such algorithms. See page 67 of Cook (2012).
8. Combinatorial optimization problems have been known much longer than just for half a century. The TSP, for example, originated in the nineteenth century. However, even moderately large TSPs could not be solved efficiently before the advent of computers and efficient algorithms. My reference point in time here is one of the earliest computational milestones, the 1947 discovery of a technique called the simplex algorithm, which is able to solve many combinatorial optimization problems that are not truly hard. See Dantzig (1963).
9. See Sibani et al. (1993), as well as Figure 4 and Table 5 of Hernando et al. (2013), which show these numbers for the traveling salesman problem. (The corresponding routing problem of the same size would have even more local minima.)
10. See Chapter 10 of Glover and Kochenberger (2003).
11. One can take two different perspectives on the nature of the “marble” in evolution, real or simulated. A marble can represent an individual, as in the image I use in the main text. It can also represent an average location or center of mass for an entire population. Strong genetic drift is analogous to high temperature, in that it causes fluctuations in the population’s center of mass.
12. See Turing (2013).
13. See Holland (1975) and Mitchell (1998). Holland was not the first to work with such algorithms. One important predecessor was the German scientist Ingo Rechenberg, whose work is less widely known. See Rechenberg (1973). Various flavors of such algorithms have been developed, and they come under a variety of names, such as genetic programming and evolutionary algorithms. See, for example, Koza (1992). For simplicity, I will here restrict myself to the term genetic algorithms.
14. For example, two genetic algorithms for the vehicle routing problem that use fifty or fewer individuals are described by Prins (2004), as well as by Baker and Ayechew (2003).
15. To be sure, this kind of recombination may not work exactly as in biology. For example, recombining two DNA chromosomes is like swapping the customers in the first half of one delivery route with the customers in the second half of another route. The problem is that the resulting child might not even be a valid route: it might not visit all customers, or it might visit some customers twice. The best way to simulate recombination depends on the problem and its encoding in an algorithm’s genome.
16. See Koza et al. (2003). You may have noticed that I did not mention the analogue of a third feature that helps biological evolution explore an adaptive landscape—the sprawling network of ridges of approximately equal altitude from Chapter 4. That’s because such networks remain poorly explored in the solution landscapes of computer science, but we have hints that they could help solve difficult problems there as well. See Raman and Wagner (2011), as well as Banzhaf and Leier (2006).
17. See Glover and Kochenberger (2003), as well as Moore and Mertens (2011). Large instances of problems like the VRP or TSP are often solved by a combination of algorithms. One might start with a greedy algorithm, then change the resulting route through the strategic swapping of edges to avoid self-crossing paths, perturb the structure of the problem itself to solve a similar but easier problem in order to obtain tight upper and lower bounds on the solution, then try to map the solution of the easier problem onto a valid solution for the harder one, which can then be improved further, and so on. See Chapter 9 of Moore and Mertens (2011). These multistep procedures are often not conceived with the structure of a solution landscape in mind, but their steps help avoid getting trapped in its local minima. Such procedures also often take advantage of mathematical insights into the structure of a problem, whereas general-purpose algorithms like genetic algorithms can be applied to any problem. That’s both an advantage and a limitation, as general-purpose algorithms are usually not as efficient as custom-made algorithms for very specific problems.
18. The tours I discuss refer to the traveling salesman problem, the close relative of vehicle routing with one vehicle, one depot, and no further constraints. The 666-city tour was reported in Holland (1987). For a review of this and other impressive computational records see Chapter 8 of Cook (2012).
19. Once these building blocks are chosen, the engineer designing a genetic algorithm also faces another important and difficult choice, namely how to evaluate the performance of a solution by choosing the right “fitness function.” This choice may be simple for problems like the vehicle routing problem, but it can be difficult for other problems, especially if they involve complex technologies like engines or airplanes whose performance has multiple aspects.
20. See Koza et al. (1999).
21. See Keane et al. (2005). See also Keats (2006) and Koza et al. (2003). For the effects that creative machines may have on patent and intellectual property law, see Plotkin (2009).
22. See Wang et al. (2013).
23. See Keats (2006).
24. See Hornby et al. (2011).
25. See S
chmidt and Lipson (2009). The authors used an evolutionary computation method called symbolic regression, which combines mathematical building blocks into equations that aim to describe experimental data.
26. See page 1 of Plotkin (2009).
27. Not all of them are unique, of course, but the same holds for biological evolution, which has come up with similar solutions to some problems multiple times through what biologists call convergent evolution.
28. See Van Tonder et al. (2002), as well as Taylor et al. (2011) and Pachet (2012).
29. See Fernandez and Vico (2013).
30. See Muscutt (2007), as well as Cope (1991) and Adams (2010).
31. See Adams (2010).
32. See Muscutt (2007).
33. See Johnson (1997).
34. See Muscutt (2007).
35. See Cope (1991) and Adams (2010).
36. See Fernandez and Vico (2013), as well as http://www.geb.uma.es/melomics/melomics.html. For some press coverage on the computer and algorithm behind this composition see Smith (2013) and Ball (2012).
37. See Pachet (2008), as well as https://www.francoispachet.fr/continuator/. I note that the task of improvising in another person’s style is less difficult than creating compositions from scratch. See, for example, Fernandez and Vico (2013).
38. See Levy (2012).
39. See Podolny (2015).
40. See Levy (2012).
41. See Clerwall (2014).
42. See Constine (2015).
Chapter 7: Darwin in the Mind
1. For a detailed account of the painting’s creation, together with the historical context, see Chipp (1988).
2. See Chipp (1988), but also Weisberg and Hass (2007), as well as Weisberg (2004) and Simonton (2007a).
3. See Simonton (1999) and Simonton (2007a).
4. The ideas of Bain and other early thinkers on Darwinian creativity are summarized in Campbell (1960). Darwin’s great contribution lay in recognizing the importance of natural selection and common descent, but not in elucidating the origin of new variation by random mutation. He did not know where new variation came from and freely admitted his ignorance.
5. See James (1880).
6. See Campbell (1960). Campbell’s term referred to the inner workings of the human mind, but it applies in equal measure to the growth of human knowledge. The philosopher Karl Popper recognized this when he said that “the growth of our knowledge is the result of a process closely resembling what Darwin called natural selection.” See page 26 of Simonton (1999).
7. See page 190 of Dehaene (2014).
8. Simonton’s analysis of Picasso’s Guernica was not uncontroversial. Much of the controversy revolved around the question of how unrelated the imagery and sketches were to anything that had come before them, and thus how free Picasso’s associative process really was. See Weisberg (2004) and Dasgupta (2004), as well as Simonton (2007b) and Weisberg and Hass (2007). But as I discuss in the main text, even blind variation in biological evolution builds on previous variation and is thus not free in this sense. See Wagner (2012). I note that an analogous tension exists in evolutionary biology, where students of organismal development point out that development constrains the kind of variation that DNA mutations can generate. See Maynard-Smith et al. (1985) for the concept of constrained evolution.
9. See Weisberg and Hass (2007).
10. See pages 331 and 340 of Simonton (2007a).
11. See John-Steiner (1997).
12. These and other quotes can be found on pages 26–34 of Simonton (1999).
13. As quoted in Lohr (2007).
14. See Plunkett (1986) and Rosen (2010). For further examples see Wagner (2014) and pages 35–39 of Simonton (1999).
15. See page 84 of Simonton (1988). Needless to say, using citation counts as the only indicator of influence can be highly misleading. There are huge differences among fields in the average number of citations a work receives. For example, research in biology gets more citations than research in mathematics. Citations to new research methods tend to be more numerous than to other kinds of research. And some unfortunate authors receive many negative citations, references to how research should not be done. Other issues with the use of citation counts are summarized on page 85 of Simonton (1988).
16. See page 84 of Simonton (1988).
17. See Lariviere et al. (2009).
18. See Simonton (1985). It is worth noting that Koehler, one of the fathers of Gestalt psychology, was opposed to the idea that trial-and-error could explain his chimpanzees’ problem solving. See page 389 of Campbell (1960) for a discussion of his objections and those of others against Darwinian creativity. The key sticking point seems to be again the question of whether candidate solutions are created from scratch or build on what is already there, for example, pre-existing concepts that require some previous insight into the problem to be solved.
19. See Simonton (1977).
20. Page 92 of Simonton (1988) discusses this and other examples.
21. See page 93 of Simonton (1988).
22. See pages 154–155 of Simonton (1999).
23. Cited on page 186 of Simonton (1994).
24. See Stern (1978).
25. See pages 184–187 of Simonton (1994), as well as Stern (1978) and Sinatra et al. (2016). The latter study also shows that different scientists differ in their potential to create highly important work in their lifetime, even though the impact of any one work is hit or miss.
26. I am referring to one of the earliest successful theories of color vision known as the Young-Helmholtz theory, which proposed the trichromatic nature of our vision.
27. See Chapter 3 of Palmer (1999) and Chapter 1 of Gärdenfors (2000).
28. See Chapter 31 of Kandel et al. (2013) and Chapter 2 of Gärdenfors (2000).
29. See Gärdenfors (2000).
30. See Simonton (2007a).
31. See page 356 of Weisberg and Hass (2007).
32. See pages 45–46 of Padel (2008).
33. See page 14 of Hadamard (1945).
34. See Campbell (1960).
35. See Chapter 1 of Wales (2003).
36. See page 282 of von Helmholtz (1908).
Chapter 8: Not All Those Who Wander Are Lost
1. See page 16 of Bateson and Martin (2013).
2. Ibid., 17.
3. See Caro (1995) and Henig (2008).
4. See references on page 342 of Caro (1995).
5. See Harcourt (1991).
6. See Cameron et al. (2008).
7. See Fagen and Fagen (2009).
8. Practicing this behavior also has other benefits. For example, females who participate in non-conceptive sexual behavior also invest more into the first eggs they lay. See Pruitt and Riechert (2011).
9. See Spinka et al. (2001) and Henig (2008). Both sources also discuss a number of alternative hypotheses about the purpose of animal play, which comprises very heterogeneous activities.
10. See Wenner (2009).
11. See page 31 of Bateson and Martin (2013).
12. Cited on page 247 of Root-Bernstein and Root-Bernstein (1999).
13. See pages 58–61 of Bateson and Martin (2013).
14. See page 82 of Jung (1971).
15. See page 198 of Martin (2002).
16. For these and other examples, see pages 198–204 of Martin (2002).
17. Digital assistants can be used to the same effect, as can more sophisticated experiments that test reaction times. See Jackson and Balota (2012).
18. See Kane et al. (2007), as well as Jackson and Balota (2012), Killingsworth and Gilbert (2010), and Christoff (2012).
19. See Mooneyham and Schooler (2013).
20. See pages 13–14 of Hadamard (1945).
21. See Baird et al. (2012).
22. See Mrazek et al. (2013).
23. See Schooler et al. (2014) and references therein.
24. See Schooler et al. (2014). One might think that the two opposing mental processes are instead analogous to selection and mutation. Ho
wever, it appears that our minds incessantly create spontaneous associations, and what mind-wandering does is to permit remote rather than close associations to come to the fore. See Baror and Bar (2016). The importance of a balance between opposing forces becomes especially clear when it is seriously out of whack in mental illnesses like schizophrenia and psychosis, whose symptoms include thought disorders such as a rambling form of speech known as word salad. Low latent inhibition and low negative priming, phenomena associated with creative personality traits in some experiments, have also been associated with schizophrenia. See Lubow and Gewirtz (1995), Beech and Claridge (1987), as well as Lubow et al. (1992). More generally, creativity has been associated with psychoticism, a dispositional trait causing susceptibility to psychotic symptoms. See Eysenck (1993). Perhaps more frequent, however, are mood disorders such as depression. See Chapter 4 of Runco (2014). Common wisdom had it for centuries that outstanding creativity effectively comes with madness. “Great wits are sure to madness near allied, and thin partitions do their bounds divide” is how the seventeenth-century poet John Dryden expressed it. Alas, that wisdom is a bit dated. In the words of psychologist Mihaly Csikszentmihalyi, who has interviewed countless eminent creators, “the reigning stereotype of the tortured genius is to a large extent myth.” See page 19 of Csikszentmihalyi (1996). See also Simonton (2014). Even a mind with outsized creative powers can be mentally healthy and happy.
25. See page 2 of Bateson and Martin (2013).
26. As quoted in the TED talk “Tales of Creativity and Play” by Tim Brown, CEO of the design company IDEO, available at http://www.ted.com/talks/tim_brown_on_creativity_and_play.
27. Successful creative teams share a property called psychological safety, which allows their members to express themselves freely. See Duhigg (2016).
Life Finds a Way Page 28