Home
Parisian
Evolution / Cooperative Co-evolution
Parisian
Evolution
The
Parisian approach is actually a generalisation of the classifier
systems approaches. It is based on the capability of an EA not only
to push its best individual towards the global optimum, but also to
drive its whole population into attractive areas of the search space.
The idea is then to design a fitness landscape where the solution to
the problem is given by the whole population or at least a set of
individuals, rather than a single one. Each individual only encodes a
part of a solution, the global solution to the problem then arises
from several ``collaborating'' individuals.
This
approach refers to the spirit of co-evolution approaches: a
population is viewed as a ``society'' building in a common effort the
solution we are looking for, but contrary to co-evolution, the
species are not specifically identified or separated. In other terms,
the difference between Parisian evolution and mainstream artificial
evolution essentially resides in the population's semantics rather
than the internal evolutionary engine. Of course the design of such
algorithms may become slightly more complex than with a classical
evolutionary approach, as e.g. maintaining the diversity of the
population is a crucial factor in the success of a Parisian approach.
Moreover, splitting the problem into interconnected subproblems is
not always possible. However, there is great benefit whenever it is
possible to do so: a Parisian approach limits the computational waste
occurring in classical EA implementations, where at the end of
evolution, the whole final population is dumped except the best
individual only. Experimental and theoretical developments proved
that an evolutionary algorithm (EA) collects more information about
its environment than the sole knowledge of the global optimum. The
Parisian approach tries to exploit this important feature of EAs.
|
|
A
Parisian EA usually contains all the usual components of an EA,
plus the following (optional) additional ingredients:
multiple
fitness functions : a ``global'' fitness calculated on the whole
population, or on a vast portion of it, and one or several
``local'' fitness functions measuring each individual's
contribution to the global solution.
the
global fitness may result from the sum of individuals'
contributions, or in some cases the algorithm may work the other
way, each individual's own fitness being defined as its marginal
contribution to global fitness,
a
diversity mechanism, in order to avoid degenerate solutions where
most individuals would get crowded together into a few areas in
the search space.
|
Examples
of applications :
home