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 :