ABSTRACT

When an executable structure such as a program or a function is the object of an evolutionary computation, representation plays a crucial role in determining the ultimate success of the system. If a traditional, syntax-laden programming language is chosen to represent the evolving programs, then manipulation by simple evolutionary operators will most likely produce syntactically invalid offspring. A more beneficial approach is to design the representation to ensure that only syntactically correct programs are created. This reduces the ultimate size of the search space considerably. One method for ensuring syntactic correctness of generated programs is to evolve the desired program’s parse tree rather than an actual, unparsed, syntax-laden program. Use of the parse tree representation completely removes the ‘syntactic sugar’ introduced into a programming language to ensure human readability and remove parsing ambiguity.