Group Properties of Crossover and Mutation

posted 6/18/02

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
(406) 243-4790

Michael D. Vose
Dept. of Computer Science 
University of Tennessee
203 Claxton Complex
1122 Volunteer Blvd.
Knoxville, TN  37996-3450

Jonathon E. Rowe
Artificial Intelligence Group
Dept. Computer & Information Science
De Montfort University
Milton Keynes MK7 6HP
Great Britain


It is supposed that the finite search space $\Omega$ has certain
symmetries which can be described in terms of a group of permutations
acting upon it. If crossover and mutation respect these symmetries
then these operators can be described in terms of a mixing matrix and
a group of permutation matrices. Conditions under which certain
subsets of $\Omega$ are invariant under crossover are investigated,
leading to a generalization of the term \emph{schema}. Finally, it is
sometimes possible for the group acting on $\Omega$ to induce a group
structure on $\Omega$ itself.