Polar IFS + Individual Genetic Programming = Efficient IFS Inverse Problem Solving

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

@TechReport{collet:1999:RR-3849,
  author =       "Pierre Collet and Evelyne Lutton and 
                 Frederic Raynal and Marc Schoenauer",
  title =        "Polar {IFS} + Individual Genetic Programming =
                 Efficient {IFS} Inverse Problem Solving",
  institution =  "INRIA",
  year =         "1999",
  number =       "RR-3849",
  address =      "Domaine de Voluceau - Rocquencourt - B.P. 105 78153 Le
                 Chesnay Cedex France",
  month =        dec,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://minimum.inria.fr/evo-lab/Publications/RR-PolarIFS.ps.gz",
  abstract =     "The inverse problem for Iterated Functions Systems
                 (finding an IFS whose attractor is a target 2D shape)
                 with non-affine IFS is a very complex task. Successful
                 approaches have been made using Genetic Programming,
                 but there is still room for improvement in both the IFS
                 and the GP parts. The main difficulty with non-linear
                 IFS is the efficient handling of contractance
                 constraints. This paper introduces Polar IFS, a
                 specific representation of IFS functions that shrinks
                 the search space to mostly contractive functions.
                 Moreover, the Polar representation gives direct access
                 to the fixed points of the functions, whereas the fixed
                 point of general non-linear IFS can only be numerically
                 estimated. On the evolutionary side, the
                 {"}individual{"} approach is similar to the Michigan
                 approach of Classifier Systems: each individual of the
                 population embodies a single function rather than the
                 whole IFS. A solution to the inverse problem is then
                 built from a set of individuals. Both improvements show
                 a drastic cut-down on CPU-time: good results are
                 obtained with small populations in few generations.",
  abstract =     "Lorsque l'on s'interesse aux IFS (systemes de
                 fonctions iterees) non affines, la resolution du
                 probleme inverse (c'est-a-dire trouver l'IFS dont
                 l'attracteur approxime au mieux une forme
                 bidimensionnelle donnee) devient un probleme tres
                 complexe. Ce probleme a deja ete resolu avec succes a
                 l'aide de strategies de programmation genetique,
                 fondees sur une representation des fonctions sous forme
                 d'arbres. La principale difficulte de cette approche
                 etant la gestion efficace des contraintes de
                 contractance sur les fonctions, nous proposons ici
                 l'emploi d'une representation polaire des IFS non
                 affines, centree sur le point fixe de chaque fonction.
                 Cette representation a deux principaux avantages :

                 une contrainte simple sur la definition de la
                 composante radiale de chaque fonction assure sa
                 convergence vers un point fixe (le point central de sa
                 representation polaire),

                 l'acces au point fixe de chaque fonction est direct (il
                 n'est plus necessaire de l'estimer comme dans
                 l'approche en coordonnees cartesiennes).

                 Nous presentons ensuite une strategie originale de
                 programmation genetique, fondee sur une exploitation
                 plus {"}economique{"} des strategies evolutionnaires :
                 l'approche {"}individuelle{"}, o\`{u} chaque individu
                 de la population represente une seule fonction (au lieu
                 d'un IFS complet). La solution au probleme etant
                 fournie par un ensemble d'individus de la population
                 finale, des resultats sont obtenus de fa\c{c}on plus
                 rapide et plus efficace que dans la version classique
                 o\`{u} tous les individus de la population finale sauf
                 un (le meilleur) sont ecartes.",
  notes =        "in english",
  size =         "30 pages",
}

Genetic Programming entries for Pierre Collet Evelyne Lutton Frederic Raynal Marc Schoenauer