A Methodology for Processing Problem Constraints in Genetic Programming

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

  author =       "Cezary Z. Janikow",
  title =        "A Methodology for Processing Problem Constraints in
                 Genetic Programming",
  journal =      "Computers and Mathematics with Applications",
  year =         "1996",
  volume =       "32",
  number =       "8",
  pages =        "97--113",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://www.cs.umsl.edu/~janikow/psdocs/cgp.CMwA.ps",
  URL =          "http://www.sciencedirect.com/science/article/B6TYJ-41GX54B-9/1/5a1e263b86597ce90a6eec429c357ce5",
  URL =          "http://citeseer.ist.psu.edu/326996.html",
  ISSN =         "0898-1221",
  DOI =          "doi:10.1016/0898-1221(96)00170-8",
  abstract =     "Search mechanisms of artificial intelligence combine
                 two elements: representation, which determines the
                 search space, and a search mechanism, which actually
                 explores the space. Unfortunately, many searches may
                 explore redundant and/or invalid solutions. Genetic
                 programming refers to a class of evolutionary
                 algorithms based on genetic algorithms, but using a
                 parameterized representation in the form of trees.
                 These algorithms perform searches based on simulation
                 of nature. They face the same problems of
                 redundant/invalid subspaces. These problems have just
                 recently been addressed in a systematic manner. This
                 paper presents a methodology devised for the public
                 domain genetic programming tool lil-gp. This
                 methodology uses data typing and semantic information
                 to constrain the representation space so that only
                 valid, and possibly unique, solutions will be explored.
                 The user enters problem-specific constraints, which are
                 transformed into a normal set. This set is checked for
                 feasibility, and subsequently, it is used to limit the
                 space being explored. The constraints can determine
                 valid, possibly unique spaces. Moreover, they can also
                 be used to exclude subspaces the user considers
                 uninteresting, using some problem-specific knowledge. A
                 simple example is followed thoroughly to illustrate the
                 constraint language, transformations, and the normal
                 set. Experiments with Boolean 11-multiplexer illustrate
                 practical applications of the method to limit redundant
                 space exploration by using problem-specific
  notes =        "http://laplace.cs.umsl.edu/~janikow/cgp-lilgp/ CGP
                 uses GP [Koza] to evolve programs (or trees in
                 general). It extends GP by allowing syntactic and
                 sematical constraints on function calls (the
                 constraints can be weighted rather than strict), plus
                 function overloading. In future releases, evolution of
                 representation (i.e., constraints), ADFs, and recursive
                 functions are planned.

                 lil-gp comparison of solving 11-multiplexor problem
                 nine different ways with different type systems. Some
                 tighter (than Koza) type systems (eg different address
                 and data bits, different function sets) are worse than
                 Koza GP and some are better. Problem dependant reasons
                 for this suggested. Comparison with GIL. STGP",

Genetic Programming entries for Cezary Z Janikow