Royal road R2
The problem
R2 is the royal road function of Mitchell, Forrest and Holland's (1992) Figure 1, which Forrest and Mitchell later called R2. It's a sum over 15 schemas s, each scoring its order, its number of defined bits, c_s = order(s), when a string is an instance of it:
F(x) = Σₛ c_s σ_s(x), σ_s(x) = 1 if x is an instance of s, 0 otherwise
The schemas form a tree over 64 bits: 8 blocks of 8 consecutive ones (c = 8), the 4 pairs of
adjacent blocks, 16 ones each (c = 16), the 2 halves of 32 ones (c = 32) and the whole string
(c = 64). The string of all ones is an instance of all 15 and scores 8 · 8 + 4 · 16 + 2 · 32 + 64
= 256. A string whose first 16 bits are ones scores 8 + 8 + 16 = 32. The function is genoxide's
problems::binary::RoyalRoad::r2(); R1 is its lowest level alone.
What makes it hard
The intermediate schemas were meant as stepping stones: a genetic algorithm would combine two complete blocks into a pair, two pairs into a half, and climb the tree by crossover. A hill climber gains nothing from them: a step that doesn't complete or break a block changes neither R1 nor R2, so a climber that keeps changes that are no worse takes the same steps on both. The difficulty is R1's: a block short of complete scores nothing, and a string that completes one spreads through the population, its zeros elsewhere hitchhiking with it.
Mitchell et al. ran their genetic algorithm 50 times: it found the optimum after 590 generations on average (with a standard error of 50), 542 at the median, and 1,022 without crossover (their Table 1). Their iterated hill climber never found it in 256,000 evaluations; later, Mitchell, Holland and Forrest (1994) found random-mutation hill climbing faster than the GA on R1.
Representation
A Binary genome of 64 bits is the string itself. The fitness is R2, to maximize.
Algorithm
A genetic algorithm with Mitchell et al.'s settings:
- a population of 128;
- tournament selection of size 2, in place of their fitness-proportionate selection with sigma scaling (at most 1.5 expected offspring), which genoxide doesn't have;
- single-point crossover at a rate of 0.7 per pair of parents;
- bit-flip mutation with probability 0.005 per bit;
- the default generational scheme, which keeps the best individual.
A run from seed 1 stops at 256, or after 256,000 evaluations, the paper's 2,000 generations of 128;
then runs from seeds 1 to 50, as in the paper. For comparison, random-mutation hill climbing
(LocalSearch flipping one bit at a time and keeping the change if it's no worse) from seeds 1 to
200, as on R1.
Output
The table follows the run from seed 1: the generations at which its best score improves. Then the generations and evaluations at which it reaches 256. The last three lines give the 50 runs of the GA, how many reach 256 and the mean and median of their generations, with the paper's for comparison, and the 200 runs of hill climbing, with their evaluations. The function is evaluated in Rust in both languages, so both print the same.
The project page plays back the run from seed 1: the first 16 strings of the population, as blocks of ones complete and spread.
Good results
The optimum is 256. The run from seed 1 reaches it at generation 69, and all 50 runs from seeds 1 to 50 do, after 661 generations on average and 478 at the median, close to the paper's 590 and 542. Over seeds 1 to 300, every run reached it within 256,000 evaluations, after 27,296 at the median (genoxide doesn't evaluate a child that is a copy of its parent again). Random-mutation hill climbing reaches it in all 200 runs after 6,793 evaluations on average and 6,144 at the median, the same as on R1, step for step: on R2 too, it needs about a quarter of the GA's evaluations.
Known optimum: 256 (all ones)
Source: examples/royal_road_r2
Interactive run: tachsin.gr/projects/genoxide/examples/royal-road-r2
cargo run --release --example royal_road_r2
//! Royal road R2: maximize 8 blocks of 8 ones, and the pairs, quadruples and whole string above
//! them, each scoring its number of bits when complete, with a genetic algorithm with the
//! settings of Mitchell, Forrest and Holland (1992).
//!
//! The GA has their population of 128, single-point crossover at a rate of 0.7 and a mutation
//! probability of 0.005 per bit, with tournament selection of size 2 in place of their
//! fitness-proportionate selection with sigma scaling. A run from seed 1 prints the generations at
//! which its best improves; then runs from seeds 1 to 50, as in their Table 1, give the
//! generations to the optimum, 256. As a comparison, random-mutation hill climbing, one bit at a time. The function
//! is genoxide's `problems::binary::RoyalRoad::r2`.
//!
//! 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 royal_road_r2
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::RoyalRoad;
const BITS: usize = 64;
// the runs of the GA, as in the paper's Table 1, and of hill climbing
const RUNS: u64 = 50;
const CLIMBS: u64 = 200;
// the most evaluations of a run, the paper's 2000 generations of 128
const BUDGET: u64 = 256_000;
// the genetic algorithm from `seed`
fn ga(problem: &RoyalRoad, seed: u64) -> Result<Ga<Binary, Tournament, PointCrossover, BitFlip>> {
Ga::builder(problem.representation())
.population_size(128)
.select(Tournament::new(2)?)
.crossover(PointCrossover::one_point())
.crossover_rate(0.7)
.mutate(BitFlip::per_gene(0.005)?)
.seed(seed)
.build()
}
// the mean and the median of `values`
fn mean_and_median(mut values: Vec<f64>) -> (f64, f64) {
values.sort_by(f64::total_cmp);
let middle = values.len() / 2;
let median = if values.len() % 2 == 1 {
values[middle]
} else {
(values[middle - 1] + values[middle]) / 2.0
};
(values.iter().sum::<f64>() / values.len() as f64, median)
}
fn main() -> Result<()> {
let problem = RoyalRoad::r2();
let optimum = problem.optimum().expect("known").value();
println!("Royal road R2: 8 blocks of 8 bits and the levels above, maximum {optimum}");
println!("a GA with single-point crossover, from seed 1");
println!("generation 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(BITS, optimum);
let mut last = -1.0;
let outcome = Engine::new(ga(&problem, 1)?, problem)
.stop_when(Stop::target(optimum).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
let best = progress.best().and_then(Fitness::score).unwrap_or(0.0);
// the generations at which the best improves
if best > last {
println!("{:>10} {best:>4}", progress.generation());
last = best;
}
})
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"{} after {} generations and {} evaluations",
outcome.best_fitness(),
outcome.generations(),
outcome.evaluations()
);
// the GA from seeds 1 to 50, and hill climbing from seeds 1 to 200
let mut generations = Vec::new();
for seed in 1..=RUNS {
let outcome = Engine::new(ga(&problem, seed)?, problem)
.stop_when(Stop::target(optimum).or(Stop::evaluations(BUDGET)))
.run()?;
if outcome.stop_reason() == StopReason::Target {
generations.push(outcome.generations() as f64);
}
}
let reached = generations.len();
let (mean, median) = mean_and_median(generations);
println!(
"\nGA, seeds 1 to {RUNS}: {reached} reach {optimum}; mean {mean:.0}, median {median:.0} \
generations"
);
println!(" (the paper's GA, 50 runs: mean 590, median 542)");
let mut evaluations = Vec::new();
for seed in 1..=CLIMBS {
let search = LocalSearch::builder(problem.representation())
.neighbor(BitFlip::count(1)?)
.seed(seed)
.build()?;
let outcome = Engine::new(search, problem)
.stop_when(Stop::target(optimum).or(Stop::evaluations(BUDGET)))
.run()?;
if outcome.stop_reason() == StopReason::Target {
evaluations.push(outcome.evaluations() as f64);
}
}
let reached = evaluations.len();
let (mean, median) = mean_and_median(evaluations);
println!(
"hill climbing, seeds 1 to {CLIMBS}: {reached} reach {optimum}; mean {mean:.0}, median \
{median:.0} evaluations"
);
trace.write();
Ok(())
}
python examples/royal_road_r2/main.py
"""Royal road R2: maximize 8 blocks of 8 ones, and the pairs, quadruples and whole string above
them, each scoring its number of bits when complete, with a genetic algorithm with the settings
of Mitchell, Forrest and Holland (1992).
The GA has their population of 128, single-point crossover at a rate of 0.7 and a mutation
probability of 0.005 per bit, with tournament selection of size 2 in place of their
fitness-proportionate selection with sigma scaling. A run from seed 1 prints the generations at
which its best improves; then runs from seeds 1 to 50, as in their Table 1, give the generations
to the optimum, 256. As a comparison, random-mutation hill climbing, one bit at a time. The
function is genoxide's problems.binary.RoyalRoad.r2(), which run evaluates in Rust.
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/royal_road_r2/main.py
"""
import genoxide as gx
from trace import Trace
BITS = 64
# the runs of the GA, as in the paper's Table 1, and of hill climbing
RUNS = 50
CLIMBS = 200
# the most evaluations of a run, the paper's 2000 generations of 128
BUDGET = 256_000
def ga(problem, seed):
"""The genetic algorithm from ``seed``."""
return gx.Ga(
problem.genome,
population_size=128,
select=gx.Tournament(2),
crossover=gx.PointCrossover(1),
crossover_rate=0.7,
mutation=gx.BitFlip(rate=0.005),
seed=seed,
)
def mean_and_median(values):
"""The mean and the median of ``values``."""
values = sorted(values)
middle = len(values) // 2
median = values[middle] if len(values) % 2 else (values[middle - 1] + values[middle]) / 2
return sum(values) / len(values), median
problem = gx.problems.binary.RoyalRoad.r2()
optimum = problem.optimum.value
print(f"Royal road R2: 8 blocks of 8 bits and the levels above, maximum {optimum:.0f}")
print("a GA with single-point crossover, from seed 1")
print("generation best")
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(BITS, optimum)
last = -1.0
def progress(progress):
global last
best = progress.best_fitness or 0.0
# the generations at which the best improves
if best > last:
print(f"{progress.generation:>10} {best:>4.0f}")
last = best
trace.record(progress)
result = ga(problem, 1).run(problem, target=optimum, evaluations=BUDGET, on_generation=progress)
print(
f"{result.best_fitness:.0f} after {result.generations} generations and "
f"{result.evaluations} evaluations"
)
# the GA from seeds 1 to 50, and hill climbing from seeds 1 to 200
generations = []
for seed in range(1, RUNS + 1):
result = ga(problem, seed).run(problem, target=optimum, evaluations=BUDGET)
if result.stop_reason == "target":
generations.append(result.generations)
mean, median = mean_and_median(generations)
print(
f"\nGA, seeds 1 to {RUNS}: {len(generations)} reach {optimum:.0f}; mean {mean:.0f}, "
f"median {median:.0f} generations"
)
print(" (the paper's GA, 50 runs: mean 590, median 542)")
evaluations = []
for seed in range(1, CLIMBS + 1):
search = gx.LocalSearch(problem.genome, neighbor=gx.BitFlip(count=1), seed=seed)
result = search.run(problem, target=optimum, evaluations=BUDGET)
if result.stop_reason == "target":
evaluations.append(result.evaluations)
mean, median = mean_and_median(evaluations)
print(
f"hill climbing, seeds 1 to {CLIMBS}: {len(evaluations)} reach {optimum:.0f}; "
f"mean {mean:.0f}, median {median:.0f} evaluations"
)
trace.write()
What it prints, from a seeded run:
Royal road R2: 8 blocks of 8 bits and the levels above, maximum 256
a GA with single-point crossover, from seed 1
generation best
0 16
6 40
10 48
12 64
20 72
26 80
52 136
69 256
256 after 69 generations and 4767 evaluations
GA, seeds 1 to 50: 50 reach 256; mean 661, median 478 generations
(the paper's GA, 50 runs: mean 590, median 542)
hill climbing, seeds 1 to 200: 200 reach 256; mean 6793, median 6144 evaluations