Perform crossover operation on AST in genetic programming

Question

3.00/5 (1 vote)

See more:

So in general when you perform a crossover in GA, you directly flip a random section in the "genome", with the corresponding section in the other parent, and mutate it based on the mutation rate.

Consider the sequences below:

0100 1000 0001 1011

0010 0110 1101 1111

A crossover without any mutation might look like this:

0100 0110 1101 1011

0010 1000 0001 1111

In that case, blocks 2 and 3 were swapped and blocks 1 and 4 remained unchanged.

I'm unsure how that would work in GP with abstract syntax trees however, because there is no guarantee that the point in the abstract tree you reference in the first parent will be compatible with the section from the second parent, for example one section might have a return type of boolean while the other has a return type of string, such as in the example below:

    p1
   /  \
  b    i
 /\   /\
b  f i  s

    p2
   /  \
  s    b
 /\   /\
i  n s  i

if you were to try to crossover branch 1 from parent 1 which has a return type of b, with branch 1 from parent 2 which has a return type of s, it would create a syntax error if it were to be ran, so how would I correctly perform a crossover on an AST, specific examples would be appreciated.

What I have tried:

I have done some research on the subject but from what I can tell the algorithms I have found assume uniformity among return types.

Posted 29-Apr-16 11:13am

Sicppy

Updated 29-Apr-16 14:52pm

Add a Solution

Comments

Sergey Alexandrovich Kryukov 29-Apr-16 23:41pm

Your problem is not programming, but lack of any reasonable definition of "crossover" for such generalized data structure. You did not even define your structure of a "typed tree". The problem is some mathematics, not programming. Frankly, I don't know suitable theory myself. In "pure" lambda calculus (which is not like .NET lambda expressions), the expression can be reduced to a list, that is, pure combinatorics, that reduces the definition of GA to your previous one, which is well-known. I just don't know the mathematical model for more general expression trees. Something can always be introduced, but how productive it can be. Perhaps you need to study some literature of mathematics / applied mathematics related to the GP. Sorry for not answering your question...

By the way, I don't really understand how you can work with different types at all? The simple model is: all operands are, say, floating-point values. But then you have a complete algebra (you cannot have fractional powers though, which would require complex numbers, but wider algebra can use complex numbers).

But how you can work with mixed types? You can work with them in ad-hoc manner, but you need to consider some set of expression trees which can be transformed in some random manner (not just crossover). How can you even talk about different types of operands at all? If you think you can, what is the mathematical model of an expression? Forget about crossover, just describe the expression. Don't even bother showing it on couple of example, it would make no sense; comprehensively describe the general case.

Note that the use of tree structure with one single operand type in relation with GP is described pretty much everywhere, so it is not a problem...

—SA

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Peter Leow · Answer 1 · 2016-04-29T14:52:00

Solution 1

Before crossing over, check their return types. If the return types are not comparable, pick another chromosome. You should have a large population to pick from.

Posted 29-Apr-16 14:52pm

Peter Leow

Updated 29-Apr-16 14:55pm

v3

Comments

Sicppy 29-Apr-16 22:06pm

I was just going to have it randomly select from a list of nodes of the same return type in each parent, would that be considered an incorrect implementation of the algorithm?