use crate::gatypes::SolutionDataTypes;
use rand::rngs::SmallRng;
use rand::seq::SliceRandom;
use rand::SeedableRng;
use smallvec::SmallVec;
use std::sync::Arc;
pub type ObjVec = SmallVec<[f64; 4]>;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ConfigError(String);
impl ConfigError {
pub fn new(message: impl Into<String>) -> Self {
ConfigError(message.into())
}
pub fn message(&self) -> &str {
&self.0
}
}
impl std::fmt::Display for ConfigError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.0)
}
}
impl std::error::Error for ConfigError {}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum Encoding {
#[default]
PerGene,
Permutation,
}
#[derive(Clone, Debug)]
pub enum EvalFn {
Single(fn(&Vec<f64>) -> Vec<f64>),
Batch(fn(&Vec<Vec<f64>>) -> Vec<Vec<f64>>),
}
#[derive(Debug, Clone)]
pub struct Problem {
pub solution_length: usize,
pub number_of_objectives: usize,
pub objective_constraint: Option<Vec<Option<f64>>>, pub objective_constraint_operands: Option<Vec<Option<String>>>, pub direction: Option<Vec<i8>>, pub solution_data_types: Vec<SolutionDataTypes>, pub eval_fn: EvalFn,
pub variable_constraints: Option<Vec<fn(&Vec<f64>) -> f64>>,
pub encoding: Encoding,
}
impl Problem {
#[allow(clippy::too_many_arguments)]
pub fn try_new(
solution_length: usize,
number_of_objectives: usize,
objective_constraint: Option<Vec<Option<f64>>>, objective_constraint_operands: Option<Vec<Option<String>>>, direction: Option<Vec<i8>>,
solution_data_types: Vec<SolutionDataTypes>, objective_function: fn(&Vec<f64>) -> Vec<f64>
) -> Result<Self, ConfigError> {
if solution_length != solution_data_types.len() {
return Err(ConfigError::new("solution_length does not match solution_data_types length"));
}
if let Some(ref constraints) = objective_constraint {
if constraints.len() != number_of_objectives {
return Err(ConfigError::new("objective_constraint length does not match number_of_objectives"));
}
}
if let Some(ref operands) = objective_constraint_operands {
if operands.len() != number_of_objectives {
return Err(ConfigError::new("objective_constraint_operands length does not match number_of_objectives"));
}
}
match (&objective_constraint, &objective_constraint_operands) {
(Some(_), None) => {
return Err(ConfigError::new(
"objective_constraint is set but objective_constraint_operands is None — supply both or neither",
))
}
(None, Some(_)) => {
return Err(ConfigError::new(
"objective_constraint_operands is set but objective_constraint is None — supply both or neither",
))
}
_ => {}
}
if let Some(ref operands) = objective_constraint_operands {
for op in operands.iter().flatten() {
if !matches!(op.as_str(), "<" | ">" | "<=" | ">=" | "==" | "!=") {
return Err(ConfigError::new(format!(
"Invalid operand: {op} (expected one of <, >, <=, >=, ==, !=)"
)));
}
}
}
let direction: Option<Vec<i8>> = direction.or_else(|| Some(vec![-1; number_of_objectives]));
if let Some(ref dirs) = direction {
if dirs.len() != number_of_objectives {
return Err(ConfigError::new("direction length does not match number_of_objectives"));
}
if let Some(bad) = dirs.iter().find(|d| **d != 1 && **d != -1) {
return Err(ConfigError::new(format!(
"direction entries must be 1 (maximize) or -1 (minimize), got {bad}"
)));
}
}
Ok(Problem {
solution_length,
number_of_objectives,
objective_constraint,
objective_constraint_operands,
direction,
solution_data_types,
variable_constraints: None,
eval_fn: EvalFn::Single(objective_function),
encoding: Encoding::PerGene,
})
}
#[allow(clippy::too_many_arguments)]
pub fn new(
solution_length: usize,
number_of_objectives: usize,
objective_constraint: Option<Vec<Option<f64>>>, objective_constraint_operands: Option<Vec<Option<String>>>, direction: Option<Vec<i8>>,
solution_data_types: Vec<SolutionDataTypes>, objective_function: fn(&Vec<f64>) -> Vec<f64>
) -> Self {
Self::try_new(
solution_length,
number_of_objectives,
objective_constraint,
objective_constraint_operands,
direction,
solution_data_types,
objective_function,
)
.unwrap_or_else(|e| panic!("{}", e))
}
pub fn with_permutation_encoding(mut self) -> Self {
self.encoding = Encoding::Permutation;
self
}
pub fn generate_solution(&self, rng: &mut SmallRng) -> Vec<f64> {
if self.encoding == Encoding::Permutation {
let mut perm: Vec<f64> = (0..self.solution_length).map(|i| i as f64).collect();
perm.shuffle(rng);
return perm;
}
let mut solution: Vec<f64> = Vec::new();
for solution_type in &self.solution_data_types {
match solution_type {
SolutionDataTypes::BitBinary(binary) => {
solution.push(binary.generate_value(rng).unwrap() as f64);
}
SolutionDataTypes::Integer(integer) => {
solution.push(integer.generate_value(rng).unwrap() as f64);
}
SolutionDataTypes::Real(real) => {
solution.push(real.generate_value(rng).unwrap());
}
}
}
solution
}
pub fn with_variable_constraints(mut self, constraints: Vec<fn(&Vec<f64>) -> f64>) -> Self {
self.variable_constraints = Some(constraints);
self
}
pub fn has_constraints(&self) -> bool {
self.objective_constraint.as_ref().is_some_and(|c| !c.is_empty())
|| self.variable_constraints.as_ref().is_some_and(|g| !g.is_empty())
}
}
#[derive(Clone, Copy, Debug)]
pub struct GenomeKey<'a>(pub &'a [f64]);
impl PartialEq for GenomeKey<'_> {
fn eq(&self, other: &Self) -> bool {
self.0.len() == other.0.len() && self.0.iter().zip(other.0).all(|(a, b)| a.to_bits() == b.to_bits())
}
}
impl Eq for GenomeKey<'_> {}
impl std::hash::Hash for GenomeKey<'_> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
state.write_usize(self.0.len());
for v in self.0 {
state.write_u64(v.to_bits());
}
}
}
pub(crate) fn first_of_each_genome(pop: &[Solution], order: &[usize]) -> Vec<usize> {
let mut seen = std::collections::HashSet::with_capacity(order.len());
order.iter().copied().filter(|&i| seen.insert(GenomeKey(&pop[i].solution))).collect()
}
#[derive(Debug, Clone)]
pub struct Solution {
pub problem: Arc<Problem>,
pub solution: Vec<f64>, pub objective_fitness_values: ObjVec,
pub constraint_values: ObjVec,
pub evaluated: bool, pub constraint_violation: usize, pub constraint_violation_magnitude: f64, pub feasible: bool
}
impl Solution {
pub fn new(problem: Arc<Problem>) -> Self {
let mut rng = SmallRng::from_entropy();
let solution = problem.generate_solution(&mut rng);
let objective_fitness_values: ObjVec = ObjVec::new();
let constraint_values: ObjVec = ObjVec::new();
let evaluated: bool = false;
let constraint_violation = 0;
let feasible = false;
Solution {
problem,
solution,
objective_fitness_values,
constraint_values,
evaluated,
constraint_violation,
constraint_violation_magnitude: 0.0,
feasible,
}
}
pub fn evaluate_constraints(&mut self) -> Vec<f64> {
let mut constraint_values: Vec<f64> = Vec::new();
match (&self.problem.objective_constraint, &self.problem.objective_constraint_operands) {
(Some(_), None) => panic!(
"objective_constraint is set but objective_constraint_operands is None — \
supply both (e.g. Some(vec![Some(\"<\".into())])) or neither"
),
(None, Some(_)) => panic!(
"objective_constraint_operands is set but objective_constraint is None — \
supply both or neither"
),
_ => {}
}
if let (Some(constraints), Some(operands)) =
(&self.problem.objective_constraint, &self.problem.objective_constraint_operands)
{
for i in 0..constraints.len() {
let (Some(bound), Some(op)) = (constraints[i], operands[i].as_deref()) else {
constraint_values.push(1.0);
continue;
};
let obj = self.objective_fitness_values[i];
let satisfied = match op {
"<" => obj < bound,
">" => obj > bound,
"<=" => obj <= bound,
">=" => obj >= bound,
"==" => obj == bound,
"!=" => obj != bound,
other => panic!("Invalid operand: {}", other),
};
constraint_values.push(satisfied as i8 as f64);
}
}
constraint_values
}
pub fn calculate_constraint_violation(&mut self) -> usize {
let mut constraint_violation = 0;
for constraint_value in &self.constraint_values {
if *constraint_value == 0.0 {
constraint_violation += 1;
}
}
if let Some(gs) = &self.problem.variable_constraints {
for g in gs {
if g(&self.solution) > 0.0 {
constraint_violation += 1;
}
}
}
constraint_violation
}
pub fn calculate_constraint_violation_magnitude(&self) -> f64 {
let mut total = 0.0;
if let (Some(constraints), Some(operands)) =
(&self.problem.objective_constraint, &self.problem.objective_constraint_operands)
{
for i in 0..constraints.len() {
let (Some(bound), Some(op)) = (constraints[i], operands[i].as_deref()) else {
continue;
};
let obj = self.objective_fitness_values[i];
total += match op {
"<" | "<=" => (obj - bound).max(0.0),
">" | ">=" => (bound - obj).max(0.0),
"==" => (obj - bound).abs(),
"!=" => if obj == bound { 1.0 } else { 0.0 },
other => panic!("Invalid operand: {}", other),
};
}
}
if let Some(gs) = &self.problem.variable_constraints {
for g in gs {
total += g(&self.solution).max(0.0);
}
}
total
}
pub fn is_feasible(&self) -> bool {
self.constraint_violation == 0
}
pub fn evaluate(&mut self) {
self.objective_fitness_values = match self.problem.eval_fn {
EvalFn::Single(f) => f(&self.solution).into(),
EvalFn::Batch(_) => panic!(
"Solution::evaluate() called on a batch-mode Problem. \
Use the GA's population evaluation instead \
(NSGAII::evaluate_population / NSGAIII::run)."
),
};
self.evaluated = true;
self.constraint_values = self.evaluate_constraints().into();
self.constraint_violation = self.calculate_constraint_violation();
self.constraint_violation_magnitude = self.calculate_constraint_violation_magnitude();
self.feasible = self.is_feasible();
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::gatypes::{BitBinary, Integer, Real};
use crate::benchmark_objective_functions::parabloid_5_loc;
#[test]
fn test_bit_binary() {
let mut rng = SmallRng::seed_from_u64(0);
let bit_binary = BitBinary::new();
let value = bit_binary.generate_value(&mut rng).unwrap();
assert!(value == 0 || value == 1);
}
#[test]
fn test_integer() {
let mut rng = SmallRng::seed_from_u64(0);
let integer = Integer::new(Some(10), Some(20));
let value = integer.generate_value(&mut rng).unwrap();
assert!((10..=20).contains(&value)); }
#[test]
fn test_real() {
let mut rng = SmallRng::seed_from_u64(0);
let real = Real::new(Some(10.0), Some(20.0));
let value = real.generate_value(&mut rng).unwrap();
assert!((10.0..=20.0).contains(&value)); }
#[test]
fn test_problem_initialization() {
let solution_data_types = vec![
SolutionDataTypes::BitBinary(BitBinary::new()),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(20))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(20.0))),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(20))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(20.0))),
];
let problem = Problem::new(
5,
1,
None,
None,
None,
solution_data_types,
parabloid_5_loc,
);
assert_eq!(problem.solution_length, 5);
assert_eq!(problem.number_of_objectives, 1);
}
#[test]
fn test_generate_solution() {
let solution_data_types = vec![
SolutionDataTypes::BitBinary(BitBinary::new()),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(20))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(20.0))),
SolutionDataTypes::Integer(Integer::new(Some(-100), Some(20))),
SolutionDataTypes::Real(Real::new(Some(-10.0), Some(20.0))),
];
let problem = Problem::new(
5,
1,
None,
None,
None,
solution_data_types,
parabloid_5_loc,
);
let mut rng = SmallRng::seed_from_u64(0);
let solution: Vec<f64> = problem.generate_solution(&mut rng);
println!("{:?}", solution);
assert_eq!(solution.len(), 5);
}
#[test]
fn test_solution_evaluation() {
let solution_data_types = vec![
SolutionDataTypes::BitBinary(BitBinary::new()),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(20))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(20.0))),
SolutionDataTypes::Integer(Integer::new(Some(-100), Some(20))),
SolutionDataTypes::Real(Real::new(Some(-10.0), Some(20.0))),
];
let problem = Arc::new(Problem::new(
5,
1,
None,
None,
None,
solution_data_types,
parabloid_5_loc,
));
let mut solution = Solution::new(Arc::clone(&problem));
solution.evaluate();
assert!(solution.evaluated);
assert_eq!(solution.objective_fitness_values.len(), 1);
}
#[test]
fn test_solution_feasibility() {
let solution_data_types = vec![
SolutionDataTypes::BitBinary(BitBinary::new()),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(20))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(20.0))),
SolutionDataTypes::Integer(Integer::new(Some(-100), Some(20))),
SolutionDataTypes::Real(Real::new(Some(-10.0), Some(20.0))),
];
let problem = Arc::new(Problem::new(
5,
1,
None,
None,
None,
solution_data_types,
parabloid_5_loc,
));
let mut solution = Solution::new(Arc::clone(&problem));
solution.evaluate();
assert!(solution.is_feasible());
}
#[test]
fn test_solution_constraint_violation() {
let solution_data_types = vec![
SolutionDataTypes::Real(Real::new(Some(0.0), Some(20.0))),
SolutionDataTypes::Real(Real::new(Some(0.0), Some(20.0))),
SolutionDataTypes::Real(Real::new(Some(0.0), Some(20.0))),
SolutionDataTypes::Real(Real::new(Some(0.0), Some(20.0))),
SolutionDataTypes::Real(Real::new(Some(0.0), Some(20.0))),
];
let problem = Arc::new(Problem::new(
5,
1,
Some(vec![Some(15.0)]),
Some(vec![Some("<".to_string())]),
None,
solution_data_types,
parabloid_5_loc,
));
let mut feasible = Solution::new(Arc::clone(&problem));
feasible.solution = vec![1.0, 2.0, 3.0, 4.0, 5.0];
feasible.evaluate();
assert_eq!(feasible.constraint_violation, 0, "solution at optimum should have no violations");
let mut infeasible = Solution::new(Arc::clone(&problem));
infeasible.solution = vec![10.0, 10.0, 10.0, 10.0, 10.0];
infeasible.evaluate();
assert_eq!(infeasible.constraint_violation, 1, "solution with objective 285 should violate < 15");
assert!(!infeasible.feasible);
}
#[test]
fn test_variable_constraints() {
fn sphere(x: &Vec<f64>) -> Vec<f64> { vec![x.iter().map(|v| v * v).sum()] }
let problem = Arc::new(
Problem::new(
2, 1, None, None, Some(vec![-1]),
vec![
SolutionDataTypes::Real(Real::new(Some(0.0), Some(10.0))),
SolutionDataTypes::Real(Real::new(Some(0.0), Some(10.0))),
],
sphere,
)
.with_variable_constraints(vec![|x: &Vec<f64>| x.iter().sum::<f64>() - 5.0]),
);
let mut feasible = Solution::new(Arc::clone(&problem));
feasible.solution = vec![1.0, 1.0]; feasible.evaluate();
assert_eq!(feasible.constraint_violation, 0);
assert!(feasible.feasible);
let mut infeasible = Solution::new(Arc::clone(&problem));
infeasible.solution = vec![4.0, 4.0]; infeasible.evaluate();
assert_eq!(infeasible.constraint_violation, 1);
assert!(!infeasible.feasible);
}
#[test]
fn test_problem_with_constraints() {
let solution_data_types = vec![
SolutionDataTypes::BitBinary(BitBinary::new()),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(20))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(20.0))),
SolutionDataTypes::Integer(Integer::new(Some(-100), Some(20))),
SolutionDataTypes::Real(Real::new(Some(-10.0), Some(20.0))),
];
let problem = Problem::new(
5,
1,
Some(vec![Some(15.0)]),
Some(vec![Some("<".to_string())]),
None,
solution_data_types,
parabloid_5_loc,
);
assert_eq!(problem.solution_length, 5);
assert_eq!(problem.number_of_objectives, 1);
assert_eq!(problem.objective_constraint.as_ref().unwrap().len(), 1);
assert_eq!(problem.objective_constraint_operands.as_ref().unwrap().len(), 1);
}
}