- “RS” = “random schema”
- He proposed them for his thesis on fitness landscape structure, but didn’t have the time to pay them much attention and so removed them. Not sure if they’ve ever been explored any further.
- He and I chatted about them at SFI tea one afternoon in the mid 1990s? I guess?
Simplest definition I can come up with for his original formulation:
for a landscape of N bits:
create a set of R random schemata of length N, each with S≤R set bits, and associate with this a random fitness contribution (i.i.d., from whatever distribution you prefer)
The fitness of a given bit string is the sum of the contributions for all the schemata it matches.
So for example:
A 7-bit landscape, with R=8, S=5:
#10#011 => 1
10#011# => 2
#111#00 => 3
##01110 => 5
11#000# => 8
#101#10 => 13
11#011# => -21
01010## => -34
which induces the following fitnesses:
0000000 => 0
0101010 => -21
1100110 => -21
0110011 => 0
1110000 => 0
1110101 => 0
1111111 => 0
etc…
Some things are already obvious: the number of different fitness values is highly dependent on the probability of a match, and the diversity of a match; there are a lot of “neutral networks” (by Terry’s intention); there’s a phase transition somewhere as S approaches R.
Perhaps not immediately obvious, but salient for fitness landscape groupies, is that you can re-represent any Nk landscape as an RS landscape. That is, you can create a schema for each neighborhood of each spin, and assign the equivalent fitness contribution for that bit under that "neighborhood" state. The divergence from Nk landscapes comes (surprisingly) by reducing the number of schemata, and permitting the existence of neutral "plateaus" in what would otherwise be a locally rugged landscape.
In my Penn thesis work I explored a variant, as a proxy for a sort of “intrinsic energy” function for binary strings. In this, rather than schemata I used match strings, and every substring that matched contributed the specified energy. This had the benefit of being applicable to arbitrary length strings, and permitting some of the higher-order structures in the overlapping matches to play off one another.
For example, this energy “map”:
0 => 2
1 => 0.1
00 => 5
01 => 0.5
10 => 1
11 => 8
000 => 1.9
001 => 6
100 => 4
1010 => 9
1100 => 1.1
10101 => 32
produces the following “fitnesses” (or energies):
0000000 => 7*2 + 6*5 + 5*1.9 = 53.5
01010 => 3*2 + 2*0.1 + 2*0.5 + 2*1 + 9 = 18.2
1100110110 => 6*0.1 + 4*2 + 3*8 + 3*1 + 2*0.5 +
1*5 + 1*6 + 1*1.1 = 48.7
001 => 2*2 + 1*0.1 + 1*5 + 1*0.5 + 6 = 15.6
11011 => 4*0.1 + 2 + 2*8 + 1 + 0.5 = 19.9
11001110010101 => …
etc…
In this case, it makes a bit more sense for some of the patterns to have negative contributions, but it still doesn’t really matter. In the end, it’s possible to define an energy contribution for every pattern up to some limit, and that works fine. It makes the landscape less “neutral” and more “rugged”, but not exactly rugged in the sense most people think. Neighborhoods are complicated, since some patterns will never interact with one another, and there is a lot of detailed information in the symmetry groups of the string operators you’re using.
As I recall Terry pointed out when I suggested this variant, this is “really” just a shorthand for classes of RS schemata. Except for the length thing.
Same thing, but with arbitrary match patterns (including wildcards or “spacers”), which connects them with RS landscapes as such.
John Holland defines "hyperplane-defined functions" (hdfs) which are strikingly similar to RS landscapes as I first heard of them in this paper (PDF), though I'm quite sure I was hearing about them from Terry back in the 90s. Bill Rand revisited and extends these in his thesis (PDF), formalizing them with some conditions for nice analysis, and also making them dynamic landscapes. Several papers among those three on shaky-ladder and other hdf-like fitness landscapes follow.
Wow, you have a good memory :-) And hi! I just noticed I had 15 notifications on Twitter (which I no longer use) and followed them here. I don't know if I ever wrote code for RS landscapes, but knowing me I probably did. I certainly will still have my notes on those ideas if they might be of interest.
What are you up to? I'm terry@jon.es so feel free to continue in email.