Inversion

30 Minutes Body

Online Fitness Training Programs

Get Instant Access

Holland (1975) included proposals for adapting the encodings in his original proposal for GAs (also see Goldberg (1989a). Holland, acutely aware that correct linkage is essential for single-point crossover to work well, proposed an "inversion" operator specifically to deal with the linkage problem in fixed-length strings.

Inversion is a reordering operator inspired by a similar operator in real genetics. Unlike simple GAs, in real genetics the function of a gene is often independent of its position in the chromosome (though often genes in a local area work together in a regulatory network), so inverting part of the chromosome will retain much or all of the "semantics" of the original chromosome.

To use inversion in GAs, we have to find some way for the functional interpretation of an allele to be the same no matter where it appears in the string. For example, in the chromosome encoding a cellular automaton (see section 2.1), the leftmost bit under lexicographic ordering is the output bit for the neighborhood of all zeros. We would want that bit to represent that same neighborhood even if its position were changed in the string under an inversion. Holland proposed that each allele be given an index indicating its "real" position, to be used when evaluating a chromosome's fitness. For example, the string 00010101 would be encoded as

with the first member of each pair giving the "real" position of the given allele. This is the same string as, say,

Chapter 4: Theoretical Foundations of Genetic Algorithms {(1.0) (2,0) (6,1) (5,0) (4,1) (3.0) (7.0) (8.1)}

Inversion works by choosing two points in the string and reversing the order of the bits between them—in the example just given, bits 3-6 were reversed. This does not change the fitness of the chromosome, since to calculate the fitness the string is ordered by the indices. However, it does change the linkages: the idea behind inversion is to produce orderings in which beneficial schemas are more likely to survive. Suppose that in the original ordering the schema 00**01** is very important. Under the new ordering, that schema is 0010****. Given that this is a high-fitness schema and will now tend to survive better under single-point crossover, this permutation will presumably tend to survive better than would the original string.

The reader may have noticed a hitch in combining inversion with single-point crossover. Suppose, for example, that

crosses with

after the third bit. The offspring are {(1.0) (2.0) (6.1) (4.1) (1.1) (8,1) (6,0) (7.0))

The first offspring has two copies each of bits 1 and 6 and no copies of bits 3 and 5. The second offspring has two copies of bits 3 and 5 and no copies of bits 1 and 6. How can we ensure that crossover will produce offspring with a full set of loci? Holland proposed two possible solutions: (1) Permit crossover only between chromosomes with the same permutation of the loci. This would work, but it severely limits the way in which crossover can be done. (2) Employ a "master/slave" approach: choose one parent to be the master, and temporarily reorder the other parent to have the same ordering as the master. Use this ordering to produce offspring, returning the second parent to its original ordering once crossover has been performed. Both methods have been used in experiments on inversion.

Inversion was included in some early work on GAs but did not produce any stunning improvements in performance (Goldberg 1989a). More recently, forms of inversion have been incorporated with some success into GAs applied to "ordering problems" such as the DNA fragment assembly problem (Parsons, Forrest, and Burks, in press). However, the verdict on the benefits of inversion to GAs is not yet in; more systematic experimental and theoretical studies are needed. In addition, any performance benefit conferred by inversion must be weighed against the additional space (to store indices for every bit) and additional computation time (e.g., to reorder one parent before crossover) that inversion requires.

Was this article helpful?

0 0
Fitness and Exercise

Fitness and Exercise

Are you looking for the solutions to start a healthy lifestyle, stay free from bad illness, have a better sex life and more romantic involvements for a more satisfied life but just do not know how and where to get started? Then this will be the most important letter you'll ever read for today.

Get My Free Ebook


Post a comment