Evolutionary program induction directed by logic grammars

Man Leung WONG, K. S. LEUNG

Research output: Journal PublicationsJournal Article (refereed)

22 Citations (Scopus)

Abstract

Program induction generates a computer program that can produce the desired behavior for a given set of situations. Two of the approaches in program induction are inductive logic programming (ILP) and genetic programming (GP). Since their formalisms are so different, these two approaches cannot be integrated easily, although they share many common goals and functionalities. A unification will greatly enhance their problem-solving power. Moreover, they are restricted in the computer languages in which programs can be induced. In this paper, we present a flexible system called LOGENPRO (The LOgic grammar-based GENetic PROgramming system) that uses some of the techniques of GP and ILP. It is based on a formalism of logic grammars. The system applies logic grammars to control the evolution of programs in various programming languages and represent context-sensitive information and domain-dependent knowledge. Experiments have been performed to demonstrate that LOGENPRO can emulate GP and GP with automatically defined functions (ADFs). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. The experiments show that LOGENPRO has superior performance to that of GP and GP with ADFs when more domain-dependent knowledge is available. We have applied LOGENPRO to evolve general recursive functions for the even-n-parity problem from noisy training examples. A number of experiments have been performed to determine the impact of domain-specific knowledge and noise in training examples on the speed of learning.
Original languageEnglish
Pages (from-to)143-180
Number of pages38
JournalEvolutionary Computation
Volume5
Issue number2
DOIs
Publication statusPublished - 1997
Externally publishedYes

Fingerprint

Genetic programming
Genetic Programming
Grammar
Proof by induction
Logic
Inductive logic programming (ILP)
Inductive Logic Programming
Computer programming languages
Recursive functions
Experiment
Recursive Functions
Dependent
Experiments
Unification
Parity
Programming Languages
Computer program listings

Keywords

  • Machine learning
  • genetic programming
  • logic grammars

Cite this

@article{c5cee4f8b4c74c44b1d8d7c1bfceaffa,
title = "Evolutionary program induction directed by logic grammars",
abstract = "Program induction generates a computer program that can produce the desired behavior for a given set of situations. Two of the approaches in program induction are inductive logic programming (ILP) and genetic programming (GP). Since their formalisms are so different, these two approaches cannot be integrated easily, although they share many common goals and functionalities. A unification will greatly enhance their problem-solving power. Moreover, they are restricted in the computer languages in which programs can be induced. In this paper, we present a flexible system called LOGENPRO (The LOgic grammar-based GENetic PROgramming system) that uses some of the techniques of GP and ILP. It is based on a formalism of logic grammars. The system applies logic grammars to control the evolution of programs in various programming languages and represent context-sensitive information and domain-dependent knowledge. Experiments have been performed to demonstrate that LOGENPRO can emulate GP and GP with automatically defined functions (ADFs). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. The experiments show that LOGENPRO has superior performance to that of GP and GP with ADFs when more domain-dependent knowledge is available. We have applied LOGENPRO to evolve general recursive functions for the even-n-parity problem from noisy training examples. A number of experiments have been performed to determine the impact of domain-specific knowledge and noise in training examples on the speed of learning.",
keywords = "Machine learning, genetic programming, logic grammars",
author = "WONG, {Man Leung} and LEUNG, {K. S.}",
year = "1997",
doi = "10.1162/evco.1997.5.2.143",
language = "English",
volume = "5",
pages = "143--180",
journal = "Evolutionary Computation",
issn = "1063-6560",
publisher = "MIT Press Journals",
number = "2",

}

Evolutionary program induction directed by logic grammars. / WONG, Man Leung; LEUNG, K. S.

In: Evolutionary Computation, Vol. 5, No. 2, 1997, p. 143-180.

Research output: Journal PublicationsJournal Article (refereed)

TY - JOUR

T1 - Evolutionary program induction directed by logic grammars

AU - WONG, Man Leung

AU - LEUNG, K. S.

PY - 1997

Y1 - 1997

N2 - Program induction generates a computer program that can produce the desired behavior for a given set of situations. Two of the approaches in program induction are inductive logic programming (ILP) and genetic programming (GP). Since their formalisms are so different, these two approaches cannot be integrated easily, although they share many common goals and functionalities. A unification will greatly enhance their problem-solving power. Moreover, they are restricted in the computer languages in which programs can be induced. In this paper, we present a flexible system called LOGENPRO (The LOgic grammar-based GENetic PROgramming system) that uses some of the techniques of GP and ILP. It is based on a formalism of logic grammars. The system applies logic grammars to control the evolution of programs in various programming languages and represent context-sensitive information and domain-dependent knowledge. Experiments have been performed to demonstrate that LOGENPRO can emulate GP and GP with automatically defined functions (ADFs). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. The experiments show that LOGENPRO has superior performance to that of GP and GP with ADFs when more domain-dependent knowledge is available. We have applied LOGENPRO to evolve general recursive functions for the even-n-parity problem from noisy training examples. A number of experiments have been performed to determine the impact of domain-specific knowledge and noise in training examples on the speed of learning.

AB - Program induction generates a computer program that can produce the desired behavior for a given set of situations. Two of the approaches in program induction are inductive logic programming (ILP) and genetic programming (GP). Since their formalisms are so different, these two approaches cannot be integrated easily, although they share many common goals and functionalities. A unification will greatly enhance their problem-solving power. Moreover, they are restricted in the computer languages in which programs can be induced. In this paper, we present a flexible system called LOGENPRO (The LOgic grammar-based GENetic PROgramming system) that uses some of the techniques of GP and ILP. It is based on a formalism of logic grammars. The system applies logic grammars to control the evolution of programs in various programming languages and represent context-sensitive information and domain-dependent knowledge. Experiments have been performed to demonstrate that LOGENPRO can emulate GP and GP with automatically defined functions (ADFs). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. The experiments show that LOGENPRO has superior performance to that of GP and GP with ADFs when more domain-dependent knowledge is available. We have applied LOGENPRO to evolve general recursive functions for the even-n-parity problem from noisy training examples. A number of experiments have been performed to determine the impact of domain-specific knowledge and noise in training examples on the speed of learning.

KW - Machine learning

KW - genetic programming

KW - logic grammars

UR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-0001604898&doi=10.1162%2fevco.1997.5.2.143&partnerID=40&md5=426071fd0ab648c1d544028bb521ad22

U2 - 10.1162/evco.1997.5.2.143

DO - 10.1162/evco.1997.5.2.143

M3 - Journal Article (refereed)

VL - 5

SP - 143

EP - 180

JO - Evolutionary Computation

JF - Evolutionary Computation

SN - 1063-6560

IS - 2

ER -