Child pages
  • NKWalk
Skip to end of metadata
Go to start of metadata

The Sendero Project

The NK adaptive walk


Each site has D = (A - 1)N one-mutant neighbours, e.g., where A = 2 and N = 5 then D = 5. An organization begins its walk at a random point on the landscape, e.g., a location in the range 00000 through 11111, such as 01110. The fitness of this location is calculated, as illustrated in the NK landscape page 2. Whether an agent moves on the landscape is determined by one of three adaptive walk methods:

  • One-mutant change: an organisation chooses a single new location from the set of "one-mutant change" neighbours (a neighbouring location whose configuration differs from the current system in only one property). If the new location provides higher fitness then the organisation moves to this new location, otherwise the organisation stays in its current location.
  • Fitter dynamics: the organisation chooses a new location from the set of "one-mutant change" neighbours, but if the fitness of the new location is not fitter than the current location, then the search continues until a fitter variant is found, or all neighbours have been checked.
  • Greedy dynamics: an organisation chooses a new system configuration by looking at every "one-mutant change" neighbour and choosing the one with the highest fitness.

Once an organisation cannot find a fitter neighbouring location it stops walking the landscape and remains on a (possibly sub-optimal) local peak. The fitness associated with a particular simulation run is calculated as the average of the fitness of the organizations (for example, 100) released onto the landscape.

Benchmarking Sendero to Kauffman's Origins of Order

The NK model was run in Sendero to replicate Kauffman's Table 2.1 from "The Origins of Order". For each combination of N and K 100 runs are conducted and the results averaged; each individual run has 100 agents released at random on to the landscape. All of the simulations were run on a standard laptop computer with the exception of N = 96. The longest run on a laptop was for N = 48 and K ranging from 0 to 47 - this run took five hours. For lower values of N the run time is much shorter, with N = 8 running in less than a minute. This performance makes Sendero suitable for running all but the largest simulations on a personal computer.

 

 

 

 

 

N

 

 

 

 

 

K

8

 

16

 

24

 

48

 

96

 

0

0.65

0.65

0.67

0.65

0.67

0.66

0.65

0.66

0.67

0.66

2

0.70

0.70

0.71

0.70

0.71

0.70

0.68

0.70

0.71

0.71

4

0.70

0.70

0.70

0.71

0.71

0.70

0.69

0.70

0.71

0.70

8

0.67

0.66

0.68

0.68

0.69

0.68

0.69

0.69

0.69

0.68

16

 

 

0.64

0.65

0.65

0.66

0.66

0.66

0.66

0.66

24

 

 

 

 

0.63

0.63

0.64

0.64

0.65

0.64

48

 

 

 

 

 

 

0.60

0.60

0.61

0.61

96

 

 

 

 

 

 

 

 

0.58

0.58

Table 1: Sendero results shown in bold for various values of N and K with Kauffman's original results shown in non-bold text (values on diagonal are minus one, e.g., when N = 16 then K = 15)


 

Sample output from running the NK model in Sendero

The following graphs show fitness values for various combinations of N and K. All graphs represent single runs where each run has 100 agents released at random on to the fitness landscape.


 

Figure 1: Sendero output for N = 24 and K = 0

In Fig. 1 the average, maximum, minimum fitness all converge as all agents find the single peak on the landscape (K = 0) and global fitness is roughly 0.63. In Fig. 2 K is small relative to N and average fitness improves, as expected, over the case where K = 0, demonstrating that some complexity is better overall than zero complexity.


 
 

Figure 2: Sendero output for N = 24 and K = 4


 

Figure 3: Sendero output for N = 24 and K = 23

In Fig. 3 there is maximal complexity, K = N - 1, and agents quickly become stuck on the random, uncorrelated landscape. Average fitness falls back to around 0.63. As N increases the K = N -1 effect becomes more pronounced, as in Fig. 4 where K = 47 and average fitness is 0.60.



Figure 4: Sendero output for N = 48 and K = 47

Long jumps


Once an organization has become trapped on a local peak then it might be allowed to make a long jump. This involves selecting a location at random, assessing its fitness and then moving to that location if the fitness is higher than the current location. This is the search party strategy whereby a clone is sent out to explore and the organization only commits itself once a fitter location than the current local peak can be found. Without stopping criteria the run continues until the tick limit is reached. Alternatively, the user can specify how many successful jumps an organization can make or a time limit for finding a fitter location by jumping.

In Fig. 5 agents are allowed to jump once they have reached a local peak. The model is run for 500 generations and there are no stopping conditions for long jumping, i.e., agents trapped on local peaks can continue to look for fitter locations until the last time tick. Fitness continues to increase beyond the point where it would have stopped if only local walks were allowed, although the increase in fitness is slow.

 
 
Figure 5: Sendero output for fitness, N = 24, K = 8, long jumps allowed (with no stopping condition)

Fig. 6 shows the fraction still walking. Without long jumps the simulation would have stopped somewhere around generation 200. With long jumps agents continue to search for fitter locations but, as Figure 5 shows, they do so with less and less effectiveness. Kauffman shows that it becomes exponentially more difficult to improve fitness with each successful long jump.


 

Figure 6: Sendero output for fraction still walking, N = 24, K = 8, long jumps allowed (with no stopping condition)

Communication


A communication network allows the organizations thrown onto the landscape to communicate with each other according to the network connections established for the simulation (e.g., random network, fully connected network).

Life and death


This option allows organizations to be removed and new ones to be added, keeping the population at a constant level. A fitness threshhold is set by the user and this is used to determine whic organizations die - if an organization has a difference between it and the fittest organiztion that is greater than the threshhold then it is removed. Another organization is generated either by copying an existing organization or by selecting a random new location. The "both" method looks at the genetic load of the landscape and decides whether to generate a location at random (more variety needed) or to copy an existing organization (current organizations performing well).

Continue to: the NKC Model

NKC Home


 

  • No labels