A Study on Evolutionary Automatic Generation of Programs Using Graph Structured Representation

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

  author =       "Shinichi Shirakawa",
  title =        "A Study on Evolutionary Automatic Generation of
                 Programs Using Graph Structured Representation",
  school =       "Faculty of Environment and Information Sciences,
                 Yokohama National University",
  year =         "2009",
  address =      "Japan",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://hdl.handle.net/10131/6717",
  URL =          "http://kamome.lib.ynu.ac.jp/dspace/bitstream/10131/6717/1/12201064-01.pdf",
  size =         "116 pages",
  abstract =     "A construction of the complex algorithms and systems
                 is becoming increasingly important along with
                 development of the computers and the machines. In
                 general, it is difficult to handed construction of
                 algorithms because it requires much trial and error. On
                 the other hand, automatic programming, which generates
                 computer programs automatically, has been actively
                 investigated in recent studies. Automatic programming
                 is the methods for full−automatic generation of
                 programs (algorithns) without handed

                 Genetic programming (GP)is a typical example of
                 automatic progamming. GP evolves computer programs,
                 which usually have a tree structure, and searches for a
                 desired program using a genetic algorithm (GA). GA is a
                 search algorithm which generates new individuals
                 (searching points)by using genetic operators such as
                 selection, crossover, and mutation, and then discovers
                 practical or optimal solution fast. It is possible to
                 search fbr GP if the evaluation value of a certain
                 solution(program)can be given. Therefore, we expect to
                 obtain practical solutions even if a detailed procedure
                 of the algorithms that wants to be achieved is
                 uncertain. GP have been applied to various fields and
                 its effectiveness is demonstrated. The typical examples
                 are symbolic regression, circuit design, image
                 processing, and autonomous robots contro1. Recently,
                 many extensions and improvements to GP have been
                 proposed. However, various problems exist when the
                 complex program is constructed automatically. The tree
                 structure which is usually used in GP is dificult to
                 represent loop and recursion, and it is necessary to
                 handle multiple data types. Moreover, GP has a tendency
                 to create programs with unecessarily Iarge size.

                 In this study, automatic programming methods whose
                 representation is graph (network) structure are
                 proposed. The reason to use the graph structure is its
                 height description abiIity. It has various advalltages
                 such as reusing of nodes, loop structure and containing
                 time series by using graph structure.

                 At first, the author targets automatic construction of
                 image transformation as a problem domain. The author
                 proposes an automatic construction method for image
                 transformation by using graph representation, named
                 Genetic Image Network (GIN)and its extended method,
                 Feed Forward Genetic Image Network (FFGIN). From
                 several experiments of automatic construction of image
                 transformation, we verify the effectiveness of GIN and

                 After that, the author proposes a method of automatic
                 construction of image classifiers based on GIN,
                 designated as Genetic lmage Network for lmage
                 Classification (GIN−IC). GIN−IC transforms original
                 images to easier−to−classify images using image
                 transformation nodes, and selects adequate image
                 fbatures using feature extraction nodes. The author
                 applies GrN−IC to test problems involving
                 multi−class categorization of texture images, and
                 shows that the use of irnage transformation nodes is
                 effective for image classification problems.

                 In addition, the author proposes Graph Structured
                 Program Evolution (GRAPE) which is an automatic
                 generation method for arbitrary programs. The author
                 applies GRAPE to automatic generation of programs which
                 need loop structUre such as factorial and sorting a
                 list. From the experimental results, the author shows
                 that GRAPE enables to construct the complex programs
                 which are difficult to automatic construction by usual

                 Finally, the author proposes a method fbr evolving
                 search algorithms using GRAPE. The author applies the
                 proposed method to construct search algorithms for
                 benchmark function optimization and template matching
                 problems. Numerical experiments show that the
                 constructed search algorithms are effective for these
                 search spaces and also for several other search
  notes =        "In Japanese",

Genetic Programming entries for Shinichi Shirakawa