I am trying to implement genetic programming using random binary trees. It is essentially a parse tree with special subset of operators including: and, >, <. Note that in my implementation, I am merely comparing numbers. So it is obvious that leaf nodes cannot be operators given a certain predefined max depth. I am looking for some reference material on the rules involved in this type of implementation. I can come up with a few but want to verify if my logic is right so that in the future when I add additional more complex operators, I can be able to design a class structure that is easily changeable.
Some rules:
Given max depth of N, at depth N, it must be numbers. Root node cannot be a number. Root node must be an operator. If the parent of a node is not an and operator, the current node cannot be an and operator.
Genetic Progamming in its pure form works with a set of nonterminals (NTs) and terminals (Ts). The NTs are usually operators, functions, etc., while Ts are usualy variables, constants, or you can look at those as zero-arity functions. When you do crossover, you pick a subtree in each parent and you switch those. When you do mutation, you delete a subtree and generate a random one (with a limited depth). When generating a tree (either in the initialisation phase or in mutation), you have some depth limit. Until this limit is reached you put nodes both from NTs and Ts. When you reach the limit, you put nodes from Ts only.
The pure GP also requires closure property: any nonterminal must accept any nonterminal or terminal as any of its children. This seems not to hold for your case: for example, and does not make sense for two numbers.
I suggest you have a look at Strongly Typed GP. It is basically a GP with type constraints on nonterminals' children and type information of nonterminals' and terminals' output. In your case, for example, your operator < would require its children to be of a numeric type and its output type would be boolean.
Another possibility is Grammatical Evolution. It is my favourite one because of its huge flexibility by just modifying the grammar. It takes a completely different approach than (ST)GP and it can encode identical requirements (and even more). It works with linear variable-length genomes that are translated into programs using a context-free grammar in Backus-Naur Form. The grammar is the only thing that defines your solution structure. In your case the grammar could look like
<expr> ::= <bool-expr>
| <num-expr>
<bool-expr> ::= (<num-expr> > <num-expr>)
| (<num-expr> < <num-expr>)
| (<bool-expr> and <bool-expr>)
<num-expr> ::= ...
with <expr> as the start symbol.
Regarding the depth-related rules, this is something not used in GP very much. The only depth-related things are the initialisation procedure (you have to limit the size of solutions somehow) and bloat control (you want smaller solutions than the huge ones). I didn't came across any GP algorithm that worked with structure constraints based on the depth. If your only depth-related constraint is the maximum solution depth than this can be easy modelled by assigning the worst fitness (or just penalizing) to solutions that violate this constraint.
Constraints like
If the parent of a node is not an "and" operator, the current node cannot be an "and" operator.
are doable but you will either have to use custom crossover and mutation operators that will check the constraint(s) (if you are going to use the (ST)GP-like approach) or, in the case of GE, you can define the grammar in more detail so that it would not produce such solutions. Example of that constraint could be:
<bool-expr> ::= <and-expr>
| <not-expr>
| <or-expr>
# <not-expr> is not "and" so its child can be <or-expr> or <not-expr>
<not-expr> ::= not <or-expr>
| not <not-expr>
# the same for the <or-expr> but you have to write down all the combinations
<or-expr> ::= <not-expr> or <not-expr>
| <not-expr> or <or-expr>
| <or-expr> or <not-expr>
| <or-expr> or <or-expr>