NK.hpp

This file provides code to build NK-based algorithms.

Two version of landscapes are provided. NKLandscape pre-calculates the entire landscape, for easy lookup. NKLandscapeMemo does lazy evaluation, memorizing values when they’re first used. NKLandscape is faster, but goes up in memory size exponentially with K. NKLandscapeMemo is slightly slower, but can handle arbitrarily large landscapes.

Todo:

Right now we make the library user decide between NKLandscape and NKLandscapeMemo. Based on K value, we should be able to do this automatically, so we could merge the two.

class NKLandscape
#include <NK.hpp>

An NK Landscape is a popular tool for studying theoretical questions about evolutionary dynamics. It is a randomly generated fitness landscape on which bitstrings can evolve. NK Landscapes have two parameters: N (the length of the bitstrings) and K (epistasis). Since you have control over the amount of epistasis, NK Landscapes are often called “tunably rugged” - a useful feature, since the ruggedness of the fitness landscape is thought to be important to many evolutionary dynamics. For each possible value that a site and its K neighbors to the right can have, a random fitness contribution is chosen. These contributions are summed across the bitstring. So when K = 0, each site has a single optimal value, resulting in a single smooth fitness peak.

For more information, see Kauffman and Levin, 1987 (Towards a general theory of adaptive walks on rugged landscapes).

This object handles generating and maintaining an NK fitness landscape. Note: Overly large Ns and Ks currently trigger a seg-fault, caused by trying to build a table that is larger than will fit in memory. If you are using small values for N and K, you can get better performance by using an NKLandscapeConst instead.

Public Functions

inline NKLandscape()
NKLandscape(const NKLandscape&) = default
NKLandscape(NKLandscape&&) = default
inline NKLandscape(size_t _N, size_t _K, Random &random)

N is the length of bitstrings in your population, K is the number of neighboring sites the affect the fitness contribution of each site (i.e. epistasis or ruggedness), random is the random number generator to use to generate this landscape.

inline ~NKLandscape()
NKLandscape &operator=(const NKLandscape&) = delete
NKLandscape &operator=(NKLandscape&&) = default
inline void Reset(Random &random)

Randomize the landscape without changing the landscape size.

inline void Config(size_t _N, size_t _K, Random &random)

Configure for new values of N and K.

inline size_t GetN() const

Returns N.

inline size_t GetK() const

Returns K.

inline size_t GetStateCount() const

Get the number of posssible states for a given site.

inline size_t GetTotalCount() const

Get the total number of states possible in the landscape (i.e. the number of different fitness contributions in the table)

inline double GetFitness(size_t n, size_t state) const

Get the fitness contribution of position [n] when it (and its K neighbors) have the value [state]

inline double GetFitness(std::vector<size_t> states) const

Get the fitness of a whole bitstring.

inline double GetFitness(BitVector genome) const

Get the fitness of a whole bitstring (pass by value so can be modified.)

inline double GetSiteFitness(size_t n, BitVector genome) const

Get the fitness of a site in a bitstring.

inline vector<double> GetFitnesses(BitVector genome) const

Get the fitness of a whole bitstring (pass by value so can be modified.)

inline void SetState(size_t n, size_t state, double in_fit)
inline void RandomizeStates(Random &random, size_t num_states = 1)

Private Members

size_t N

The number of bits in each genome.

size_t K

The number of OTHER bits with which each bit is epistatic.

size_t state_count

The total number of states associated with each bit table.

size_t total_count

The total number of states in the entire landscape space.

vector<vector<double>> landscape

The actual values in the landscape.

class NKLandscapeMemo
#include <NK.hpp>

The NKLandscapeMemo class is simialar to NKLandscape, but it does not pre-calculate all of the landscape states. Instead it determines the value of each gene combination on first use and memorizes it.

Public Functions

NKLandscapeMemo() = delete
NKLandscapeMemo(const NKLandscapeMemo&) = delete
NKLandscapeMemo(NKLandscapeMemo&&) = default
inline NKLandscapeMemo(size_t _N, size_t _K, Random &random)
inline ~NKLandscapeMemo()
NKLandscapeMemo &operator=(const NKLandscapeMemo&) = delete
NKLandscapeMemo &operator=(NKLandscapeMemo&&) = default
inline size_t GetN() const
inline size_t GetK() const
inline double GetFitness(size_t n, const BitVector &state) const
inline double GetFitness(const BitVector &genome) const

Private Members

size_t N
size_t K
mutable vector<memo_function<double(const BitVector&)>> landscape
vector<BitVector> masks