Biological Models¶

graphfla.problems provides synthetic fitness landscapes from evolutionary biology. Their behavior is well characterized, and each has a parameter that controls ruggedness. This makes them suitable for checking an analysis pipeline before applying it to experimental data, and for comparing methods under controlled conditions.

All models on this page define fitness over \(n\) binary variables. Classic NP-hard optimization problems are documented under Combinatorial Problems.

Every problem is a subclass of OptimizationProblem and is used the same way. Create an instance, then call evaluate(config) for a single configuration, or get_data() to enumerate all \(2^n\) binary configurations with their fitness values. The output of get_data() can be passed directly to BooleanLandscape.build_from_data. Higher fitness is better for every problem.

Cost of full enumeration

get_data() returns \(2^n\) rows, which is practical up to about \(n = 20\). For larger \(n\), evaluate configurations individually with evaluate(), or stream them with iter_data().

Overview¶

API	Purpose
`OptimizationProblem`	Base class for defining a custom problem.
`NK`	Kauffman's model with tunable epistasis; \(k\) controls ruggedness.
`RoughMountFuji`	Weighted sum of an additive and a random component; \(\alpha\) controls ruggedness.
`HoC`	Independent random fitness for every configuration.
`Additive`	Independent contributions from each variable, with no epistasis.
`Eggbox`	Periodic fitness that depends only on the number of ones.

Base Class¶

To define a custom problem, subclass OptimizationProblem and implement evaluate(config). The base class provides get_data() and iter_data(). The example in the class documentation below is a complete implementation.

graphfla.problems.OptimizationProblem(
    n: int, seed: Optional[int] = None
)

Base class for binary maximization problems.

ParametersAttributesMethodsExamplesNotes

Parameters

n : int: Number of binary variables. Must be positive.
seed : int or None, default=None: Seed for the instance's random number generator. An integer makes repeated instances reproducible; None uses system-provided randomness.

Attributes

variables : range: Zero-based variable indices, range(n).
rng : random.Random: Instance-local generator; global random state is not modified.

Find a method

evaluate()

evaluate(
    config: Union[str, Sequence[int]],
) -> Union[int, float]

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or variable values encoded as 0/1 or booleans.

Returns

fitness : int or float: Objective value, with larger values indicating better solutions. The concrete subclass determines the scalar type.

Raises

NotImplementedError: Always raised by the base class; subclasses must implement this method.

iter_data()

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import OptimizationProblem
>>> class CountOnes(OptimizationProblem):
...     def evaluate(self, config):
...         return sum(self._validate_config(config))
>>> CountOnes(n=2).get_data()
(['00', '01', '10', '11'], [0, 1, 1, 2])

Subclasses implement evaluate; get_data enumerates the binary search space and returns inputs suitable for a BooleanLandscape.

Notes

All concrete problems use larger fitness values for better solutions. NK, RoughMountFuji and HoC draw and cache random values on first access: reproducing a realization requires the same seed and evaluation order. Evaluating a cached configuration does not draw new values. Treat generated model attributes as read-only; construct a new instance to change the model.

NK Model¶

In Kauffman's NK model, each of the \(n\) variables contributes to fitness according to its own state and the states of \(k\) other variables chosen at random. Fitness is the mean of these \(n\) contributions. Each contribution is drawn from \(U(0, 1)\) the first time its combination of states is evaluated, and then cached.

The parameter \(k\) sets the degree of epistasis. With \(k = 0\), the model is additive and has a single peak. With \(k = n - 1\), the fitness values of different configurations are independent, as in the House of Cards model. Such a landscape has on average \(2^n / (n + 1)\) local optima, or about 50,000 for \(n = 20\).

graphfla.problems.NK(
    n: int,
    k: int,
    exponent: float = 1.0,
    seed: Optional[int] = None,
)

NK landscape with random interaction partners and fitness contributions.

ParametersAttributesMethodsExamplesNotes

Parameters

n : int: Number of binary variables. Must be positive.
k : int: Number of other variables contributing to each variable's fitness component. Must satisfy 0 <= k < n.
exponent : float, default=1.0: Finite power applied to the mean fitness contribution. Positive values preserve fitness ordering; zero gives constant fitness and negative values reverse ordering (undefined if the mean contribution is zero).
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible values for the same evaluation order. None uses system-provided randomness.

