Diversity
trumps fitness
By
Kimberly Patch,
Technology Research NewsComputer algorithms that solve problems by mimicking evolution generally compare several possible answers that are represented as individuals made up of a group of genetic traits. The algorithms choose the best ones, immediately discard the rest, and mix the traits from the winners to produce a new generation to choose from.
A researcher from Switzerland has taken a different approach with an evolutionary algorithm that shows promise for solving difficult problems with lots of possible answers. The key difference is the Fitness Uniform Selection Strategy (FUSS) algorithm doesn't immediately discard the losing combinations.
In keeping more possibilities around for a longer time, the algorithm continues to cover a wide range of possibilities. This increases the chance that the best solution will be found more quickly, and decreases the chance that the solution found will be the best solution only within a restricted range of traits, according to Marcus Hutter, a postdoctoral researcher at the Research Institute for Artificial Intelligence in Switzerland.
The idea is that, although the end goal is to obtain an individual with the best traits possible, the best path to that goal is not necessarily through producing many individuals with the best traits possible in each generation. By keeping a wider range of individuals around, FUSS can be faster in finding a solution with the best combination of traits for certain types of difficult problems, according to Hutter.
The FUSS pool of individuals as a whole may not be as as fit, or close to a solution, at each step as the pool of individuals in a standard evolutionary selection algorithm. In the end, however, this doesn't really matter, said Hutter. "We're not primarily interested in a population converging to maximal fitness, but only in a single individual of maximal fitness," he said.
For example, the problem of designing a motor with minimal gas consumption only requires one solution, not a group of solutions almost as good as the best solution. The traditional approach finds a pool of good designs among which lies the best one. In contrast, the FUSS approach finds one or a few optimal designs, but with a better chance that the best one is really the optimal solution in problems with many possibilities, according to Hutter.
This is because as the whole population in a standard evolutionary algorithm becomes more fit over time, the population also becomes less diverse, which means it has a greater chance of finding a solution that is optimal for only a certain range of possibilities.
"In a typical FUSS population there are many unfit and only a few fit individuals. [Because] the fraction of fittest individuals in a population is always small," the whole population is not likely to move toward a sub optimal design, said Hutter.
Standard approaches use less memory because they eliminate more possibilities, but "a wrong step at some point in evolution might cause further evolution in the wrong direction. Once a local optimal has been found and all unfit individuals [have been]... eliminated it is very difficult to undo the wrong step," said Hutter. "In FUSS, all fitness levels remain occupied... new mutants are steadily created, occasionally... leading to further evolution in a more promising direction," he said.
The approach is novel, according to Erick Cantu-Paz, a computer scientist at the Center for Applied Scientific Computing at Lawrence Livermore National Laboratories. "I was actually surprised by the originality of the idea," he said. The approach "breaks out of the convention of trying to increase the average fitness of the population. This method obviously preserves diversity [and] preserving diversity is a good thing because it prevents useful building blocks [from being deleted] from the population," he said.
The flip side is the algorithm needs more memory to preserve the larger population of individuals, said Cantu-Paz.
The method is a good fit for problems where keeping a lot of diversity in the population helps build a solution through crossover or mutation, he said. It will likely be useful "for difficult problems where you would need to keep a lot of complicated pieces around," said Cantu-Paz.
Hutter is working to find the range of problems the FUSS approach is appropriate for. One possibility is using it it to optimize fluid dynamics problems, which are inherently complicated.
The research was funded by the Dalle Molle Insitute for Artificial Intelligence (IDSIA) in Switzerland, the Office of Naval Research (ONR) and NASA.
Timeline: < 2 years
Funding: Institute, Government
TRN Categories: Artificial Life and Evolutionary Computing
Story Type: News
Related Elements: Technical paper, "Fitness Uniform Selection to Preserve Genetic Diversity," Computing Research Repository (CORR), March 14, 2001: http://xxx.lanl.gov/abs/cs.AI/0103015.
Advertisements:
March 28/April 4, 2001
Page One
Programming goes quantum
Diversity trumps fitness
Nanotubes paint clear picture
Hitting the deck cools microdevices
Magnetic fields move microbeads
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
