Two-bar truss
The problem
Two bars, AC and BC, hang from supports A and B and join at C, y metres below them, where a load of 100 kN hangs. A is 4 m and B 1 m to the side of C. The truss should use as little material as possible and stress its bars as little as possible:
minimize f₁ = x₁ √(16 + y²) + x₂ √(1 + y²) the volume, in m³
f₂ = max(σ_AC, σ_BC) the larger stress, in kPa
σ_AC = 20 √(16 + y²) / (y x₁), σ_BC = 80 √(1 + y²) / (y x₂)
subject to max(σ_AC, σ_BC) ≤ 10⁵
x₁, x₂ in [0, 0.01] m² (the bars' sections), y in [1, 3] m
The definition is Deb, Pratap and Moitra's (2000, eq. 1), checked in the authors' preprint, KanGAL report 200002; the bounds on the sections are from its text. The preprint calls x₁ and x₂ the bars' lengths, but they are their cross-sections. Deb and Srinivasan (2006, KanGAL report 2005007) restate the problem with the same bounds and derive its front.
The optimal front, derived from the definition (and by Deb and Srinivasan): on it both bars carry
the same stress S. For a given y and S the least volume is then (400 + 100y²) / (yS), smallest at
y = 2, so the first piece of the front is the hyperbola f₁ f₂ = 400, from (0.004, 10⁵) down to S =
4000√5 ≈ 8944.27, where x₂ reaches its bound of 0.01. Less stress needs a deeper truss: x₂ stays at
0.01 and y grows from 2 to 3, with f₂ = 8000 √(1 + y²) / y and f₁ = (4 + y²) / (80 √(1 + y²)),
down to the least stress, 8000√10/3 ≈ 8432.74, at a volume of 0.0513870. genoxide's TwoBarTruss
gives both pieces as its optimal front.
What makes it hard
The two objectives differ by seven orders of magnitude and the front is strongly curved: along the hyperbola, the stress falls from 10⁵ to under 10⁴ while the volume grows tenfold. The second piece is short but different in kind: its solutions have a bar at its bound and a depth other than 2. A bar with no section, at the bound 0, has an infinite stress.
Representation
A Real genome of 3 genes: x₁, x₂ and y. The problem is genoxide's
multi::problems::engineering::TwoBarTruss (gx.problems.multi_engineering.TwoBarTruss in Python),
whose fitness is the two objectives and the constraint violation.
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/3 per gene). The paper ran NSGA-II with a population of 100 for 100 generations.
Output
The first line gives the size of the final front and how many of its solutions are feasible, the
second the range of each objective on it. The third gives its IGD+ (Ishibuchi et al., 2015, EMO
2015, LNCS 9019: 110-125) 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, 1.0663.
Both use objectives scaled to [0, 1] on the front by its ideal point (0.004, 8432.74) and nadir
point (0.0513870, 10⁵). 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 is feasible and spread over both pieces, from a stress of 10⁵ down to 8432.74. 100 points of the optimal front, spread evenly along it, give 99.70% of its hypervolume and an IGD+ of 0.0015.
The run's front has 100 feasible solutions, 93 on the first piece and 7 on the second, from a volume of 0.004012 at a stress of 99,962 to a stress of 8432.7: an IGD+ of 0.0034 and 99.35% of the whole front's hypervolume. Over seeds 1 to 20, every run ends the same way: IGD+ from 0.0032 to 0.0037, and 99.30% to 99.40% of the hypervolume. 100 generations, the paper's, are already as good: 99.27% to 99.40%.
Deb, Pratap and Moitra report NSGA-II solutions from (0.00407, 99,755) to (0.05304, 8439); the last is dominated by the optimal front's end, (0.0513870, 8432.74). Deb and Srinivasan tabulate three solutions, printed to three or four digits, which evaluate to within 0.3% of their values; genoxide's tests check them.
Known optimum: the front f₁ f₂ = 400 for stresses from 10⁵ down to 4000√5, then x₂ = 0.01 and y from 2 to 3, down to 8000√10/3 ≈ 8432.74; hypervolume 1.0663 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))
Source: examples/two_bar_truss
Interactive run: tachsin.gr/projects/genoxide/examples/two-bar-truss
cargo run --release --example two_bar_truss
//! Two-bar truss: minimize the volume of a truss of two bars and the stress in them, whose front
//! has two pieces.
//!
//! NSGA-II with a population of 100, simulated binary crossover and polynomial mutation at a rate
//! of 1/3 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 two_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::TwoBarTruss;
use genoxide::prelude::*;
// the run's length
const GENERATIONS: u64 = 250;
fn main() -> Result<()> {
let problem = TwoBarTruss;
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
.population_size(100)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 3.0, 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) = (
TwoBarTruss.ideal_point().expect("known"),
TwoBarTruss.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 {:.6} to {:.6}, stress from {:.1} to {:.1}",
low(0),
high(0),
low(1),
high(1)
);
let found = scaled(front);
let volume = hypervolume(&found, &[1.1, 1.1], &[Minimize; 2]);
let optimal = TwoBarTruss.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(&TwoBarTruss.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/two_bar_truss/main.py
"""Two-bar truss: minimize the volume of a truss of two bars and the stress in them, whose front
has two pieces.
NSGA-II with a population of 100, simulated binary crossover and polynomial mutation at a rate of
1/3 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/two_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.TwoBarTruss()
nsga2 = gx.Nsga2(
problem.genome,
objectives=problem.objectives,
population_size=100,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=1 / 3),
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]:.6f} to {high[0]:.6f}, "
f"stress from {low[1]:.1f} to {high[1]:.1f}"
)
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 0.004012 to 0.051884, stress from 8432.7 to 99962.4
IGD+ 0.00340, hypervolume 1.0593, 99.35% of the whole front's 1.0663