Attributes

dependence : list of tuple of int: For each variable, its own index and k distinct random partner indices, sorted in ascending order.
values : dict: Cached contributions in [0, 1). Keys are internal integer encodings of variable/background pairs; use evaluate to access fitness values.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> float

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or variable values encoded as 0/1 or booleans.

Returns

fitness : float: Mean fitness contribution raised to exponent.

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import NK
>>> problem = NK(n=3, k=1, seed=0)
>>> fitness = problem.evaluate([0, 1, 0])
>>> 0.0 <= fitness < 1.0
True
>>> problem.evaluate([0, 1, 0]) == fitness
True

Notes

Fitness is the mean of n independent uniform contributions, raised to exponent. Contributions are sampled on first access and then cached; the seed and evaluation order together determine the realized landscape. With k=0 and exponent=1, the model is additive. At most n * 2**(k + 1) contributions are cached.

The following example generates an NK landscape and computes two ruggedness measures:

from graphfla.problems import NK
from graphfla.landscape import BooleanLandscape
from graphfla.analysis import local_optima_ratio, autocorrelation

problem = NK(n=10, k=4, seed=42)
X, f = problem.get_data()

landscape = BooleanLandscape().build_from_data(X, f, verbose=False)
print(f"Local optima ratio: {local_optima_ratio(landscape):.3f}")
print(f"Autocorrelation:    {autocorrelation(landscape, seed=0):.3f}")

Rough Mount Fuji Model¶

The Rough Mount Fuji model adds random fluctuations to an additive landscape. Each variable has a coefficient \(w_i\) drawn from \(U(-1, 1)\), and each configuration has a random value \(u(\sigma)\) drawn from \(U(0, 1)\) when it is first evaluated:

\[ F(\sigma) = (1 - \alpha) \sum_{i=1}^{n} w_i \sigma_i + \alpha \, u(\sigma). \]

With \(\alpha = 0\) the landscape is additive, and with \(\alpha = 1\) it is a House of Cards landscape. The additive term is not normalized by \(n\), so \(\alpha\) is a mixing weight rather than the fraction of fitness variance due to the random component.

graphfla.problems.RoughMountFuji(
    n: int, alpha: float = 0.5, seed: Optional[int] = None
)

Weighted additive and random binary fitness landscape.

ParametersAttributesMethodsExamplesNotes

Parameters

n : int: Number of binary variables. Must be positive.
alpha : float, default=0.5: Weight of the random component, in [0, 1]. Zero gives an additive landscape and one gives a House of Cards landscape.
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible values for the same evaluation order. None uses system-provided randomness.

Attributes

smooth_contribution : ndarray of shape (n,): Additive coefficients drawn independently and uniformly from [-1, 1].
random_values : dict: Cached independent uniform values in [0, 1), keyed by configuration.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> float

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or variable values encoded as 0/1 or booleans.

Returns

fitness : float: Weighted sum of additive and random components.

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import RoughMountFuji
>>> problem = RoughMountFuji(n=3, alpha=0.0, seed=0)
>>> problem.evaluate([0, 0, 0])
0.0
>>> round(problem.evaluate([1, 0, 0]), 4)
0.6888

Notes

Fitness is (1 - alpha) * sum(w[i] * config[i]) + alpha * u(config). The additive sum is not normalized by n, so alpha is a mixing weight, not a fraction of fitness variance. Random values are drawn on first access and cached; evaluation order affects the realization for a fixed seed.

House of Cards Model¶

The House of Cards model assigns every configuration an independent fitness value from \(U(0, 1)\). Fitness is uncorrelated between neighbors, so the landscape is maximally rugged. HoC(n) produces the same landscape as RoughMountFuji(n, alpha=1.0) with the same seed.

graphfla.problems.HoC(n: int, seed: Optional[int] = None)

House of Cards landscape with independent random fitness values.

ParametersAttributesMethodsExamplesNotes

Parameters

n : int: Number of binary variables. Must be positive.
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible values for the same evaluation order. None uses system-provided randomness.

Attributes

random_values : dict: Cached independent uniform values in [0, 1), keyed by configuration.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> float

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or variable values encoded as 0/1 or booleans.

Returns

