How algorithms will optimize everything.
In 1852, mathematics professor Augustus De Morgan described a problem posed by a student:
If a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured—four colours may be wanted, but not more—the following is the case in which four colours are wanted. Query cannot a necessity for five or more be invented.
That is, you’ll never need more than four colors on an ordinary two-dimensional map in order to color every country differently from the countries adjoining it. A proof for the four-color conjecture evaded mathematicians until 1976, when Kenneth Appel and Wolfgang Haken announced a solution. They had reduced the set of all possible map configurations to 1,936 fundamental configurations, then used 1,200 hours of computer time to verify that each could be colored with only four colors. In all, their program performed billions of individual calculations.
Appel and Haken’s computer-based casewise approach was immediately controversial. Theirs was the first major proof that couldn’t be entirely comprehended by an individual human—what a critic labeled a “non-surveyable proof.” Since then, mathematicians have continued to be skeptical of computer proofs. In 1998, Thomas Hales offered a casewise computer-checked proof to the Kepler conjecture; a reviewer likened the years-long process of checking it to proof-reading a phone book.
At first glance, these sorts of arguments look like academic quirks—the preoccupation of a rarified group of intellectuals who think computer proofs aren’t beautiful enough. But the four-color proof was the first landmark application of a problem-solving approach that has become commonplace in the digital realm and will soon be commonplace in the physical world. Our environment is about to become computer optimized.
We’re surrounded by what you might call non-surveyable objects: a modern airliner results from millions of person-hours of design and engineering work, and no individual engineer could possibly verify every aspect of its design or search the entire space of design alternatives to identify improvements. The Web takes this even further. Not only is the codebase for Google Search large and complex beyond the comprehension of any individual, but it also routinely generates web pages on demand that no human has ever seen before, or will ever see again.
What’s new is the use of machine learning techniques to create and optimize physical designs. Researchers have been investigating the idea for decades, but cheap cloud computing and advances in machine learning will make these techniques accessible in the design of nearly anything. The result is a design whose rationales are known only to an artificial-intelligence algorithm, in which there are design decisions that no human can articulate. These designs are likely to be much more complex than human designs, and they make accessible a vast design space that ordinary human iteration wouldn’t be able to explore.
Machine-learning techniques are now widely used to optimize complex information systems. A genetic algorithm starts with a fundamental description of a desired outcome—say, an airline timetable that’s optimized for fuel savings and passenger convenience. It adds in constraints—the number of planes an airline owns, the airports it operates in, and the number of seats on each plane. It loads what you might think of as independent variables—details on thousands of flights from an existing timetable, or perhaps randomly generated dummy information.