Skip to content

Four-bar truss

The problem

A truss of four bars carries a load F = 10 kN at a joint. The bars' cross-sections x₁ … x₄, in cm², should give the truss the least volume and its loaded joint the least displacement:

minimize   f₁ = L (2x₁ + √2 x₂ + √2 x₃ + x₄)                    the volume, in cm³
           f₂ = (FL/E) (2/x₁ + 2√2/x₂ − 2√2/x₃ + 2/x₄)          the displacement, in cm
F = 10 kN, L = 200 cm, E = 2·10⁵ kN/cm², σ = 10 kN/cm²
x₁, x₄ in [F/σ, 3F/σ] = [1, 3], x₂, x₃ in [√2 F/σ, 3F/σ] = [√2, 3]

The bounds keep each bar's stress under σ. Stadler and Dauer's survey (1993) and Cheng and Li's paper (1999), the problem's sources, couldn't be read: the definition, constants and bounds are those of Costa and Fernandes (2009, 8th World Congress on Structural and Multidisciplinary Optimization, problem (4-truss)), who restate it after Stadler and Dauer with the displacement as a constraint. Tanabe and Ishibuchi's restatement (2020, problem RE2-4-1) has √x₃ where the volume has √2 x₃, which is dimensionally wrong and moves the front.

The optimal front, derived from the definition: x₃ adds to the volume and takes from the displacement's third term, so both objectives are least at x₃ = √2. The rest is a convex problem, whose optimal solutions minimize f₁ + λ f₂ for some λ > 0: x₁ = √(λ/20000) and x₂ = x₄ = √(λ/10000), each clamped to its bounds. That gives three pieces: x₁ = 1, x₂ = √2 and x₄ from 1 to √2 (volumes 1400 to 1482.84); then x₂ = x₄ = √2 x₁ from √2 to 3 (to 2697.06); then x₂ = x₄ = 3 and x₁ from 3/√2 to 3 (to 3048.53). genoxide's FourBarTruss gives these pieces as its optimal front.

What makes it hard

Not much: there are no constraints besides the bounds, and the front is convex. The objectives' scales differ by five orders of magnitude, and one gene, x₃, must sit on its lower bound in every optimal solution; the front's kinks, where a gene reaches a bound, need solutions on both sides.

Representation

A Real genome of 4 genes, the cross-sections. The problem is genoxide's multi::problems::engineering::FourBarTruss (gx.problems.multi_engineering.FourBarTruss in Python).

Algorithm

NSGA-II with a population of 100 for 250 generations, simulated binary crossover (η = 20, at a rate of 0.9) and polynomial mutation (η = 20, at a rate of 1/4 per gene).

Output

The first line gives the size of the final front and how many of its solutions are feasible (all are: the problem has no constraints), the second the range of each objective on it. The third gives its IGD+ (Ishibuchi et al., 2015) to 2,000 points of the optimal front, and its hypervolume up to the reference point (1.1, 1.1), as a share of the whole front's, from 100,000 of its points, 0.8891. Both use objectives scaled to [0, 1] on the front by its ideal point (1400, 0.0027614) and nadir point (3048.53, 0.04). In Python, run evaluates the problem in Rust, so both versions print the same.

The project page plays this run back, over the optimal front.

Good results

A good front covers all three pieces, from a volume of 1400 to 3048.53. 100 points of the optimal front, spread evenly along it, give 99.48% of its hypervolume and an IGD+ of 0.0023.

The run's front has 100 solutions, 13 on the first piece, 72 on the second and 15 on the third, from (1400.00, 0.040000) to (3048.52, 0.002762), none with x₃ above 1.417: an IGD+ of 0.0040 and 99.09% of the whole front's hypervolume. Over seeds 1 to 20, every run ends the same way: IGD+ from 0.0038 to 0.0043, and 99.04% to 99.16% of the hypervolume.

Reference: Stadler, W. and Dauer, J. (1993). Multicriteria optimization in engineering: a tutorial and survey. In Structural Optimization: Status and Promise, Progress in Astronautics and Aeronautics 150, AIAA: 209-249.

Known optimum: the front from (1400, 0.04) to (2200 + 600√2, (2√2 − 2)/300) ≈ (3048.53, 0.0027614), in three pieces with x₃ = √2; hypervolume 0.8891 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))

Source: examples/four_bar_truss

Interactive run: tachsin.gr/projects/genoxide/examples/four-bar-truss

cargo run --release --example four_bar_truss

//! Four-bar truss: minimize the volume of a truss of four bars and the displacement of its loaded
//! joint, whose front has three pieces.
//!
//! NSGA-II with a population of 100, simulated binary crossover and polynomial mutation at a rate
//! of 1/4 per gene, for 250 generations. Prints how many solutions of the final front are feasible,
//! the range of each objective on it, their IGD+ to the optimal front and their hypervolume.
//!
//! 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 four_bar_truss
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::MultiProblem;
use genoxide::multi::problems::engineering::FourBarTruss;
use genoxide::prelude::*;

// the run's length
const GENERATIONS: u64 = 250;

