Royal road R1
The problem
R1 is a sum over 8 schemas, each a block of 8 consecutive bits that must all be ones, s₁ = 11111111∗∗…∗ to s₈ = ∗∗…∗11111111, each with the coefficient cᵢ = 8, its order (Mitchell, Holland and Forrest, 1994, Figure 1):
R1(x) = Σᵢ cᵢ δᵢ(x), δᵢ(x) = 1 if x is an instance of sᵢ, 0 otherwise
A string scores 8 for each complete block: a string with two complete blocks scores 16, and the
string of 64 ones, the optimum, 64. The function is genoxide's problems::binary::RoyalRoad::r1().
Its hierarchical sibling, R2, scores the blocks' combinations too.
What makes it hard
The royal road functions were designed to be easy for a genetic algorithm: crossover would combine complete blocks into strings with more of them, a "royal road" to the optimum, while a hill climber would have to set 8 bits at once to complete a block. Both expectations failed (Forrest and Mitchell, 1993, as summarized by Mitchell et al.). A block short of complete scores nothing, so a string's fitness says nothing about its 7 of 8 ones: the search drifts on plateaus. In a genetic algorithm, a string with a new block takes over the population, and the zeros next to the block hitchhike with it, slowing the discovery of the blocks beside it.
A hill climber that flips one bit at a time and keeps any change that's no worse drifts freely inside the incomplete blocks without losing the complete ones. Mitchell et al. analyze it: the expected time to find one block of K ones is slightly above 2ᴷ, 301.2 evaluations for K = 8, and to find N blocks about E(K, 1) N (1 + 1/2 + … + 1/N), 6,549 evaluations for R1 (their equation 1).
Representation
A Binary genome of 64 bits is the string itself. The fitness is R1, to maximize.
Algorithm
Random-mutation hill climbing (RMHC), Mitchell et al.'s: start from a random string, flip one bit
chosen at random, and keep the change if the string is no worse. In genoxide, that's LocalSearch
with BitFlip::count(1) as its neighbor, one neighbor per step, and the default acceptance of
neighbors that are no worse. A run from seed 1 stops at 64, or after 256,000 evaluations, the
paper's limit; then 200 runs, seeds 1 to 200, as in the paper's Table 1.
For comparison, a genetic algorithm with the paper's population of 128, single-point crossover at a rate of 0.7 and mutation of 0.005 per bit (Mitchell, Forrest and Holland, 1992), with tournament selection of size 2 in place of their fitness-proportionate selection with sigma scaling, from seeds 1 to 50 with the same limit.
Output
The first lines follow the run from seed 1: the evaluations at which it completes a block, its score rising by 8, and the evaluations to 64. Then two lines for the 200 runs of RMHC, how many reach 64 and the mean and median of their evaluations, with the paper's for comparison, and two for the 50 runs of the genetic algorithm. 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 string, its blocks filling with ones one after another.
Good results
The optimum is 64. The run from seed 1 reaches it after 10,101 evaluations, and every one of the 200 runs does, after 6,793 evaluations on average, with a median of 6,144. Mitchell et al.'s 200 runs took 6,179 on average (with a standard error of 186) and 5,775 at the median, against their expected 6,549. The genetic algorithm reaches 64 from all 50 seeds too, after 34,303 evaluations on average, five times as many as hill climbing; the paper's GA took 61,334 (and genoxide doesn't evaluate a child that is a copy of its parent again).
Known optimum: 64 (all ones)
Source: examples/royal_road_r1
Interactive run: tachsin.gr/projects/genoxide/examples/royal-road-r1
cargo run --release --example royal_road_r1
//! Royal road R1: maximize 8 blocks of 8 ones, each scoring only when complete, with
//! random-mutation hill climbing, which Mitchell, Holland and Forrest (1994) found faster on it
//! than their genetic algorithm.
//!
//! Random-mutation hill climbing (RMHC) flips one bit, chosen at random, and keeps the change if
//! it's no worse: genoxide's `LocalSearch` with `BitFlip::count(1)`. A run from seed 1 prints the
//! evaluations at which each block is completed; then 200 runs, as in the paper's Table 1, give
//! the mean and median evaluations to the optimum, 64. As a comparison, a genetic algorithm with
//! the paper's population, crossover and mutation (and tournament selection) from 50 seeds. The
//! function is genoxide's `problems::binary::RoyalRoad::r1`.
//!
//! 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_r1
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::RoyalRoad;
const BITS: usize = 64;
// the runs of RMHC, as in the paper's Table 1, and of the genetic algorithm
const RUNS: u64 = 200;
const GA_RUNS: u64 = 50;
// the most evaluations of a run, the paper's
const BUDGET: u64 = 256_000;
// random-mutation hill climbing from `seed`
fn rmhc(problem: &RoyalRoad, seed: u64) -> Result<LocalSearch<Binary, BitFlip>> {
LocalSearch::builder(problem.representation())
.neighbor(BitFlip::count(1)?)
.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::r1();
let optimum = problem.optimum().expect("known").value();
println!("Royal road R1: 8 blocks of 8 bits, maximum {optimum}");
println!("random-mutation hill climbing from seed 1");
println!("R1 evaluations");
// 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 = 0.0;
let outcome = Engine::new(rmhc(&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 evaluations at which a block is completed
if best > last {
println!("{best:>2} {:>11}", progress.evaluations());
last = best;
}
})
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"{} after {} evaluations",
outcome.best_fitness(),
outcome.evaluations()
);
// RMHC from seeds 1 to 200, and the genetic algorithm from seeds 1 to 50
let mut evaluations = Vec::new();
for seed in 1..=RUNS {
let outcome = Engine::new(rmhc(&problem, seed)?, 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!(
"\nRMHC, seeds 1 to {RUNS}: {reached} reach {optimum}; mean {mean:.0}, median {median:.0} \
evaluations"
);
println!(" (the paper's 200 runs: mean 6179, median 5775)");
let mut evaluations = Vec::new();
for seed in 1..=GA_RUNS {
let ga = 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()?;
let outcome = Engine::new(ga, 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!(
"GA, seeds 1 to {GA_RUNS}: {reached} reach {optimum}; mean {mean:.0}, median {median:.0} \
evaluations"
);
println!(" (the paper's GA, 200 runs: mean 61334, median 54208)");
trace.write();
Ok(())
}
python examples/royal_road_r1/main.py
"""Royal road R1: maximize 8 blocks of 8 ones, each scoring only when complete, with
random-mutation hill climbing, which Mitchell, Holland and Forrest (1994) found faster on it than
their genetic algorithm.
Random-mutation hill climbing (RMHC) flips one bit, chosen at random, and keeps the change if it's
no worse: genoxide's LocalSearch with BitFlip(count=1). A run from seed 1 prints the evaluations
at which each block is completed; then 200 runs, as in the paper's Table 1, give the mean and
median evaluations to the optimum, 64. As a comparison, a genetic algorithm with the paper's
population, crossover and mutation (and tournament selection) from 50 seeds. The function is
genoxide's problems.binary.RoyalRoad.r1(), 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_r1/main.py
"""
import genoxide as gx
from trace import Trace
BITS = 64
# the runs of RMHC, as in the paper's Table 1, and of the genetic algorithm
RUNS = 200
GA_RUNS = 50
# the most evaluations of a run, the paper's
BUDGET = 256_000
def rmhc(problem, seed):
"""Random-mutation hill climbing from ``seed``."""
return gx.LocalSearch(problem.genome, neighbor=gx.BitFlip(count=1), 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.r1()
optimum = problem.optimum.value
print(f"Royal road R1: 8 blocks of 8 bits, maximum {optimum:.0f}")
print("random-mutation hill climbing from seed 1")
print("R1 evaluations")
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(BITS, optimum)
last = 0.0
def progress(progress):
global last
best = progress.best_fitness or 0.0
# the evaluations at which a block is completed
if best > last:
print(f"{best:>2.0f} {progress.evaluations:>11}")
last = best
trace.record(progress)
result = rmhc(problem, 1).run(problem, target=optimum, evaluations=BUDGET, on_generation=progress)
print(f"{result.best_fitness:.0f} after {result.evaluations} evaluations")
# RMHC from seeds 1 to 200, and the genetic algorithm from seeds 1 to 50
evaluations = []
for seed in range(1, RUNS + 1):
result = rmhc(problem, seed).run(problem, target=optimum, evaluations=BUDGET)
if result.stop_reason == "target":
evaluations.append(result.evaluations)
mean, median = mean_and_median(evaluations)
print(
f"\nRMHC, seeds 1 to {RUNS}: {len(evaluations)} reach {optimum:.0f}; mean {mean:.0f}, "
f"median {median:.0f} evaluations"
)
print(" (the paper's 200 runs: mean 6179, median 5775)")
evaluations = []
for seed in range(1, GA_RUNS + 1):
ga = 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,
)
result = ga.run(problem, target=optimum, evaluations=BUDGET)
if result.stop_reason == "target":
evaluations.append(result.evaluations)
mean, median = mean_and_median(evaluations)
print(
f"GA, seeds 1 to {GA_RUNS}: {len(evaluations)} reach {optimum:.0f}; mean {mean:.0f}, "
f"median {median:.0f} evaluations"
)
print(" (the paper's GA, 200 runs: mean 61334, median 54208)")
trace.write()
What it prints, from a seeded run:
Royal road R1: 8 blocks of 8 bits, maximum 64
random-mutation hill climbing from seed 1
R1 evaluations
8 451
16 625
24 638
32 1615
40 1656
48 1837
56 3717
64 10101
64 after 10101 evaluations
RMHC, seeds 1 to 200: 200 reach 64; mean 6793, median 6144 evaluations
(the paper's 200 runs: mean 6179, median 5775)
GA, seeds 1 to 50: 50 reach 64; mean 34303, median 30996 evaluations
(the paper's GA, 200 runs: mean 61334, median 54208)