fitness : float: Cached uniform random value in [0, 1).

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import HoC
>>> problem = HoC(n=3, seed=0)
>>> round(problem.evaluate([0, 1, 0]), 4)
0.2589
>>> problem.evaluate([0, 1, 0]) == problem.evaluate((False, True, False))
True

Notes

This is RoughMountFuji with alpha=1, including its initial random draws. Fitness is drawn once per configuration, not once per evaluation; the seed and order of first visits together determine the realization.

Additive Model¶

In the additive model, each variable has two contributions, one for each state, drawn from \(U(0, 1)\). Fitness is the sum of the contributions selected by the configuration. Without epistasis, the landscape has a single peak, and every path of improving single mutations leads to it.

graphfla.problems.Additive(
    n: int, seed: Optional[int] = None
)

Binary landscape with independent contributions from each variable.

ParametersAttributesMethodsExamples

Parameters

n : int: Number of binary variables. Must be positive.
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible contributions, sampled at construction. None uses system-provided randomness.

Attributes

contributions : list of tuple of float: Two independent uniform values in [0, 1) per variable, one for each binary state. Fitness is their sum, without normalization by n.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> float

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or variable values encoded as 0/1 or booleans.

Returns

fitness : float: Sum of the selected per-variable contributions, in [0, n).

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> round(problem.evaluate([0, 1]), 4)
1.1033
>>> X, f = problem.get_data()
>>> len(X), len(f)
(4, 4)

Eggbox Model¶

The Eggbox model is deterministic. Fitness depends only on the number of ones in the configuration:

\[ F(\sigma) = \sin^2\!\Bigl(\pi \cdot \text{frequency} \cdot \sum_{i=1}^{n} \sigma_i\Bigr). \]

All configurations with the same number of ones have the same fitness. With the default frequency=0.5, configurations with an odd number of ones have fitness 1 and those with an even number have fitness 0. Every single mutation then moves between the two groups, so half of all configurations are global optima. This makes the model a useful edge case for ruggedness and basin analyses.

graphfla.problems.Eggbox(
    n: int,
    frequency: float = 0.5,
    seed: Optional[int] = None,
)

Periodic binary landscape determined by the number of selected bits.

ParametersMethodsExamples

Parameters

n : int: Number of binary variables. Must be positive.
frequency : float, default=0.5: Positive, finite frequency in sin(pi * frequency * sum(config))**2. A half-integer frequency gives alternating peaks and valleys; integer frequencies give zero fitness in exact arithmetic. Higher frequencies need not produce more peaks on the discrete binary space.
seed : int or None, default=None: Accepted for consistency with other problems; fitness is deterministic and independent of seed.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> float

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or variable values encoded as 0/1 or booleans.

Returns

fitness : float: Squared sine of pi times frequency times the number of ones, in [0, 1].

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import Eggbox
>>> problem = Eggbox(n=3)
>>> [round(problem.evaluate(x), 4) for x in ([0, 0, 0], [0, 0, 1])]
[0.0, 1.0]

Full Example¶

The following example builds an NK landscape and computes measures of ruggedness, fitness-distance correlation and epistasis:

from graphfla.problems import NK
from graphfla.landscape import BooleanLandscape
from graphfla.analysis import (
    autocorrelation,
    classify_epistasis,
    fdc,
    local_optima_ratio,
)

problem = NK(n=10, k=5, seed=42)
X, f = problem.get_data()
landscape = BooleanLandscape().build_from_data(X, f, verbose=False)

print(f"Local optima ratio: {local_optima_ratio(landscape):.3f}")
print(f"Autocorrelation:    {autocorrelation(landscape, seed=0):.3f}")
print(f"FDC:                {fdc(landscape):.3f}")
print(classify_epistasis(landscape, seed=0))

References¶

Stuart A. Kauffman, "The Origins of Order: Self-Organization and Selection in Evolution", Oxford University Press (1993).
Stuart A. Kauffman and Simon Levin, "Towards a general theory of adaptive walks on rugged landscapes", J. Theor. Biol. (1987).
Takuyo Aita et al., "Analysis of a local fitness landscape with a model of the rough Mount Fuji-type landscape", Biophys. Chem. (2000).

Biological Models¶

Overview¶

Base Class¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Notes

NK Model¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Notes

Rough Mount Fuji Model¶

See Also

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Notes

House of Cards Model¶

See Also

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Notes

Additive Model¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Eggbox Model¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Full Example¶

References¶