**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

### Abstract:

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.

**Genetic Machine Learning**

**Geyer-Schulz1996b**-
Andreas Geyer-Schulz.
*Fuzzy Rule-Based Expert Systems and
Genetic Machine Learning,*
volume 3 of *Studies in Fuzziness and Soft Computing*.
Physica-Verlag, Heidelberg, 2nd revised edition, 1996.

**Koza1992**-
John R. Koza.
*Genetic Programming: On the Programming of Computers by Means of
Natural Selection*.
The MIT Press, Cambridge, Massachusetts, 1992.

* (c) 1996 Walter Boehm, and Andreas Geyer-Schulz, *

Tue Jan 14 09:50:54 MET 1997