genetic_algorithm/genotype/
unique.rs

1use super::builder::{Builder, TryFromBuilderError};
2use super::{EvolveGenotype, Genotype, HillClimbGenotype, MutationType, PermutateGenotype};
3use crate::allele::Allele;
4use crate::chromosome::{Chromosome, Genes};
5use crate::population::Population;
6use factorial::Factorial;
7use itertools::Itertools;
8use num::BigUint;
9use rand::distributions::{Distribution, Uniform};
10use rand::prelude::*;
11use std::fmt;
12use std::hash::Hash;
13
14pub type DefaultAllele = usize;
15
16/// Genes are a vector of values taken from the allele_list using clone(). The values don't need to
17/// be unique, they are only treated as positionally unique (never changed, only swapped). The
18/// genes_size is derived to be the same as allele_list length. On random initialization, the
19/// allele_list is shuffled to form the genes. Each pair of genes has an equal probability of
20/// mutating. If a pair of genes mutates, the values are swapped. Defaults to usize as item.
21///
22/// # Panics
23///
24/// Does not support gene or point crossover. Will panic when tried, but
25/// [EvolveBuilder](crate::strategy::evolve::EvolveBuilder) shouldn't allow this.
26/// Use [CrossoverClone](crate::crossover::CrossoverClone) or
27/// [CrossoverRejuvenate](crate::crossover::CrossoverRejuvenate) instead.
28///
29/// # Example (usize, default):
30/// ```
31/// use genetic_algorithm::genotype::{Genotype, UniqueGenotype};
32///
33/// let genotype = UniqueGenotype::builder()
34///     .with_allele_list((0..100).collect())
35///     .with_genes_hashing(true) // optional, defaults to true
36///     .with_chromosome_recycling(true) // optional, defaults to true
37///     .build()
38///     .unwrap();
39/// ```
40///
41/// # Example (struct)
42/// ```
43/// use genetic_algorithm::genotype::{Allele, Genotype, UniqueGenotype};
44///
45/// #[derive(Clone, Copy, PartialEq, Hash, Debug)]
46/// struct Item(pub u16, pub u16);
47/// genetic_algorithm::impl_allele!(Item);
48///
49/// let genotype = UniqueGenotype::builder()
50///     .with_allele_list(vec![
51///         Item(23, 505),
52///         Item(26, 352),
53///         Item(20, 458),
54///     ])
55///     .with_genes_hashing(true) // optional, defaults to true
56///     .with_chromosome_recycling(true) // optional, defaults to true
57///     .build()
58///     .unwrap();
59/// ```
60#[derive(Debug, Clone)]
61pub struct Unique<T: Allele + Hash = DefaultAllele> {
62    pub genes_size: usize,
63    pub allele_list: Vec<T>,
64    gene_index_sampler: Uniform<usize>,
65    pub seed_genes_list: Vec<Vec<T>>,
66    pub genes_hashing: bool,
67    pub chromosome_recycling: bool,
68}
69
70impl<T: Allele + Hash> TryFrom<Builder<Self>> for Unique<T> {
71    type Error = TryFromBuilderError;
72
73    fn try_from(builder: Builder<Self>) -> Result<Self, Self::Error> {
74        if builder.allele_list.is_none() {
75            if builder.allele_lists.is_some() {
76                Err(TryFromBuilderError(
77                    "UniqueGenotype requires with_allele_list (singular), not with_allele_lists",
78                ))
79            } else {
80                Err(TryFromBuilderError("UniqueGenotype requires allele_list"))
81            }
82        } else if builder.allele_list.as_ref().map(|o| o.is_empty()).unwrap() {
83            Err(TryFromBuilderError(
84                "UniqueGenotype requires non-empty allele_list",
85            ))
86        } else {
87            let allele_list = builder.allele_list.unwrap();
88            let genes_size = allele_list.len();
89            if builder.genes_size.is_some_and(|s| s != genes_size) {
90                return Err(TryFromBuilderError(
91                    "UniqueGenotype genes_size is derived from allele_list length, don't set it explicitly",
92                ));
93            }
94            Ok(Self {
95                genes_size,
96                allele_list: allele_list.clone(),
97                gene_index_sampler: Uniform::from(0..allele_list.len()),
98                seed_genes_list: builder.seed_genes_list,
99                genes_hashing: builder.genes_hashing,
100                chromosome_recycling: builder.chromosome_recycling,
101            })
102        }
103    }
104}
105
106impl<T: Allele + Hash> Unique<T> {
107    fn mutation_type(&self) -> &MutationType<T> {
108        &MutationType::Random
109    }
110}
111impl<T: Allele + Hash> Genotype for Unique<T> {
112    type Allele = T;
113
114    fn genes_size(&self) -> usize {
115        self.genes_size
116    }
117    fn sample_gene_index<R: Rng>(&self, rng: &mut R) -> usize {
118        self.gene_index_sampler.sample(rng)
119    }
120    fn sample_gene_indices<R: Rng>(
121        &self,
122        count: usize,
123        allow_duplicates: bool,
124        rng: &mut R,
125    ) -> Vec<usize> {
126        if allow_duplicates {
127            rng.sample_iter(self.gene_index_sampler)
128                .take(count)
129                .collect()
130        } else {
131            rand::seq::index::sample(rng, self.genes_size, count.min(self.genes_size)).into_vec()
132        }
133    }
134
135    fn mutate_chromosome_genes<R: Rng>(
136        &self,
137        number_of_mutations: usize,
138        allow_duplicates: bool,
139        chromosome: &mut Chromosome<Self::Allele>,
140        rng: &mut R,
141    ) {
142        if allow_duplicates {
143            for _ in 0..number_of_mutations {
144                let index1 = self.gene_index_sampler.sample(rng);
145                let index2 = self.gene_index_sampler.sample(rng);
146                chromosome.genes.swap(index1, index2);
147            }
148        } else {
149            rand::seq::index::sample(
150                rng,
151                self.genes_size,
152                (number_of_mutations * 2).min(self.genes_size),
153            )
154            .iter()
155            .tuples()
156            .for_each(|(index1, index2)| chromosome.genes.swap(index1, index2));
157        }
158        chromosome.reset_metadata(self.genes_hashing);
159    }
160    fn set_seed_genes_list(&mut self, seed_genes_list: Vec<Genes<Self::Allele>>) {
161        self.seed_genes_list = seed_genes_list;
162    }
163    fn seed_genes_list(&self) -> &Vec<Genes<Self::Allele>> {
164        &self.seed_genes_list
165    }
166    fn set_genes_hashing(&mut self, genes_hashing: bool) {
167        self.genes_hashing = genes_hashing;
168    }
169    fn random_genes_factory<R: Rng>(&self, rng: &mut R) -> Vec<T> {
170        if self.seed_genes_list.is_empty() {
171            let mut genes = self.allele_list.clone();
172            genes.shuffle(rng);
173            genes
174        } else {
175            self.seed_genes_list.choose(rng).unwrap().clone()
176        }
177    }
178    fn genes_capacity(&self) -> usize {
179        self.genes_size
180    }
181    fn genes_hashing(&self) -> bool {
182        self.genes_hashing
183    }
184    fn chromosome_recycling(&self) -> bool {
185        self.chromosome_recycling
186    }
187}
188
189impl<T: Allele + Hash> EvolveGenotype for Unique<T> {}
190impl<T: Allele + Hash> HillClimbGenotype for Unique<T> {
191    fn fill_neighbouring_population<R: Rng>(
192        &self,
193        chromosome: &Chromosome<Self::Allele>,
194        population: &mut Population<Self::Allele>,
195        _rng: &mut R,
196    ) {
197        (0..self.genes_size())
198            .tuple_combinations()
199            .for_each(|(first, second)| {
200                let mut new_chromosome = population.new_chromosome(chromosome);
201                new_chromosome.genes.swap(first, second);
202                new_chromosome.reset_metadata(self.genes_hashing);
203                population.chromosomes.push(new_chromosome);
204            });
205    }
206
207    fn neighbouring_population_size(&self) -> BigUint {
208        if self.genes_size < 2 {
209            return BigUint::ZERO;
210        }
211        let n = BigUint::from(self.genes_size);
212        let k = BigUint::from(2usize);
213
214        n.factorial() / (k.factorial() * (n - k).factorial())
215    }
216}
217
218impl<T: Allele + Hash> PermutateGenotype for Unique<T> {
219    fn chromosome_permutations_into_iter<'a>(
220        &'a self,
221        _chromosome: Option<&Chromosome<Self::Allele>>,
222    ) -> Box<dyn Iterator<Item = Chromosome<Self::Allele>> + Send + 'a> {
223        if self.seed_genes_list.is_empty() {
224            Box::new(
225                self.allele_list
226                    .clone()
227                    .into_iter()
228                    .permutations(self.genes_size())
229                    .map(Chromosome::new),
230            )
231        } else {
232            Box::new(
233                self.seed_genes_list
234                    .clone()
235                    .into_iter()
236                    .map(Chromosome::new),
237            )
238        }
239    }
240
241    fn chromosome_permutations_size(&self) -> BigUint {
242        if self.seed_genes_list.is_empty() {
243            BigUint::from(self.genes_size).factorial()
244        } else {
245            self.seed_genes_list.len().into()
246        }
247    }
248    fn allows_permutation(&self) -> bool {
249        true
250    }
251}
252
253impl<T: Allele + Hash> fmt::Display for Unique<T> {
254    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
255        writeln!(f, "genotype:")?;
256        writeln!(f, "  genes_size: {}", self.genes_size)?;
257        writeln!(f, "  mutation_type: {:?}", self.mutation_type())?;
258        writeln!(
259            f,
260            "  chromosome_permutations_size: {}",
261            self.chromosome_permutations_size_report()
262        )?;
263        writeln!(
264            f,
265            "  neighbouring_population_size: {}",
266            self.neighbouring_population_size_report()
267        )?;
268        writeln!(
269            f,
270            "  expected_number_of_sampled_index_duplicates: {}",
271            self.expected_number_of_sampled_index_duplicates_report()
272        )?;
273        writeln!(f, "  seed_genes: {:?}", self.seed_genes_list.len())
274    }
275}
genetic_algorithm/genotype/unique.rs

genetic_algorithm/genotype/
unique.rs
