genetic_algorithm/fitness.rs
1//! The search goal to optimize towards (maximize or minimize).
2//!
3//! Each problem will usually have its own specific [Fitness] function, therefore you need to
4//! implement it yourself. Because the [Fitness] function is specific, it is also bound to the
5//! [Genotype] through a trait attribute (no reason to make it generic, as the client implements for
6//! a single [Genotype] type).
7//!
8//! See [Fitness] Trait for examples and further documentation
9pub mod cache;
10pub mod placeholders;
11pub mod prelude;
12
13pub use self::cache::Cache as FitnessCache;
14
15use crate::chromosome::Chromosome;
16use crate::genotype::Genotype;
17use crate::population::Population;
18use crate::strategy::{StrategyAction, StrategyConfig, StrategyState};
19use rayon::prelude::*;
20use std::cell::RefCell;
21use std::time::Instant;
22use thread_local::ThreadLocal;
23
24/// Use isize for easy handling of scores (ordering, comparing) as floats are tricky in that regard.
25pub type FitnessValue = isize;
26
27#[derive(Copy, Clone, Debug)]
28pub enum FitnessOrdering {
29 Maximize,
30 Minimize,
31}
32
33/// This is just a shortcut for `Self::Genotype`
34pub type FitnessGenotype<F> = <F as Fitness>::Genotype;
35/// This is just a shortcut for `<Self::Genotype as Genotype>::Chromosome`
36pub type FitnessChromosome<F> = <<F as Fitness>::Genotype as Genotype>::Chromosome;
37/// This is just a shortcut for `<Self::Genotype as Genotype>::Genes`
38pub type FitnessGenes<F> = <<F as Fitness>::Genotype as Genotype>::Genes;
39/// This is just a shortcut for `Population<<Self::Genotype as Genotype::Chromosome>`
40pub type FitnessPopulation<F> = Population<<<F as Fitness>::Genotype as Genotype>::Chromosome>;
41
42/// The fitness function, is implemented as a fitness method object.
43///
44/// Normally the fitness returns [`Some(FitnessValue)`](FitnessValue) for the chromosome, which can be minimized or
45/// maximized in the search strategy (e.g. [Evolve](crate::strategy::evolve::Evolve)) by providing the [FitnessOrdering].
46///
47/// If the fitness returns `None`, the chromosome is assumed invalid and taken last in the [selection](crate::select) phase (also when minimizing).
48///
49/// # User implementation
50///
51/// There are two possible levels to implement. At least one level needs to be implemented:
52/// * [`calculate_for_chromosome(...) -> Option<FitnessValue>`](Fitness::calculate_for_chromosome)
53/// * The standard situation, suits all strategies. Implementable with all Genotypes.
54/// * Standard [Genotype]s have [GenesOwner](crate::chromosome::GenesOwner) chromosomes. These
55/// chromosomes have a `genes` field, which can be read for the calculations.
56/// * non-standard [Genotype]s with [GenesPointer](crate::chromosome::GenesPointer) chromosomes.
57/// These chromosomes have don't have a `genes` field, so you need to retrieve the genes using
58/// [genotype.genes_slice(&chromosome)](crate::genotype::Genotype::genes_slice), which can then
59/// be read for the calculations. But for these types you usually don't want to reach this call
60/// level, see other level below
61/// * [`calculate_for_population(...) -> Vec<Option<FitnessValue>>`](Fitness::calculate_for_population)
62/// * *Only overwrite for matrix Genotypes (designed for possible GPU acceleration)*
63/// * If not overwritten, results in calling
64/// [calculate_for_chromosome](Fitness::calculate_for_chromosome) for each chromosome in the
65/// population. So it doesn't have to be implemented by default, but it is a possible point to
66/// intercept with a custom implementation where the whole population data is available.
67/// * Only for [Genotype] with [GenesPointer](crate::chromosome::GenesPointer) chromosomes. These
68/// chromosomes don't have a `genes` field to read, but a `row_id`. The matrix [Genotype] has a contiguous
69/// memory `data` field with all the data, which can be calculated in one go.
70/// * [DynamicMatrixGenotype](crate::genotype::DynamicMatrixGenotype)
71/// * [StaticMatrixGenotype](crate::genotype::StaticMatrixGenotype)
72/// * The order and length of the rows in the genotype data matrix needs to be preserved in the
73/// returned vector as it matches the row_id on the chromosome
74/// * The order and length of the population does not matter at all and will most likely not align.
75/// The population is provided, because the full genotype matrix data also contains untainted
76/// chromosomes which already have a fitness_score (and will not be updated). The results for
77/// these chromosomes will be ignored, thus these do not have to be recalculated, so knowing
78/// which ones might be relevant (or not). The order of the results still need to align, so if the
79/// calculation is skipped, a `None` value should be inserted in the results to keep the order
80/// and length aligned.
81///
82/// The strategies use different levels of calls in [Fitness]. So you cannot always just intercept at
83/// [calculate_for_population](Fitness::calculate_for_population) and be sure
84/// [calculate_for_chromosome](Fitness::calculate_for_chromosome) will not be called:
85///
86/// * Population level calculations (calling
87/// [calculate_for_chromosome](Fitness::calculate_for_chromosome) indirectly through
88/// [calculate_for_population](Fitness::calculate_for_population), if not overwritten)
89/// * [Evolve](crate::strategy::evolve::Evolve)
90/// * [HillClimb](crate::strategy::hill_climb::HillClimb) with [SteepestAscent](crate::strategy::hill_climb::HillClimbVariant::SteepestAscent)
91/// * Chromosome level calculations (calling
92/// [calculate_for_chromosome](Fitness::calculate_for_chromosome) directly, bypassing
93/// [calculate_for_population](Fitness::calculate_for_population) entirely)
94/// * [Permutate](crate::strategy::permutate::Permutate)
95/// * [HillClimb](crate::strategy::hill_climb::HillClimb) with [Stochastic](crate::strategy::hill_climb::HillClimbVariant::Stochastic)
96///
97/// Therefore, additionally, you might need to implement
98/// [calculate_for_chromosome](Fitness::calculate_for_chromosome) for
99/// [GenesPointer](crate::chromosome::GenesPointer) chromosomes. This is sometimes needed when
100/// testing out different strategies with different call levels. Problably no longer needed once
101/// settled on a strategy.
102///
103/// # Panics
104///
105/// [calculate_for_chromosome](Fitness::calculate_for_chromosome) has a default implementation which panics, because it doesn't need to
106/// be implemented for genotypes which implement [calculate_for_population](Fitness::calculate_for_population). Will panic if reached and not implemented.
107///
108/// # Example (calculate_for_chromosome, standard GenesOwner chromosome):
109/// ```rust
110/// use genetic_algorithm::fitness::prelude::*;
111///
112/// #[derive(Clone, Debug)]
113/// pub struct CountTrue;
114/// impl Fitness for CountTrue {
115/// type Genotype = BinaryGenotype;
116/// fn calculate_for_chromosome(
117/// &mut self,
118/// chromosome: &FitnessChromosome<Self>,
119/// _genotype: &FitnessGenotype<Self>
120/// ) -> Option<FitnessValue> {
121/// Some(chromosome.genes.iter().filter(|&value| *value).count() as FitnessValue)
122/// }
123/// }
124/// ```
125///
126/// # Example (calculate_for_population, static matrix calculation, GenesPointer chromosome):
127/// ```rust
128/// use genetic_algorithm::fitness::prelude::*;
129/// use genetic_algorithm::strategy::evolve::prelude::*;
130///
131/// #[derive(Clone, Debug)]
132/// pub struct SumStaticMatrixGenes;
133/// impl Fitness for SumStaticMatrixGenes {
134/// type Genotype = StaticMatrixGenotype<u16, 10, 100>;
135/// fn calculate_for_population(
136/// &mut self,
137/// population: &Population<StaticMatrixChromosome>,
138/// genotype: &FitnessGenotype<Self>,
139/// ) -> Vec<Option<FitnessValue>> {
140/// // pure matrix data calculation on [[T; N] M]
141/// // the order of the rows needs to be preserved as it matches the row_id on the chromosome
142/// // the order of the population does not matter at all and will most likely not align
143/// genotype
144/// .data
145/// .iter()
146/// .map(|genes| {
147/// genes
148/// .iter()
149/// .sum::<u16>() as FitnessValue
150/// })
151/// .map(Some)
152/// .collect()
153/// }
154/// }
155/// ```
156///
157/// # Example (calculate_for_population, dynamic matrix calculation, GenesPointer chromosome):
158/// ```rust
159/// use genetic_algorithm::fitness::prelude::*;
160/// use genetic_algorithm::strategy::evolve::prelude::*;
161///
162/// #[derive(Clone, Debug)]
163/// pub struct SumDynamicMatrixGenes;
164/// impl Fitness for SumDynamicMatrixGenes {
165/// type Genotype = DynamicMatrixGenotype<u16>;
166/// fn calculate_for_population(
167/// &mut self,
168/// population: &Population<DynamicMatrixChromosome>,
169/// genotype: &FitnessGenotype<Self>,
170/// ) -> Vec<Option<FitnessValue>> {
171/// // pure matrix data calculation on Vec<T> with genes_size step
172/// // the order of the rows needs to be preserved as it matches the row_id on the chromosome
173/// // the order of the population does not matter at all and will most likely not align
174/// genotype
175/// .data
176/// .chunks(genotype.genes_size())
177/// .map(|genes| {
178/// genes
179/// .iter()
180/// .sum::<u16>() as FitnessValue
181/// })
182/// .map(Some)
183/// .collect()
184/// }
185/// }
186/// ```
187///
188/// # Example (calculate_for_chromosome, matrix fall back, GenesPointer chromosome):
189/// *Note: For exploration purposes when switching stratgies a lot, not really used in final implementation*
190/// ```rust
191/// use genetic_algorithm::fitness::prelude::*;
192/// use genetic_algorithm::strategy::hill_climb::prelude::*;
193///
194/// #[derive(Clone, Debug)]
195/// pub struct SumStaticMatrixGenes;
196/// impl Fitness for SumStaticMatrixGenes {
197/// type Genotype = StaticMatrixGenotype<u16, 10, 100>;
198/// fn calculate_for_chromosome(
199/// &mut self,
200/// chromosome: &FitnessChromosome<Self>,
201/// genotype: &Self::Genotype,
202/// ) -> Option<FitnessValue> {
203/// let score = genotype.genes_slice(chromosome).iter().sum::<u16>();
204/// Some(score as FitnessValue)
205/// }
206/// }
207///
208pub trait Fitness: Clone + Send + Sync + std::fmt::Debug {
209 type Genotype: Genotype;
210 fn call_for_state_population<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
211 &mut self,
212 genotype: &Self::Genotype,
213 state: &mut S,
214 config: &C,
215 thread_local: Option<&ThreadLocal<RefCell<Self>>>,
216 ) {
217 let now = Instant::now();
218 self.call_for_population(
219 state.population_as_mut(),
220 genotype,
221 thread_local,
222 config.fitness_cache(),
223 );
224 state.add_duration(StrategyAction::Fitness, now.elapsed());
225 }
226 fn call_for_state_chromosome<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
227 &mut self,
228 genotype: &Self::Genotype,
229 state: &mut S,
230 config: &C,
231 ) {
232 if let Some(chromosome) = state.chromosome_as_mut() {
233 let now = Instant::now();
234 self.call_for_chromosome(chromosome, genotype, config.fitness_cache());
235 state.add_duration(StrategyAction::Fitness, now.elapsed());
236 }
237 }
238 /// Pass thread_local for external control of fitness state in multithreading
239 fn call_for_population(
240 &mut self,
241 population: &mut FitnessPopulation<Self>,
242 genotype: &Self::Genotype,
243 thread_local: Option<&ThreadLocal<RefCell<Self>>>,
244 cache: Option<&FitnessCache>,
245 ) {
246 let fitness_scores = self.calculate_for_population(population, genotype);
247 if fitness_scores.is_empty() {
248 if let Some(thread_local) = thread_local {
249 population
250 .chromosomes
251 .par_iter_mut()
252 .filter(|c| c.fitness_score().is_none())
253 .for_each_init(
254 || {
255 thread_local
256 .get_or(|| std::cell::RefCell::new(self.clone()))
257 .borrow_mut()
258 },
259 |fitness, chromosome| {
260 fitness.call_for_chromosome(chromosome, genotype, cache);
261 },
262 );
263 } else {
264 population
265 .chromosomes
266 .iter_mut()
267 .filter(|c| c.fitness_score().is_none())
268 .for_each(|c| self.call_for_chromosome(c, genotype, cache));
269 }
270 } else {
271 genotype.update_population_fitness_scores(population, fitness_scores);
272 }
273 }
274 fn call_for_chromosome(
275 &mut self,
276 chromosome: &mut FitnessChromosome<Self>,
277 genotype: &Self::Genotype,
278 cache: Option<&FitnessCache>,
279 ) {
280 let value = match (cache, chromosome.genes_hash()) {
281 (Some(cache), Some(genes_hash)) => {
282 if let Some(value) = cache.read(genes_hash) {
283 Some(value)
284 } else if let Some(value) = self.calculate_for_chromosome(chromosome, genotype) {
285 cache.write(genes_hash, value);
286 Some(value)
287 } else {
288 None
289 }
290 }
291 _ => self.calculate_for_chromosome(chromosome, genotype),
292 };
293 chromosome.set_fitness_score(value);
294 }
295 /// Optional interception point for client implementation.
296 ///
297 /// The order and length of the results need to align with the order and length of the genotype data matrix.
298 /// The order and length of the population does not matter at all and will most likely not align.
299 fn calculate_for_population(
300 &mut self,
301 _population: &FitnessPopulation<Self>,
302 _genotype: &Self::Genotype,
303 ) -> Vec<Option<FitnessValue>> {
304 Vec::new()
305 }
306 /// Optional interception point for client implementation
307 fn calculate_for_chromosome(
308 &mut self,
309 _chromosome: &FitnessChromosome<Self>,
310 _genotype: &Self::Genotype,
311 ) -> Option<FitnessValue> {
312 panic!("Implement calculate_for_chromosome for your Fitness (or higher in the call stack when using StaticMatrixGenotype)");
313 }
314}