use crate::core::{Encoding, Solution};
use crate::gatypes::SolutionDataTypes;
use rand::Rng;
use rand::rngs::SmallRng;
pub trait Crossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, rng: &mut SmallRng) -> (Solution, Solution);
}
pub struct SimulatedBinaryCrossover {
pub probability: f64,
pub distribution_index: f64,
}
impl SimulatedBinaryCrossover {
pub fn new(probability: Option<f64>, distribution_index: Option<f64>) -> Self {
Self {
probability: probability.unwrap_or(1.0),
distribution_index: distribution_index.unwrap_or(20.0),
}
}
fn sbx_crossover(&self, x1: f64, x2: f64, lower: f64, upper: f64, rng: &mut SmallRng) -> (f64, f64) {
if (x2 - x1).abs() > f64::EPSILON {
let y1 = x1.min(x2);
let y2 = x1.max(x2);
let beta = 1.0 + 2.0 * (y1 - lower) / (y2 - y1);
let alpha = 2.0 - beta.powf(-(self.distribution_index + 1.0));
let rand = rng.gen::<f64>();
let betaq = if rand <= 1.0 / alpha {
(rand * alpha).powf(1.0 / (self.distribution_index + 1.0))
} else {
(1.0 / (2.0 - rand * alpha)).powf(1.0 / (self.distribution_index + 1.0))
};
let mut c1 = 0.5 * ((y1 + y2) - betaq * (y2 - y1));
let mut c2 = 0.5 * ((y1 + y2) + betaq * (y2 - y1));
if rng.gen::<bool>() {
std::mem::swap(&mut c1, &mut c2);
}
(c1.clamp(lower, upper), c2.clamp(lower, upper))
} else {
(x1, x2)
}
}
}
impl Crossover for SimulatedBinaryCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
let random_number: f64 = rng.gen();
match solution_type {
SolutionDataTypes::Real(real) => {
if random_number < self.probability {
let lower_bound = real.lower_bound.unwrap_or(f64::MIN);
let upper_bound = real.upper_bound.unwrap_or(f64::MAX);
let (c1, c2) = self.sbx_crossover(child1.solution[i], child2.solution[i], lower_bound, upper_bound, rng);
child1.solution[i] = c1;
child2.solution[i] = c2;
}
}
_ => {}
}
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct DifferentialEvolutionCrossover {
pub probability: f64,
pub scaling_factor: f64,
}
impl DifferentialEvolutionCrossover {
pub fn new(probability: Option<f64>, scaling_factor: Option<f64>) -> Self {
Self {
probability: probability.unwrap_or(0.9),
scaling_factor: scaling_factor.unwrap_or(0.8),
}
}
}
impl Crossover for DifferentialEvolutionCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
if let SolutionDataTypes::Real(real) = solution_type {
if rng.gen::<f64>() < self.probability {
let lower = real.lower_bound.unwrap_or(f64::MIN);
let upper = real.upper_bound.unwrap_or(f64::MAX);
let mut c1 = parent1.solution[i] + self.scaling_factor * (parent2.solution[i] - parent1.solution[i]);
let mut c2 = parent2.solution[i] + self.scaling_factor * (parent1.solution[i] - parent2.solution[i]);
c1 = c1.clamp(lower, upper);
c2 = c2.clamp(lower, upper);
child1.solution[i] = c1;
child2.solution[i] = c2;
}
}
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct ParentCentricCrossover {
pub nparents: usize,
pub noffspring: usize,
pub eta: f64,
pub zeta: f64
}
impl Crossover for ParentCentricCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, _rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
match solution_type {
SolutionDataTypes::Real(real) => {
let lower = real.lower_bound.unwrap_or(f64::MIN);
let upper = real.upper_bound.unwrap_or(f64::MAX);
let mut sum = 0.0;
for _ in 0..self.nparents {
sum += parent1.solution[i] + parent2.solution[i];
}
let avg = sum / self.nparents as f64;
let mut c1 = parent1.solution[i] + self.eta * (avg - parent1.solution[i]);
let mut c2 = parent2.solution[i] + self.eta * (avg - parent2.solution[i]);
c1 = c1.clamp(lower, upper);
c2 = c2.clamp(lower, upper);
child1.solution[i] = c1;
child2.solution[i] = c2;
}
SolutionDataTypes::Integer(integer) => {
let lower = integer.lower_bound.unwrap_or(i64::MIN) as f64;
let upper = integer.upper_bound.unwrap_or(i64::MAX) as f64;
let mut sum = 0.0;
for _ in 0..self.nparents {
sum += parent1.solution[i] + parent2.solution[i];
}
let avg = sum / self.nparents as f64;
let mut c1 = parent1.solution[i] + self.eta * (avg - parent1.solution[i]);
let mut c2 = parent2.solution[i] + self.eta * (avg - parent2.solution[i]);
c1 = c1.round().clamp(lower, upper);
c2 = c2.round().clamp(lower, upper);
child1.solution[i] = c1;
child2.solution[i] = c2;
}
_ => {}
}
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct UnimodalDistributionCrossover {
pub probability: f64,
pub distribution_index: f64,
pub nparents: usize,
pub zeta: f64,
pub eta: f64
}
impl Crossover for UnimodalDistributionCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, _rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
if let SolutionDataTypes::Real(real) = solution_type {
let lower = real.lower_bound.unwrap_or(f64::MIN);
let upper = real.upper_bound.unwrap_or(f64::MAX);
let mut sum = 0.0;
for _j in 0..self.nparents {
sum += parent1.solution[i] + parent2.solution[i];
}
let avg = sum / self.nparents as f64;
let mut c1 = parent1.solution[i] + self.eta * (avg - parent1.solution[i]);
let mut c2 = parent2.solution[i] + self.eta * (avg - parent2.solution[i]);
c1 = c1.clamp(lower, upper);
c2 = c2.clamp(lower, upper);
child1.solution[i] = c1;
child2.solution[i] = c2;
}
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct BlendCrossover {
pub probability: f64,
pub alpha: f64,
}
impl Crossover for BlendCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, _rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
if let SolutionDataTypes::Real(real) = solution_type {
let lower = real.lower_bound.unwrap_or(f64::MIN);
let upper = real.upper_bound.unwrap_or(f64::MAX);
let mut c1 = 0.5 * (1.0 + self.alpha) * parent1.solution[i] + 0.5 * (1.0 - self.alpha) * parent2.solution[i];
let mut c2 = 0.5 * (1.0 + self.alpha) * parent2.solution[i] + 0.5 * (1.0 - self.alpha) * parent1.solution[i];
c1 = c1.clamp(lower, upper);
c2 = c2.clamp(lower, upper);
child1.solution[i] = c1;
child2.solution[i] = c2;
}
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct UniformCrossover {
pub probability: f64,
}
impl Crossover for UniformCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
if matches!(solution_type, SolutionDataTypes::Real(_)) {
continue;
}
if rng.gen::<f64>() < self.probability {
child1.solution[i] = parent2.solution[i];
child2.solution[i] = parent1.solution[i];
}
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct ArithmeticCrossover {
pub probability: f64,
}
impl Crossover for ArithmeticCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
for (i, solution_type) in parent1.problem.solution_data_types.iter().enumerate() {
if rng.gen::<f64>() >= self.probability {
continue;
}
let a: f64 = rng.gen();
let (x1, x2) = (parent1.solution[i], parent2.solution[i]);
let (mut c1, mut c2) = (a * x1 + (1.0 - a) * x2, (1.0 - a) * x1 + a * x2);
match solution_type {
SolutionDataTypes::Integer(integer) => {
let lower = integer.lower_bound.unwrap_or(i64::MIN) as f64;
let upper = integer.upper_bound.unwrap_or(i64::MAX) as f64;
c1 = c1.round().clamp(lower, upper);
c2 = c2.round().clamp(lower, upper);
}
SolutionDataTypes::Real(real) => {
let lower = real.lower_bound.unwrap_or(f64::MIN);
let upper = real.upper_bound.unwrap_or(f64::MAX);
c1 = c1.clamp(lower, upper);
c2 = c2.clamp(lower, upper);
}
SolutionDataTypes::BitBinary(_) => continue,
}
child1.solution[i] = c1;
child2.solution[i] = c2;
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct OrderCrossover {
pub probability: f64,
}
impl Default for OrderCrossover {
fn default() -> Self {
Self { probability: 0.9 }
}
}
fn ox1(segment_donor: &[f64], order_donor: &[f64], cut1: usize, cut2: usize) -> Vec<f64> {
let n = segment_donor.len();
let mut child = vec![f64::NAN; n];
let mut taken = vec![false; n];
for i in cut1..cut2 {
child[i] = segment_donor[i];
let v = segment_donor[i] as usize;
if v < n {
taken[v] = true;
}
}
let mut write = cut2 % n;
for k in 0..n {
let read = (cut2 + k) % n;
let gene = order_donor[read];
let v = gene as usize;
if v < n && taken[v] {
continue;
}
while !child[write].is_nan() {
write = (write + 1) % n;
}
child[write] = gene;
if v < n {
taken[v] = true;
}
}
child
}
impl Crossover for OrderCrossover {
fn crossover(&self, parent1: &Solution, parent2: &Solution, rng: &mut SmallRng) -> (Solution, Solution) {
let mut child1 = parent1.clone();
let mut child2 = parent2.clone();
let n = parent1.solution.len();
if n >= 2 && rng.gen::<f64>() < self.probability {
let a = rng.gen_range(0..n);
let b = rng.gen_range(0..n);
let (cut1, cut2) = if a <= b { (a, b) } else { (b, a) };
let (cut1, cut2) = if cut1 == cut2 { (cut1, (cut2 + 1).min(n)) } else { (cut1, cut2) };
child1.solution = ox1(&parent1.solution, &parent2.solution, cut1, cut2);
child2.solution = ox1(&parent2.solution, &parent1.solution, cut1, cut2);
}
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
pub struct CrossoverManager {
default_real_crossover: Box<dyn Crossover + Send>,
default_integer_crossover: Box<dyn Crossover + Send>,
default_binary_crossover: Box<dyn Crossover + Send>,
permutation_crossover: Box<dyn Crossover + Send>,
}
impl CrossoverManager {
pub fn new() -> Self {
Self {
default_real_crossover: Box::new(SimulatedBinaryCrossover::new(None, None)),
default_integer_crossover: Box::new(UniformCrossover { probability: 0.5 }),
default_binary_crossover: Box::new(UniformCrossover { probability: 0.5 }),
permutation_crossover: Box::new(OrderCrossover::default()),
}
}
pub fn set_permutation_crossover(&mut self, crossover: Box<dyn Crossover + Send>) {
self.permutation_crossover = crossover;
}
pub fn set_default_real_crossover(&mut self, crossover: Box<dyn Crossover + Send>) {
self.default_real_crossover = crossover;
}
pub fn set_default_integer_crossover(&mut self, crossover: Box<dyn Crossover + Send>) {
self.default_integer_crossover = crossover;
}
pub fn set_default_binary_crossover(&mut self, crossover: Box<dyn Crossover + Send>) {
self.default_binary_crossover = crossover;
}
pub fn perform_crossover(
&self,
parent1: &Solution,
parent2: &Solution,
rng: &mut SmallRng,
) -> Vec<Solution> {
let (child1, child2) = self.perform_crossover_pair(parent1, parent2, rng);
vec![child1, child2]
}
pub fn perform_crossover_pair(
&self,
parent1: &Solution,
parent2: &Solution,
rng: &mut SmallRng,
) -> (Solution, Solution) {
if parent1.problem.encoding == Encoding::Permutation {
return self.permutation_crossover.crossover(parent1, parent2, rng);
}
let types = &parent1.problem.solution_data_types;
let need = |f: fn(&SolutionDataTypes) -> bool| types.iter().any(f);
let real = if need(|t| matches!(t, SolutionDataTypes::Real(_))) {
Some(self.default_real_crossover.crossover(parent1, parent2, rng))
} else { None };
let integer = if need(|t| matches!(t, SolutionDataTypes::Integer(_))) {
Some(self.default_integer_crossover.crossover(parent1, parent2, rng))
} else { None };
let binary = if need(|t| matches!(t, SolutionDataTypes::BitBinary(_))) {
Some(self.default_binary_crossover.crossover(parent1, parent2, rng))
} else { None };
let present = real.is_some() as u8 + integer.is_some() as u8 + binary.is_some() as u8;
let (mut child1, mut child2) = if present == 1 {
real.or(integer).or(binary).expect("one gene type present")
} else {
let mut c1 = parent1.clone();
let mut c2 = parent2.clone();
for (i, solution_type) in types.iter().enumerate() {
let res = match solution_type {
SolutionDataTypes::Real(_) => real.as_ref(),
SolutionDataTypes::Integer(_) => integer.as_ref(),
SolutionDataTypes::BitBinary(_) => binary.as_ref(),
};
if let Some((rc1, rc2)) = res {
c1.solution[i] = rc1.solution[i];
c2.solution[i] = rc2.solution[i];
}
}
(c1, c2)
};
child1.evaluated = false;
child1.feasible = false;
child2.evaluated = false;
child2.feasible = false;
(child1, child2)
}
}
#[cfg(test)]
mod tests {
use super::*;
use rand::SeedableRng;
use std::sync::Arc;
fn test_rng() -> SmallRng {
SmallRng::seed_from_u64(0)
}
use crate::core::{EvalFn, Problem, Solution};
use crate::gatypes::{SolutionDataTypes, Real, BitBinary, Integer};
fn setup_problem() -> Problem {
Problem {
solution_length: 5,
number_of_objectives: 1,
objective_constraint: Some(vec![Some(10.0)]),
objective_constraint_operands: Some(vec![Some("<".to_string())]),
direction: Some(vec![1]),
solution_data_types: vec![
SolutionDataTypes::BitBinary(BitBinary::new()),
SolutionDataTypes::Integer(Integer::new(Some(10), Some(2000))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(1000.0))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(1000.0))),
SolutionDataTypes::Real(Real::new(Some(10.0), Some(1000.0))),
],
variable_constraints: None,
encoding: crate::core::Encoding::PerGene,
eval_fn: EvalFn::Single(|x| vec![x.iter().sum()]),
}
}
fn setup_solutions(problem: Arc<Problem>) -> Vec<Solution> {
vec![
Solution {
problem: Arc::clone(&problem),
solution: vec![1.0, 10.0, 10.0, 10.0, 10.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
},
Solution {
problem: Arc::clone(&problem),
solution: vec![1.0, 20.0, 20.0, 20.0, 20.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
},
Solution {
problem: Arc::clone(&problem),
solution: vec![0.0, 15.0, 15.0, 15.0, 15.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
},
]
}
#[test]
fn test_sbx_crossover() {
let problem = Arc::new(setup_problem());
let solutions = setup_solutions(Arc::clone(&problem));
let sbx = SimulatedBinaryCrossover::new(None, None);
let (_child1, _child2) = sbx.crossover(&solutions[0], &solutions[2], &mut test_rng());
}
#[test]
fn test_sbx_crossover_same_values() {
let sbx = SimulatedBinaryCrossover::new(None, None);
let (c1, c2) = sbx.sbx_crossover(10.0, 10.0, 0.0, 30.0, &mut test_rng());
assert_eq!(c1, 10.0);
assert_eq!(c2, 10.0);
}
#[test]
fn test_sbx_crossover_same_values_with_bounds() {
let sbx = SimulatedBinaryCrossover::new(None, None);
let (c1, c2) = sbx.sbx_crossover(10.0, 10.0, 10.0, 10.0, &mut test_rng());
assert_eq!(c1, 10.0);
assert_eq!(c2, 10.0);
}
#[test]
fn test_uniform_crossover_with_bitbinary_and_integer() {
let problem = Arc::new(setup_problem());
let parent1 = Solution {
problem: Arc::clone(&problem),
solution: vec![1.0, 10.0, 10.0, 10.0, 10.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let parent2 = Solution {
problem: Arc::clone(&problem),
solution: vec![0.0, 20.0, 20.0, 20.0, 20.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let uc = UniformCrossover { probability: 1.0 };
let (child1, child2) = uc.crossover(&parent1, &parent2, &mut test_rng());
assert_ne!(child1.solution, parent1.solution);
assert_ne!(child2.solution, parent2.solution);
}
#[test]
fn test_parent_centric_crossover() {
let problem = Arc::new(setup_problem());
let parent1 = Solution {
problem: Arc::clone(&problem),
solution: vec![1.0, 10.0, 20.0, 30.0, 40.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let parent2 = Solution {
problem: Arc::clone(&problem),
solution: vec![0.0, 60.0, 70.5, 80.2, 90.3],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let pcc = ParentCentricCrossover { nparents: 2, noffspring: 2, eta: 0.5, zeta: 0.5 };
let (child1, child2) = pcc.crossover(&parent1, &parent2, &mut test_rng());
assert_ne!(child1.solution, parent1.solution);
assert_ne!(child2.solution, parent2.solution);
}
#[test]
fn test_unimodal_distribution_crossover() {
let problem = Arc::new(setup_problem());
let parent1 = Solution {
problem: Arc::clone(&problem),
solution: vec![1.0, 10.0, 20.0, 30.0, 40.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let parent2 = Solution {
problem: Arc::clone(&problem),
solution: vec![0.0, 60.0, 70.5, 80.2, 90.3],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let udc = UnimodalDistributionCrossover { probability: 1.0, distribution_index: 20.0, nparents: 2, zeta: 0.5, eta: 0.5 };
let (child1, child2) = udc.crossover(&parent1, &parent2, &mut test_rng());
assert_ne!(child1.solution, parent1.solution);
assert_ne!(child2.solution, parent2.solution);
}
#[test]
fn test_default_crossover_manager() {
let problem = Arc::new(setup_problem());
let parent1 = Solution {
problem: Arc::clone(&problem),
solution: vec![1.0, 10.0, 20.0, 30.0, 40.0],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let parent2 = Solution {
problem: Arc::clone(&problem),
solution: vec![0.0, 60.0, 70.5, 80.2, 90.3],
objective_fitness_values: Default::default(),
constraint_values: Default::default(),
constraint_violation: 0,
constraint_violation_magnitude: 0.0,
feasible: false,
evaluated: false,
};
let cm = CrossoverManager::new();
let children = cm.perform_crossover(&parent1, &parent2, &mut test_rng());
assert_ne!(children[0].solution, parent1.solution);
assert_ne!(children[1].solution, parent2.solution);
}
}