Genetic Programming Estimates of Kolmogorov Complexity   [GP]

by

Conte, M., Tautteur, G., Falco, I., D., Falco, I., ., Cioppa, A., D. and Tarantino, E.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Genetic Algorithms: Proceedings of the Seventh International Conference (Conference proceedings), 1997, p. 743-750
Keywords:Genetic Programming, Genetic Algorithms
Abstract:
In this paper the problem of the Kolmogorov complexity related to binary strings is faced. We propose a Genetic Programming approach [GP] which consists in evolving a population of Lisp programs looking for the optimal program that generates a given string. This evolutionary approach has permited to overcome the intractable space and time difficulties occurring in methods which perform an approximation of the Kolmogorov complexity function. The experimental results are quite significant and also show interesting computational strategies so proving the effectiveness of the implemented technique.
Notes:
ICGA-97
URL(s):Postscript
(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{DeFalco:1997:GPekc,
  author =       "M. Conte and G. Tautteur and I. {De Falco} and A.
                 Della Cioppa and E. Tarantino",
  title =        "Genetic Programming Estimates of Kolmogorov
                 Complexity",
  booktitle =    "Genetic Algorithms: Proceedings of the Seventh
                 International Conference",
  year =         "1997",
  editor =       "Thomas Back",
  pages =        "743--750",
  address =      "Michigan State University, East Lansing, MI, USA",
  publisher_address = "San Francisco, CA, USA",
  month =        "19-23 " # jul,
  publisher =    "Morgan Kaufmann",
  keywords =     "Genetic Programming, Genetic Algorithms",
  ISBN =         "1-55860-487-1",
  URL =          "http://www.irsip.na.cnr.it/~hotg/papers/kc.ps",
  size =         "8 pages",
  abstract =     "In this paper the problem of the Kolmogorov complexity
                 related to binary strings is faced. We propose a
                 Genetic Programming approach which consists in evolving
                 a population of Lisp programs looking for the optimal
                 program that generates a given string. This
                 evolutionary approach has permited to overcome the
                 intractable space and time difficulties occurring in
                 methods which perform an approximation of the
                 Kolmogorov complexity function. The experimental
                 results are quite significant and also show interesting
                 computational strategies so proving the effectiveness
                 of the implemented technique.",
  notes =        "ICGA-97",
}