use super::*;
use crate::algorithms::nsga2::Objective;
use crate::construction::heuristics::InsertionContext;
use crate::models::common::SingleDimLoad;
use crate::models::Problem;
use crate::solver::mutation::*;
use crate::solver::population::{Individual, SelectionPhase};
use crate::solver::RefinementContext;
use crate::utils::{parallel_into_collect, unwrap_from_result, Environment};
use std::cmp::Ordering;
use std::sync::Arc;
pub type MutationProbability = Box<dyn Fn(&RefinementContext, &InsertionContext) -> bool + Send + Sync>;
pub type MutationGroup = Vec<(Arc<dyn Mutation + Send + Sync>, MutationProbability)>;
pub struct StaticSelective {
mutation_group: MutationGroup,
}
impl HyperHeuristic for StaticSelective {
fn search(&mut self, refinement_ctx: &RefinementContext, individuals: Vec<&Individual>) -> Vec<Individual> {
parallel_into_collect(individuals.iter().enumerate().collect(), |(idx, insertion_ctx)| {
refinement_ctx
.environment
.parallelism
.thread_pool_execute(idx, || self.mutate(refinement_ctx, insertion_ctx))
})
}
}
impl StaticSelective {
pub fn new(mutation_group: MutationGroup) -> Self {
Self { mutation_group }
}
pub fn new_with_defaults(problem: Arc<Problem>, environment: Arc<Environment>) -> Self {
let default_mutation = Self::create_default_mutation(problem, environment.clone());
let local_search = Arc::new(LocalSearch::new(Arc::new(CompositeLocalOperator::new(
vec![
(Arc::new(ExchangeInterRouteBest::default()), 100),
(Arc::new(ExchangeInterRouteRandom::default()), 30),
(Arc::new(ExchangeIntraRouteRandom::default()), 30),
(Arc::new(RescheduleDeparture::default()), 20),
],
1,
2,
))));
Self::new(vec![
(
Arc::new(DecomposeSearch::new(default_mutation.clone(), (2, 8), 4)),
create_context_mutation_probability(
300,
10,
vec![(SelectionPhase::Exploration, 0.05), (SelectionPhase::Exploitation, 0.05)],
environment.random.clone(),
),
),
(local_search.clone(), create_scalar_mutation_probability(0.05, environment.random.clone())),
(default_mutation, create_scalar_mutation_probability(1., environment.random.clone())),
(local_search, create_scalar_mutation_probability(0.05, environment.random.clone())),
])
}
fn mutate(&self, refinement_ctx: &RefinementContext, insertion_ctx: &InsertionContext) -> InsertionContext {
unwrap_from_result(
self.mutation_group.iter().filter(|(_, probability)| probability(refinement_ctx, insertion_ctx)).try_fold(
insertion_ctx.deep_copy(),
|ctx, (mutation, _)| {
let new_insertion_ctx = mutation.mutate(refinement_ctx, &ctx);
if refinement_ctx.problem.objective.total_order(&insertion_ctx, &new_insertion_ctx)
== Ordering::Greater
{
Err(new_insertion_ctx)
} else {
Ok(new_insertion_ctx)
}
},
),
)
}
pub fn create_default_mutation(
problem: Arc<Problem>,
environment: Arc<Environment>,
) -> Arc<dyn Mutation + Send + Sync> {
let recreate = Arc::new(WeightedRecreate::new(vec![
(Arc::new(RecreateWithSkipBest::new(1, 2)), 50),
(Arc::new(RecreateWithRegret::new(2, 3)), 20),
(Arc::new(RecreateWithCheapest::default()), 20),
(Arc::new(RecreateWithPerturbation::new_with_defaults(environment.random.clone())), 10),
(Arc::new(RecreateWithSkipBest::new(3, 4)), 5),
(Arc::new(RecreateWithGaps::default()), 5),
(Arc::new(RecreateWithBlinks::<SingleDimLoad>::new_with_defaults(environment.random.clone())), 5),
(Arc::new(RecreateWithFarthest::default()), 2),
(Arc::new(RecreateWithSkipBest::new(4, 8)), 2),
(Arc::new(RecreateWithNearestNeighbor::default()), 1),
]));
let close_route = Arc::new(CloseRouteRemoval::default());
let random_route = Arc::new(RandomRouteRemoval::default());
let random_job = Arc::new(RandomJobRemoval::new(RuinLimits::default()));
let random_ruin = Self::create_default_random_ruin();
let ruin = Arc::new(WeightedRuin::new(vec![
(vec![(Arc::new(AdjustedStringRemoval::default()), 1.), (random_ruin.clone(), 0.1)], 100),
(vec![(Arc::new(NeighbourRemoval::default()), 1.), (random_ruin.clone(), 0.1)], 10),
(vec![(Arc::new(WorstJobRemoval::default()), 1.), (random_ruin.clone(), 0.1)], 10),
(vec![(Arc::new(ClusterRemoval::new_with_defaults(problem, environment)), 1.), (random_ruin, 0.1)], 5),
(vec![(close_route, 1.), (random_job.clone(), 0.1)], 2),
(vec![(random_route, 1.), (random_job, 0.1)], 1),
]));
Arc::new(RuinAndRecreate::new(ruin, recreate))
}
pub fn create_default_random_ruin() -> Arc<dyn Ruin + Send + Sync> {
Arc::new(WeightedRuin::new(vec![
(vec![(Arc::new(CloseRouteRemoval::default()), 1.)], 100),
(vec![(Arc::new(RandomRouteRemoval::default()), 1.)], 10),
(vec![(Arc::new(RandomJobRemoval::new(RuinLimits::default())), 1.)], 2),
]))
}
}
pub fn create_scalar_mutation_probability(
scalar_probability: f64,
random: Arc<dyn Random + Send + Sync>,
) -> MutationProbability {
Box::new(move |_, _| random.is_hit(scalar_probability))
}
pub fn create_context_mutation_probability(
jobs_threshold: usize,
routes_threshold: usize,
phases: Vec<(SelectionPhase, f64)>,
random: Arc<dyn Random + Send + Sync>,
) -> MutationProbability {
let phases = phases.into_iter().collect::<HashMap<_, _>>();
Box::new(move |refinement_ctx, insertion_ctx| {
let below_thresholds = insertion_ctx.problem.jobs.size() < jobs_threshold
|| insertion_ctx.solution.routes.len() < routes_threshold;
if below_thresholds {
return false;
}
let phase_probability = phases.get(&refinement_ctx.population.selection_phase()).cloned().unwrap_or(0.);
random.is_hit(phase_probability)
})
}