Crate ratio_genetic

Expand description

Ratio’s genetic algorithms library

Genetic algorithm implementations in the field of Dependency Structure Matrix (DSM) analysis. It’s currently in an Alpha state, so the code is all very much subject to change.

The library is setup according to the Strategy pattern.

The basic idea behind the Strategy pattern is that, given an algorithm solving a particular problem, we define only the skeleton of the algorithm at an abstract level, and we separate the specific algorithms’ implementation into different parts.

Genetic algorithms in the field of DSM analysis usually concern themselves with an optimal ordering of the given input DSM. Possible applications include both clustering and sequencing. For all implementations in this library, the “input in rows, feedback above diagonal” (IR/FAD) convention is followed. Usually only positive valued (f64 >=0.0) matrices are considered, where values indicate a dependency between the column (source) and row (target) of the matrix. This corresponds to a dependency between a source node and target node in a graph.

In clustering applications, one strives to find groups of nodes that have relatively strong connections (nonzero values in the DSM). This results in fitness functions that usually promote intra-cluster dependencies over inter-cluster dependencies.

In sequencing applications, one usually wants to minimize the potentially negative effect of feedback loops and promote feedforward effects. This results in fitness functions that penalize the number of upper triangle dependencies and try to push them as far to the bottom left of the lower triangle af possible.

The simple module includes a Simple Genetic Algorithm (SGA) trait and default implementation that does the bare minimum for a given number of generations of a given number of chromosomes. Alternatives for the key stages in a genetic algorithm (selection, crossover, and mutation) may be found in the respective modules.

Sequencing example

The following is an example that shows how to approach a sequencing problem.

use rand::thread_rng;
use nalgebra::{dmatrix, DMatrix};
use ratio_genetic::{
    convergence::ConvergenceNever,
    crossover::CrossoverIPX,
    evaluator::EvaluatorFeedbackMarks,
    generator::GeneratorRandomSequence,
    mutator::MutatorSwap,
    recorder::{FitnessStatistics, RecorderFitnessStatistics},
    selector::SelectorRoulette,
    simple::{SimpleGeneticAlgorithm, SimpleGeneticOperators, SimpleGeneticSettings},
};
// The source of randomness.
let mut rng = thread_rng();
// A DSM sequencing problem.
struct SequencingProblem<T: num_traits::Num> {
    matrix: DMatrix<T>,
}
impl<T: num_traits::Num> SimpleGeneticAlgorithm for SequencingProblem<T> {
    type Gene = usize; // Genes are sequence indices.
    type Fitness = usize; // Number of non-feedback marks (zeros) that we want to maximize.
    type Record = FitnessStatistics; // Type of record we want to keep for every generation.
}
// A problem instance where the ideal solution would be to reverse the ordering.
let sga = SequencingProblem::<usize> {
    matrix: dmatrix![
        0,1,0;
        0,0,1;
        0,0,0],
};
// Basic settings for the SGA.
let settings = SimpleGeneticSettings {
    n_genes: Some(sga.matrix.shape().0),
    n_chromosomes: Some(10), // 10 chromosomes or individuals in each generation.
    n_generations: Some(5),  // 5 generations after which we exit.
    n_records: None,         // Just keep records for all generations.
    n_hall_of_fame: Some(1), // keep only the best performing chromosome in a ranking.
    p_crossover: 0.3, // Probability of crossover applied to pair, replacing them with offspring.
    p_mutation: 0.05, // Probability for any chromosome be subject to mutation.
};
// Create operators and group them in a struct.
let mut generator = GeneratorRandomSequence::new();
let mut evaluator = EvaluatorFeedbackMarks::new(sga.matrix.to_owned(), 1);
let mut selector = SelectorRoulette::new();
let mut crossover = CrossoverIPX::new();
let mut mutator = MutatorSwap::new(0.05);
let mut convergence = ConvergenceNever::new();
let mut recorder = RecorderFitnessStatistics::new();
let mut operators = SimpleGeneticOperators::new(
    &mut generator,
    &mut evaluator,
    &mut recorder,
    &mut selector,
    &mut crossover,
    &mut mutator,
    &mut convergence,
);
// Fire the algorithm and print the best result for illustrative purposes.
let lineage = sga.execute(&mut rng, None, &settings, &mut operators);
let best = lineage.hall_of_fame.best().unwrap();
println!("{:?}: {:?}", best.genes, best.fitness);
// [2, 1, 0]: 3