Group Properties of Crossover and Mutation

posted 6/18/02



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

Michael D. Vose
Dept. of Computer Science 
University of Tennessee
203 Claxton Complex
1122 Volunteer Blvd.
Knoxville, TN  37996-3450
USA
vose@cs.utk.edu


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

Abstract

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.