Technology Research News
Computer 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
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,"
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
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.
28/April 4, 2001
Programming goes quantum
Diversity trumps fitness
Nanotubes paint clear
Hitting the deck
Magnetic fields move
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link