An examination of tuneable, random search landscapes
Robert E. Smith, James E. Smith · UWE Research Repository (UWE Bristol) · 1998
This paper carefully considers random landscapes related to Kauffman's NK model.In particular, it considers a superset of this model (the NKP model) recently suggested in the GA-analytic literature.Landscapes are exhaustively examined for both the distribution of local optima relative to the global optima, and for characteristics that would effect juxtapositional (building block based) search.The later is accomplished through a Walshbased analysis.The results indicate that K and P have distinct effects on peak distribution, K controlling peak placement, and P affecting relative peak height.The results indicate that P has little effect on a landscape's expected juxtapositional complexity.Moreover, the results suggest that landscapes developed by the NKP procedure are unlikely to have substantial juxtapositional complexity.A Walsh-based procedure that embodies the flavor of the NKP procedure, but can allow for greater expected juxtapositional complexity, is suggested. Kauffman's NK LandscapesIn this discussion we will assume all genes are binary, for convenience.However, the results are extensible to problems with larger gene alphabets.Specifying an NK landscape requires the following parameters:N -the total number of bits (genes).K -the amount of epistasis.Each bit depends on K other bits to determine that its fitness contribution.We will call the K+1 bits involved in each contribution a subfunction.b i -N (possibly random) bitmasks (i = 1,2,3…N).Each bitmask is of length N, and contains K+1 ones.The 1s in a bitmask indicate the bits in an individual that are used to determine the value of the ith sub-function.Given these parameters, one can construct a random NK landscapes as follows:A. Construct an N by 2 K+1 table, X. B.Fill X with random numbers, typically from a standard uniform distribution.Given the table X, and the bitmasks, one determines the fitness of an individual as follows:A. For each bitmask bi, select out the substring of the individual that correspond with the K+1 one-valued bits in that bitmask. B.Decode these bits into their decimal integer equivalent j.C. Add the entry A(i, j) to the overall fitness function value for this individual.Note that the fitness values are normalized by dividing by N.A typical set of bitmasks for this type of problem consists of all N bitmasks that have K+1 consecutive ones.In this case the string is treated as a circle, so that the consecutive 1 bits wrap around.This set of bitmasks outlines a function where any given bit depends on the K preceding bits to determine its contribution to fitness.However, bitmasks are sometimes used such that b i has the ith bit set to one, but the remaining K one-valued bits are selected at random.Some other possibilities are discussed in Altenberg (1997).