Efficient Linkage Discovery by Limited Probing

posted 6/30/04

Robert B. Heckendorn
Department of Computer Science 
University of Idaho,
Moscow, ID 83844-1010, USA
heckendo@uidaho.edu


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

This paper has been accepted for publication in the journal
Evolutionary Computation.  An date for publication has not
been set.


Abstract

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.