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.
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."
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.