Efficient Linkage Discovery by Limited Probing
Robert B. Heckendorn
Department of Computer Science
University of Idaho,
Moscow, ID 83844-1010, USA
Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
This paper has been accepted for publication in the journal
Evolutionary Computation. An date for publication has not
This paper addresses the problem of discovering the structure
of a fitness function from binary strings to the reals under
the assumption of bounded epistasis. Two loci (string positions)
are epistatically linked if the effect of changing the allele
(value) at one locus depends on the allele at the other locus.
Similarly, a group of loci are epistatically
linked if the effect of changing the allele at one locus depends
on the alleles at all other loci of the group. Under the
assumption that the size of such groups of loci are bounded,
and assuming that the function is given only as a ``black box
function'', this paper presents and analyzes a randomized algorithm
that finds the complete epistatic structure of the function
in the form of the Walsh coefficients of the function.