Could Evolutionary Computation Cut Billions of Years in Solving Problems?
Happy birthday, Darwin! A computer science and mathematics team from Hampshire College in Massachusetts and the State University of New York in New Paltz has used evolutionary processes to solve a century-old algebra problem far faster and more efficiently than any past efforts of humans or machines. The work suggests that evolutionary computation may be able to help us solve problems in a range of different fields.
Hampshire’s Lee Spector, a computer scientist specializing in genetic programming, and SUNY-New Paltz’s David M. Clark, a mathematician—along with Spector’s students Ian Lindsay and Bradford Barr and former student Jon Klein—won the 2008 Genetic and Evolutionary Computation Conference’s top prize
for human-competitive results produced by genetic and evolutionary computation. To win this prize, contestants must show that their systems equal or improve upon the performance of humans.
Using a Beowulf-style computer cluster, they simulated Darwinian processes to look for discriminator terms, majority terms, and Mal’cev terms for finite algebras. Put simply, they were searching for formulas that are useful in the design of electronic switching circuits.
To succeed, they needed a formula of manageable size produced in a reasonable amount of time. Two prior methods had been developed for solving the problem, neither of which meets both requirements: Abstract methods from universal algebra result in millions of characters, rendering resultant formulas useless for practical application. A direct computer search would take billions of years—in fact, close to the amount of time the universe has existed—to find a solution.
Evolutionary computation produced useful formulas of fewer than 300 characters within just a few hours.
In addition to advancing knowledge in both mathematics and genetic programming, these research findings will be of practical benefit to electronic engineers, as electronic switching circuits are used in many electronic devices.
“Humanity faces many problems, like those stemming from global climate change, for which new technologies may be part of the solution,” Spector said. “Human ingenuity can take us far in designing such technologies, but evolution by natural selection is an even more powerful designer than human intelligence. For this reason we should apply evolutionary computation to our most urgent and intractable problems.”
Evolutionary computation is a growing sub-field of computer science. Evolutionary processes are built into computer software. The user specifies the ingredients that can be used and how the desirability of any particular design can be measured. The system then creates and tests thousands or millions of random combinations of the ingredients. The better combinations are allowed to produce “children” by mutation (random changes) and recombination (random part-swapping). This often produces, after many generations, genuinely novel and useful designs and inventions.
Both Spector and Clark stressed that their interdisciplinary collaboration was key to their project’s success. By using simulated Darwinian processes on a computer to solve a mathematical problem, they were able to demonstrate quantitatively that evolutionary processes can be vastly more effective than previously available theoretical or computational methods.