johnmee / nigel Goto Github PK

Suitable for using the normalised probabilistic selection routine created in #2 create a crossover (mate) routine which, given two candidates (contributing and receiving parents)

• determines what node types it has in common
• picks one of those nodes at random in the parent and copies the node and its subtree/branch
• picks a similarly typed node in the receiving parent at random
• overwrites that node/subtree/branch with the one taken from the contributor
• returns the new individual

if there are no common node-types then it raises an error so the calling algorithm can decide what to do.

Via GP. Should be able to just copy/paste from deap example and build a notebook around it. Execute.

https://deap.readthedocs.org/en/master/examples/gp_parity.html

Firstly, let's define what we mean by program 'architecture'.
According to Koza (GP2 pp525) the architecture of an individual program in the population is defined by:
a) the number of function-defining branches,
b) the number of arguments possessed by each function-defining branch, and
c) if there is more than one function-defining branch, the nature of the hierarchical references (if any) allowed between the function-defining branches

Secondly, we need to step through the following process each time we create an individual:

1. Randomly select the number of ADF's it will have (between 0 and Max_ADFs_Allowed). Note than "Max_ADFs_Allowed" is a control parameter we need to be able to set.
2. Name the ADF's from left to right as ADF0, ADF1, ADF2, ...... etc.
3. Randomly select the number of arguments that each ADF will have (between 1 and "Max_ARGs_Allowed_in_ADFs"). Note than "Max_ARGs_Allowed_in_ADFs" is a control parameter we need to be able to set.
4. Name the arguments fro left to right as ARG0, ARG1, ARG2, ...... etc.
5. Create function sets for each ADF and RPB, comprising the union of the primitive functions of the problem with whatever ADF's may appear to the left of that branch (i.e. if the primitive function set for the problem is {NOR, AND, OR} and their are 2 ADF's then ADF0 would have a function set being {NOR, AND, OR}, ADF1 would have a function set being {ADF0, NOR, AND, OR}, and the Result Producing Branch (RPB) will have a function set {ADF0, ADF1, NOR, AND, OR})
6. We now have a terminal set and function set for each ADF and RPB so we can then go about using the ourGrow method to create the individual
7. Repeat steps 1 through 6 to create all individuals of the population

As per Kosa and O'Neill:

Given a population and asked to pick out a single individual it should choose one based on a probability which is weighted by its fitness relative to all the others.

When generating populations we're seeing some pretty large trees. We're expecting to only see initial trees of depth 5.

Work out what's going on there...

then push changes to https://johnmee.com:8889/notebooks/DynamicADFFiveParity.ipynb

Apply to solving the Pythagoras problem

I'm not sure how many or what, but keep it simple and implement an ADF and see it get used in a solution.

The documentation talks about and demonstrates drawing of trees with graphing software. Pete even had it going in his work. They look a bit like this:

Make that happen so that we can spit out images of selected individuals during a run.

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 for both crossover fragments to be mutually compatible with their respective receivers both syntactically and and semantically is unlikely. 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.

Naturally, 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.
• Firstly, 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)
• Secondly, 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.
• Thirdly, 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).