Mengjie Zhang, Linear and Graph Genetic Programming

Linear and Graph Genetic Programming

• Overview:

  In 1992, John Koza introduced tree based genetic programming. In recent years, this form has been successfully applied to many applications, from regression, circuit design, image processing and recognition, binary classification to recently multiclass classification problems. While showing promise, tree based genetic programming has several limitations. Typically, genetic programs generated by this form of genetic programming only produce one floating point value from the root node. For simple regression problems, this is perfect. For binary classification problems, this format is also reasonable: a positive returned output value of the program corresponds to one class and non-positive value to the other class. However, for multiclass problems, this is not that straightforward.

  One approach is to change the representation of the genetic programs from a tree to a graph. In other words, we need a GP system generated graph based programs so that multiple values from the roots can be produced, each of which corresponds to a particular class.

  Another approach is to change the representation of genetic programs from a tree to a human written like program, that is, we allow a genetic program has multiple statements arranged linearly. In addition, each of such programs should also be able to produce multiple output values.

• Tasks and Goals of this Project

  The goal of this project is to investigate new representations of genetic programs so that multiple output values can be produced from a single genetic program. We expect that this approach would be easier to use for multiclass classification problems. This project will focus on linear and graph genetic programming. Specifically, this project will investigate:

  • How linear and graph GP systems can be implemented and applied to multiclass classification problems;
  • Whether neural networks can be evolved from genetic programming as genetic programs;
  • How terminals, functions, and fitness measures can be embedded into linear/graph genetic programming; and
  • Whether the new form of GP outperforms tree based GP for multiclass classification problems.

  The methods developed will be examined on a sequence of multiclass classification problems of increasing difficulty and compared with the tree based genetic programming.

• More information can be seen from Meng's research projects . Related Publications can be viewed from here: Meng's recent publications. Contact me if you want to get a copy of those papers, or if you want to know more detail about this project.