- 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
programming.
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 FFGIN.
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 GP.
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 spaces.",
- notes = "In Japanese",
