Skip to main content

Posted in Research Topics.

Genetic Computation (1997-2000)

Genetic Programming (GP) systems were originally cumbersome and unable to evolve complex programs. But are these necessary impediments? Can GP be modified to become more efficient in the evolution of complex programs including polymorphism, recursion and higher-order functions? Building on earlier work in Functional Programming, a novel approach investigated the use of pure lambda-expression parse trees, augmented the GP system with a polymorphic higher-order type system, and incorporated recursion over finite lists. The results show substantial benefit, increase in expressiveness, decrease in parse tree size, and improved performance:

  • Recursion, Lambda Abstraction and Genetic Programming (Yu and Clack, in Proceedings Third Genetic Programming Conference, eds. J.R. Koza et al, pp 422-431, ISBN 1-55860-548-7, Morgan Kaufman, 1998)
  • PolyGP: A Polymorphic Genetic Programming System in Haskell (Yu a Clack, in Proceedings Third Genetic Programming Conference, eds. J.R. Koza et al, pp 416-421, ISBN 1-55860-548-7, Morgan Kaufman, 1998)
  • Performance-Enhanced Genetic Programming (Clack and Yu, LNCS 1213:87-100,ISSN 0302-9743, Springer, 1997)

Traditional Genetic Algorithm (GA) behaviour was also unsatisfactory - to achieve good performance a crossover operator had to be chosen to match the chromosome encoding. By using explicit and detailed history about which previous modifications were beneficial and which were not, can a general-purpose GA crossover operator be devised that is insensitive to encoding? Selective Crossover is a novel extended GA representation with an enhanced crossover procedure: it monitors contributions to fitness on a per-gene basis and guarantees good behaviour regardless of problem encoding. It works exceptionally well with problems of high epistasis where it finds a better solution than the conventional crossover operators, and does this with the least number of evaluations (a repeatable 25% improvement):

  • Royal Road Encodings and Schema Propagation in Selective Crossover (Vekaria and Clack, in Proceedings WSC4: 4th Online World Conference on Soft Computing in Industrial Applications, eds. Y.Suzuki et al, pp 281-292, ISBN 185233293X, Springer, 2000)
  • Biases Introduced by Adaptive Recombination Operators (Vekaria and Clack, in Proceedings Genetic and Evolutionary Computation Conference (GECCO'99), eds. Banzhaf et al, pp 670-677, ISBN 1558606114, Morgan Kaufman, 1999)
  • Selective Crossover in Genetic Algorithms: An Empirical Study (Vekaria and Clack, LNCS 1498:438-447, ISSN: 0302-9743, Springer 1998)
  • Selective Crossover in Genetic Algorithms (Vekaria and Clack, in Proceedings Third Genetic Programming Conference, eds. J.R. Koza et al, pp 609, ISBN 1-55860-548-7, Morgan Kaufman, 1998)
  • Genetic Programming with Gene Dominance (Vekaria and Clack, in Late Breaking Papers at the Genetic Programming 1997 Conference, pp 300, ISBN 0-18-206995-8, Stanford University Bookstore, 1997)