Skip to content

Gear train design

The problem

A compound gear train of four gears passes the rotation of an input shaft to an output shaft at a fixed ratio. Sandgren (1990) chooses the numbers of teeth of the four gears, T_a, T_b, T_d and T_f, so that the ratio T_d T_b / (T_a T_f) is as close as possible to 1/6.931. Each gear has 12 to 60 teeth. In the form that Deb and Goyal (1996, Computer Science and Informatics 26(4): 30-45) restate, the score is the squared error of the ratio:

(1/6.931 − T_d T_b / (T_a T_f))²

The target, 1/6.931, is 0.14427932. With 16 and 19 teeth over 43 and 49, the ratio is 304/2107 = 0.14428097.

What makes it hard

Every variable is an integer, and there are no constraints besides the bounds. There are 49⁴ = 5,764,801 designs, few enough to evaluate all of them, which is how the minimum is known.

The score depends only on the two products T_d T_b and T_a T_f. A change of one tooth changes a product by 1.7% (at 60 teeth) to 8% (at 12), so neighboring designs have very different scores. The best designs are scattered: three designs share the second best squared error, 2.3e-11, among them 13 and 20 over 34 and 53, with no gear in common with the best one.

Representation

An Integer genome of 4 genes, (T_d, T_b, T_a, T_f), each from 12 to 60: the design itself. The fitness is the squared error, to minimize. The problem is genoxide's GearTrain, which brings its bounds and its minimum.

Algorithm

A genetic algorithm with the pieces that genoxide's guide lists for integers in ranges:

  • a population of 100;
  • binary tournaments (size 2);
  • uniform crossover, which takes each gene from either parent;
  • uniform mutation, which redraws a gene with probability 0.25, one gene per child on average, since there are four.

Uniform crossover combines the gears of two parents, so it can join a good pair T_d T_b from one with a good pair T_a T_f from the other. The run stops at the minimum, or after 20,000 generations.

Output

The first line gives the squared error of the best design, the generations it took, and the known minimum. The second gives its teeth, (T_d, T_b, T_a, T_f), its ratio and the target ratio. In Python, run evaluates the problem in Rust, so both versions print the same.

The project page plays this run back.

Good results

The minimum is 2.700857e-12, at 16 · 19 / (43 · 49), and at the three designs that swap 16 with 19 or 43 with 49. The run reaches it after about 180 generations, at most about 18,000 evaluations: a third of a percent of the designs.

Other seeds can take much longer: runs often sit for a while at 2.307816e-11, the error of 12 designs such as 13 · 20 / (34 · 53), none of which a change of a single gear improves. Over seeds 1 to 100, every run reached the minimum, half of them within 2,300 generations and 99 within 10,000; the slowest took 13,660. With a limit of 2,000 generations, half of seeds 1 to 30 would have stopped short of it.

Reference: Sandgren, E. (1990). Nonlinear integer and discrete programming in mechanical design optimization. Journal of Mechanical Design 112(2): 223-229.

Known optimum: 2.700857e-12 (squared error of the ratio)

Source: examples/gear_train

Interactive run: tachsin.gr/projects/genoxide/examples/gear-train

cargo run --release --example gear_train

//! Gear train design (Sandgren, 1990): the numbers of teeth of a compound gear train of four
//! gears, from 12 to 60 each, whose ratio is closest to 1/6.931. An integer problem.
//!
//! The problem is genoxide's `GearTrain`, on integer genes; its score is the squared error of
//! the ratio. A genetic algorithm with uniform crossover and a mutation that redraws each gene
//! with probability 0.25 searches the 49⁴ ≈ 5.8 million designs, until it reaches the minimum,
//! 2.700857e-12, known by evaluating them all.
//!
//! 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 gear_train
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::engineering::GearTrain;

fn main() -> Result<()> {
    let problem = GearTrain;
    let minimum = problem.optimum().expect("known").value();
    let ga = Ga::builder(problem.representation())
        .population_size(100)
        .select(Tournament::new(2)?)
        .crossover(UniformCrossover::new())
        .mutate(UniformMutation::per_gene(0.25)?)
        .minimize()
        .seed(1)
        .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();
    let outcome = Engine::new(ga, problem)
        .stop_when(Stop::target(minimum).or(Stop::generations(20_000)))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;

    let teeth = outcome.best_genome();
    let ratio = (teeth[0] * teeth[1]) as f64 / (teeth[2] * teeth[3]) as f64;
    println!(
        "error {:.6e} after {} generations (the minimum: {minimum:.6e})",
        outcome.best_fitness().score().unwrap_or(f64::NAN),
        outcome.generations()
    );
    println!(
        "teeth ({}, {}, {}, {}), ratio {ratio:.8} (the target: {:.8})",
        teeth[0],
        teeth[1],
        teeth[2],
        teeth[3],
        1.0 / 6.931
    );
    trace.write();
    Ok(())
}

python examples/gear_train/main.py

"""Gear train design (Sandgren, 1990): the numbers of teeth of a compound gear train of four gears,
from 12 to 60 each, whose ratio is closest to 1/6.931. An integer problem.

The problem is genoxide's ``GearTrain``, on integer genes; its score is the squared error of the
ratio. A genetic algorithm with uniform crossover and a mutation that redraws each gene with
probability 0.25 searches the 49⁴ ≈ 5.8 million designs, until it reaches the minimum,
2.700857e-12, known by evaluating them all.

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/gear_train/main.py
"""

import genoxide as gx

from trace import Trace

problem = gx.problems.engineering.GearTrain()
minimum = problem.optimum.value
ga = gx.Ga(
    problem.genome,
    objective=problem.objective,
    population_size=100,
    select=gx.Tournament(2),
    crossover=gx.UniformCrossover(),
    mutation=gx.UniformMutation(rate=0.25),
    seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(problem)
result = ga.run(problem, target=minimum, generations=20_000, on_generation=trace.on_generation)

teeth = result.best_genome.tolist()
ratio = teeth[0] * teeth[1] / (teeth[2] * teeth[3])
print(
    f"error {result.best_fitness:.6e} after {result.generations} generations "
    f"(the minimum: {minimum:.6e})"
)
print(f"teeth {tuple(teeth)}, ratio {ratio:.8f} (the target: {1 / 6.931:.8f})")
trace.write()

What it prints, from a seeded run:

error 2.700857e-12 after 183 generations (the minimum: 2.700857e-12)
teeth (16, 19, 43, 49), ratio 0.14428097 (the target: 0.14427932)