Deceptive trap
The problem
A trap function scores a block of k bits by its number of ones u (Deb and Goldberg, 1993, equation 1):
f(u) = a (z − u) / z for u ≤ z
b (u − z) / (k − z) otherwise
It falls from a at u = 0 to 0 at the slope change z, and rises to b > a at u = k. Ackley (1987, A
Connectionist Machine for Genetic Hillclimbing, section 3.3.3) introduced it with a = 8k, b = 10k
and z = ⌊3k/4⌋; Deb and Goldberg analyze any a, b and z. Here a = k − 1, b = k and z = k − 1, so a
block of k = 4 bits scores 3, 2, 1 and 0 for 0 to 3 ones, and 4 for all four. The string has 10
consecutive blocks, bits 0 to 3, 4 to 7 and so on, 40 bits, and scores the sum of its blocks: 40
at most, for the string of all ones, and 30 for the string of all zeros. The function is genoxide's
problems::binary::Trap::new(10, 4).
What makes it hard
Every step up within a block leads to all zeros, except the last one: from 3 ones, the fourth gives 4, and anything else less. A block with u ones below 4 gains by losing a one. Deb and Goldberg prove that a trap is fully deceptive (every schema of order below k, averaged over the strings it contains, favors the all-zeros block) if and only if all schemata of order k − 1 are (Theorem 1), and give the condition on r = a/b (inequality 16). With a = k − 1, b = k and z = k − 1, r = 3/4 is above their limit (k − 1)/(2k − 3) = 3/5 for k = 4 (eq. 20): the blocks are fully deceptive. genoxide's tests check this by averaging over every schema. A hill climber takes each block to its attractor, all zeros, unless the block starts with all ones, or with three and the missing bit is the first to flip.
The 10 blocks are independent, so a search that finds the optimum of each block, and keeps it, solves the whole. A genetic algorithm can, if crossover passes whole blocks from parent to child and selection keeps the complete ones; the blocks are tight, 4 adjacent bits, so a point crossover rarely cuts one.
Representation
A Binary genome of 40 bits is the string itself. The fitness is the sum of the blocks' values, to
maximize.
Algorithm
A genetic algorithm:
- a population of 1000, enough to hold several copies of each block's optimum from the start;
- tournament selection of size 4;
- two-point crossover, which cuts the string at two points: of the 39 places it can cut, 9 are between blocks, and a cut elsewhere breaks one block;
- bit-flip mutation at a rate of 1/40 per bit;
- the default generational scheme, which keeps the best individual.
A run from seed 1 stops at 40, or after 300 generations; then runs from seeds 1 to 20. Two
contrasts run from the same seeds: the same GA with uniform crossover, which takes each bit from
either parent and so breaks the blocks apart, and hill climbing, LocalSearch flipping one bit at a
time and keeping the change if it's no worse, for 10,000 evaluations.
Output
The table follows the run from seed 1: each generation's best score, its population's median score and the blocks of the best string that are all ones. Then the generation and evaluations at which it reaches 40. The last three lines give the runs from seeds 1 to 20: how many reach 40 with two-point crossover and after how many generations (the median), how many with uniform crossover and the median number of blocks of ones they end with, and hill climbing's median best and blocks of ones. 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, blocks of ones spreading through them.
Good results
The optimum is 40. The run from seed 1 reaches it at generation 15, after 14,687 evaluations, and so do all 20 runs from seeds 1 to 20, after a median of 15 generations. Over seeds 1 to 300, every run reached it, within 95 generations.
The contrasts don't. Uniform crossover reaches it from none of the 20 seeds in 300 generations: its runs end with a median of 3 blocks of ones of the 10. Hill climbing ends at a median of 31: one block of ones and nine at the deceptive attractor, 3 each.
Known optimum: 40 (all ones)
Source: examples/deceptive_trap
Interactive run: tachsin.gr/projects/genoxide/examples/deceptive-trap
cargo run --release --example deceptive_trap
//! Deceptive trap: maximize 10 blocks of Deb and Goldberg's trap function of 4 bits, which leads
//! each block away from its optimum, with a genetic algorithm whose two-point crossover keeps
//! the blocks together.
//!
//! A block of 4 bits scores 3 − u for u ones below 4, and 4 with all of them: fully deceptive,
//! every schema of order below 4 favoring all zeros. A run from seed 1 prints each generation;
//! then runs from seeds 1 to 20 count how often the GA reaches the optimum, 40. As contrasts: the
//! same GA with uniform crossover, which breaks the blocks apart, and hill climbing, one bit at a
//! time, which climbs to the deceptive attractor. The function is genoxide's
//! `problems::binary::Trap`.
//!
//! 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 deceptive_trap
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::Trap;
const BLOCKS: usize = 10;
const K: usize = 4;
const BITS: usize = BLOCKS * K;
const SEEDS: u64 = 20;
const GENERATIONS: u64 = 300;
// the evaluations of a hill climb
const CLIMB: u64 = 10_000;
// the genetic algorithm with `crossover`, from `seed`
fn ga<C: Crossover<Binary>>(
problem: &Trap,
crossover: C,
seed: u64,
) -> Result<Ga<Binary, Tournament, C, BitFlip>> {
Ga::builder(problem.representation())
.population_size(1000)
.select(Tournament::new(4)?)
.crossover(crossover)
.mutate(BitFlip::per_gene(1.0 / BITS as f64)?)
.seed(seed)
.build()
}
// the blocks of `genome` that are all ones
fn blocks_of_ones(genome: &Bits) -> usize {
(0..BLOCKS)
.filter(|block| (block * K..(block + 1) * K).all(|i| genome.get(i) == Some(true)))
.count()
}
// 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 problem = Trap::new(BLOCKS, K);
let optimum = problem.optimum().expect("known").value();
println!("Deceptive trap: {BLOCKS} blocks of {K} bits, maximum {optimum}");
println!("a GA with two-point crossover, from seed 1");
println!("generation best median blocks of ones in the 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 outcome = Engine::new(ga(&problem, PointCrossover::two_point(), 1)?, problem)
.stop_when(Stop::target(optimum).or(Stop::generations(GENERATIONS)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
let scores = snapshot.population().iter();
let scores = scores.filter_map(|individual| individual.fitness()?.score());
println!(
"{:>10} {:>4} {:>6} {:>2}",
progress.generation(),
snapshot
.best()
.fitness()
.and_then(Fitness::score)
.unwrap_or(0.0),
median(scores.collect()),
blocks_of_ones(snapshot.best().genome())
);
})
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"{} after {} generations and {} evaluations",
outcome.best_fitness(),
outcome.generations(),
outcome.evaluations()
);
// two-point crossover from seeds 1 to 20, and uniform crossover as a contrast
let mut reached = Vec::new();
for seed in 1..=SEEDS {
let outcome = Engine::new(ga(&problem, PointCrossover::two_point(), seed)?, problem)
.stop_when(Stop::target(optimum).or(Stop::generations(GENERATIONS)))
.run()?;
if outcome.stop_reason() == StopReason::Target {
reached.push(outcome.generations() as f64);
}
}
println!(
"\nseeds 1 to {SEEDS}, two-point crossover: {} of {SEEDS} reach {optimum}, after a median \
of {:.1} generations",
reached.len(),
median(reached)
);
let (mut uniform, mut bests) = (0, Vec::new());
for seed in 1..=SEEDS {
let outcome = Engine::new(ga(&problem, UniformCrossover::new(), seed)?, problem)
.stop_when(Stop::target(optimum).or(Stop::generations(GENERATIONS)))
.run()?;
uniform += usize::from(outcome.stop_reason() == StopReason::Target);
bests.push(blocks_of_ones(outcome.best_genome()) as f64);
}
println!(
"contrast, uniform crossover: {uniform} of {SEEDS} reach it in {GENERATIONS} generations; \
a median of {:.1} blocks of ones",
median(bests)
);
// hill climbing: one bit flipped at a time, kept if no worse
let (mut scores, mut blocks) = (Vec::new(), Vec::new());
for seed in 1..=SEEDS {
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(CLIMB)))
.run()?;
scores.push(outcome.best_fitness().score().expect("valid"));
blocks.push(blocks_of_ones(outcome.best_genome()) as f64);
}
println!(
"contrast, hill climbing ({CLIMB} evaluations): a median best of {:.1}, with {:.1} \
blocks of ones",
median(scores),
median(blocks)
);
trace.write();
Ok(())
}
python examples/deceptive_trap/main.py
"""Deceptive trap: maximize 10 blocks of Deb and Goldberg's trap function of 4 bits, which leads
each block away from its optimum, with a genetic algorithm whose two-point crossover keeps the
blocks together.
A block of 4 bits scores 3 − u for u ones below 4, and 4 with all of them: fully deceptive, every
schema of order below 4 favoring all zeros. A run from seed 1 prints each generation; then runs
from seeds 1 to 20 count how often the GA reaches the optimum, 40. As contrasts: the same GA with
uniform crossover, which breaks the blocks apart, and hill climbing, one bit at a time, which
climbs to the deceptive attractor. The function is genoxide's problems.binary.Trap, 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/deceptive_trap/main.py
"""
import genoxide as gx
from trace import Trace
BLOCKS = 10
K = 4
BITS = BLOCKS * K
SEEDS = 20
GENERATIONS = 300
# the evaluations of a hill climb
CLIMB = 10_000
def ga(problem, crossover, seed):
"""The genetic algorithm with ``crossover``, from ``seed``."""
return gx.Ga(
problem.genome,
population_size=1000,
select=gx.Tournament(4),
crossover=crossover,
mutation=gx.BitFlip(rate=1 / BITS),
seed=seed,
)
def blocks_of_ones(genome):
"""The blocks of ``genome`` that are all ones."""
return sum(all(genome[block * K : (block + 1) * K]) for block in range(BLOCKS))
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
problem = gx.problems.binary.Trap(BLOCKS, K)
optimum = problem.optimum.value
print(f"Deceptive trap: {BLOCKS} blocks of {K} bits, maximum {optimum:.0f}")
print("a GA with two-point crossover, from seed 1")
print("generation best median blocks of ones in the best")
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(BITS, optimum)
def progress(progress):
print(
f"{progress.generation:>10} {progress.best_fitness:>4.0f} "
f"{median(progress.scores):>6g} {blocks_of_ones(progress.best_genome):>2}"
)
trace.record(progress)
result = ga(problem, gx.PointCrossover(2), 1).run(
problem, target=optimum, generations=GENERATIONS, on_generation=progress
)
print(
f"{result.best_fitness:.0f} after {result.generations} generations and "
f"{result.evaluations} evaluations"
)
# two-point crossover from seeds 1 to 20, and uniform crossover as a contrast
reached = []
for seed in range(1, SEEDS + 1):
result = ga(problem, gx.PointCrossover(2), seed).run(
problem, target=optimum, generations=GENERATIONS
)
if result.stop_reason == "target":
reached.append(result.generations)
print(
f"\nseeds 1 to {SEEDS}, two-point crossover: {len(reached)} of {SEEDS} reach {optimum:.0f}, "
f"after a median of {median(reached):.1f} generations"
)
uniform, bests = 0, []
for seed in range(1, SEEDS + 1):
result = ga(problem, gx.UniformCrossover(), seed).run(
problem, target=optimum, generations=GENERATIONS
)
uniform += result.stop_reason == "target"
bests.append(blocks_of_ones(result.best_genome))
print(
f"contrast, uniform crossover: {uniform} of {SEEDS} reach it in {GENERATIONS} generations; "
f"a median of {median(bests):.1f} blocks of ones"
)
# hill climbing: one bit flipped at a time, kept if no worse
scores, blocks = [], []
for seed in range(1, SEEDS + 1):
search = gx.LocalSearch(problem.genome, neighbor=gx.BitFlip(count=1), seed=seed)
result = search.run(problem, target=optimum, evaluations=CLIMB)
scores.append(result.best_fitness)
blocks.append(blocks_of_ones(result.best_genome))
print(
f"contrast, hill climbing ({CLIMB} evaluations): a median best of {median(scores):.1f}, "
f"with {median(blocks):.1f} blocks of ones"
)
trace.write()
What it prints, from a seeded run:
Deceptive trap: 10 blocks of 4 bits, maximum 40
a GA with two-point crossover, from seed 1
generation best median blocks of ones in the best
0 23 13 2
1 30 16 4
2 30 19 4
3 34 20 7
4 34 22 7
5 34 24 7
6 34 25 7
7 36 25 7
8 36 26 7
9 38 27 8
10 38 28 8
11 38 28 8
12 38 29 8
13 38 30 8
14 39 30 9
15 40 31 10
40 after 15 generations and 14687 evaluations
seeds 1 to 20, two-point crossover: 20 of 20 reach 40, after a median of 15.0 generations
contrast, uniform crossover: 0 of 20 reach it in 300 generations; a median of 3.0 blocks of ones
contrast, hill climbing (10000 evaluations): a median best of 31.0, with 1.0 blocks of ones