with CGP v2.1

In GP, this is dealt with by either penalizing such structures (*e.g.*,
by setting evaluation to 0) to ensure their extinction, or by extending
interpretations (*e.g.*, protected division) to validate otherwsie
invalid structures - but these choices are arbitrary in general. Koza has
introduced *structure-preserving crossover* - an *ad-hoc, *domain-specific
approach, aimed at preventing crossover from generating undesired structures.
The objective of *Constrained Genetic Programming* (CGP) is to provide
general and domain-independent means for dealing with these problems in
crossover, as well as in initialization and mutation. Arising from this
need, CGP has now evolved into a more elaborate means to dictate *strong
(weak*) constraints (heuristics) on the solution space. In fact, we
are currently working on using similar mechanisms to evolve GP representation
in the process of the same evolution.

CGP was developed in 1995 at NASA/JSC and UMSL, simultaneously and independently
of Montana's *Strongly Typed *GP (STGP). `CGP v1` in fact implemented
the same ideas as STGP, except that 1) rather than using type names for
inducing constraints, it expected explicit constraints - this allows CGP
to specify semantic constraints, 2) CGP's crossover was shown to be stronger
(*i.e.*, able to generate more valid programs) 3) STGP has practically
merged type constraints with tree depths. But the biggest difference lies
in CGP's formal methodology. Constraints can be entered in multiple
forms because they show up in different forms. These constraints are transformed
into a normal form, which is shown to be a minimal description of the same
constraints. Constrained initialization, mutation, and crossover are shown
to satisfy the normal constraints, and they are shown to have the same
complexity (__O__) as the unconstrained operators. `CGP v2.1`
extends `v1` by also introducing data typing and overloading (as
in programming languages). Overloading allows defining functions, such
as *plus*, to compute different types according to the types of its
instance's arguments. It also allows weak constraints, that are heuristic
preferences (weighted) on some evolved forms over others.

Another advantage that `CGP v2.1` offers is its extensive implementation:
it has been implemented into *lil-gp* ( public domain tool for developing
GP). Therefore, all lil-gp's capabilities are still available (currently,
`lil-gp 1.02` has been used, but plug-in approach allows for easy
merging CGP with future lil-gp release). The only exception is that even
though CGP provides for propagating constraints between modules, the implementation
has not been extended to ADFs.

In the tutorial we will present the constraint language, formal analysis
of constraints and constrained operators, and comparison of CGP to STGP.
We will illustrate `CGP v2.1` with application examples. We will
discuss the implications of being able to control the search space (theoretical
and practical). We will also discuss current/future developments: ADFs,
recursive functions, merging with depth limitations, and evolving GP representation.

I anticipate to spend roughly about 10% on discussing the context, 50 % the CGP methodology, 20% on demonstrations, 10% on practical results and discussion, and 10% on future directions.

Context introduction would discuss implications of closure, sufficiency, and tree limits on the mapping between solution and representation spaces, along with possible problems that may arise given some properties of the mapping.

CGP methodology would discuss the methodology, formalism, and compare CGP with STGP. This would include recent additions such as heuristic constraints and function overloading.

Demonstrations would illustrate how domain-specific constraints can be expressed in the constraint language, and how they affect the effective GP search space. Practical results would follow with experimental results demonstrating that huge gains are possible - but only if the right spaces are allowed to be explored. This will lead to conclusions - future work on evolving GP representation so that "the right" spaces are evolved, plus ADFs, recursive functions, etc.