Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

by Genetic Programming

Takuya Ito

Scho ol of Information Science,

Japan Advanced Institute of Science and Technology

January 14, 1999

Abstract

Genetic Programming (GP) can generate computer programs automatically without

any explicit knowledge for target programs (solution programs). The solution programs

are generated by means of selection and some genetic op erators. However, GP has a

diculty, which it often takes too much time to generate solution programs. This may

b e a criticalproblem when GP generates large scale programs.

The goal of this work is to generate computer programs eciently by means of the

framework of GP. \Ecient" means to reduce the numb er of generations which is nec-

essary to generate solution programs. Torealize this goal, this work improves a genetic

op erator ofGP.Thereare threegenetic operatorsforGP,crossover,mutation andrepro-

duction. Among these genetic op erators, crossover mainly contributes to searching for

solutionprograms. Therefore,this workimprovescrossover. Thenormalcrossoverselects

acrossoverpointrandomlysothat itbreaks building blo cks(i.e., eectivesmall program

whichcontributestoimprovingtnessperformance)duetoitsblindapplication. Tosolve

this problem, this work prop osesfour new crossovers

The rst crossoveris a\depth-dep endent crossover" and the second crossoverisa \re-

vised depth-dep endent crossover". \Depth-dependent" means that no de selection prob-

ability is determined by the depth of the tree structure. On these crossovers, shallower

no des are more oftenselected, and deepernodes are selectedrarely. The building blo cks

can beprotected by swappingshallowernodes.

The third crossoveris a \non-destructivedepth-dependentcrossover",which is acom-

bination of the depth-dep endent crossover and a \non-destructive crossover". \Non-

destructive" means that osprings of crossover are kept only if their tness are better

than tness of their parents. This crossover is prop osed tosolve the program size prob-

lem of the depth-dep endent crossover.

The fourth crossoveris a \self-tuning depth-dependent crossover". On this crossover,

eachindividualof thep opulationhas adierentdepthselection probabilityand depthse-

lectionprobabilityofaselectedindividualiscopiedtothenextgeneration. Thiscrossover

c

problems.

This workcompares GPp erformances (i.e.,tness valueand the size of generatedpro-

grams)ofthe normalcrossoverwith performancesof these fourcrossoversusing standard

GP problems and an originalrob ot problem. These exp erimental results clarify that the

sup eriorityof the prop osedcrossoverstothe normalcrossover.

Furthermore, this work discusses the building block hypothesis, which explains how

crossover searches solution programs with a survey of previous works and these experi-

mentalresults.

Key Words: Genetic Programming (GP), the depth-dep endent crossover,

the non-destructive depth-dependent crossover, the self-

tuning depth-dep endent crossover, building blo ck, building

blo ck hypothesis