Mengjie Zhang, Linear and Graph Genetic Programming

Linear and Graph Genetic Programming

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 classification or problems that need multiple outputs or graphs, this approach is not suitable.

One approach is to change the representation of the genetic programs from a tree to a graph. In this way, a GP system can generate graph based programs that can produce multiple output values and graph based programs.

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.

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 and problems that need multiple outputs and graph based programs. Specifically, this project will investigate:

  • New program reresentation and structures in linear genetic programming for multiclass classification;
  • New grammar representation in tree based and linear genetic programming for combinatorial optimisation such as scheduling and web service composition;
  • New program representation for program/software testing.

A strong background in Java/C/C++ programming and a basic background in Artificial Intelligence and statistics are required. A good background in machine learning, and operations research is desired (COMP307, COMP361).

The Evolutionary Computation Research Group here has good international reputation in the field and would like to continue the momentum. Please check http://homepages.ecs.vuw.ac.nz/~mengjie/papers/index.shtml, http://ecs.victoria.ac.nz/Main/MengjieZhang, and http://ecs.victoria.ac.nz/Groups/ECRG/ for publications and other information.