Genetic Programming for Multiclass Object Classification

Created by W.Langdon from gp-bibliography.bib Revision:1.4208

  author =       "William Richmond Smart",
  title =        "Genetic Programming for Multiclass Object
  school =       "Victoria University of Wellington",
  year =         "2005",
  type =         "Master of Science in Computer Science",
  address =      "new Zealand",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  size =         "160 pages",
  abstract =     "This thesis investigates the use of Genetic
                 Programming (GP) in solving object classification tasks
                 of three or more classes (multiclass). Methods are
                 developed to improve the performance of the GP system
                 at four multiclass object classification tasks of
                 varying difficulty, by investigating two aspects of

                 The first aspect of GP is the classification strategy,
                 or the method used to translate a real program output
                 into a class label for classification. Previous
                 classification strategies typically arrange the program
                 output space into class regions, which in some methods
                 can change position or class during evolution. We have
                 developed a new classification strategy that does not
                 deal with the regions directly, but instead models the
                 output of a program using normal distributions.
                 Advantages of the new approach include the use of
                 improved fitness measures, and the possibility of
                 multiple programs being used together to predict the
                 class of a test example. In experiments, this method
                 performs significantly better than the three other
                 classification strategies it was tested against,
                 especially on difficult tasks.

                 We have also developed a method which decomposes the
                 multiclass classification task into many binary
                 subtasks. Unlike previous approaches, this method
                 solves all binary subtasks in one evolution using a
                 modified, multi-objective fitness function. The
                 multiclass task is solved by combining expert programs,
                 each able to solve one subtask. In experiments, this
                 method outperforms the basic approach, and a previous
                 'divide-and-conquer' approach, especially on difficult

                 The second aspect of GP investigated is the use of
                 hybrid searches, involving both evolutionary search and
                 gradient-descent search. By adding weights to the links
                 of genetic programs, we have enabled a similar search
                 to that of neural networks, within each generation of a
                 GP search. The weights control the effect of each
                 subtree in a program, and may be efficiently optimised
                 using gradient-descent. The use of weights was found to
                 improve accuracy over the basic approach, and slightly
                 improve on the gradient-descent search of numeric
                 terminals alone.

                 We have also developed a novel hybrid search in which
                 changes to each program's fitness occur only through
                 gradient-descent, though the evolutionary search still
                 modifies program structure. This is possible through
                 modified genetic operators and inclusion factors which
                 allow certain subtrees in a program to be 'mapped-out'
                 of the program's calculations. Unfortunately, the new
                 search is found to decrease accuracy and increase time
                 per run for the GP system.

                 The aim of this thesis, to improve the performance of
                 GP at multiclass object classification tasks, has been
                 achieved. This thesis contains methods that
                 significantly improve the performance of a GP system
                 for these problems, over the basic approach. The work
                 of this thesis serves to improve GP as a competitive
                 method on multiclass object classification tasks.",

Genetic Programming entries for Will Smart