Crate ratio_genetic 

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

Documentation

Please refer to the crate’s documentation on docs.rs for more information on it’s usage.

Changelog

This repository keeps a CHANGELOG.md according to the recommendations by Keep a Changelog.

Contributions

Contributions are welcome! By submitting a contribution, you agree to license your work under the terms of the Mozilla Public License 2.0. Please ensure that your contributions adhere to the existing code style and include appropriate tests and documentation where applicable.

To get started:

1. Fork the repo
2. Create a new branch
3. Make your changes
4. Make sure you run just fix to adhere to the project’s formatting
5. Submit a merge request with a clear description of the changes

Licensing

This project is licensed under the Mozilla Public License 2.0. You are free to use, modify, and distribute this code, provided that any files you modify or create that are based on MPL-licensed files also remain under the MPL. You must include a copy of the license with the source and make the source code available when distributing binaries.

See the LICENSE file for the full license text.

Code examples both in the docstrings and rendered documentation thereof are free to use!

At Ratio, we are huge supporters of open-source code and the open-source community. In our Python projects we usually strive to use one of the (L)GPL flavors. These are difficult to pair with compiled codebases, however, which is where we see the MPL-2.0 as a great fit for our open-source Rust efforts. It’s a weak copyleft license that just protects the source as it is written and encourages changes to the crate’s source to be published accordingly. It’s sort of “automagically” implied and done right when cargo would pull in the source files to build with, as (the mentioning of) the license is included in the header of each file, and any binaries you generate with them are not of our concern from a distribution perspective.

Enjoy the code!

Modules

alias

Common type/trait aliases

convergence

Convergence procedures

crossover

Crossover procedures

evaluator

Fitness calculation

generator

Chromosomes generators

lineage

Lineage storage

mutator

Mutation procedures

recorder

Recorder functionality

selector

Selection procedures

simple

Simple Genetic Algorithm (SGA) procedures