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.