Koza's 11-multiplexer
The problem
A multiplexer has address bits and data bits, and outputs the data bit that the address selects. The 11-multiplexer has 3 address bits, a0 to a2, and 8 data bits, d0 to d7: with a2 a1 a0 = 110, the output is d6. Given only its truth table, the 2048 combinations of the 11 inputs with the right output for each, the task is to find a Boolean function that computes it.
Koza (1992) used it to show that genetic programming finds programs for problems whose solution has a hierarchical structure: the 11-multiplexer is 7 conditionals, a decision on a2 over decisions on a1 over decisions on a0. With 4000 programs and at most 51 generations, his run found a correct one in generation 9. The critique of GP benchmarks (McDermott et al. 2012, Genetic programming needs better benchmarks, GECCO 2012: 791-798) lists it among the overused problems; it stays GP's classic Boolean test, with an exact optimum.
The Python version runs the same search with gx.gp, the problem itself as the fitness
function, evaluated in Rust (gx.gp.boolean.Multiplexer(3)): it prints the same output and
writes the same trace.
What makes it hard
The search sees only how many of the 2048 cases a program gets right. A program that returns one data bit is right in 1152 cases: the 256 where that bit is selected, and half the others. Building on that needs the address bits combined in the right way, and a program that gets 1536 cases right can be far from one that gets them all. Programs also grow: the parts that don't change the output pile up (bloat), and the search slows down as they do.
Representation
A tree of a genetic program (gp::Tree) of Koza's primitives, from gp::boolean::Multiplexer:
the functions and, or, not and if (if(a, b, c) is b when a is true, else c), and the 11 inputs as
terminals. One type, Boolean. gp::Gp sets Koza's limits and initialization: depth at most 17 and
at most 1024 nodes, and ramped half-and-half with depths 2 to 6, the initial population divided
evenly among the depths and the two methods without duplicates (Gp::ramped_half_and_half).
The fitness is the number of cases a tree gets wrong, Koza's standardized fitness, minimized: 0 is the optimum. Trees are evaluated on 64 cases at once, a bit per case in a 64-bit word, so all 2048 cases take 32 passes over the tree.
Algorithm
A genetic algorithm of 4000 trees, Koza's population size. Parents are chosen by double tournament
(Luke and Panait 2002): the winners of two tournaments of 7 on fitness meet in a tournament of
size, where the smaller wins with probability 0.7 (D = 1.4, the setting Luke and Panait (2006)
found best), which holds bloat back. Subtree crossover at a rate of 0.9 (Koza's, points at
function nodes 90% of the time, within the limits) and, at a rate of 0.1, one of four mutations
(gp::Mutations): subtree (weight 0.5), point (0.3), hoist (0.1) and shrink (0.1). The run stops
when every case is right, or after 50 generations, the 51 of Koza's runs with the initial one.
Output
The first two lines give the problem and the setting. Then come how the run stopped, after how many
generations and evaluations, how many cases the best tree gets right, and the tree itself, with its
size and depth, written as genoxide writes trees (Tree::display).
The project page plays this run back.
Good results
The optimum is a function right in all 2048 cases. The run of output.txt found one after 15
generations and 51,907 evaluations, in 40 nodes. Read from the root, it tests a0, then a1 and a2,
and returns the selected data bit; some of its tests repeat one made above them, which is how
evolved programs look before they're simplified.
Over seeds 1 to 100 (the seed of the algorithm and of the initial population), all 100 runs found a correct function within 50 generations: after 14 generations and 49,675 evaluations in the median, and 21 generations at most. The functions found had 57 nodes in the median and 152 at most.
Without the pressure on size (D = 1, so the size tournament is a coin toss and the selection a tournament of 7 on fitness), 91 of the 100 runs found one within 50 generations, after 19 generations in the median, and the functions found had 148 nodes in the median and 782 at most.
Known optimum: All 2048 cases right
Source: examples/multiplexer_11
Interactive run: tachsin.gr/projects/genoxide/examples/multiplexer-11
cargo run --release --example multiplexer_11
//! Koza's 11-multiplexer: find the Boolean function that uses 3 address bits to select one of 8
//! data bits, from all 2048 cases of its truth table, by genetic programming.
//!
//! Trees of Koza's functions (and, or, not, if) and the 11 inputs, evolved by a genetic
//! algorithm with subtree crossover and a mix of mutations, and double tournaments against
//! bloat. The fitness is the number of the 2048 cases a tree gets wrong; the run stops when it
//! gets all of them right.
//!
//! 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 multiplexer_11
//! ```
mod trace;
use genoxide::gp::boolean::Multiplexer;
use genoxide::gp::{Gp, Mutations, SubtreeCrossover, Tree};
use genoxide::prelude::*;
const POPULATION: usize = 4000;
fn main() -> Result<()> {
let problem = Multiplexer::new(3)?;
let set = problem.primitives().clone();
println!("Koza's 11-multiplexer: 3 address bits select one of 8 data bits, 2048 cases");
println!("{POPULATION} trees, until every case is right\n");
// Koza's limits and initialization: depth 17, ramped half-and-half of depths 2 to 6
let gp = Gp::builder(set.clone()).build()?;
let initial = gp.ramped_half_and_half(POPULATION, &mut StreamRng::seed_from_u64(1))?;
let ga = Ga::builder(gp)
.population_size(POPULATION)
.initial_genomes(initial)
.select(DoubleTournament::new(7, 1.4)?)
.crossover(SubtreeCrossover::new())
.mutate(
Mutations::builder()
.subtree(0.5)
.point(0.3)
.hoist(0.1)
.shrink(0.1)
.build()?,
)
.crossover_rate(0.9)
.mutation_rate(0.1)
.minimize()
.seed(1)
.build()?;
let mut trace = trace::Trace::from_env(&problem);
let outcome = Engine::new(ga, |tree: &Tree| problem.errors(tree) as f64)
.stop_when(Stop::target(0.0).or(Stop::generations(50)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let best = outcome.best_genome();
println!(
"{:?} after {} generations and {} evaluations",
outcome.stop_reason(),
outcome.generations(),
outcome.evaluations()
);
println!(
"cases right: {} of {}",
problem.cases() - problem.errors(best),
problem.cases()
);
println!(
"\nthe function, {} nodes of depth {}:\n{}",
best.len(),
best.depth(&set),
best.display(&set)
);
trace.write();
Ok(())
}
python examples/multiplexer_11/main.py
"""Koza's 11-multiplexer: find the Boolean function that uses 3 address bits to select one of 8
data bits, from all 2048 cases of its truth table, by genetic programming.
Trees of Koza's functions (and, or, not, if) and the 11 inputs, evolved by a genetic algorithm
with subtree crossover and a mix of mutations, and double tournaments against bloat. The fitness
is the number of the 2048 cases a tree gets wrong; the run stops when it gets all of them right.
The problem is evaluated in Rust (``gx.gp.boolean``), 64 cases at once, so the run is the Rust
example's, to the bit, on every platform.
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/multiplexer_11/main.py
"""
import genoxide as gx
from trace import Trace
POPULATION = 4000
problem = gx.gp.boolean.Multiplexer(3)
print("Koza's 11-multiplexer: 3 address bits select one of 8 data bits, 2048 cases")
print(f"{POPULATION} trees, until every case is right")
print()
# Koza's limits and initialization: depth 17, ramped half-and-half of depths 2 to 6
gp = gx.gp.Gp(problem.primitives())
ga = gx.Ga(
gp,
population_size=POPULATION,
initial_genomes=gp.ramped_half_and_half(POPULATION, 1),
select=gx.DoubleTournament(7, 1.4),
crossover=gx.gp.SubtreeCrossover(),
mutation=gx.gp.Mutations(
[
(0.5, gx.gp.SubtreeMutation()),
(0.3, gx.gp.PointMutation(count=1)),
(0.1, gx.gp.HoistMutation()),
(0.1, gx.gp.ShrinkMutation()),
]
),
crossover_rate=0.9,
mutation_rate=0.1,
objective="minimize",
seed=1,
)
trace = Trace(problem)
# the problem itself is the fitness: the cases a tree gets wrong, counted in Rust
result = ga.run(problem, target=0.0, generations=50, on_generation=trace.on_generation)
best = result.best_genome
print(
f"{result.stop_reason.capitalize()} after {result.generations} generations and "
f"{result.evaluations} evaluations"
)
print(f"cases right: {problem.cases - problem.errors(best)} of {problem.cases}")
print()
print(f"the function, {len(best)} nodes of depth {best.depth}:")
print(best)
trace.write()
What it prints, from a seeded run:
Koza's 11-multiplexer: 3 address bits select one of 8 data bits, 2048 cases
4000 trees, until every case is right
Target after 15 generations and 51907 evaluations
cases right: 2048 of 2048
the function, 40 nodes of depth 5:
if(a0, if(a1, if(a0, if(a2, d7, d3), d2), if(a2, d5, if(a1, d2, if(a0, d1, d0)))), if(a2, if(a1, if(a1, if(a2, d6, d3), d1), d4), if(a1, d2, if(a0, d1, d0))))