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/// The type used for fitness scores. isize (not f64) enables equality checks needed for staleness
25/// detection. For float-based fitness, scale manually: `(score / precision) as FitnessValue`.
26pub type FitnessValue = isize;
27
28/// Convert a float score to [`FitnessValue`] with the given precision.
29///
30/// Shorthand for `(score / precision) as FitnessValue`.
31/// Accepts both f32 and f64 (and any type implementing `Into<f64>`).
32///
33/// # Example
34/// ```
35/// use genetic_algorithm::fitness::fitness_value;
36/// assert_eq!(fitness_value(3.14159_f32, 0.001_f32), 3141);
37/// assert_eq!(fitness_value(3.14159_f64, 0.001_f64), 3141);
38/// ```
39pub fn fitness_value(score: impl Into<f64>, precision: impl Into<f64>) -> FitnessValue {
40    (score.into() / precision.into()) as FitnessValue
41}
42
43/// Whether to maximize or minimize fitness scores. Default is Maximize.
44#[derive(Copy, Clone, Debug)]
45pub enum FitnessOrdering {
46    Maximize,
47    Minimize,
48}
49
50/// This is just a shortcut for `Self::Genotype`
51pub type FitnessGenotype<F> = <F as Fitness>::Genotype;
52/// This is just a shortcut for `Chromosome<<Self::Genotype as Genotype>::Allele>`
53pub type FitnessChromosome<F> = Chromosome<<<F as Fitness>::Genotype as Genotype>::Allele>;
54/// This is just a shortcut for `Vec<<Self::Genotype as Genotype>::Allele>`
55pub type FitnessGenes<F> = Vec<<<F as Fitness>::Genotype as Genotype>::Allele>;
56/// This is just a shortcut for `Population<<Self::Genotype as Genotype>::Allele>`
57pub type FitnessPopulation<F> = Population<<<F as Fitness>::Genotype as Genotype>::Allele>;
58
59/// The fitness function, is implemented as a fitness method object.
60///
61/// Normally the fitness returns [`Some(FitnessValue)`](FitnessValue) for the chromosome, which can be minimized or
62/// maximized in the search strategy (e.g. [Evolve](crate::strategy::evolve::Evolve)) by providing the [FitnessOrdering].
63///
64/// If the fitness returns `None`, the chromosome is assumed invalid and taken last in the [selection](crate::select) phase (also when minimizing).
65///
66/// # User implementation
67///
68/// You must implement [`calculate_for_chromosome(...) ->
69/// Option<FitnessValue>`](Fitness::calculate_for_chromosome) which calculates the fitness for a
70/// single chromosome. Chromosomes have a `genes` field, which can be read for the calculations.
71///
72/// Fitness uses &mut self for performance because it dominates the runtime. Preparing memory
73/// allocations on initialization and reusing them for each chromosome can really impact
74/// performance. For parallel evaluation, each thread gets its own clone via ThreadLocal.
75///
76/// # Example (calculate_for_chromosome, standard GenesOwner chromosome):
77/// ```rust
78/// use genetic_algorithm::fitness::prelude::*;
79///
80/// #[derive(Clone, Debug)]
81/// pub struct CountTrue;
82/// impl Fitness for CountTrue {
83///     type Genotype = BinaryGenotype;
84///     fn calculate_for_chromosome(
85///         &mut self,
86///         chromosome: &FitnessChromosome<Self>,
87///         _genotype: &FitnessGenotype<Self>
88///     ) -> Option<FitnessValue> {
89///         Some(chromosome.genes.iter().filter(|&value| *value).count() as FitnessValue)
90///     }
91/// }
92/// ```
93pub trait Fitness: Clone + Send + Sync + std::fmt::Debug {
94    type Genotype: Genotype;
95    fn call_for_state_population<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
96        &mut self,
97        genotype: &Self::Genotype,
98        state: &mut S,
99        config: &C,
100        thread_local: Option<&ThreadLocal<RefCell<Self>>>,
101    ) {
102        let now = Instant::now();
103        self.call_for_population(
104            state.population_as_mut(),
105            genotype,
106            thread_local,
107            config.fitness_cache(),
108        );
109        state.add_duration(StrategyAction::Fitness, now.elapsed());
110    }
111    fn call_for_state_chromosome<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
112        &mut self,
113        genotype: &Self::Genotype,
114        state: &mut S,
115        config: &C,
116    ) {
117        if let Some(chromosome) = state.chromosome_as_mut() {
118            let now = Instant::now();
119            self.call_for_chromosome(chromosome, genotype, config.fitness_cache());
120            state.add_duration(StrategyAction::Fitness, now.elapsed());
121        }
122    }
123    /// Pass thread_local for external control of fitness state in multithreading
124    fn call_for_population(
125        &mut self,
126        population: &mut FitnessPopulation<Self>,
127        genotype: &Self::Genotype,
128        thread_local: Option<&ThreadLocal<RefCell<Self>>>,
129        cache: Option<&FitnessCache>,
130    ) {
131        if let Some(thread_local) = thread_local {
132            population
133                .chromosomes
134                .par_iter_mut()
135                .filter(|c| c.fitness_score().is_none())
136                .for_each_init(
137                    || {
138                        thread_local
139                            .get_or(|| std::cell::RefCell::new(self.clone()))
140                            .borrow_mut()
141                    },
142                    |fitness, chromosome| {
143                        fitness.call_for_chromosome(chromosome, genotype, cache);
144                    },
145                );
146        } else {
147            population
148                .chromosomes
149                .iter_mut()
150                .filter(|c| c.fitness_score().is_none())
151                .for_each(|c| self.call_for_chromosome(c, genotype, cache));
152        }
153    }
154    fn call_for_chromosome(
155        &mut self,
156        chromosome: &mut FitnessChromosome<Self>,
157        genotype: &Self::Genotype,
158        cache: Option<&FitnessCache>,
159    ) {
160        let value = match (cache, chromosome.genes_hash()) {
161            (Some(cache), Some(genes_hash)) => {
162                if let Some(value) = cache.read(genes_hash) {
163                    Some(value)
164                } else if let Some(value) = self.calculate_for_chromosome(chromosome, genotype) {
165                    cache.write(genes_hash, value);
166                    Some(value)
167                } else {
168                    None
169                }
170            }
171            _ => self.calculate_for_chromosome(chromosome, genotype),
172        };
173        chromosome.set_fitness_score(value);
174    }
175    /// Must be implemented by client
176    fn calculate_for_chromosome(
177        &mut self,
178        chromosome: &FitnessChromosome<Self>,
179        genotype: &Self::Genotype,
180    ) -> Option<FitnessValue>;
181}
genetic_algorithm/fitness.rs

genetic_algorithm/
fitness.rs
