(This is only semi-frivolous.)

Getting crossover to behave well was a big question in genetic programming for a long time. “Behave well” means “produce children which are semantically between their parents”. Most GP crossovers don’t achieve this very well.

But Moraglio and friends (PPSN 2012) pointed out that it’s actually
really simple. If you have two trees *t1* and *t2*, you can get an
offspring *tn* which is on the (Euclidean) line segment between them
in this retrospectively obvious way: *tn = (1-r) t1 + r t2*, where *r*
is a random constant in *[0, 1]*. This is the geometric semantic
crossover.

The *(1-r) t1 + r t2* pattern is, if you like, a linear interpolation
from *t1* to *t2*. For every fitness case, as *r* increases, you move
from the value of *t1* to that of *t2*.

There is a variation: in the original Moraglio et al paper, instead of
a random constant *r*, you can have a random tree *r(X)* (where *X* is
the independent variables). If *r(X)* is in *[0, 1]* then for each
fitness case the value of *tn* is between the values of *t1* and *t2*.
In this case, the values for all fitness cases don’t all move linearly
and in lock-step from *t1* to *t2*. So *tn* is in the Manhattan line
segment between *t1* and *t2* (instead of the Euclidean one, as
above).

Also another slight variation: in the Vanneschi et al paper (EuroGP
2013), *r(X)* is a random tree, but is not restricted to *[0, 1]*, so
*tn* is in the same hyperplane as the parents, but is not necessarily
between them.

All of these have in common the same basic pattern: you take two
numbers which sum to 1 (eg *r* and *(1-r)*), and use them as
coefficients in a weighted sum of the parents. Are there any other
options?

What about a trigonometric formula, like *cos^2(u) + sin^2(u) = 1*?
Then we can define a crossover as *tn = cos^2(r) t1 + sin^2(r) t2*.
Here, *r* could be any independent variable, or it could be a random
tree *r(X)*.

Or, if we see the original geometric semantic crossover as a weighted
mean of the parents, what about other types of means? The geometric
mean of *a* and *b* is *sqrt(ab)*, and you could define a crossover
*tn = sqrt(t1 t2)*. But that would be bad for the same reason it would
be bad to always use the (unweighted) mean *tn = (t1 + t2)/2*. But
there is a weighted geometric mean, which for just two values *a* and
*b* is just *exp(r ln(a) + (1-r) ln(b))*. So we could define a
crossover as *tn = exp(r ln(t1) + (1-r) ln (t2))*, and again *r* is
either a constant or a random tree *r(X)*.

There is also the harmonic mean, but that assumes the input values are positive.

Another option: one could use the Vanneschi et al crossover where
*r(X)* is a random tree, but stay in *[0, 1]* using a sigmoidal map.
So the crossover would be defined as *tn = sigmoid((1-r(X)) t1 + r(X)
t2)*.

A final option: why is *r(X)* a *random* tree? Why not call any of
these a three-parent crossover, where *r(X)* is selected from the
previous population just like *t1* and *t2*? Vanneschi et al
anticipate this idea with their “slight abuse of terminology”, calling
*r* an “ancestor” of later individuals.

Both the trigonometric crossover and the geometric mean crossover
(uh-oh, “geometric” is being used in two senses now) are geometric
when using a random constant *r*. When using a random tree *r(X)*,
they are still “weakly” geometric, ie geometric in Vanneschi’s sense.
The sigmoid crossover is geometric for *r(X)*, and wouldn’t really
make any sense for constant *r*.

All have the possible advantage that they allow for more complex tree structures to come about – not just weighted sums of trees. If we just wanted weighted sums, we’d use linear regression! Maybe we could use several types of crossover in a single run, in order to accumulate complex tree structures?

First question: are there other options?

Empirical question: would it work?