use std::fmt::Debug;
use crate::evolutionary_strategy::{EvolutionaryStrategy, IdentityStrategy};
use crate::fitness::FitnessFunction;
use crate::terminating::TerminatingCondition;
use crate::perturbation::PerturbationOperator;
use crate::comparison::BetterThanOperator;
// Functions
#[derive(Debug, Clone, PartialEq)]
pub struct LocalSearchCandidate<TInput, TResult>
{
pub fit: TResult,
pub pos: TInput,
pub cycle: usize
}
#[derive(Debug, Clone, PartialEq)]
pub struct LocalSearchResult<TInput, TResult>
where TResult: Clone
{
pub best_candidate: LocalSearchCandidate<TInput, TResult>,
// How many cycles there were
pub cycles: usize,
// statistics
pub best_candidates: Vec<LocalSearchCandidate<TInput, TResult>>
}
fn local_search_first_improving<
TInput, TResult, TErr, TFit, TTerminatingCondition, TPerturbationOperator, TBetterThanOperator>(
fit: &TFit,
terminating_condition: &mut TTerminatingCondition,
perturbation_operator: &mut TPerturbationOperator,
better_than_operator: &TBetterThanOperator,
initial: &TInput
) -> Result<LocalSearchResult<TInput, TResult>, TErr>
where
TResult: Clone,
TInput: Clone,
TFit: FitnessFunction<In = TInput, Out = TResult, Err = TErr>,
TTerminatingCondition: TerminatingCondition<TInput, TResult>,
TPerturbationOperator: PerturbationOperator<Chromosome = TInput>,
TBetterThanOperator: BetterThanOperator<TResult>,
{
local_search_first_improving_evolving(
fit,
terminating_condition,
perturbation_operator,
better_than_operator,
&mut IdentityStrategy,
initial
)
}
fn local_search_first_improving_evolving<
TInput, TResult, TErr, TFit, TTerminatingCondition, TPerturbationOperator, TBetterThanOperator, TEvolutionaryStrategy>(
fit: &TFit,
terminating_condition: &mut TTerminatingCondition,
perturbation_operator: &mut TPerturbationOperator,
better_than_operator: &TBetterThanOperator,
evolutionary_strategy: &mut TEvolutionaryStrategy,
initial: &TInput
) -> Result<LocalSearchResult<TInput, TResult>, TErr>
where
TResult: Clone,
TInput: Clone,
TFit: FitnessFunction<In = TInput, Out = TResult, Err = TErr>,
TTerminatingCondition: TerminatingCondition<TInput, TResult>,
TPerturbationOperator: PerturbationOperator<Chromosome = TInput>,
TEvolutionaryStrategy: EvolutionaryStrategy<TResult, TPerturbationOperator>,
TBetterThanOperator: BetterThanOperator<TResult>,
<TEvolutionaryStrategy as EvolutionaryStrategy<TResult, TPerturbationOperator>>::Err: Debug
{
let mut best_candidate = LocalSearchCandidate {
pos: initial.clone(),
fit: fit.fit(&initial)?,
cycle: 0
};
let mut stats: Vec<LocalSearchCandidate<TInput, TResult>> = vec![];
let mut cycle: usize = 0;
while !terminating_condition.should_terminate(&best_candidate, &stats, cycle) {
let perturbed = perturbation_operator.perturb(&best_candidate.pos);
let perturbed_fit = fit.fit(&perturbed)?;
// Minimize
let better = if better_than_operator.better_than(&perturbed_fit, &best_candidate.fit) {
best_candidate = LocalSearchCandidate {
pos: perturbed.clone(),
fit: perturbed_fit,
cycle
};
stats.push(best_candidate.clone());
true
} else {
false
};
evolutionary_strategy.step(
perturbation_operator,
better,
&stats)
// TODO
.expect("Evolution failed.");
cycle += 1;
}
Ok(LocalSearchResult {
best_candidate,
best_candidates: stats,
cycles: cycle
})
}
#[cfg(test)]
pub mod tests {
use nalgebra::SVector;
use crate::{binary_string::{BinaryString, Bounds}, comparison::MinimizingOperator, evolutionary_strategy::OneToFiveStrategy, fitness::{one_max::OneMax, real::Linear, rosenbrock::Rosenbrock, sphere::Sphere, BinaryFitnessWrapper}, local_search::{local_search_first_improving, local_search_first_improving_evolving}, perturbation::{BinaryStringBitPerturbation, BoundedPerturbation, BoundedPerturbationStrategy, PatternPerturbation, RandomDistributionPerturbation}, terminating::{AndTerminatingConditions, EqualTerminatingCondition, NoBetterForCyclesTerminatingCondition}};
#[test]
fn test_local_search_sphere() {
let optimum = BinaryString::new(vec![0, 0, 1, 0, 0,
0, 0, 1, 0, 0]);
let min = SVector::<f64, 2>::from_element(0.0);
let max = SVector::<f64, 2>::from_element(31.0);
let optimum_real = optimum.to_real(&min, &max).unwrap();
let sphere = Sphere::new(optimum_real);
let sphere_wrapped = BinaryFitnessWrapper::new(sphere, min, max);
let result = local_search_first_improving(
&sphere_wrapped,
&mut
AndTerminatingConditions::new(
vec![
&mut EqualTerminatingCondition::new_remembered(optimum.clone()),
&mut NoBetterForCyclesTerminatingCondition::new(100)
]
),
&mut BinaryStringBitPerturbation::new(0.3),
&MinimizingOperator::new(),
&BinaryString::new(vec![1; 10]),
).unwrap();
println!("{:?}", result);
assert_eq!(
result.best_candidate.fit,
0.0
);
assert_eq!(
result.best_candidate.pos,
optimum
);
}
#[test]
fn test_local_search_one_max() {
let one_max = OneMax::new();
let optimum = BinaryString::new(vec![0; 10]);
let result = local_search_first_improving(
&one_max,
&mut
AndTerminatingConditions::new(
vec![
&mut EqualTerminatingCondition::new_remembered(optimum.clone()),
&mut NoBetterForCyclesTerminatingCondition::new(100)
]
),
&mut BinaryStringBitPerturbation::new(0.3),
&MinimizingOperator::new(),
&BinaryString::new(vec![1; 10]),
).unwrap();
println!("{:?}", result);
assert_eq!(
result.best_candidate.fit,
0
);
assert_eq!(
result.best_candidate.pos,
optimum
);
}
// #[test]
// fn test_local_search_labs() {
// let labs = LABS::new();
// let optimum = BinaryString::new(vec![0; 20]);
// let result = local_search_first_improving(
// &labs,
// &mut
// AndTerminatingConditions::new(
// vec![
// // &mut EqualTerminatingCondition::new_remembered(optimum.clone()),
// &mut NoBetterForCyclesTerminatingCondition::new(1000)
// ]
// ),
// &mut BinaryStringBitPerturbation::new(0.1),
// &MinimizingOperator::new(),
// &BinaryString::new(vec![0; 20]),
// ).unwrap();
// println!("{:?}", result);
// assert_eq!(
// result.best_candidate.fit,
// 0
// );
// assert_eq!(
// result.best_candidate.pos,
// optimum
// );
// }
#[test]
fn test_local_search_rosenbrock() {
let rosenbrock = Rosenbrock::new();
let optimum = BinaryString::new(vec![1, 0, 0, 0, 1, 1, 0, 0, 0, 1]);
let min = SVector::<f64, 2>::from_element(-16.0);
let max = SVector::<f64, 2>::from_element(15.0);
let rosenbrock_wrapped = BinaryFitnessWrapper::new(rosenbrock, min, max);
let result = local_search_first_improving(
&rosenbrock_wrapped,
&mut
AndTerminatingConditions::new(
vec![
&mut EqualTerminatingCondition::new_remembered(optimum.clone()),
&mut NoBetterForCyclesTerminatingCondition::new(100)
]
),
&mut BinaryStringBitPerturbation::new(0.3),
&MinimizingOperator::new(),
&BinaryString::new(vec![0; 10]),
).unwrap();
println!("{:?}", result);
assert_eq!(
result.best_candidate.fit,
0.0
);
assert_eq!(
result.best_candidate.pos,
optimum
);
}
#[test]
fn test_local_search_linear() {
let optimum = SVector::<f64, 2>::from_vec(vec![-10.0, 10.0]);
let max = SVector::<f64, 2>::from_vec(vec![10.0, 10.0]);
let min = -SVector::<f64, 2>::from_vec(vec![10.0, 10.0]);
let linear = Linear::new(7.0, SVector::<f64, 2>::from_vec(vec![0.2, -0.5]));
let result = local_search_first_improving(
&linear,
&mut
AndTerminatingConditions::new(
vec![
&mut EqualTerminatingCondition::new_remembered(optimum.clone()),
&mut NoBetterForCyclesTerminatingCondition::new(100)
]
),
&mut BoundedPerturbation::new(
RandomDistributionPerturbation::normal(0.5).unwrap(),
min,
max,
BoundedPerturbationStrategy::Retry(10)),
&MinimizingOperator::new(),
&SVector::<f64, 2>::zeros(),
).unwrap();
println!("{:?}", result);
assert_eq!(
result.best_candidate.fit,
-0.0
);
assert_eq!(
result.best_candidate.pos,
optimum
);
}
#[test]
fn test_local_search_linear_pattern() {
let optimum = SVector::<f64, 2>::from_vec(vec![-10.0, 10.0]);
let max = SVector::<f64, 2>::from_vec(vec![10.0, 10.0]);
let min = -SVector::<f64, 2>::from_vec(vec![10.0, 10.0]);
let linear = Linear::new(7.0, SVector::<f64, 2>::from_vec(vec![0.2, -0.5]));
let result = local_search_first_improving(
&linear,
&mut
AndTerminatingConditions::new(
vec![
&mut EqualTerminatingCondition::new_remembered(optimum.clone()),
&mut NoBetterForCyclesTerminatingCondition::new(100)
]
),
&mut BoundedPerturbation::new(
PatternPerturbation::new(0.5),
min,
max,
BoundedPerturbationStrategy::Retry(10)),
&MinimizingOperator::new(),
&SVector::<f64, 2>::zeros(),
).unwrap();
println!("{:?}", result);
assert_eq!(
result.best_candidate.fit,
-0.0
);
assert_eq!(
result.best_candidate.pos,
optimum
);
}
#[test]
fn test_local_search_linear_onetofive() {
let optimum = SVector::<f64, 2>::from_vec(vec![-10.0, 10.0]);
let max = SVector::<f64, 2>::from_vec(vec![10.0, 10.0]);
let min = -SVector::<f64, 2>::from_vec(vec![10.0, 10.0]);
let linear = Linear::new(7.0, SVector::<f64, 2>::from_vec(vec![0.2, -0.5]));
let result = local_search_first_improving_evolving(
&linear,
&mut
AndTerminatingConditions::new(
vec![
&mut EqualTerminatingCondition::new_remembered(optimum.clone()),
&mut NoBetterForCyclesTerminatingCondition::new(100)
]
),
&mut BoundedPerturbation::new(
RandomDistributionPerturbation::normal(0.5).unwrap(),
min,
max,
BoundedPerturbationStrategy::Retry(10)),
&MinimizingOperator::new(),
&mut OneToFiveStrategy,
&SVector::<f64, 2>::zeros(),
).unwrap();
println!("{:?}", result);
assert_eq!(
result.best_candidate.fit,
-0.0
);
assert_eq!(
result.best_candidate.pos,
optimum
);
}
}