Emergent Behaviour, Population-based Search and Low-pass Filtering

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Riccardo Poli and Alden H. Wright and 
                 Nicholas F. McPhee and William B. Langdon",
  title =        "Emergent Behaviour, Population-based Search and
                 Low-pass Filtering",
  institution =  "Department of Computer Science, University of Essex",
  year =         "2006",
  type =         "Technical Report",
  number =       "CSM-446",
  month =        feb,
  ISSN =         "1744-8050",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://cswww.essex.ac.uk/technical-reports/2006/csm-446.pdf",
  abstract =     "In recent work we have formulated a model of emergent
                 coordinated behaviour for a population of interacting
                 entities. The model is a modified spring mass model
                 where the masses can perceive the environment and
                 generate external forces. As a result of the
                 interactions the population behaves like a single
                 organism moving under the effect the vector sum of the
                 external forces generated by each entity. When such
                 forces are proportional to the gradient of a resource
                 distribution f(x), the resultant force controlling the
                 single emergent organism is proportional to the
                 gradient of a modified food distribution. This is the
                 result of applying a filtering kernel to f(x). The
                 kernel is typically a low-pass filter.

                 This model can be applied to genetic algorithms (GAs)
                 and other population-based search algorithms. For
                 example, in previous research, we have found kernels
                 (via genetic programming) that allow the single
                 organism model to track the motion of the centre of
                 mass of GAs and particle swarm optimisers accurately
                 for many generations.

                 we corroborate this model in several ways. Firstly, we
                 provide a mathematical proof that on any problem and
                 for any crossover operator, the effect of crossover is
                 that of reducing the amplitude of the derivatives
                 (slopes) of the population distribution. This implies
                 that a GA perceives an effective fitness landscape
                 which is a smoothed, low-pass filtered version of the
                 original. Then, taking inspiration from this result and
                 our active mass-spring model, we propose a class of
                 fitness functions, OneMix, where there is an area of
                 the landscape with high frequency variations. This area
                 contains the global optimum but a genetic algorithm
                 with high crossover probability should not be able
                 ``see'' it due to its low-pass behaviour. So, a GA with
                 strong crossover should be deceived and attracted
                 towards a local optimum, while with low crossover
                 probability this should not happen. This is, indeed,
                 what happens as we demonstrate with a variety of
                 empirical runs and with infinite-population model
                 simulations. Finally, following our earlier approach,
                 we also evolved kernels for OneMix, obtaining again a
                 good fit between the behaviour of the
                 ``single-organism'' hill-climber and the GA.",
  notes =        "See also \cite{poli:2006:cec}",
  size =         "23 pages",

Genetic Programming entries for Riccardo Poli Alden H Wright Nicholas Freitag McPhee William B Langdon