Entropy as an Organizing Principle for Selection in Evolutionary Robotics (Julius Faber)

Master Thesis

In evolutionary computation, a goal-based objective function is typically un-
able to include the local challenges on the way towards its fulfillment and tends
to to cause the search to converge prematurely. Therefore, this work proposes
to use objectives that are defined by different aspects of an individuals in-
teraction with the environment and a selection procedure able to reallocate
search efforts in order to avoid convergence. The objectives, curiosity, novelty
and evolvability, differ in the time-scale they operate over and the amount of
information they include about the problem structure. The common theme
of these objectives is their tendency to increase the diversity of behaviors,
which is assumed can act as general-purpose utility value. The goal is to
combine the benefits of the objectives by optimizing subsets of them simulta-
neously with a multi-objective EA. Entropy is used as unifying framework for
modelling the objectives and determining which of their values are considered
desirable. Using entropy for the latter part relies on the fact that degenerate
behaviors are more pervasive in search spaces than functional ones. Thus,
selecting for high-entropy values implicitly treats the frequency with which a
behavior occurs as a heuristic of its interestingness, reallocating search efforts
towards diversity. The performance of the different objectives and selection
methods are evaluated by solving deceptive navigation tasks. Verified on a
more challenging biped locomotion experiment, the new finding of this work
is that entropy selection is as good or better than optimization. Concerning
the individual objectives, these work’s results support previous findings that
novelty is a very good indicator for selection and additionally show that it
can be efficiently modelled with entropy. The method of modelling novelty
with entropy is shown to be applicable to many, possibly higher dimensional
and less informative behavioral characterizations simultaneously without a de-
crease in conceptual simplicity and computational efficiency, indicating how
future research could explore more complex behavior spaces and problems.
Concerning the evolvability objective, which describes the capacity to pro-
duce diversity and generalization, this work investigates how it can be esti-
mated from the many individuals discarded during search, in order to avoid
IIthe many extra evaluations necessary to calculate it precisely. Also, this work
proposes how an elitist-multiobjective EAs could interpret evolvability as adap-
tive variation without referring to a specific task. Taken together, the negative
results of both evolvability-estimations indicate that different behaviors might
have different potentials for evolvability and should therefore not be compared
on it globally.

Link to Thesis [1]

Paulo Urbano

Joel Lehman

Oliver Brock