Walter Böhm,
Department of Mathematical Methods of Statistics,
Institute of Statistics,
Vienna University of Economics and Business Administration,
Augasse 2-6, A-1090 Vienna, Austria.
E-mail: boehm@wu-wien.ac.at
Andreas Geyer-Schulz
Department of Applied Computer Science,
Institute of Information Processing
Vienna University of Economics and Business Administration,
Augasse 2-6, A-1090 Vienna, Austria.
E-mail: geyers@wu-wien.ac.at
In this paper we solve the problem of exactly uniform generation of complete derivation trees from k-bounded context-free languages. The result is applied and is used for developing an exact uniform initialization routine for a genetic programming variant based on an explicit representation of the grammar of the context-free language (simple genetic algorithm over k-bounded context-free languages) [Geyer-Schulz1996b]. In this genetic programming variant the grammar is used to generate complete derivation trees which constitute the genomes for the algorithm. For the case that no a priori information about the solution is available, we prove that this (simple random sampling) algorithm is optimal in the sense of a minimax strategy. An exact uniform initialization routine for Koza's genetic programming variant [Koza1992] is derived as a special case.