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

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

@InProceedings{poli:2006:cec,
  author =       "R. Poli and A. H. Wright and N. F. McPhee and 
                 W. B. Langdon",
  title =        "Emergent Behaviour, Population-based Search and
                 Low-pass Filtering",
  booktitle =    "2006 IEEE World Congress on Computational
                 Intelligence, 2006 IEEE Congress on Evolutionary
                 Computation",
  year =         "2006",
  pages =        "395--402",
  address =      "Vancouver",
  month =        "16-21 " # jul,
  keywords =     "genetic algorithms, genetic programming, PSO",
  URL =          "http://www.cs.essex.ac.uk/staff/poli/papers/ceclowpass2006.pdf",
  URL =          "http://ieeexplore.ieee.org/iel5/11108/35623/01688294.pdf?tp=&isnumber=35623&arnumber=1688294&punumber=11108",
  size =         "8 pages",
  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 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.

                 In this paper 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:CSM446}",
}

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