Genetic algorithms and simulated annealing are only two animals in a large zoo of problem-solving algorithms. That zoo houses many other creatures with exotic names, like branch-and-bound, linear programming, and tabu search. They were created by scientists who pored over old, important, and difficult problems like that of the traveling salesman and accumulated deep knowledge about their mathematical structure. This knowledge helped them illuminate different shortcuts through the solution landscape and design algorithms to excel at finding these shortcuts. And these algorithms can perform impressively on hard problems, like that of finding shortest routes.17
For example, the shortest route connecting 666 of the world’s tourist destinations has been known since 1987. That’s when an algorithm succeeded in finding it among more than 101500 possible routes. In 1998, after another decade of algorithm design and improvements in computing power, researchers at Rice University found the shortest route connecting 13,509 cities and towns in the United States.
An even bigger problem would interest Santa Claus: find the shortest route between all 1.9 million known human settlements. Even though this problem is still unsolved, the algorithm that discovered the best known route—7.5 million kilometers long—has done a great job: one can prove mathematically that this route is at most 0.5 percent longer than the unknown shortest route. If Santa ran a trucking company and had to worry about profit margins, he could rest easy.18
That’s what state-of-the art algorithms can accomplish when wielded by teams of computer scientists with huge amounts of computing power. They can sometimes find the best solutions even for problems of staggering complexity. And when they cannot, it’s because even their shortcuts are no match for the complexity of a solution landscape. For example, even though simulated annealing is guaranteed to find the deepest valley in any landscape—eventually—some problems require cooling so glacially slow that it might take thousands of years to find the deepest valley.
Most state-of-the-art algorithms are made for problems that are so well studied that their solution landscape is visible in hazy outline. But many of the problems that engineers face day-to-day—how to reduce the emissions of a combustion engine, increase the efficiency of a solar panel, or decrease the side effects of a drug—are one-of-a-kind, novel problems where the landscape lies in the dark. In these situations, we are blind, and our algorithms need to explore solution landscapes blindly. That’s where genetic algorithms shine, because they explore this landscape just like biological evolution explores adaptive landscapes, through blind mutation and selection. If that blindness seems like a fatal handicap, just think about the marvels that biological evolution has created.
Today’s algorithms produce remarkable feats, but most people would not call their products—a shortest delivery route, optimal staffing at a hospital, or a humming electric grid—creative. To see what’s missing, it is useful to take another look at genetic algorithms, because they follow the same steps that evolution has used to create living beings as spectacular as redwood trees and blue whales. We have no trouble seeing these species as the results of a creative process, so what’s the difference? It cannot lie in how an algorithm creates something new, because the how is similar between biological and simulated evolution. It must lie, then, in what the algorithm creates—in its chromosomes and what they encode.
Whereas the chromosomes of most genetic algorithms are strings of numbers that represent abstract concepts like the order in which customers are visited, the DNA of a real chromosome is a string of molecules that encodes objects in the real world, from minute proteins to huge dinosaurs. Whenever evolution creates a protein to digest a new food, sense a new smell, or disarm a new antibiotic, and whenever it creates a gazelle that runs a bit faster, a bird that soars a bit higher, or a fish that dives a bit deeper, it solves an immense combinatorial optimization problem. The elements of this problem are the same old four DNA letters. Evolution combines them in ever-new ways, scouring an adaptive landscape to find its highest peaks.
The message could not be clearer: for true creation, choose the right building blocks.19
Among the first to understand this principle—and implement it—was John Koza, a former Ph.D. student of genetic algorithm pioneer John Holland. Beginning in the 1990s, Koza and his collaborators designed genetic algorithms whose chromosomes encoded the components of electric circuits, such as resistors and capacitors, as well as how these components were wired together.20 They used these algorithms to evolve not only new kinds of circuitry, but circuitry that met a rigorous legal standard for creativity. This standard is not so different from how psychologists define creativity—an original solution to a problem—except that it clearly defines the meaning of original: worthy of receiving a patent. Every invention solves some problem, but only the most original ones are patentable. In the words of US patent law, an invention is patentable if it is not obvious to a person with ordinary skills in the invention’s field. Koza’s genetic algorithms helped create electronic circuits that met this standard.
In the course of a few years, these algorithms created wiring diagrams for more than a dozen functioning circuits, such as the kind of low-pass filter that sends rumbling low-frequency sounds to a sound system’s subwoofer. Several of these circuits had been invented by human engineers and patented by companies such as AT&T and Bell Labs years before Koza’s work. But their reinvention made a powerful point: algorithms can be creative, and their products can rival those of human creators.
Another case in point: in 2005, the algorithms of Koza’s team discovered a new kind of controller—the kind that holds the speed of your car steady when it is on cruise control. The controller was sufficiently innovative that the team received a patent for it.
It was the first patented invention made by a machine.21
The creative potential of evolutionary algorithms does not end there. With chromosomes that encode the surface texture of solar cells, a genetic algorithm can evolve surfaces that excel at trapping light and increase solar-cell efficiency. In this light-harvesting problem, many suboptimal surfaces—shallow valleys—exist, and mechanisms like recombination are needed to leap over these inferior solutions.22
With chromosomes that encode the complex lens system of telescopes or binoculars, a genetic algorithm can evolve a wide-field eye piece superior to one patented by human lens designers.23 And with chromosomes tuned to the parts of an antenna, a genetic algorithm can equip NASA’s space missions with new kinds of antennae that can operate in outer space. Such an antenna was placed onto satellites in one of NASA’s space technology missions in 2006. It bears the distinction of being the first human hardware in space that was not designed by humans but rather was evolved by an algorithm.24
And as for engineering, so too for science. We admire the ingenuity of scientists like Newton and Galileo who can distill mathematical laws of nature from observing a physical system like a planet or a pendulum. As it turns out, algorithms mimicking evolution can do the same thing. In a 2009 study, scientists at Cornell University described an algorithm that can discover the equations of motion of a simple pendulum—one weight suspended from a pivot—or a more complicated double pendulum—two weights and two pivots. All the algorithm needs is data on the pendulum’s motion as well as the building blocks of the solution. These building blocks are variables and mathematical functions. In other words, such an algorithm does not manipulate transistors, lenses, or wires, but it mutates and recombines mathematical functions until it has found a combination of these functions that describes the data perfectly.25
Given such feats, we should not be surprised that genetic algorithms have been called “Thomas Edison in a box.”26 Or should we say, “Galileo in a box?” The age of creative machines clearly has arrived.
Many people recoil at this thought. It is an inconvenient truth on a par with the realization that the earth is not the center of the universe, that we share a common ancestor with chimpanzees, and that we are not the only
animals to recognize ourselves in a mirror. Discoveries like this have chipped away at our self-importance over the centuries since the Copernican revolution. But, like it or not, they are here to stay, just like the discovery that we humans have no monopoly on creativity.
And here is a thought that may soften the blow: the word machine still evokes in many of us visions of the products of a bygone era—eighteenth-century contraptions like steam engines, mechanized looms, or chronometers made of springs, rods, bearings, chains, and gears. But creative machines are not like this. Not at all. Nor are the algorithms they execute. An algorithm is often compared to a recipe followed slavishly by a chef—the machine—but no such algorithm could produce anything new. Every time you execute such an algorithm, you get the same dish. A genetic algorithm—and algorithms like simulated annealing—are different from a conventional recipe because they are stochastic. This means that randomness is essential to them, just as in biological evolution, where DNA mutations and recombination occur at random locations in a genome and where every such random change can alter evolution’s path. The products of creative machines can therefore be just as unpredictable, original, and unique as the products of biological evolution—or as human works of art.27
Art created by computers may feel even more disturbing than technology created by them because the uniqueness of great art feels at odds with the notion of an algorithmic search through a landscape. To resolve that dissonance, it helps to recall once again that the landscapes we have encountered are vast enough to admit innumerable creations that are as unique as snowflakes. Because an algorithm’s journey through such a landscape is unpredictable, it may discover each such creation only once.
A striking work of art in the Ryoanji Zen temple of Kyoto illustrates the kind of problem that an artsy algorithm might solve. This temple houses a famous rock garden with a simple design consisting of fifteen carefully arranged rocks on a bed of gravel. The garden exudes an atmosphere of uncanny harmony and serenity. A UNESCO World Heritage Site, it is visited by thousands of tourists every year. Sadly, we have no idea how the artist created the garden’s powerful effect because the garden is some five hundred years old and the artist left no record. However, cognitive scientist Gert van Tonder and two collaborators used mathematical tools to analyze its design and found a surprisingly simple pattern. From the temple’s veranda—the place from which the garden is best viewed—the symmetry of the rock arrangement evokes the fractal pattern of a branching tree. It’s a kind of pattern that humans find attractive, perhaps because of our evolutionary roots in African savannas. In other words, part of the rock garden’s appeal lies in an abstract image extracted from a motif omnipresent in nature. Consciously or not, the artist solved the problem of creating a serene ambience by embedding this image in the garden’s rock arrangement.28
Understanding the power of a work of art is one thing. Creating it is another. But even there algorithms are making great strides. And it is no coincidence that some of their most promising achievements have occurred in creating musical compositions. It’s because music provides the ideal building blocks for a creative algorithm.
The elementary building blocks of musical compositions are motifs, snippets of melodies that can be varied in ways that composers and improvisers have known and classified for centuries. Composers “augment” a motif by slowing it down, “diminish” it by speeding it up, invert it, permute its notes, play it backward, transpose it into a new key, and so on. That such “mutated” motifs could be randomly combined into novel pieces of music was already known in the eighteenth century, when musical dice games, or Musikalische Würfelspiele, as they are known in German, became popular parlor games in Europe. In such games—the best-known has been attributed to Mozart himself—dice are rolled and cards are drawn to select small snippets of music from a larger collection, which are then concatenated to compose a waltz, a polonaise, or a minuet.
The computer age took this tradition to new heights.29 It brought forth a branch of artificial intelligence research that uses algorithms to create musical compositions. One of its pioneers was David Cope, an accomplished American composer whose own work was lauded by critics and performed at Carnegie Hall when he was still a young man in the 1980s. During this time, while trying to write a commissioned opera, he experienced a severe bout of writer’s block that lasted for months. In his despair to keep producing the music that fed his family, he started to ask whether computers could help him compose. His efforts eventually culminated in a program he called Experiments in Musical Intelligence, or, more affectionately, “Emmy.”30
When Emmy was fed a composer’s work, she—yes, that’s how Cope refers to his program—analyzed the work to find signature elements of the composer’s style. She then varied these building blocks—mutation—and created new combinations of them. The results were novel compositions in the style of a Bach, Mahler, or Vivaldi. And they poured forth at breathtaking speed. In Cope’s own words: “You pushed the button and out came hundreds and thousands of sonatas.”31
We value any one composer’s work partly because there is a limited amount of it. After all, composers are mortal. Cope realized that Emmy’s unlimited creativity would diminish the value of any one composition. And so he let Emmy die. After several years, he mothballed her digital brain, but not until he had published more than a thousand of her compositions.32 Some of them appeared on CD, and others can be admired on internet platforms like YouTube. Some listeners deride these compositions as soulless, while others find them deeply touching. But many people—unless they are told beforehand—would not identify them as machine-made, making Emmy’s oeuvre a musical version of Alan Turing’s famous test for distinguishing artificial intelligence from human intelligence. In Turing’s original version from the 1950s, the test needs at least three participants: a human, an artificial intelligence, and a judge. The judge poses questions to the other two participants, but he cannot see them, and he receives only written answers to his questions. He thus needs to guess whether each answer comes from the human or the artificial intelligence. If he guesses wrong, the artificial intelligence has passed the test.
A similar test was performed with one of Emmy’s Bach-style compositions at the University of Oregon. An audience—the judges—listened to Emmy’s composition, a composition by Bach, and a third, Bach-style composition written by a contemporary composer, all of them performed by a professional pianist. When the audience members were asked to tell which was which, they got it wrong. They declared that Emmy’s composition was a genuine Bach and that the other human composition was written by the computer.33 Emmy had passed this musical Turing test.
Some critics nonetheless snivel at Emmy’s compositions and call them “imitations.” To them, Cope responds that “all composers quote and allude to music, including their own” and “I can find passage after passage in Mozart’s symphonies that quote and paraphrase similar passages in Haydn. However, we still revere both composers.”34 Cope has viewed music composition as “inspired plagiarism,” and when he calls Emmy’s compositions “recombinant music” it is not to diminish their originality.35 Rather, it is an acknowledgment that composers often do not create from scratch. Instead, they reuse, modify, and recombine what has come before them. Like nature does.
Even though mutation and recombination played a role in Emmy’s creations, she did not execute a genetic algorithm because she did not evolve a composition by continual mutation and selection over multiple generations. But other algorithms do. One of them is Melomics, whose name comes from “melody” and “genomics.” In 2012, Melomics created a composition that was performed and recorded by the London Symphony Orchestra and its top-notch professional musicians. Some listeners have described the recording as artistic, delightful, and expressive, but as with most modern music, opinions are divided.36
Algorithms can also create in other genres, like jazz. One such algorithm, called the Continuator, is the brainchild of François Pachet from the Sony
Computer Science Laboratory in Paris. The Continuator “listens” to a human player’s improvisation and learns to improvise in the same style. Pachet subjected these improvisations to a Turing test, in which the professional jazz pianist Albert van Veenendaal improvised on the piano. Pachet employed not one but two judges, both of them music critics, who had to determine whether an improvisation they heard came from van Veenendaal or from the Continuator. They could not.37
The following story is fodder for yet another Turing test:
Friona fell 10–8 to Boys Ranch in five innings on Monday at Friona despite racking up seven hits and eight runs. Friona was led by a flawless day at the dish by Hunter Sundre, who went 2–2 against Boys Ranch pitching. Sundre singled in the third inning and tripled in the fourth inning… Friona piled up the steals, swiping eight bags in all.38
The story summarizes a Little League baseball game. That’s unusual—Little League does not receive much press coverage—but even more unusual is this: the story was written by a computer. It is the product of the Chicago-based company Narrative Science. The algorithms of this and other companies prepare reports on sports events, corporate earnings, or real estate transactions, created instantly from available data when ordered by one of the company’s media clients. Many of these clients prefer anonymity, what with journalists already worried about their jobs, but they include well-respected outlets like Forbes magazine or the Associated Press, which uses them to produce three thousand financial reports per quarter.39 Chances are good that a magazine you have been reading—online or off—contains some automated reporting.40 What is more, a 2014 study showed that people cannot tell such texts from human texts.41
Computers are beginning to invade multiple domains of human creativity. They haven’t yet produced a Beethoven, Beckett, or Picasso, but their products are already more than curiosities. They appeal to human audiences and are going commercial, in companies like Narrative Science or Jukedeck—a British start-up selling algorithmic music on demand for video soundtracks.42 What is more, if other branches of artificial intelligence are any guide, their creativity will be improving faster than we think. Just remember how explosively the power of chess computers increased: they beat a world champion like Gary Kasparov less than fifty years after their humble beginnings.
Life Finds a Way Page 12
