At a certain point of time t the set of genotypes in a working population of phenotypes ( as the set of all possible phenotypes) can have - in the worst case - only genes (:= information strings) which are not in the success set , written as . The interesting question is whether we need besides mutation to change the content of also the crossover operation.
The 'classical' operators of the Genetic Algorithm Paradigm (GAP) are
The interesting question is, whether and how it is possible that the working set 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 , but as long as this set will not change this feedback will stay the same and nothing will happen. A 'bad' working set 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 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 . As we will see below there are very special circumstances where crossover can improve a working set and this happens at best in close 'cooperation' with mutation.
Let us assume as test set .
Applying crossover in this case would not change anything because with cut-point all the output of crossover would be already elements of the set .
Asking for those conditions under which crossover can produce some 'new' elements not already contained in the 'old' set - - we have to assume a 'canonical' set where every pair of members is 'different' in the sense that (on account of reproduction working sets will usually have many instances of the same pattern).
Assuming a canonical set 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 .
Assuming a test set shows, that with cut-point no new element will be generated - -.Thus there must be some other special condition under which crossover can produce something 'new'.
Looking to examples like , , , 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 with length and cut-point where there exists at least one position 'before' the cut-point and at least one position which is 'after' the cut-point x and the values at these positions are different . Under this asymmetry-condition we would get new patterns with the new elements and . Argument: For we know according to the assumption that was specific for it is still specific and is 'new' in combination with . The same holds for respectively.
But this lets open the question whether the new elements are new with regard to the whole set . 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 which would differ with and with in at least one position .
If this position would be different to , then this difference would be still valid, because the value at this position would not change in . But then could be equal to at . If this would be the case there must exist another position where differ. This must not necessarily be at position . With the assumption so far one cannot exclude that another could be equal to while differing with . 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 with length and cut-point if there exists at least one position 'before' the cut-point and at least one position which is 'after' the cut-point x and the values at these positions are different . The distinguishing positions are called the asymmetry indexes. Under this asymmetry-condition we would get new patterns with the new elements and .
We will have uniqueness of two local asymmetric patterns in a working set if this working set is a canonical set and it holds that .
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.
Gerd Doeben-Henisch 2013-01-14