LeadingOnes
The problem
LeadingOnes counts the ones of a bit string before its first zero:
LeadingOnes(x) = Σᵢ₌₁ⁿ Πⱼ₌₁ⁱ xⱼ
The string 1101 0111 scores 2. Here the strings have 100 bits, so the best score is 100, for the
string of all ones. The definition is Droste, Jansen and Wegener's (2002, Definition 16), who took
the function from Rudolph's book (1997, Convergence Properties of Evolutionary Algorithms, Kovač,
Hamburg, not read). The function is genoxide's problems::binary::LeadingOnes.
What makes it hard
The landscape is unimodal: appending a one to the leading ones always improves a string, so there are no local optima. But only one bit can improve a string, the first zero, and nothing before it may change. The bits after it don't count, and drift at random until the leading ones reach them.
Droste et al. used the function to disprove a remark, which they attribute to Mühlenbein, that every unimodal function takes the (1+1) evolutionary algorithm O(n log n) steps, as OneMax does. Their Theorem 17 proves that LeadingOnes takes Θ(n²) steps on average: at most e n² (27,183 for n = 100), and at least n²/6 (1,667) except with a probability exponentially small in n.
Representation
A Binary genome of 100 bits is the string itself. The fitness is its number of leading ones, to
maximize.
Algorithm
The (1+1) evolutionary algorithm of Droste et al.: one string, each of whose bits is flipped with
probability 1/n, the child replacing it if it's no worse. In genoxide, that's LocalSearch with
bit-flip mutation at a rate of 1/100 as its neighbor, one neighbor per step, and the default
acceptance of neighbors that are no worse.
LocalSearch draws a neighbor again when the mutation flips nothing, so each evaluation is a step
of the (1+1) EA that changes the string. A step of the (1+1) EA flips nothing with probability
(1 − 1/n)ⁿ = 0.366 for n = 100, and such steps don't change the string, so the search is the
(1+1) EA's, without its idle steps: the (1+1) EA takes on average 1 / 0.634 times as many steps
as there are evaluations here.
A run from seed 1 stops at the optimum, or after 1,000,000 evaluations. Then runs from seeds 1 to 100 count the evaluations to the optimum.
Output
The first lines give the run from seed 1: the evaluations at which the leading ones first reach 10, 20, … 100, and the evaluations to the optimum. The last two lines give the runs from seeds 1 to 100: how many reach the optimum, the mean of their evaluations, the fewest, the median and the most, and n² for comparison. 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 leading ones growing from the left while the bits after them change at random.
Good results
The optimum is 100. The run from seed 1 reaches it after 4,452 evaluations. Every run from seeds 1 to 100 reaches it, after 5,332 evaluations on average, from 3,503 to 7,802, with a median of 5,312.5. Counted with its idle steps, the (1+1) EA takes about 5,332 / 0.634 ≈ 8,410 steps on average, between Droste et al.'s n²/6 and e n².
Known optimum: 100 (all ones)
Source: examples/leading_ones
Interactive run: tachsin.gr/projects/genoxide/examples/leading-ones
cargo run --release --example leading_ones
//! LeadingOnes: maximize the number of ones before the first zero of a string of 100 bits, with
//! the (1+1) evolutionary algorithm.
//!
//! The (1+1) EA keeps one string, flips each of its bits with probability 1/n and keeps the child
//! if it's no worse: genoxide's `LocalSearch` with `BitFlip::per_gene(1/n)` as its neighbor. A run
//! from seed 1 prints the evaluations at which the leading ones reach 10, 20, … 100; then runs
//! from seeds 1 to 100 give the evaluations to the optimum, which Droste, Jansen and Wegener
//! (2002) proved to be Θ(n²). The function is genoxide's `problems::binary::LeadingOnes`.
//!
//! 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 leading_ones
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::LeadingOnes;
const BITS: usize = 100;
const SEEDS: u64 = 100;
// the most evaluations of a run
const BUDGET: u64 = 1_000_000;
// the (1+1) evolutionary algorithm from `seed`
fn one_plus_one(problem: &LeadingOnes, seed: u64) -> Result<LocalSearch<Binary, BitFlip>> {
LocalSearch::builder(problem.representation())
.neighbor(BitFlip::per_gene(1.0 / BITS as f64)?)
.seed(seed)
.build()
}
fn main() -> Result<()> {
let problem = LeadingOnes::new(BITS);
let optimum = problem.optimum().expect("known").value();
println!("LeadingOnes of {BITS} bits, the (1+1) EA from seed 1");
println!("leading ones 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 next = 10.0;
let outcome = Engine::new(one_plus_one(&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 the leading ones first reach each tenth of the string
while best >= next {
println!("{next:>12.0} {:>11}", progress.evaluations());
next += 10.0;
}
})
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"{} leading ones after {} evaluations (the optimum: {BITS})",
outcome.best_fitness(),
outcome.evaluations()
);
// the evaluations to the optimum from seeds 1 to 100
let mut evaluations = Vec::new();
for seed in 1..=SEEDS {
let outcome = Engine::new(one_plus_one(&problem, seed)?, problem)
.stop_when(Stop::target(optimum).or(Stop::evaluations(BUDGET)))
.run()?;
if outcome.stop_reason() == StopReason::Target {
evaluations.push(outcome.evaluations());
}
}
evaluations.sort_unstable();
let count = evaluations.len();
let mean = evaluations.iter().sum::<u64>() as f64 / count as f64;
let median = if count % 2 == 1 {
evaluations[count / 2] as f64
} else {
(evaluations[count / 2 - 1] + evaluations[count / 2]) as f64 / 2.0
};
println!(
"\nseeds 1 to {SEEDS}: {count} reach the optimum, after {mean:.0} evaluations on average"
);
println!(
"(fewest {}, median {median:.1}, most {}); n² = {}",
evaluations[0],
evaluations[count - 1],
BITS * BITS
);
trace.write();
Ok(())
}
python examples/leading_ones/main.py
"""LeadingOnes: maximize the number of ones before the first zero of a string of 100 bits, with
the (1+1) evolutionary algorithm.
The (1+1) EA keeps one string, flips each of its bits with probability 1/n and keeps the child if
it's no worse: genoxide's LocalSearch with BitFlip(rate=1/n) as its neighbor. A run from seed 1
prints the evaluations at which the leading ones reach 10, 20, … 100; then runs from seeds 1 to
100 give the evaluations to the optimum, which Droste, Jansen and Wegener (2002) proved to be
Θ(n²). The function is genoxide's problems.binary.LeadingOnes, 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/leading_ones/main.py
"""
import genoxide as gx
from trace import Trace
BITS = 100
SEEDS = 100
# the most evaluations of a run
BUDGET = 1_000_000
def one_plus_one(problem, seed):
"""The (1+1) evolutionary algorithm from ``seed``."""
return gx.LocalSearch(problem.genome, neighbor=gx.BitFlip(rate=1 / BITS), seed=seed)
problem = gx.problems.binary.LeadingOnes(BITS)
optimum = problem.optimum.value
print(f"LeadingOnes of {BITS} bits, the (1+1) EA from seed 1")
print("leading ones evaluations")
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(BITS, optimum)
next_tenth = 10
def progress(progress):
global next_tenth
best = progress.best_fitness or 0.0
# the evaluations at which the leading ones first reach each tenth of the string
while best >= next_tenth:
print(f"{next_tenth:>12} {progress.evaluations:>11}")
next_tenth += 10
trace.record(progress)
result = one_plus_one(problem, 1).run(
problem, target=optimum, evaluations=BUDGET, on_generation=progress
)
print(
f"{result.best_fitness:.0f} leading ones after {result.evaluations} evaluations "
f"(the optimum: {BITS})"
)
# the evaluations to the optimum from seeds 1 to 100
evaluations = []
for seed in range(1, SEEDS + 1):
result = one_plus_one(problem, seed).run(problem, target=optimum, evaluations=BUDGET)
if result.stop_reason == "target":
evaluations.append(result.evaluations)
evaluations.sort()
count = len(evaluations)
mean = sum(evaluations) / count
if count % 2:
median = float(evaluations[count // 2])
else:
median = (evaluations[count // 2 - 1] + evaluations[count // 2]) / 2
print(f"\nseeds 1 to {SEEDS}: {count} reach the optimum, after {mean:.0f} evaluations on average")
print(f"(fewest {evaluations[0]}, median {median:.1f}, most {evaluations[-1]}); n² = {BITS * BITS}")
trace.write()
What it prints, from a seeded run:
LeadingOnes of 100 bits, the (1+1) EA from seed 1
leading ones evaluations
10 291
20 414
30 947
40 1332
50 1927
60 2102
70 3313
80 3525
90 3952
100 4452
100 leading ones after 4452 evaluations (the optimum: 100)
seeds 1 to 100: 100 reach the optimum, after 5332 evaluations on average
(fewest 3503, median 5312.5, most 7802); n² = 10000