OneMax
The problem
OneMax scores a bit string by the number of its ones, Σ xᵢ: Droste, Jansen and Wegener (2002,
Definition 9) define it as the linear function whose weights are all 1. It has no single origin;
Ackley (1987, A Connectionist Machine for Genetic Hillclimbing, section 3.3.1) tested his genetic
hill climber on a "One Max" that scores ten times the number of ones. The string 10110010 scores 4.
Here the strings have 500 bits, so the best score is 500, for the string of all ones. The function
is genoxide's problems::binary::OneMax.
What makes it hard
Little, by design: it's the baseline that other problems are compared with. Each bit counts on its own, and the bits don't interact. Every string other than the optimum gains a one when a single zero flips, so there are no local optima. What the problem measures is how fast an algorithm climbs.
The slow part is the end. At a flip rate of 1/500 per bit, a mutation flips a given zero with probability 0.2%, and it can flip a one at the same time. For the (1+1) evolutionary algorithm, which keeps one string and flips each bit with probability 1/n, the expected number of evaluations is of the order of n log n (Droste et al., 2002, Lemma 10).
Representation
A Binary genome of 500 bits is the solution itself: there is nothing to decode. The fitness is the
genome's number of ones, to maximize.
Algorithm
A genetic algorithm with the pieces that genoxide's guide (AGENTS.md) lists for yes/no choices:
- a population of 100;
- tournament selection of size 3, within the guide's usual 2 to 5;
- uniform crossover, which takes each bit from either parent with probability 0.5, at genoxide's default crossover rate of 0.9;
- bit-flip mutation at a rate of 1/500 per bit, one flip per child on average;
- the default generational scheme, which keeps the best individual (elitism 1).
The bits don't interact, so there are no blocks of neighboring bits for a point crossover to keep together; uniform crossover mixes the parents' ones freely. The run stops at 500 ones, or after 10,000 generations.
Output
The first line is a table header. Each row gives a generation, every 50th, and the best count in the population. Generation 0 is the random population. A random string has 250 ones on average, give or take about 11, so the best of 100 has a little under 280. The count then climbs fast, and slows down as the last zeros get rare.
The last line gives the final count, the generations and the evaluations. The evaluations are fewer than 100 per generation: a child equal to its parent inherits its fitness and isn't evaluated again.
The project page plays this run back.
Good results
The optimum is 500 ones. The run reaches it after about 120 generations and 10,000 evaluations. Over seeds 1 to 100, every run reached it, after 106 generations at the median and at most 156.
Known optimum: 500 (all ones)
Source: examples/one_max
Interactive run: tachsin.gr/projects/genoxide/examples/one-max
cargo run --release --example one_max
//! OneMax: find the bit string with the most ones.
//!
//! The "hello world" of genetic algorithms: a binary genome, tournament selection, uniform
//! crossover and bit-flip mutation, with the best count printed every 50 generations. The function
//! is genoxide's `problems::binary::OneMax`.
//!
//! 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 one_max
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::OneMax;
const LEN: usize = 500;
fn main() -> Result<()> {
let problem = OneMax::new(LEN);
let optimum = problem.optimum().expect("known").value();
let ga = Ga::builder(problem.representation())
.population_size(100)
.select(Tournament::new(3)?)
.crossover(UniformCrossover::new())
.mutate(BitFlip::per_gene(1.0 / LEN as f64)?)
.seed(42)
.build()?;
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env();
println!("generation best");
let outcome = Engine::new(ga, problem)
.stop_when(Stop::target(optimum).or(Stop::generations(10_000)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
if progress.generation() % 50 == 0 {
let best = progress.best().unwrap_or(Fitness::invalid());
println!("{:>10} {best:>4}", progress.generation());
}
})
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"\n{} ones after {} generations and {} evaluations (the optimum: {LEN})",
outcome.best_fitness(),
outcome.generations(),
outcome.evaluations()
);
trace.write();
Ok(())
}
python examples/one_max/main.py
"""OneMax: find the bit string with the most ones.
The "hello world" of genetic algorithms: a binary genome, tournament selection, uniform crossover
and bit-flip mutation, with the best count printed every 50 generations. The function is
genoxide's problems.binary.OneMax, 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/one_max/main.py
"""
import genoxide as gx
from trace import Trace
LEN = 500
problem = gx.problems.binary.OneMax(LEN)
ga = gx.Ga(
problem.genome,
population_size=100,
select=gx.Tournament(3),
crossover=gx.UniformCrossover(),
mutation=gx.BitFlip(rate=1 / LEN),
seed=42,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(LEN)
def progress(progress):
if progress.generation % 50 == 0:
print(f"{progress.generation:>10} {progress.best_fitness:>4.0f}")
trace.record(progress)
print("generation best")
result = ga.run(
problem, target=problem.optimum.value, generations=10_000, on_generation=progress
)
print(
f"\n{result.best_fitness:.0f} ones after {result.generations} generations and "
f"{result.evaluations} evaluations (the optimum: {LEN})"
)
trace.write()
What it prints, from a seeded run:
generation best
0 274
50 476
100 498
500 ones after 120 generations and 10380 evaluations (the optimum: 500)