TY - GEN

T1 - Canonical representation genetic programming

AU - Woodward, John R.

AU - Bai, Ruibin

N1 - Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - Search spaces sampled by the process of Genetic Programming often consist of programs which can represent a function in many different ways. Thus, when the space is examined it is highly likely that different programs may be tested which represent the same function, which is an undesirable waste of resources. It is argued that, if a search space can be constructed where only unique representations of a function are permitted, then this will be more successful than employing multiple representations. When the search space consists of canonical representations it is called a canonical search space, and when Genetic Programming is applied to this search space, it is called Canonical Representation Genetic Programming. The challenge lies in constructing these search spaces. With some function sets this is a trivial task, and with some function sets this is impossible to achieve. With other function sets it is not clear how the goal can be achieved. In this paper, we specically examine the search space dened by the function set {+, -, z.ast;, /} and the terminal set {x,1} Drawing inspiration from the fundamental theorem of arithmetic, and results regarding the fundamental theorem of algebra, we construct a representation where each function that can be constructed with this primitive set has a unique representation.

AB - Search spaces sampled by the process of Genetic Programming often consist of programs which can represent a function in many different ways. Thus, when the space is examined it is highly likely that different programs may be tested which represent the same function, which is an undesirable waste of resources. It is argued that, if a search space can be constructed where only unique representations of a function are permitted, then this will be more successful than employing multiple representations. When the search space consists of canonical representations it is called a canonical search space, and when Genetic Programming is applied to this search space, it is called Canonical Representation Genetic Programming. The challenge lies in constructing these search spaces. With some function sets this is a trivial task, and with some function sets this is impossible to achieve. With other function sets it is not clear how the goal can be achieved. In this paper, we specically examine the search space dened by the function set {+, -, z.ast;, /} and the terminal set {x,1} Drawing inspiration from the fundamental theorem of arithmetic, and results regarding the fundamental theorem of algebra, we construct a representation where each function that can be constructed with this primitive set has a unique representation.

KW - Genetic programming

UR - http://www.scopus.com/inward/record.url?scp=67650697303&partnerID=8YFLogxK

U2 - 10.1145/1543834.1543914

DO - 10.1145/1543834.1543914

M3 - Conference contribution

AN - SCOPUS:67650697303

SN - 9781605583266

T3 - 2009 World Summit on Genetic and Evolutionary Computation, 2009 GEC Summit - Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation, GEC'09

SP - 585

EP - 592

BT - 2009 World Summit on Genetic and Evolutionary Computation, 2009 GEC Summit - Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation, GEC'09

PB - Association for Computing Machinery (ACM)

T2 - 2009 World Summit on Genetic and Evolutionary Computation, 2009 GEC Summit - 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation, GEC'09

Y2 - 12 June 2009 through 14 June 2009

ER -