fugue_evo/genome/
traits.rs

1//! Core genome traits
2//!
3//! This module defines the `EvolutionaryGenome` trait and related types,
4//! with integration to Fugue PPL for probabilistic operations.
5
6use fugue::{addr, Address, Trace};
7
8// Re-export ChoiceValue for use in genome implementations
9pub use fugue::ChoiceValue;
10use rand::Rng;
11use serde::{de::DeserializeOwned, Serialize};
12
13use crate::error::GenomeError;
14use crate::genome::bounds::MultiBounds;
15
16/// Core genome abstraction with Fugue integration for evolutionary algorithms.
17///
18/// This trait defines the interface for evolvable solution representations,
19/// with explicit Fugue trace integration for probabilistic operations.
20/// Genomes must be cloneable, serializable, and thread-safe.
21///
22/// # Fugue Integration
23///
24/// The key insight is that Fugue's traces can represent genomes. Each gene
25/// is stored at an indexed address, enabling:
26/// - Trace-based mutation (selective resampling)
27/// - Trace-based crossover (merging parent traces)
28/// - Probabilistic interpretation of genetic operators
29pub trait EvolutionaryGenome: Clone + Send + Sync + Serialize + DeserializeOwned + 'static {
30    /// The allele type for individual genes
31    type Allele: Clone + Send;
32
33    /// The phenotype or decoded solution type
34    type Phenotype;
35
36    /// Convert genome to Fugue trace for probabilistic operations.
37    ///
38    /// Each gene is stored at an indexed address (e.g., "gene#0", "gene#1", ...),
39    /// enabling trace-based evolutionary operators.
40    fn to_trace(&self) -> Trace;
41
42    /// Reconstruct genome from Fugue trace after evolutionary operations.
43    ///
44    /// This is the inverse of `to_trace()`, extracting gene values from
45    /// the trace's choice map.
46    fn from_trace(trace: &Trace) -> Result<Self, GenomeError>;
47
48    /// Decode genome into phenotype for fitness evaluation
49    fn decode(&self) -> Self::Phenotype;
50
51    /// Compute dimensionality for adaptive operators
52    fn dimension(&self) -> usize;
53
54    /// Generate a random genome within the given bounds
55    fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self;
56
57    /// Get the genome's genes as a slice (for numeric genomes)
58    fn as_slice(&self) -> Option<&[Self::Allele]> {
59        None
60    }
61
62    /// Get the genome's genes as a mutable slice (for numeric genomes)
63    fn as_mut_slice(&mut self) -> Option<&mut [Self::Allele]> {
64        None
65    }
66
67    /// Distance metric between two genomes (default: 0.0)
68    fn distance(&self, _other: &Self) -> f64 {
69        0.0
70    }
71
72    /// Get the address prefix used for trace storage (default: "gene")
73    fn trace_prefix() -> &'static str {
74        "gene"
75    }
76}
77
78/// Trait for genomes that can be represented as real vectors
79pub trait RealValuedGenome: EvolutionaryGenome<Allele = f64> {
80    /// Get the genes as a slice of f64 values
81    fn genes(&self) -> &[f64];
82
83    /// Get the genes as a mutable slice of f64 values
84    fn genes_mut(&mut self) -> &mut [f64];
85
86    /// Create from a vector of genes
87    fn from_genes(genes: Vec<f64>) -> Result<Self, GenomeError>;
88
89    /// Apply bounds to all genes
90    fn apply_bounds(&mut self, bounds: &MultiBounds) {
91        bounds.clamp_vec(self.genes_mut());
92    }
93}
94
95/// Trait for genomes that can be represented as bit strings
96pub trait BinaryGenome: EvolutionaryGenome<Allele = bool> {
97    /// Get the bits as a slice
98    fn bits(&self) -> &[bool];
99
100    /// Get the bits as a mutable slice
101    fn bits_mut(&mut self) -> &mut [bool];
102
103    /// Create from a vector of bits
104    fn from_bits(bits: Vec<bool>) -> Result<Self, GenomeError>;
105
106    /// Count the number of true bits (ones)
107    fn count_ones(&self) -> usize {
108        self.bits().iter().filter(|&&b| b).count()
109    }
110
111    /// Count the number of false bits (zeros)
112    fn count_zeros(&self) -> usize {
113        self.bits().iter().filter(|&&b| !b).count()
114    }
115}
116
117/// Trait for genomes that represent permutations
118pub trait PermutationGenome: EvolutionaryGenome<Allele = usize> {
119    /// Get the permutation as a slice
120    fn permutation(&self) -> &[usize];
121
122    /// Get the permutation as a mutable slice
123    fn permutation_mut(&mut self) -> &mut [usize];
124
125    /// Create from a vector of indices
126    fn from_permutation(perm: Vec<usize>) -> Result<Self, GenomeError>;
127
128    /// Check if the genome represents a valid permutation
129    fn is_valid_permutation(&self) -> bool {
130        let perm = self.permutation();
131        let n = perm.len();
132        if n == 0 {
133            return true;
134        }
135
136        let mut seen = vec![false; n];
137        for &idx in perm {
138            if idx >= n || seen[idx] {
139                return false;
140            }
141            seen[idx] = true;
142        }
143        true
144    }
145}
146
147/// Helper function to create a gene address for trace storage
148pub fn gene_address(prefix: &str, index: usize) -> Address {
149    addr!(prefix, index)
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155    use serde::{Deserialize, Serialize};
156
157    // Mock genome for testing the trait
158    #[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
159    struct MockGenome {
160        genes: Vec<f64>,
161    }
162
163    impl EvolutionaryGenome for MockGenome {
164        type Allele = f64;
165        type Phenotype = Vec<f64>;
166
167        fn to_trace(&self) -> Trace {
168            let mut trace = Trace::default();
169            for (i, &gene) in self.genes.iter().enumerate() {
170                trace.insert_choice(addr!("gene", i), ChoiceValue::F64(gene), 0.0);
171            }
172            trace
173        }
174
175        fn from_trace(trace: &Trace) -> Result<Self, GenomeError> {
176            let mut genes = Vec::new();
177            let mut i = 0;
178            while let Some(val) = trace.get_f64(&addr!("gene", i)) {
179                genes.push(val);
180                i += 1;
181            }
182            if genes.is_empty() {
183                return Err(GenomeError::InvalidStructure(
184                    "No genes found in trace".to_string(),
185                ));
186            }
187            Ok(Self { genes })
188        }
189
190        fn decode(&self) -> Self::Phenotype {
191            self.genes.clone()
192        }
193
194        fn dimension(&self) -> usize {
195            self.genes.len()
196        }
197
198        fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
199            let genes = bounds
200                .bounds
201                .iter()
202                .map(|b| rng.gen_range(b.min..=b.max))
203                .collect();
204            Self { genes }
205        }
206
207        fn as_slice(&self) -> Option<&[f64]> {
208            Some(&self.genes)
209        }
210
211        fn as_mut_slice(&mut self) -> Option<&mut [f64]> {
212            Some(&mut self.genes)
213        }
214
215        fn distance(&self, other: &Self) -> f64 {
216            self.genes
217                .iter()
218                .zip(other.genes.iter())
219                .map(|(a, b)| (a - b).powi(2))
220                .sum::<f64>()
221                .sqrt()
222        }
223    }
224
225    impl RealValuedGenome for MockGenome {
226        fn genes(&self) -> &[f64] {
227            &self.genes
228        }
229
230        fn genes_mut(&mut self) -> &mut [f64] {
231            &mut self.genes
232        }
233
234        fn from_genes(genes: Vec<f64>) -> Result<Self, GenomeError> {
235            Ok(Self { genes })
236        }
237    }
238
239    #[test]
240    fn test_mock_genome_decode() {
241        let genome = MockGenome {
242            genes: vec![1.0, 2.0, 3.0],
243        };
244        assert_eq!(genome.decode(), vec![1.0, 2.0, 3.0]);
245    }
246
247    #[test]
248    fn test_mock_genome_dimension() {
249        let genome = MockGenome {
250            genes: vec![1.0, 2.0, 3.0],
251        };
252        assert_eq!(genome.dimension(), 3);
253    }
254
255    #[test]
256    fn test_mock_genome_generate() {
257        let mut rng = rand::thread_rng();
258        let bounds = MultiBounds::symmetric(5.0, 3);
259        let genome = MockGenome::generate(&mut rng, &bounds);
260        assert_eq!(genome.dimension(), 3);
261        for gene in genome.genes() {
262            assert!(*gene >= -5.0 && *gene <= 5.0);
263        }
264    }
265
266    #[test]
267    fn test_mock_genome_distance() {
268        let g1 = MockGenome {
269            genes: vec![0.0, 0.0, 0.0],
270        };
271        let g2 = MockGenome {
272            genes: vec![3.0, 4.0, 0.0],
273        };
274        assert_eq!(g1.distance(&g2), 5.0);
275    }
276
277    #[test]
278    fn test_real_valued_genome_apply_bounds() {
279        let mut genome = MockGenome {
280            genes: vec![-10.0, 0.0, 10.0],
281        };
282        let bounds = MultiBounds::symmetric(5.0, 3);
283        genome.apply_bounds(&bounds);
284        assert_eq!(genome.genes, vec![-5.0, 0.0, 5.0]);
285    }
286
287    #[test]
288    fn test_mock_genome_to_trace() {
289        let genome = MockGenome {
290            genes: vec![1.0, 2.0, 3.0],
291        };
292        let trace = genome.to_trace();
293
294        assert_eq!(trace.get_f64(&addr!("gene", 0)), Some(1.0));
295        assert_eq!(trace.get_f64(&addr!("gene", 1)), Some(2.0));
296        assert_eq!(trace.get_f64(&addr!("gene", 2)), Some(3.0));
297    }
298
299    #[test]
300    fn test_mock_genome_from_trace() {
301        let mut trace = Trace::default();
302        trace.insert_choice(addr!("gene", 0), ChoiceValue::F64(1.5), 0.0);
303        trace.insert_choice(addr!("gene", 1), ChoiceValue::F64(2.5), 0.0);
304        trace.insert_choice(addr!("gene", 2), ChoiceValue::F64(3.5), 0.0);
305
306        let genome = MockGenome::from_trace(&trace).unwrap();
307        assert_eq!(genome.genes, vec![1.5, 2.5, 3.5]);
308    }
309
310    #[test]
311    fn test_mock_genome_trace_roundtrip() {
312        let original = MockGenome {
313            genes: vec![1.0, 2.0, 3.0, 4.0, 5.0],
314        };
315        let trace = original.to_trace();
316        let recovered = MockGenome::from_trace(&trace).unwrap();
317        assert_eq!(original, recovered);
318    }
319
320    // Mock binary genome for testing
321    #[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
322    struct MockBinaryGenome {
323        bits: Vec<bool>,
324    }
325
326    impl EvolutionaryGenome for MockBinaryGenome {
327        type Allele = bool;
328        type Phenotype = Vec<bool>;
329
330        fn to_trace(&self) -> Trace {
331            let mut trace = Trace::default();
332            for (i, &bit) in self.bits.iter().enumerate() {
333                trace.insert_choice(addr!("bit", i), ChoiceValue::Bool(bit), 0.0);
334            }
335            trace
336        }
337
338        fn from_trace(trace: &Trace) -> Result<Self, GenomeError> {
339            let mut bits = Vec::new();
340            let mut i = 0;
341            while let Some(val) = trace.get_bool(&addr!("bit", i)) {
342                bits.push(val);
343                i += 1;
344            }
345            if bits.is_empty() {
346                return Err(GenomeError::InvalidStructure(
347                    "No bits found in trace".to_string(),
348                ));
349            }
350            Ok(Self { bits })
351        }
352
353        fn decode(&self) -> Self::Phenotype {
354            self.bits.clone()
355        }
356
357        fn dimension(&self) -> usize {
358            self.bits.len()
359        }
360
361        fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
362            let bits = (0..bounds.dimension()).map(|_| rng.gen()).collect();
363            Self { bits }
364        }
365
366        fn trace_prefix() -> &'static str {
367            "bit"
368        }
369    }
370
371    impl BinaryGenome for MockBinaryGenome {
372        fn bits(&self) -> &[bool] {
373            &self.bits
374        }
375
376        fn bits_mut(&mut self) -> &mut [bool] {
377            &mut self.bits
378        }
379
380        fn from_bits(bits: Vec<bool>) -> Result<Self, GenomeError> {
381            Ok(Self { bits })
382        }
383    }
384
385    #[test]
386    fn test_binary_genome_count() {
387        let genome = MockBinaryGenome {
388            bits: vec![true, false, true, true, false],
389        };
390        assert_eq!(genome.count_ones(), 3);
391        assert_eq!(genome.count_zeros(), 2);
392    }
393
394    #[test]
395    fn test_binary_genome_trace_roundtrip() {
396        let original = MockBinaryGenome {
397            bits: vec![true, false, true, false, true],
398        };
399        let trace = original.to_trace();
400        let recovered = MockBinaryGenome::from_trace(&trace).unwrap();
401        assert_eq!(original, recovered);
402    }
403
404    // Mock permutation genome for testing
405    #[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
406    struct MockPermGenome {
407        perm: Vec<usize>,
408    }
409
410    impl EvolutionaryGenome for MockPermGenome {
411        type Allele = usize;
412        type Phenotype = Vec<usize>;
413
414        fn to_trace(&self) -> Trace {
415            let mut trace = Trace::default();
416            for (i, &val) in self.perm.iter().enumerate() {
417                trace.insert_choice(addr!("perm", i), ChoiceValue::Usize(val), 0.0);
418            }
419            trace
420        }
421
422        fn from_trace(trace: &Trace) -> Result<Self, GenomeError> {
423            let mut perm = Vec::new();
424            let mut i = 0;
425            while let Some(val) = trace.get_usize(&addr!("perm", i)) {
426                perm.push(val);
427                i += 1;
428            }
429            if perm.is_empty() {
430                return Err(GenomeError::InvalidStructure(
431                    "No permutation found in trace".to_string(),
432                ));
433            }
434            Ok(Self { perm })
435        }
436
437        fn decode(&self) -> Self::Phenotype {
438            self.perm.clone()
439        }
440
441        fn dimension(&self) -> usize {
442            self.perm.len()
443        }
444
445        fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
446            use rand::seq::SliceRandom;
447            let n = bounds.dimension();
448            let mut perm: Vec<usize> = (0..n).collect();
449            perm.shuffle(rng);
450            Self { perm }
451        }
452
453        fn trace_prefix() -> &'static str {
454            "perm"
455        }
456    }
457
458    impl PermutationGenome for MockPermGenome {
459        fn permutation(&self) -> &[usize] {
460            &self.perm
461        }
462
463        fn permutation_mut(&mut self) -> &mut [usize] {
464            &mut self.perm
465        }
466
467        fn from_permutation(perm: Vec<usize>) -> Result<Self, GenomeError> {
468            Ok(Self { perm })
469        }
470    }
471
472    #[test]
473    fn test_permutation_genome_is_valid() {
474        let valid = MockPermGenome {
475            perm: vec![2, 0, 1, 3],
476        };
477        assert!(valid.is_valid_permutation());
478
479        let invalid_dup = MockPermGenome {
480            perm: vec![0, 1, 1, 3],
481        };
482        assert!(!invalid_dup.is_valid_permutation());
483
484        let invalid_range = MockPermGenome {
485            perm: vec![0, 1, 5, 3],
486        };
487        assert!(!invalid_range.is_valid_permutation());
488
489        let empty = MockPermGenome { perm: vec![] };
490        assert!(empty.is_valid_permutation());
491    }
492
493    #[test]
494    fn test_permutation_genome_trace_roundtrip() {
495        let original = MockPermGenome {
496            perm: vec![3, 1, 4, 0, 2],
497        };
498        let trace = original.to_trace();
499        let recovered = MockPermGenome::from_trace(&trace).unwrap();
500        assert_eq!(original, recovered);
501    }
502}
fugue_evo/genome/traits.rs

fugue_evo/genome/
traits.rs
