Do we need Crossover?

At a certain point of time t the set of genotypes $G'$ in a working population of phenotypes $P' \in PG$ ($PG$ as the set of all possible phenotypes) can have - in the worst case - only genes (:= information strings) which are not in the success set $G^{+}$, written as $G'\cap G^{+} = \emptyset$. The interesting question is whether we need besides mutation to change the content of $G'$ also the crossover operation.

The 'classical' operators of the Genetic Algorithm Paradigm (GAP) are

1. reproduction (selection) is based on available fitness values indicating the 'goodness' of a working information pattern. Reproduction selects from a population the 'good' ones and multiplies them thereby minimizing the 'bad' ones (cf. Goldberg [122]:10f, Suzuki [374]:656).
2. crossover as an exchange between two information patterns selecting a 'cut point' 'x' by random ($0 < x <l$ with $l$ representing the length of the information string) and exchanging all elements 'after the cut point $x$ point by point (cf. Goldberg [122]:12).
3. mutation as a random choice of some position $x \in \{1, ..., l\}$ where the actual value at $x$ will be replaced by some other value out of $\Sigma$ (cf. Goldberg [122]:14).

The interesting question is, whether and how it is possible that the working set $P'$ can be 'changed' in the 'direction' given by the evaluation function.

The reproduction operation getting some feedback with 'fitness values' can 'improve a given working set $G'$, but as long as this set will not change this feedback will stay the same and nothing will happen. A 'bad' working set $G'$ will stay as a 'bad' set forever.

The mutation operation can change an information string either in the direction of a 'better' string with regard to the 'unknown' success set $G^{+}$ or not.

The interesting question here is, what exactly is the role of the crossover operation? Can crossover improve a set of working information strings too or not?

In the section before 5.1 I had stated (without a proof (this was the failure)), that crossover can not improve a working set $G'$. As we will see below there are very special circumstances where crossover can improve a working set $G'$ and this happens at best in close 'cooperation' with mutation.

Let us assume as test set $G' = \{ (0,0), (0,0) \}$.

Applying crossover in this case would not change anything because with cut-point $x=1$ all the output of crossover would be already elements of the set $G'$.

Asking for those conditions under which crossover can produce some 'new' elements not already contained in the 'old' set - $\forall x,g,g',G' (crossov(g,g',G',x) \notin G')$ - we have to assume a 'canonical' set $G''$ where every pair of members $g,g'$ is 'different' in the sense that $\exists i( i \in dm(g) \wedge g(i) \neq g'(i))$ (on account of reproduction working sets will usually have many instances of the same pattern).

Assuming a canonical set $G''$ we can re-formulate the question asking for those conditions under which the crossover operation can generate a pattern which is not yet an element of the canonical set $G''$.

Assuming a test set $G''=\{ (0,0), (0,1)\}$ shows, that with cut-point $x=1$ no new element will be generated - $crossov((0,0), (0,1),1,G'')) = \{(0,1), (0,0\}$ -.Thus there must be some other special condition under which crossover can produce something 'new'.

Looking to examples like $G''=\{ (0,0), (1,1)\}$ , $crossov((0,0), (1,1),1,G'')) = \{(0,1), (1,0)\}$, $G''=\{ (1,0), (0,1)\}$, $crossov((1,0), (0,1),1,G'')) = \{(1,1), (0,0)\}$ that a 'new' pattern can only emerge if values 'before' and 'after' the cut-point are simultaneously exchanged and at all positions in the domain of the patterns the values are different before the exchange. Thus we postulate a kind of asymmetry where we have two patterns $g,g'$ with length $l$ and cut-point $0 < x <l$ where there exists at least one position $i \in dm(g)$ 'before' the cut-point $i < x$ and at least one position $j \in dm(g)$ which is 'after' the cut-point x $j > x$ and the values at these positions are different $g(i) \neq g'(i) \wedge g(j) \neq g'(j)$. Under this asymmetry-condition we would get new patterns $g'_{new}, g_{new}$ with the new elements $g_{new}=(...., g(i),....,g'(j)...)$ and $g'_{new}=(...., g'(i),....,g(j)...)$. Argument: For $g_{new}$ we know according to the assumption that $g(i)$ was specific for $g_{old}$ it is still specific and $g'(j)$ is 'new' in combination with $g(i)$. The same holds for $g'_{new}$ respectively.

But this lets open the question whether the new elements are new with regard to the whole set $G''$. For a canonical set we have only postulated that for all pairs there must exists at least 'one' position where they differ. Assume that there would exist one element $g^{*} \in G''$ which would differ with $g$ and with $g'$ in at least one position $k \in dm(g^{*}$.

If this position would be different to $i \in dm(g)$, then this difference would be still valid, because the value at this position would not change in $g$. But then $g^{*}(i)$ could be equal to $g'$ at $i$. If this would be the case there must exist another position $n \in dm(g')$ where $g^{*}, g'$ differ. This must not necessarily be at position $j$. With the assumption so far one cannot exclude that another $g^{*}$ could be equal to $g'$ while differing with $g$. This argument applies also to the other sub cases.

From this we have to conclude that the condition for the 'newness' of crossover generated patterns can only be guaranteed if one postulates for (i) local asymmetry and (ii) uniqueness.

We have a local asymmetry between two patterns $g,g'$ with length $l$ and cut-point $0 < x <l$ if there exists at least one position $i \in dm(g)$ 'before' the cut-point $i < x$ and at least one position $j \in dm(g)$ which is 'after' the cut-point x $j > x$ and the values at these positions are different $g(i) \neq g'(i) \wedge g(j) \neq g'(j)$. The distinguishing positions $i,j$ are called the asymmetry indexes. Under this asymmetry-condition we would get new patterns $g'_{new}, g_{new}$ with the new elements $g_{new}=(...., g(i),....,g'(j)...)$ and $g'_{new}=(...., g'(i),....,g(j)...)$.

We will have uniqueness of two local asymmetric patterns $g,g'$ in a working set $G'$ if this working set is a canonical set $G''$ and it holds that $g^{*} \notin ran(crossov(g,g',G'',x))$.

This definition puts the 'hard work' of revealing the details to some additional proof. But even in this rough format it becomes clear that the usage of crossover is very limited. I will show up that finally crossover makes only sense if a mutation operation has introduced 'enough new patterns' to make crossover applicable.