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 …

This paper addresses the problem of determining the epistatic linkage of a function from
binary strings to the reals. There is a close relationship between the Walsh coefficients of the
function and “probes”(or perturbations) of the function. This relationship leads to two linkage
detection algorithms that generalize earlier algorithms of the same type. A rigorous
complexity analysis is given of the first algorithm. The second algorithm not only detects the
epistatic linkage, but also computes all of the Walsh coefficients. This algorithm is much …