From: Julie Letchner (letchner_at_cs.washington.edu)
Date: Sun Oct 19 2003 - 22:27:44 PDT
Eisenstein presents his experiments using evolutionary algorithms to
develop RoboCode controllers in TableREX, an encoding language developed
explicitly for this purpose.
I felt that the most valuable information in the paper was not explicitly
stated, but was the portrayal of the delicacy of genetic algorithms with
respect to design decisions. Eisenstein's work outlines two major
tradeoffs. The first is between fitness functions that reward the
end-result desired behavior but get stuck easily in local maxima, and
functions that encourage intermediate developmental traits that help to
eventually surpass many local maxima, at the cost of degraded intermediate
performance. A second tradeoff is between evolution at a very low level,
yielding the full range of evolutionary potential but resulting in
'non-compact' programs, and the preservation of 'compact' sections of code
that perform a specific, valuable function such as targeting but introduce
constraints on the space of potential solutions.
It is unfortunate that although Eisenstein is clearly conscious of the
tradeoffs described above, he does not discuss them explicitly in any
detail. In particular, his experiments probably lent him enough
understanding to be able to provide some basic heuristics for designing
fitness functions, evolutionary selection/crossover schemes, and genetic
encodings. There are a few helpful tidbits sprinkled about the paper, such
as the explanation about why gun-firing robots are quickly filtered out of
a population; however, a consolidated look at how these experiments
generalize into useful information for other genetic algorithm applications
would be nice, particularly since the development of RoboCode controllers
is a rather niche market.
In the Future Work section, the paper mentions the concept of 'compact' vs.
'non-compact' TableREX programs. Eisenstein suggests that the ability to
rearrange non-compact programs into compact ones would be useful. I think
that this idea would be more useful if taken one step further; instead of
simply identifying 'compact' sections of programs, perhaps a multi-step
evolution would be appropriate, where the first step is to evolve 'compact'
sections of code and the second step would perform evolution on these
sections as units. Such an approach could potentially simplify the issues
of selecting fitness functions and encouraging complex behavior, since the
each step's goals are more specific in a multi-step evolution process.
Finally, this paper shows that the interactions between an algorithm's
fitness function, encoding scheme, and evolutionary process are complex and
not well understood. Work on understanding how each of these processes is
affected by or changes with the others would be highly valuable in
generating better genetic algorithms for any application.
~*~*~*~*~*~*~*~*~*~*~
Julie Letchner
(206) 890-8733
University of Washington
Computer Science & Engineering
letchner_at_cs.washington.edu
This archive was generated by hypermail 2.1.6 : Sun Oct 19 2003 - 22:28:12 PDT