ADF: Point Typing

Point Typing for Structure-Preserving Crossover

Firstly, Koza states that point typing is used when the architecture of the individuals is evolutionarily selected (GP2, pp532).

For the Crossover routine/method to be compatible with various program architectures, it will work best if each reproductive operation between two parents results in only 1 offspring being generated. Unlike the double-crossover, which is possible when the architectures of each program in a population is homogenous and each crossover operation can produce 2 offspring, it works best if we only produce 1 offspring each time 2 parents mate, due to the non-homogenous architecture of the population. This is because there are a number of compatibility checks which need to be done (aside from the type matching which always is required), making a successful swap very rare. This is because crossover fragments are unlikely to be mutually compatible with their respective receivers both syntactically and and semantically. This would result in a great deal of failed attempts and wasted computer resources. Hence, when programs contain ADF's with automatically defined architectures, we define parents as either a contributing parent, or a receiving parent, and the crossover is only done in one direction: from contributor to receiver.

The contributing parent will contribute a randomly chosen program fragment for insertion into a randomly chosen point in the receiving parent, if (and only if) the below list of checks do not identify any incompatibility.

Before detailing the checks explicitly, they can broadly be described as falling into 3 areas:

1. Every terminal and function contained in the crossover fragment must be in the terminal set or function set of the branch of the receiving parent. This includes actual variables, dummy variables (e.g. ARG0, ARG1...), random constants, primitive functions, automatically defined functions.
2. The number of arguments of every function contained in the crossover fragment must equal the number of arguments for that function in the branch of the receiving parent to which it is being inserted.
3. All other syntactic rules of construction must be satisfied, including the type of the crossover fragment and the insertion point being a match.

Koza (GP2, pp533) explicitly states these 7 conditions of point-typing as:

1. All the actual variables of the problem, if any; actually appearing in the crossover fragment from the contributing parent must be in the terminal set of the branch of the receiving parent containing the point of insertion.

2. All the dummy variables (e.g. ARG0, ARG1, etc.) if any actually appearing in the crossover fragment from the contributing parent must be in the terminal set of the branch of the receiving parent containing the point of insertion.

3. All the automatically defined functions, if any actually appearing in the crossover fragment from the contributing parent must be in the function set of the branch of the receiving parent containing the point of insertion.

4. All the automatically defined functions, if any actually appearing in the crossover fragment from the contributing parent must have exactly the number of arguments specified for that automatically defined function for the branch of the receiving parent containing the point of insertion.

5. All functions (other than automatically defined functions) must also satisfy conditions (3) and (4).

6. All terminals (other than dummy variables and actual variables of the problem already mentioned in conditions (1) and (2), if any actually appearing in the crossover fragment from the contributing parent must be in the terminal set of the branch of the receiving parent containing the point of insertion.

7. All other syntactic rules of construction of the problem must be satisfied (including the type of the crossover fragment and the insertion point being a match).

---