NK landscape
The problem
Kauffman and Weinberger's NK model scores a string of N bits as the mean of N contributions. The contribution wᵢ of bit i depends on its own value and on those of K other bits, its neighbors: each of the 2^(K+1) combinations gets a value drawn independently and uniformly from (0, 1), and
W(x) = (1/N) Σᵢ wᵢ(xᵢ, x_{i₁}, …, x_{i_K})
(their equation 1). K tunes the landscape: at K = 0 the bits are independent and there's a single optimum; as K grows towards N − 1, the landscape gets more rugged, with more local optima and lower ones, until at K = N − 1 every one-bit change gives a new random fitness.
Here N = 20 and K = 4, and each bit's 4 neighbors are drawn at random from the other 19 (their
Table 2; "adjacent" neighbors, a bit's flanking ones on a circle, are their Table 1). The landscape
is genoxide's problems::binary::NkLandscape::new(20, 4, Neighborhood::Random, 1): its neighbors
and its 20 tables of 32 values are drawn from seed 1 with genoxide's portable random numbers, so
it's the same landscape on every platform and in Python. Its contributions are odd multiples of 2⁻⁵³,
added up exactly, so the fitness is the same to the bit everywhere.
What makes it hard
The optimum isn't known in closed form: each landscape has its own. genoxide's optimum computes it
exactly, here by evaluating all 2²⁰ = 1,048,576 strings, changing one bit at a time in Gray code
order so that only the contributions that depend on it change (a hundredth of a second). For
adjacent neighbors it uses dynamic programming instead, which solves landscapes of hundreds of bits.
With K = 4, a bit's best value depends on its neighbors' values, which depend on theirs: changing one bit changes its own contribution and those of the bits it bears on, five on average. The landscape has many local optima, strings that no single flip improves. A search that only climbs stops at one of them.
Representation
A Binary genome of 20 bits is the string itself. The fitness is W, to maximize.
Algorithm
Iterated local search: LocalSearch flips one bit at a time and keeps the change if the string is
no worse, and after 100 steps without a better best, restarts from the best string, changed by 5
random flips, enough to leave its basin and few enough to keep most of it. A run from seed 1 stops
at the optimum, or after 500,000 evaluations.
Then, on the landscapes of seeds 1 to 5, iterated local search and, as a contrast, a genetic algorithm run from seeds 1 to 20: a population of 500, tournaments of 2, two-point crossover and bit-flip mutation at 1/20 per bit, for 200 generations.
Output
The first lines give the landscape and its optimum, with the string that reaches it, bit 0 first. The table follows the run from seed 1: the evaluations at which its best improves, to 6 decimals, and then the string it ends with. The last table gives, for each landscape, its optimum, how many runs of iterated local search from seeds 1 to 20 reach it and their median evaluations, and how many runs of the GA do. The landscapes are evaluated in Rust in both languages, so both print the same.
The project page plays back the run from seed 1: the string, as single flips climb and restarts kick it.
Good results
The optimum of the landscape of seed 1 is 0.742541. The run from seed 1 reaches it after 927 evaluations, at the same string as exhaustive search. On the 5 landscapes, iterated local search reaches the optimum from all 20 seeds, after a median of 1,109 to 4,910 evaluations. Over landscapes 1 to 10 and seeds 1 to 100 each, it reached the optimum in 997 of 1,000 runs within 200,000 evaluations.
The genetic algorithm reaches it on the easier landscapes but not the others: from 5 of 20 seeds on landscape 2 and 6 of 20 on landscape 5, where its other runs end below the optimum within 200 generations. Each landscape is a new instance, so a method has to be judged over several.
Known optimum: 0.742541 (landscape seed 1, by exhaustive search)
Source: examples/nk_landscape
Interactive run: tachsin.gr/projects/genoxide/examples/nk-landscape
cargo run --release --example nk_landscape
//! NK landscape: maximize a landscape of Kauffman and Weinberger's NK model, N = 20 bits each
//! interacting with K = 4 others chosen at random, with iterated local search, and check it
//! against the optimum found by evaluating all 2^20 strings.
//!
//! The landscape is drawn from seed 1 with genoxide's portable random numbers. Iterated local
//! search flips one bit at a time, keeping changes that are no worse, and after 100 steps without
//! a better best restarts from the best, changed by 5 random flips. A run from seed 1 prints its
//! improvements; then, on the landscapes of seeds 1 to 5, runs from seeds 1 to 20 count how often
//! it reaches the optimum, against a genetic algorithm as a contrast. The landscapes are genoxide's
//! `problems::binary::NkLandscape`, whose `optimum` searches every string.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example nk_landscape
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::{Neighborhood, NkLandscape};
const N: usize = 20;
const K: usize = 4;
const LANDSCAPES: u64 = 5;
const SEEDS: u64 = 20;
// the most evaluations of a run of iterated local search, and generations of the GA
const BUDGET: u64 = 500_000;
const GENERATIONS: u64 = 200;
// iterated local search from `seed`
fn ils(landscape: &NkLandscape, seed: u64) -> Result<LocalSearch<Binary, BitFlip>> {
LocalSearch::builder(landscape.representation())
.neighbor(BitFlip::count(1)?)
.restart(100, 5)
.seed(seed)
.build()
}
// the median of `values`
fn median(mut values: Vec<f64>) -> f64 {
values.sort_by(f64::total_cmp);
let middle = values.len() / 2;
if values.len() % 2 == 1 {
values[middle]
} else {
(values[middle - 1] + values[middle]) / 2.0
}
}
fn main() -> Result<()> {
let landscape = NkLandscape::new(N, K, Neighborhood::Random, 1)?;
let optimum = landscape.optimum().expect("small enough");
println!("NK landscape: N = {N}, K = {K}, random neighbors, drawn from seed 1");
println!(
"the optimum, over all 2^{N} strings: {:.6} at {}",
optimum.value(),
optimum.solutions()[0]
);
println!("iterated local search from seed 1");
println!("evaluations best");
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env(N, optimum.value());
let mut last = 0.0;
let outcome = Engine::new(ils(&landscape, 1)?, landscape.clone())
.stop_when(Stop::target(optimum.value()).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
let best = progress.best().and_then(Fitness::score).unwrap_or(0.0);
if best > last {
println!("{:>11} {best:.6}", progress.evaluations());
last = best;
}
})
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"{:.6} after {} evaluations, at {}",
outcome.best_fitness().score().expect("valid"),
outcome.evaluations(),
outcome.best_genome()
);
// iterated local search and, as a contrast, a GA on landscapes 1 to 5, from seeds 1 to 20
println!("\nlandscape optimum ILS reaches median evaluations GA reaches");
for landscape_seed in 1..=LANDSCAPES {
let landscape = NkLandscape::new(N, K, Neighborhood::Random, landscape_seed)?;
let optimum = landscape.optimum().expect("small enough").value();
let mut evaluations = Vec::new();
let mut ga_reached = 0;
for seed in 1..=SEEDS {
let outcome = Engine::new(ils(&landscape, seed)?, landscape.clone())
.stop_when(Stop::target(optimum).or(Stop::evaluations(BUDGET)))
.run()?;
if outcome.stop_reason() == StopReason::Target {
evaluations.push(outcome.evaluations() as f64);
}
let ga = Ga::builder(landscape.representation())
.population_size(500)
.select(Tournament::new(2)?)
.crossover(PointCrossover::two_point())
.mutate(BitFlip::per_gene(1.0 / N as f64)?)
.seed(seed)
.build()?;
let outcome = Engine::new(ga, landscape.clone())
.stop_when(Stop::target(optimum).or(Stop::generations(GENERATIONS)))
.run()?;
ga_reached += usize::from(outcome.stop_reason() == StopReason::Target);
}
println!(
"{landscape_seed:>9} {optimum:.6} {:>8}/{SEEDS} {:>18.1} {ga_reached:>7}/{SEEDS}",
evaluations.len(),
median(evaluations)
);
}
trace.write();
Ok(())
}
python examples/nk_landscape/main.py
"""NK landscape: maximize a landscape of Kauffman and Weinberger's NK model, N = 20 bits each
interacting with K = 4 others chosen at random, with iterated local search, and check it against
the optimum found by evaluating all 2^20 strings.
The landscape is drawn from seed 1 with genoxide's portable random numbers. Iterated local search
flips one bit at a time, keeping changes that are no worse, and after 100 steps without a better
best restarts from the best, changed by 5 random flips. A run from seed 1 prints its improvements;
then, on the landscapes of seeds 1 to 5, runs from seeds 1 to 20 count how often it reaches the
optimum, against a genetic algorithm as a contrast. The landscapes are genoxide's
problems.binary.NkLandscape, which run evaluates in Rust, and whose optimum searches every string.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.
python examples/nk_landscape/main.py
"""
import genoxide as gx
from trace import Trace
N = 20
K = 4
LANDSCAPES = 5
SEEDS = 20
# the most evaluations of a run of iterated local search, and generations of the GA
BUDGET = 500_000
GENERATIONS = 200
def ils(landscape, seed):
"""Iterated local search from ``seed``."""
return gx.LocalSearch(
landscape.genome, neighbor=gx.BitFlip(count=1), restart=(100, 5), seed=seed
)
def median(values):
"""The median of ``values``."""
values = sorted(values)
middle = len(values) // 2
return values[middle] if len(values) % 2 else (values[middle - 1] + values[middle]) / 2
def text(bits):
"""A bit string as 0s and 1s."""
return "".join("1" if bit else "0" for bit in bits)
landscape = gx.problems.binary.NkLandscape(N, K, "random", seed=1)
optimum = landscape.optimum
print(f"NK landscape: N = {N}, K = {K}, random neighbors, drawn from seed 1")
print(
f"the optimum, over all 2^{N} strings: {optimum.value:.6f} at {text(optimum.solutions[0])}"
)
print("iterated local search from seed 1")
print("evaluations best")
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(N, optimum.value)
last = 0.0
def progress(progress):
global last
best = progress.best_fitness or 0.0
if best > last:
print(f"{progress.evaluations:>11} {best:.6f}")
last = best
trace.record(progress)
result = ils(landscape, 1).run(
landscape, target=optimum.value, evaluations=BUDGET, on_generation=progress
)
print(
f"{result.best_fitness:.6f} after {result.evaluations} evaluations, at "
f"{text(result.best_genome)}"
)
# iterated local search and, as a contrast, a GA on landscapes 1 to 5, from seeds 1 to 20
print("\nlandscape optimum ILS reaches median evaluations GA reaches")
for landscape_seed in range(1, LANDSCAPES + 1):
landscape = gx.problems.binary.NkLandscape(N, K, "random", seed=landscape_seed)
optimum = landscape.optimum.value
evaluations = []
ga_reached = 0
for seed in range(1, SEEDS + 1):
result = ils(landscape, seed).run(landscape, target=optimum, evaluations=BUDGET)
if result.stop_reason == "target":
evaluations.append(result.evaluations)
ga = gx.Ga(
landscape.genome,
population_size=500,
select=gx.Tournament(2),
crossover=gx.PointCrossover(2),
mutation=gx.BitFlip(rate=1 / N),
seed=seed,
)
result = ga.run(landscape, target=optimum, generations=GENERATIONS)
ga_reached += result.stop_reason == "target"
print(
f"{landscape_seed:>9} {optimum:.6f} {len(evaluations):>8}/{SEEDS} "
f"{median(evaluations):>18.1f} {ga_reached:>7}/{SEEDS}"
)
trace.write()
What it prints, from a seeded run:
NK landscape: N = 20, K = 4, random neighbors, drawn from seed 1
the optimum, over all 2^20 strings: 0.742541 at 10101011100001100010
iterated local search from seed 1
evaluations best
1 0.495078
3 0.543267
7 0.556021
8 0.617134
18 0.619018
20 0.625517
21 0.650122
31 0.691331
32 0.701480
46 0.723895
171 0.735152
907 0.736484
927 0.742541
0.742541 after 927 evaluations, at 10101011100001100010
landscape optimum ILS reaches median evaluations GA reaches
1 0.742541 20/20 1952.0 20/20
2 0.768337 20/20 2909.5 5/20
3 0.811498 20/20 3209.0 19/20
4 0.787638 20/20 1109.0 20/20
5 0.777704 20/20 4910.0 6/20