Potential fitness for genetic programming

ABSTRACT

We introduce potential fitness, a variant of fitness function that operates in the space of schemata and is applicable to tree-based genetic programing. The proposed evaluation algorithm estimates the maximum possible gain in fitness of an individual's direct offspring. The value of the potential fitness is calculated by analyzing the context semantics and subtree semantics for all contexts (schemata) of the evaluated tree. The key feature of the proposed approach is that a tree is rewarded for the correctly classified fitness cases, but it is not penalized for the incorrectly classified ones, provided that such errors are recoverable by substitution of an appropriate subtree (which is however not explicitly considered by the algorithm). The experimental evaluation on a set of seven boolean benchmarks shows that the use of potential fitness may lead to better convergence and higher success rate of the evolutionary run.

REFERENCES

• 1: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 2: Lones, M. A., and Tyrrell, A. M. Modelling biological evolvability: Implicit context and variation altering in enzyme genetic programming. BioSystems 76, 1--3 (Aug.-Oct. 2004), 229--238.
• 3: Luke, S. ECJ evolutionary computation system, 2002. (http://cs.gmu.edu/ eclab/projects/ecj/).
• 4: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 5: K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska, Eds., Morgan Kaufmann Publishers, pp. 829--836.
• 6: Majeed, H., and Ryan, C. A less destructive, context-aware crossover operator for GP. In Proceedings of the 9th European Conference on Genetic Programming (Budapest, Hungary, 10 -- 12 Apr. 2006)
• 7: P. Collet, M. Tomassini, M. Ebner, S. Gustafson, and A. Ekart, Eds., vol. 3905 of Lecture Notes in Computer Science, Springer, pp. 36--48.
• 8: Hammad Majeed , Conor Ryan , R. Muhammad Atif Azad, Evaluating GP schema in context, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068304]
• 9: McPhee, N. F., Ohs, B., and Hutchison, T. Semantic building blocks in genetic programming. In Genetic Programming (2008), M. O'Neill, L. Vanneschi, S. Gustafson, A. I. E. Alcazar, I. D. Falco, A. D. Cioppa, and E. Tarantino, Eds., vol. 4971 of LNCS, Springer, pp. 134--145.
• 10: Riccardo Poli , Jonathan Page, Solving High-Order Boolean Parity Problems with Smooth Uniform Crossover, Sub-Machine Code GP and Demes, Genetic Programming and Evolvable Machines, v.1 n.1-2, p.37-56, April 2000 [doi>10.1023/A:1010068314282]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms

Keywords:
context, evolutionary computation, genetic programming, semantics