fugue_evo/genome/
traits.rs

1//! Core genome traits
2//!
3//! This module defines the `EvolutionaryGenome` trait and related types. The
4//! classic evolutionary-computation layer is defined entirely in terms of this
5//! trait and carries **no** probabilistic-programming dependency; the fugue
6//! trace encoding lives in the separate
7//! [`TraceGenome`](crate::genome::trace_genome::TraceGenome) extension trait
8//! behind the `ppl` feature.
9
10use rand::Rng;
11use serde::{de::DeserializeOwned, Serialize};
12
13use crate::error::GenomeError;
14use crate::genome::bounds::MultiBounds;
15
16/// Core genome abstraction for evolutionary algorithms.
17///
18/// This trait defines the interface for evolvable solution representations.
19/// Genomes must be cloneable, serializable, and thread-safe.
20///
21/// Genomes that additionally support the fugue trace encoding (for the
22/// PPL-native inference layer) implement the
23/// [`TraceGenome`](crate::genome::trace_genome::TraceGenome) extension trait,
24/// available behind the `ppl` feature.
25pub trait EvolutionaryGenome: Clone + Send + Sync + Serialize + DeserializeOwned + 'static {
26    /// The allele type for individual genes
27    type Allele: Clone + Send;
28
29    /// The phenotype or decoded solution type
30    type Phenotype;
31
32    /// Decode genome into phenotype for fitness evaluation
33    fn decode(&self) -> Self::Phenotype;
34
35    /// Compute dimensionality for adaptive operators
36    fn dimension(&self) -> usize;
37
38    /// Generate a random genome within the given bounds.
39    ///
40    /// # Interpretation of `bounds`
41    ///
42    /// `MultiBounds` semantically describes a set of per-dimension numeric
43    /// `[min, max]` intervals, but only the real-valued genome types
44    /// ([`RealVector`](crate::genome::real_vector::RealVector),
45    /// [`DynamicRealVector`](crate::genome::dynamic_real_vector::DynamicRealVector))
46    /// actually consult the `min`/`max` fields. For every other built-in genome
47    /// type, **only `bounds.dimension()` (the *count* of intervals) is
48    /// consulted** — it is repurposed as a stand-in for the genome's structural
49    /// size, and the `min`/`max` values are ignored:
50    ///
51    /// - [`BitString`](crate::genome::bit_string::BitString): `dimension()` is
52    ///   the number of bits. Prefer
53    ///   [`BitString::generate_with_len`](crate::genome::bit_string::BitString::generate_with_len).
54    /// - [`Permutation`](crate::genome::permutation::Permutation): `dimension()`
55    ///   is the permutation length. Prefer
56    ///   [`Permutation::generate_with_len`](crate::genome::permutation::Permutation::generate_with_len).
57    /// - [`TreeGenome`](crate::genome::tree::TreeGenome): `dimension()` is
58    ///   remapped to a maximum tree depth. Prefer
59    ///   [`TreeGenome::generate_with_depth`](crate::genome::tree::TreeGenome::generate_with_depth).
60    ///
61    /// When you are not generating real-valued genomes, use the per-type honest
62    /// constructors listed above; they make the size/depth parameter explicit
63    /// instead of overloading `MultiBounds`.
64    fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self;
65
66    /// Get the genome's genes as a slice (for numeric genomes)
67    fn as_slice(&self) -> Option<&[Self::Allele]> {
68        None
69    }
70
71    /// Get the genome's genes as a mutable slice (for numeric genomes)
72    fn as_mut_slice(&mut self) -> Option<&mut [Self::Allele]> {
73        None
74    }
75
76    /// Distance metric between two genomes.
77    ///
78    /// This is a **required** method: there is deliberately no default
79    /// implementation, because a silent fallback (e.g. always `0.0`) would make
80    /// every pair of genomes look identical and silently break diversity-driven
81    /// mechanisms (niching, crowding, speciation).
82    ///
83    /// # Panics
84    ///
85    /// Implementations panic when the two genomes are structurally incompatible
86    /// (for fixed-structure genomes, this means different lengths / dimensions).
87    /// A structural mismatch is an invariant violation by the caller rather than
88    /// a recoverable condition. Use [`try_distance`](Self::try_distance) when a
89    /// fallible comparison is required.
90    ///
91    /// (Genome types whose comparison is meaningfully defined across differing
92    /// structures — e.g. [`DynamicRealVector`](crate::genome::dynamic_real_vector::DynamicRealVector),
93    /// which adds a length penalty, and [`TreeGenome`](crate::genome::tree::TreeGenome),
94    /// which compares size/depth — never panic.)
95    fn distance(&self, other: &Self) -> f64;
96
97    /// Fallible distance metric.
98    ///
99    /// Returns `Err(GenomeError::DimensionMismatch { .. })` (or another
100    /// [`GenomeError`]) when the two genomes are structurally incompatible,
101    /// instead of panicking as [`distance`](Self::distance) does. For genome
102    /// types whose distance is defined across differing structures this always
103    /// returns `Ok`.
104    fn try_distance(&self, other: &Self) -> Result<f64, GenomeError>;
105}
106
107/// Trait for genomes that can be represented as real vectors
108pub trait RealValuedGenome: EvolutionaryGenome<Allele = f64> {
109    /// Get the genes as a slice of f64 values
110    fn genes(&self) -> &[f64];
111
112    /// Get the genes as a mutable slice of f64 values
113    fn genes_mut(&mut self) -> &mut [f64];
114
115    /// Create from a vector of genes
116    fn from_genes(genes: Vec<f64>) -> Result<Self, GenomeError>;
117
118    /// Apply bounds to all genes
119    fn apply_bounds(&mut self, bounds: &MultiBounds) {
120        bounds.clamp_vec(self.genes_mut());
121    }
122}
123
124/// Trait for genomes that can be represented as bit strings
125pub trait BinaryGenome: EvolutionaryGenome<Allele = bool> {
126    /// Get the bits as a slice
127    fn bits(&self) -> &[bool];
128
129    /// Get the bits as a mutable slice
130    fn bits_mut(&mut self) -> &mut [bool];
131
132    /// Create from a vector of bits
133    fn from_bits(bits: Vec<bool>) -> Result<Self, GenomeError>;
134
135    /// Count the number of true bits (ones)
136    fn count_ones(&self) -> usize {
137        self.bits().iter().filter(|&&b| b).count()
138    }
139
140    /// Count the number of false bits (zeros)
141    fn count_zeros(&self) -> usize {
142        self.bits().iter().filter(|&&b| !b).count()
143    }
144}
145
146/// Trait for genomes that represent permutations
147pub trait PermutationGenome: EvolutionaryGenome<Allele = usize> {
148    /// Get the permutation as a slice
149    fn permutation(&self) -> &[usize];
150
151    /// Get the permutation as a mutable slice
152    fn permutation_mut(&mut self) -> &mut [usize];
153
154    /// Create from a vector of indices
155    fn from_permutation(perm: Vec<usize>) -> Result<Self, GenomeError>;
156
157    /// Check if the genome represents a valid permutation
158    fn is_valid_permutation(&self) -> bool {
159        let perm = self.permutation();
160        let n = perm.len();
161        if n == 0 {
162            return true;
163        }
164
165        let mut seen = vec![false; n];
166        for &idx in perm {
167            if idx >= n || seen[idx] {
168                return false;
169            }
170            seen[idx] = true;
171        }
172        true
173    }
174}
175
176// The trace-encoding surface (`TraceGenome`, `gene_address`, the `ChoiceValue`
177// re-export) lives in `crate::genome::trace_genome` behind the `ppl` feature.
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182    use serde::{Deserialize, Serialize};
183
184    // Mock genome for testing the trait
185    #[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
186    struct MockGenome {
187        genes: Vec<f64>,
188    }
189
190    impl EvolutionaryGenome for MockGenome {
191        type Allele = f64;
192        type Phenotype = Vec<f64>;
193
194        fn decode(&self) -> Self::Phenotype {
195            self.genes.clone()
196        }
197
198        fn dimension(&self) -> usize {
199            self.genes.len()
200        }
201
202        fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
203            let genes = bounds
204                .bounds
205                .iter()
206                .map(|b| rng.gen_range(b.min..=b.max))
207                .collect();
208            Self { genes }
209        }
210
211        fn as_slice(&self) -> Option<&[f64]> {
212            Some(&self.genes)
213        }
214
215        fn as_mut_slice(&mut self) -> Option<&mut [f64]> {
216            Some(&mut self.genes)
217        }
218
219        fn distance(&self, other: &Self) -> f64 {
220            self.try_distance(other)
221                .expect("distance: genomes have mismatched dimension")
222        }
223
224        fn try_distance(&self, other: &Self) -> Result<f64, GenomeError> {
225            if self.genes.len() != other.genes.len() {
226                return Err(GenomeError::DimensionMismatch {
227                    expected: self.genes.len(),
228                    actual: other.genes.len(),
229                });
230            }
231            Ok(self
232                .genes
233                .iter()
234                .zip(other.genes.iter())
235                .map(|(a, b)| (a - b).powi(2))
236                .sum::<f64>()
237                .sqrt())
238        }
239    }
240
241    impl RealValuedGenome for MockGenome {
242        fn genes(&self) -> &[f64] {
243            &self.genes
244        }
245
246        fn genes_mut(&mut self) -> &mut [f64] {
247            &mut self.genes
248        }
249
250        fn from_genes(genes: Vec<f64>) -> Result<Self, GenomeError> {
251            Ok(Self { genes })
252        }
253    }
254
255    #[test]
256    fn test_mock_genome_decode() {
257        let genome = MockGenome {
258            genes: vec![1.0, 2.0, 3.0],
259        };
260        assert_eq!(genome.decode(), vec![1.0, 2.0, 3.0]);
261    }
262
263    #[test]
264    fn test_mock_genome_dimension() {
265        let genome = MockGenome {
266            genes: vec![1.0, 2.0, 3.0],
267        };
268        assert_eq!(genome.dimension(), 3);
269    }
270
271    #[test]
272    fn test_mock_genome_generate() {
273        let mut rng = rand::thread_rng();
274        let bounds = MultiBounds::symmetric(5.0, 3);
275        let genome = MockGenome::generate(&mut rng, &bounds);
276        assert_eq!(genome.dimension(), 3);
277        for gene in genome.genes() {
278            assert!(*gene >= -5.0 && *gene <= 5.0);
279        }
280    }
281
282    #[test]
283    fn test_mock_genome_distance() {
284        let g1 = MockGenome {
285            genes: vec![0.0, 0.0, 0.0],
286        };
287        let g2 = MockGenome {
288            genes: vec![3.0, 4.0, 0.0],
289        };
290        assert_eq!(g1.distance(&g2), 5.0);
291    }
292
293    #[test]
294    fn test_real_valued_genome_apply_bounds() {
295        let mut genome = MockGenome {
296            genes: vec![-10.0, 0.0, 10.0],
297        };
298        let bounds = MultiBounds::symmetric(5.0, 3);
299        genome.apply_bounds(&bounds);
300        assert_eq!(genome.genes, vec![-5.0, 0.0, 5.0]);
301    }
302
303    #[cfg(feature = "ppl")]
304    impl crate::genome::trace_genome::TraceGenome for MockGenome {
305        fn to_trace(&self) -> fugue::Trace {
306            let mut trace = fugue::Trace::default();
307            for (i, &gene) in self.genes.iter().enumerate() {
308                trace.insert_choice(fugue::addr!("gene", i), fugue::ChoiceValue::F64(gene), 0.0);
309            }
310            trace
311        }
312
313        fn from_trace(trace: &fugue::Trace) -> Result<Self, GenomeError> {
314            let mut genes = Vec::new();
315            let mut i = 0;
316            while let Some(val) = trace.get_f64(&fugue::addr!("gene", i)) {
317                genes.push(val);
318                i += 1;
319            }
320            if genes.is_empty() {
321                return Err(GenomeError::InvalidStructure(
322                    "No genes found in trace".to_string(),
323                ));
324            }
325            Ok(Self { genes })
326        }
327    }
328
329    #[cfg(feature = "ppl")]
330    #[test]
331    fn test_mock_genome_to_trace() {
332        use crate::genome::trace_genome::TraceGenome;
333        let genome = MockGenome {
334            genes: vec![1.0, 2.0, 3.0],
335        };
336        let trace = genome.to_trace();
337
338        assert_eq!(trace.get_f64(&fugue::addr!("gene", 0)), Some(1.0));
339        assert_eq!(trace.get_f64(&fugue::addr!("gene", 1)), Some(2.0));
340        assert_eq!(trace.get_f64(&fugue::addr!("gene", 2)), Some(3.0));
341    }
342
343    #[cfg(feature = "ppl")]
344    #[test]
345    fn test_mock_genome_from_trace() {
346        use crate::genome::trace_genome::TraceGenome;
347        let mut trace = fugue::Trace::default();
348        trace.insert_choice(fugue::addr!("gene", 0), fugue::ChoiceValue::F64(1.5), 0.0);
349        trace.insert_choice(fugue::addr!("gene", 1), fugue::ChoiceValue::F64(2.5), 0.0);
350        trace.insert_choice(fugue::addr!("gene", 2), fugue::ChoiceValue::F64(3.5), 0.0);
351
352        let genome = MockGenome::from_trace(&trace).unwrap();
353        assert_eq!(genome.genes, vec![1.5, 2.5, 3.5]);
354    }
355
356    #[cfg(feature = "ppl")]
357    #[test]
358    fn test_mock_genome_trace_roundtrip() {
359        use crate::genome::trace_genome::TraceGenome;
360        let original = MockGenome {
361            genes: vec![1.0, 2.0, 3.0, 4.0, 5.0],
362        };
363        let trace = original.to_trace();
364        let recovered = MockGenome::from_trace(&trace).unwrap();
365        assert_eq!(original, recovered);
366    }
367
368    // Mock binary genome for testing
369    #[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
370    struct MockBinaryGenome {
371        bits: Vec<bool>,
372    }
373
374    impl EvolutionaryGenome for MockBinaryGenome {
375        type Allele = bool;
376        type Phenotype = Vec<bool>;
377
378        fn decode(&self) -> Self::Phenotype {
379            self.bits.clone()
380        }
381
382        fn dimension(&self) -> usize {
383            self.bits.len()
384        }
385
386        fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
387            let bits = (0..bounds.dimension()).map(|_| rng.gen()).collect();
388            Self { bits }
389        }
390
391        fn distance(&self, other: &Self) -> f64 {
392            self.try_distance(other)
393                .expect("distance: genomes have mismatched dimension")
394        }
395
396        fn try_distance(&self, other: &Self) -> Result<f64, GenomeError> {
397            if self.bits.len() != other.bits.len() {
398                return Err(GenomeError::DimensionMismatch {
399                    expected: self.bits.len(),
400                    actual: other.bits.len(),
401                });
402            }
403            Ok(self
404                .bits
405                .iter()
406                .zip(other.bits.iter())
407                .filter(|(a, b)| a != b)
408                .count() as f64)
409        }
410    }
411
412    #[cfg(feature = "ppl")]
413    impl crate::genome::trace_genome::TraceGenome for MockBinaryGenome {
414        fn to_trace(&self) -> fugue::Trace {
415            let mut trace = fugue::Trace::default();
416            for (i, &bit) in self.bits.iter().enumerate() {
417                trace.insert_choice(fugue::addr!("bit", i), fugue::ChoiceValue::Bool(bit), 0.0);
418            }
419            trace
420        }
421
422        fn from_trace(trace: &fugue::Trace) -> Result<Self, GenomeError> {
423            let mut bits = Vec::new();
424            let mut i = 0;
425            while let Some(val) = trace.get_bool(&fugue::addr!("bit", i)) {
426                bits.push(val);
427                i += 1;
428            }
429            if bits.is_empty() {
430                return Err(GenomeError::InvalidStructure(
431                    "No bits found in trace".to_string(),
432                ));
433            }
434            Ok(Self { bits })
435        }
436
437        fn trace_prefix() -> &'static str {
438            "bit"
439        }
440    }
441
442    impl BinaryGenome for MockBinaryGenome {
443        fn bits(&self) -> &[bool] {
444            &self.bits
445        }
446
447        fn bits_mut(&mut self) -> &mut [bool] {
448            &mut self.bits
449        }
450
451        fn from_bits(bits: Vec<bool>) -> Result<Self, GenomeError> {
452            Ok(Self { bits })
453        }
454    }
455
456    #[test]
457    fn test_binary_genome_count() {
458        let genome = MockBinaryGenome {
459            bits: vec![true, false, true, true, false],
460        };
461        assert_eq!(genome.count_ones(), 3);
462        assert_eq!(genome.count_zeros(), 2);
463    }
464
465    #[cfg(feature = "ppl")]
466    #[test]
467    fn test_binary_genome_trace_roundtrip() {
468        use crate::genome::trace_genome::TraceGenome;
469        let original = MockBinaryGenome {
470            bits: vec![true, false, true, false, true],
471        };
472        let trace = original.to_trace();
473        let recovered = MockBinaryGenome::from_trace(&trace).unwrap();
474        assert_eq!(original, recovered);
475    }
476
477    // Mock permutation genome for testing
478    #[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
479    struct MockPermGenome {
480        perm: Vec<usize>,
481    }
482
483    impl EvolutionaryGenome for MockPermGenome {
484        type Allele = usize;
485        type Phenotype = Vec<usize>;
486
487        fn decode(&self) -> Self::Phenotype {
488            self.perm.clone()
489        }
490
491        fn dimension(&self) -> usize {
492            self.perm.len()
493        }
494
495        fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
496            use rand::seq::SliceRandom;
497            let n = bounds.dimension();
498            let mut perm: Vec<usize> = (0..n).collect();
499            perm.shuffle(rng);
500            Self { perm }
501        }
502
503        fn distance(&self, other: &Self) -> f64 {
504            self.try_distance(other)
505                .expect("distance: genomes have mismatched dimension")
506        }
507
508        fn try_distance(&self, other: &Self) -> Result<f64, GenomeError> {
509            if self.perm.len() != other.perm.len() {
510                return Err(GenomeError::DimensionMismatch {
511                    expected: self.perm.len(),
512                    actual: other.perm.len(),
513                });
514            }
515            // Hamming-style positional disagreement (sufficient for the mock).
516            Ok(self
517                .perm
518                .iter()
519                .zip(other.perm.iter())
520                .filter(|(a, b)| a != b)
521                .count() as f64)
522        }
523    }
524
525    #[cfg(feature = "ppl")]
526    impl crate::genome::trace_genome::TraceGenome for MockPermGenome {
527        fn to_trace(&self) -> fugue::Trace {
528            let mut trace = fugue::Trace::default();
529            for (i, &val) in self.perm.iter().enumerate() {
530                trace.insert_choice(fugue::addr!("perm", i), fugue::ChoiceValue::Usize(val), 0.0);
531            }
532            trace
533        }
534
535        fn from_trace(trace: &fugue::Trace) -> Result<Self, GenomeError> {
536            let mut perm = Vec::new();
537            let mut i = 0;
538            while let Some(val) = trace.get_usize(&fugue::addr!("perm", i)) {
539                perm.push(val);
540                i += 1;
541            }
542            if perm.is_empty() {
543                return Err(GenomeError::InvalidStructure(
544                    "No permutation found in trace".to_string(),
545                ));
546            }
547            Ok(Self { perm })
548        }
549
550        fn trace_prefix() -> &'static str {
551            "perm"
552        }
553    }
554
555    impl PermutationGenome for MockPermGenome {
556        fn permutation(&self) -> &[usize] {
557            &self.perm
558        }
559
560        fn permutation_mut(&mut self) -> &mut [usize] {
561            &mut self.perm
562        }
563
564        fn from_permutation(perm: Vec<usize>) -> Result<Self, GenomeError> {
565            Ok(Self { perm })
566        }
567    }
568
569    #[test]
570    fn test_permutation_genome_is_valid() {
571        let valid = MockPermGenome {
572            perm: vec![2, 0, 1, 3],
573        };
574        assert!(valid.is_valid_permutation());
575
576        let invalid_dup = MockPermGenome {
577            perm: vec![0, 1, 1, 3],
578        };
579        assert!(!invalid_dup.is_valid_permutation());
580
581        let invalid_range = MockPermGenome {
582            perm: vec![0, 1, 5, 3],
583        };
584        assert!(!invalid_range.is_valid_permutation());
585
586        let empty = MockPermGenome { perm: vec![] };
587        assert!(empty.is_valid_permutation());
588    }
589
590    #[cfg(feature = "ppl")]
591    #[test]
592    fn test_permutation_genome_trace_roundtrip() {
593        use crate::genome::trace_genome::TraceGenome;
594        let original = MockPermGenome {
595            perm: vec![3, 1, 4, 0, 2],
596        };
597        let trace = original.to_trace();
598        let recovered = MockPermGenome::from_trace(&trace).unwrap();
599        assert_eq!(original, recovered);
600    }
601}
fugue_evo/genome/traits.rs

fugue_evo/genome/
traits.rs
