Friday, September 14, 2007

2007

Evolutionary algorithms now surpass human designers

  • 28 July 2007
  • NewScientist.com news service
  • Paul

CHARLES DARWIN's theory of evolution has been the source of much controversy since its publication in 1859, most recently involving the intelligent design (ID) lobby in the US. Now the theory is fuelling another debate, although for once the battle lines have nothing to do with religion.

Instead of pitting God against science, the emerging spat centres on evolutionary algorithms (EAs), which mimic the processes of natural selection and random mutation by "breeding", selecting and re-breeding possible designs to produce the fittest ones.

EAs take two parent designs - for a boat hull, say - and blend components of each, perhaps taking the surface area of one and the curvature of another, to produce multiple hull offspring that combine the features of the parents in different ways. Then the algorithm selects those offspring it considers are worth re-breeding - in this case those with the right combination of parameters to make a better hull. The EA then repeats the process. Although many offspring will be discarded, after thousands of generations or more, useful features accumulate in the same design, and get combined in ways that likely would not have occurred to a human designer. This is because a human does not have the time to combine all the possibilities for each feature and evaluate them, but an EA does. "Human engineers usually design stuff by tweaking a few parameters," says Steve Manos of University College London, who has created optical fibres using EAs.

Proponents of EAs say they could replace traditional methods in many fields from designing exotic new types of optical fibre and USB memory sticks to more aesthetic computer-generated art. Critics argue that the technique may lead to designs that can't be properly evaluated since no human understands which trade-offs were made and therefore where failure is likely.

Another stumbling block is a problem of perception. "To mainstream engineers there is a disbelief that a self-organising process like an EA can produce designs that outperform those designed using conventional top-down, systematic, intelligent design," says Hod Lipson, a computer scientist specialising in evolutionary design at Cornell University in Ithaca, New York. "That tension mirrors the tension between evolutionary biology and ID. That's the challenge we need to rise to in winning people over."

Lipson and other members of the US Association for Computing Machinery's Special Interest Group on Genetic and Evolutionary Computation (SIGEVO) worry that if they can't persuade their fellow engineers to use EAs, then evolved machines, systems and software that work fantastically well risk being lost.

EAs are nothing new. The automobile and aerospace industries have been using them since the late 1980s to evolve optimal wing, fin and flap profiles for aircraft, and streamlined shapes for cars. Pharmaceutical companies have also bred molecules to find drugs that bind to target proteins, and stock traders have used EAs to second-guess the stock markets (New Scientist, 30 May, p 42).

However, most of these applications require ultra-fast computers, both to breed the thousands, or even billions, of generations and to simulate the results to select those offspring that are fit for re-breeding. This has limited their use to a few niche applications.

That is now changing with the availability of ever more powerful computers, the advent of distributed computing "grids", which pool the resources of thousands of PCs, and the emergence of multicore chips (New Scientist, 10 March, p 26), which suit EAs because it's easy to divide up the tasks between cores. As a result, designs can now be evolved in days rather than months or years and EAs are going mainstream.

Exotic technologies

"We can now undertake evolutionary problems that were previously too complicated or time-consuming," says John Koza, a computer scientist and EA pioneer from Stanford University in California. "Things we couldn't have done in the past, because it would have taken two months to run the genetic program, are now possible in days or less."

Some of these EAs are being used to come up with more exotic versions of existing technologies. Joe Sullivan at the University of Limerick in Ireland used an EA to make a USB flash memory stick that lasts far longer than those on the market today. Typically, memory sticks can be erased and rewritten about 10,000 times. Every time data is erased, residual charge is left on the storage transistors. Eventually, this builds up and prevents the memory being rewritten. Using large voltages to read, write and erase memory, and applying them for longer causes more residual charge. However, applying too little voltage for too little time could make the memory unreliable. To see if he could extend the lifetime without making the device less reliable, Sullivan created a genetic algorithm that varied the voltages and their timings. The result was a combination that meant the memory stick lasted 30 times longer.

To encourage more of this kind of work, SIGEVO runs the annual Human Competitiveness Awards, dubbed the "Humies". The idea is to reward designs produced by EAs that are "competitive with the work of creative and inventive humans". The winners were announced at the Genetic and Evolutionary Computing Conference (GECCO 2007) in London this month.

Manos walked off with the $5000 gold prize for combining EAs with the emerging field of "holey" optical fibres (New Scientist, 12 June 1999, p 36). These are shot through with tens of micrometre-wide holes whose exact pattern controls the wavelength of light that can be beamed down them. Previously the holes were arranged in a hexagonal pattern, which has limited the range of bandwidths. That changed when Manos's team at the University of Sydney, Australia, allowed an EA to breed exotic new hole patterns. One looked like a flower, with larger ovoids as "petals", and doubled the fibre's bandwidth. They have patented that fibre and founded a company to market it.

Other prizewinners used EAs to do what humans already do, but faster. Pierre Legrand and colleagues at the University of Bordeaux 2, France, developed an evolutionary system to configure the electrodes for cochlear implants. Up to 22 electrodes on the auditory nerve let cochlear implants restore lost hearing, but the voltages and timings of the signals applied to them are highly individual, requiring much adjustment for speech to be audible. Legrand's team took just one-and-a-half days to configure an optimal pattern for one patient whose doctors had not succeeded in 10 years.

Not content with aiming for top results however, another group of researchers is using EAs to produce designs that dodge patents on rival inventions. Koza took a 1-metre-tall, Wi-Fi antenna made by Cisco and attempted to create another that did a better job without infringing Cisco's patent. He used an EA that bred antennas by comparing offspring with how the Cisco patent works and weeding out ones that worked similarly. "Our genetic program engineered around the existing patent and created a novel design that didn't infringe it," says Koza. Not only would this allow a company to save money on licensing fees, the new design was also itself patentable.

Patents aren't the only aspect of human creativity that EAs are closing in on. David Oranchak, a computer scientist based in Roanoke, Virginia, is using EAs to create art. Over six months, he selected the photos voted most interesting by users of the photo sharing site Flickr. His algorithm then used the colours and textures in those photos to automatically select and breed images that humans might like.

Nonetheless, EAs face challenges. A common objection is that some electronic circuits and antennas work fine, but the mathematics behind them is intractable. And if you don't know how an evolved design works, how can you know when it might fail? But Koza calls that objection "self-serving and bogus". "Like any design you can test the hell of the one solution you settle on," he says.

Celebrated UK innovator James Dyson, inventor of the bagless vacuum cleaner, has a more emotional objection. "Evolutionary algorithms will mean the end of those exciting stories about how people made great inventions by accident," he says. "Human ingenuity and intuition should remain crucial in making a success of any product."

But that could change, says Manos. "Once you show them a design that's better than anything on the market that really starts to convince them," he says.

Related Articles
Weblinks
From issue 2614 of New Scientist magazine, 28 July 2007, page 26-27
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)