genalg 0.1.0

A flexible, high-performance genetic algorithm library written in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

use crate::error::{GeneticError, Result};
use crate::evolution::Challenge;
use crate::phenotype::Phenotype;
use crate::rng::RandomNumberGenerator;

use super::LocalSearch;

/// A simulated annealing algorithm.
///
/// Simulated annealing is a probabilistic local search algorithm that allows
/// moves to worse solutions with a probability that decreases over time.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone)]
pub struct SimulatedAnnealing {
    max_iterations: usize,
    initial_temperature: f64,
    cooling_rate: f64,
}

impl SimulatedAnnealing {
    /// Creates a new simulated annealing algorithm with the given parameters.
    ///
    /// # Arguments
    ///
    /// * `max_iterations` - The maximum number of iterations to perform.
    /// * `initial_temperature` - The initial temperature.
    /// * `cooling_rate` - The cooling rate (between 0 and 1).
    ///
    /// # Returns
    ///
    /// A new simulated annealing algorithm.
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - `max_iterations` is 0
    /// - `initial_temperature` is not positive
    /// - `cooling_rate` is not between 0 and 1
    pub fn new(max_iterations: usize, initial_temperature: f64, cooling_rate: f64) -> Result<Self> {
        if max_iterations == 0 {
            return Err(GeneticError::Configuration(
                "Maximum iterations must be greater than 0".to_string(),
            ));
        }
        if initial_temperature <= 0.0 {
            return Err(GeneticError::Configuration(
                "Initial temperature must be positive".to_string(),
            ));
        }
        if !(0.0..=1.0).contains(&cooling_rate) {
            return Err(GeneticError::Configuration(
                "Cooling rate must be between 0.0 and 1.0".to_string(),
            ));
        }
        Ok(Self {
            max_iterations,
            initial_temperature,
            cooling_rate,
        })
    }
}

impl<P, C> LocalSearch<P, C> for SimulatedAnnealing
where
    P: Phenotype,
    C: Challenge<P>,
{
    fn search(&self, phenotype: &mut P, challenge: &C) -> bool {
        let mut current_solution = phenotype.clone();
        let mut best_solution = current_solution.clone();
        let mut current_score = challenge.score(&current_solution);
        let mut best_score = current_score;
        let mut temperature = self.initial_temperature;
        let mut rng = RandomNumberGenerator::new();

        for _ in 0..self.max_iterations {
            let mut neighbor = current_solution.clone();
            neighbor.mutate(&mut rng);
            let neighbor_score = challenge.score(&neighbor);

            let accept = if neighbor_score > current_score {
                true
            } else {
                let delta = neighbor_score - current_score;
                let probability = (delta / temperature).exp();
                let random: f64 = rng.fetch_uniform(0.0, 1.0, 1)[0] as f64;
                random < probability
            };

            if accept {
                current_solution = neighbor;
                current_score = neighbor_score;

                if current_score > best_score {
                    best_solution = current_solution.clone();
                    best_score = current_score;
                }
            }

            // Prevent temperature from reaching 0 too soon
            temperature *= self.cooling_rate.max(0.0001);
        }

        if best_score > challenge.score(phenotype) {
            *phenotype = best_solution;
            return true;
        }

        false
    }
}