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.
-
inline NKLandscape()
-
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
-
NKLandscapeMemo() = delete