fn main() -> Result<()> {
    let problem = FourBarTruss;
    let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
        .population_size(100)
        .crossover(SimulatedBinaryCrossover::new(20.0)?)
        .mutate(PolynomialMutation::per_gene(0.25, 20.0)?)
        .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 = MultiEngine::new(nsga2, problem)
        .stop_when(Stop::generations(GENERATIONS))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;
    let (front, size) = feasible(outcome.front());
    report(&front, size);
    trace.write();
    Ok(())
}

// the objectives scaled to [0, 1] on the front, by its ideal and nadir points
pub fn scaled(points: &[[f64; 2]]) -> Vec<[f64; 2]> {
    let (ideal, nadir) = (
        FourBarTruss.ideal_point().expect("known"),
        FourBarTruss.nadir_point().expect("known"),
    );
    let scale = |p: &[f64; 2]| [0, 1].map(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
    points.iter().map(scale).collect()
}

// the feasible solutions of the run's front: how many of them, the range of each objective,
// their IGD+ to the optimal front and their hypervolume, as a share of the whole front's
fn report(front: &[[f64; 2]], size: usize) {
    let feasible = if front.len() == size {
        "all feasible".to_string()
    } else {
        format!("{} feasible", front.len())
    };
    println!("NSGA-II, {GENERATIONS} generations: {size} solutions on the front, {feasible}");
    let low = |j: usize| front.iter().map(|p| p[j]).fold(f64::INFINITY, f64::min);
    let high = |j: usize| front.iter().map(|p| p[j]).fold(f64::NEG_INFINITY, f64::max);
    println!(
        "  volume from {:.2} to {:.2}, displacement from {:.6} to {:.6}",
        low(0),
        high(0),
        low(1),
        high(1)
    );
    let found = scaled(front);
    let volume = hypervolume(&found, &[1.1, 1.1], &[Minimize; 2]);
    let optimal = FourBarTruss.optimal_front(2000).expect("known");
    let distance = igd_plus(&found, &scaled(&optimal), &[Minimize; 2]);
    let whole = whole_front_hypervolume();
    println!(
        "  IGD+ {distance:.5}, hypervolume {volume:.4}, {:.2}% of the whole front's {whole:.4}",
        100.0 * volume / whole
    );
}

// the hypervolume of the whole optimal front, from 100,000 of its points, in scaled objectives with
// the reference point (1.1, 1.1)
pub fn whole_front_hypervolume() -> f64 {
    let front = scaled(&FourBarTruss.optimal_front(100_000).expect("known"));
    hypervolume(&front, &[1.1, 1.1], &[Minimize; 2])
}

// the objective values of the feasible solutions of a front, and the front's size
fn feasible<G: Genome>(front: &[Individual<G, multi::Scores<2>>]) -> (Vec<[f64; 2]>, usize) {
    let values = front
        .iter()
        .filter_map(|x| {
            x.fitness()
                .filter(|s| s.is_feasible())
                .and_then(|s| s.values())
        })
        .collect();
    (values, front.len())
}

python examples/four_bar_truss/main.py

"""Four-bar truss: minimize the volume of a truss of four bars and the displacement of its loaded
joint, whose front has three pieces.

NSGA-II with a population of 100, simulated binary crossover and polynomial mutation at a rate of
1/4 per gene, for 250 generations. Prints how many solutions of the final front are feasible, the
range of each objective on it, their IGD+ to the optimal front and their hypervolume.

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

import genoxide as gx

from trace import Trace, scaled, whole_front_hypervolume

# the run's length
GENERATIONS = 250

problem = gx.problems.multi_engineering.FourBarTruss()
nsga2 = gx.Nsga2(
    problem.genome,
    objectives=problem.objectives,
    population_size=100,
    crossover=gx.SimulatedBinaryCrossover(20),
    mutation=gx.PolynomialMutation(20, 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 = nsga2.run(problem, generations=GENERATIONS, on_generation=trace.on_generation)

feasible = result.front_violations == 0
front = result.front_objectives[feasible]
size = len(result.front_objectives)
count = "all feasible" if feasible.all() else f"{int(feasible.sum())} feasible"
print(f"NSGA-II, {GENERATIONS} generations: {size} solutions on the front, {count}")
low, high = front.min(axis=0), front.max(axis=0)
print(
    f"  volume from {low[0]:.2f} to {high[0]:.2f}, "
    f"displacement from {low[1]:.6f} to {high[1]:.6f}"
)
found = scaled(problem, front)
volume = gx.indicators.hypervolume(found, [1.1, 1.1])
optimal = scaled(problem, problem.optimal_front(2000))
distance = gx.indicators.igd_plus(found, optimal)
whole = whole_front_hypervolume(problem)
print(
    f"  IGD+ {distance:.5f}, hypervolume {volume:.4f}, {100 * volume / whole:.2f}% of the whole "
    f"front's {whole:.4f}"
)
trace.write()

What it prints, from a seeded run:

NSGA-II, 250 generations: 100 solutions on the front, all feasible
  volume from 1400.00 to 3048.52, displacement from 0.002762 to 0.040000
  IGD+ 0.00404, hypervolume 0.8811, 99.09% of the whole front's 0.8891