|
|
|
|
|
|
|
would still represent A. Moreover, the schema  designates the same subset of  as the schema  , though the latter is more tightly linked than the former. To define this enlarged set of representations precisely, let Vi be redefined to be the set of pairs  , for all  } and let  indicate the set of all permutations of the string (or l-tuple) s. Then  is the enlarged set of all representations of elements in . The set of schemata is enlarged accordingly to  . |
|
|
|
|
|
|
|
|
The object now is to find an operator which when used with crossover and reproduction will tend to replace an above-average schema x with a permutation  of shorter length l(x') < l(x). The genetic operator which fits this specification is inversion. It works by producing a crossover within a single structure as follows: |
|
|
|
 |
|
|
|
|
1. A structure A = a1a2...al is selected (usually at random) from the current population  (where each ai, i = 1, . . . , l, now represents a pair  . |
|
|
|
|
|
|
|
|
2. Two numbers,  and  , are selected from {0,1,2, . . ., l +1} (again at random) and are used to define x1 = min  and x2 = max . |
|
|
|
|
|
|
|
|
3. A new structure is formed from A by inverting the segment which lies to the right of position x1 and to the left of position x2, yielding  |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
It is clear that a single inversion can bring previously widely separated alleles into close proximity, viz., ax1and ax2-1 in the description. It is also clear that any possible permutation of the representation can be produced by an appropriate sequence of inversions. (More technically, the inversions (x1 = 0, x2 = 2), (x1 = 1, x2 = 3), . . ., (x1 = l - 1, x2 = l + 1) are sufficient to generate the group of all permutations of order l.) The effect of the inversion operator upon (the instances of) a schema x is to randomly produce permutations x' of x with varying lengths. Though inversion alters the linkage of schemata, it does not alter the subsets of which they designate. Every permutation x' of x designates the same subset in the set of (original) structures (since the same set of detector values occurs in both x and x'). The lengths of many schemata are affected simultaneously by a single inversion, so this operator too exhibits intrinsic parallelism. As with crossover, schemata of shorter lengths are less frequently affected by the inversion operator. |
|
|
|
|
|