Radiate is a parallel genetic programming engine capable of evolving solutions to many problems as well as training learning algorithms.

Overview

Radiate

Build Status Crates.io

Coming from Evolutionary Radiation.

Evolutionary radiation is a rapid increase in the number of species with a common ancestor, characterized by great ecological and morphological diversity - Pascal Neige.

Radiate is a parallel genetic programming engine capable of evolving solutions to many problems as well as training learning algorithms. By separating the the evolutionary process from the object being evolved, users can evolve any defined structure. The algorithm follows an evolutionary process through speciation which allows structures to optimize within their own niche.

Radiate exposes three traits to the user which must be implemented (full simple implementation below):

  1. Genome
    Genome wraps the structure to be evolved and makes the user implement two necessary functions and an optional one. Distance and crossover must be implemented but base is optional (depending on how the user chooses to fill the population).
  2. Environment
    Environment represents the evolutionary environment for the genome, which means it can contain simple statistics for the population's evolution, or parameters for crossover and distance. Internally it is wrapped in a mutable thread-safe pointer so it is not intended to be shared for each genome, but rather exist only once per population. Environment requires no implementations of its one function, however depending on the use case environment exposes a function called reset which is intended to 'reset' the environment.
  3. Problem
    Problem is what gives a genome its fitness score. It requires two implemented functions: empty and solve. Empty is required and should return a base problem (think new()). Solve takes a genome and returns that genome's fitness score, so this is where the analysis of the current state of the genome occurs.

Radiate also comes with one model already built in and another one available for use on crates.io. Those being radiate_matrix_tree and NEAT, radiate_matrix_tree is available on crates.io and NEAT comes prepackaged with radiate.

NEAT

Also known as Neuroevolution of Augmented Topologies, is the algorithm described by Kenneth O. Stanley in this paper. This NEAT implementation also includes a backpropagation function which operates much like traditional neural networks which propagate the input error back through the network to adjust the weights. In pair with the evolution engine, this can produce very nice and quick results. NEAT lets the use define how the network will be constructed, whether that be in a traditional neural network fashion where layers are stacked next to each other or with evolutionary topologies as explained in the paper. This means NEAT can be used in an evolutionary sense, through forward propagation and back propagation, or any combination of the two. There are examples of both in /examples. more color on Neat in radiate/src/models/

Radiate also supports off-machine training where you can set up a problem to solve on one machine, then send the parameters to it from another through Radiate Web.

Setup

The population is pretty easy to set up assuming the all traits have been implemented. The population is a higher abstraction to keep track of variables used during evolution but not needed within an epoch - things like the problem, solution, printing to the screen etc. A new population is filled initially with default settings:

pub fn new() -> Self {   
    Population {
        // define the number of members to participate in evolution and be injected into the current generation
        size: 100,
        // determine if the species should be aiming for a specific number of species by adjusting the distance threshold
        dynamic_distance: false,
        // debug_progress is only used to print out some information from each generation
        // to the console during training to get a glimpse of what is going on
        debug_progress: false,
        // create a new config to help the speciation of the population
        config: Config::new(),
        // create a new empty generation to be passed down through the population 
        curr_gen: Generation::<T, E>::new(),
        // keep track of fitness score stagnation through the population
        stagnation: Stagnant::new(0, Vec::new()),
        // Arc<Problem> so the problem can be sent between threads safely without duplicating the problem, 
        // if the problem gets duplicated every time, a supervised learning problem with a lot of data could take up a large amount of memory
        solve: Arc::new(P::empty()),
        // create new solver settings which will hold the specific settings for the defined solver 
        // that will allow the structure to evolve through generations
        environment: Arc::new(RwLock::new(E::default())),
        // determine which genomes will live on and pass down to the next generation
        survivor_criteria: SurvivalCriteria::Fittest,
        // determine how to pick parents to reproduce
        parental_criteria: ParentalCriteria::BiasedRandom
    }
}

Example

A quick and easy example of implementing all the needed traits and running the genetic engine to generate a string print "hello world!". There are examples of how to run a Neat neural network in radiate/src/models/. To run this:

git clone https://github.com/pkalivas/radiate.git
cd radiate
cargo build --verbose && cargo run --bin helloworld

On my computer (Windows 10, x64-based, i7-7700 @ 4.20GHz, 32GB RAM) this finishes in less than half a second.

extern crate radiate;
extern crate rand;

use std::error::Error;
use std::time::Instant;
use std::sync::{Arc, RwLock};
use rand::Rng;
use radiate::prelude::*;

fn main() -> Result<(), Box<dyn Error>> {
    let thread_time = Instant::now();
    let (top, _) = Population::<Hello, HelloEnv, World>::new()
        .size(100)
        .populate_base()
        .dynamic_distance(true)
        .stagnation(10, vec![Genocide::KillWorst(0.9)])
        .configure(Config {
            inbreed_rate: 0.001,
            crossover_rate: 0.75,
            distance: 0.5,
            species_target: 5
        })
        .run(|model, fit, num| {
            println!("Generation: {} score: {:.3?}\t{:?}", num, fit, model.as_string());
            fit == 12.0 || num == 500
        })?;
        
    println!("\nTime in millis: {}, solution: {:?}", thread_time.elapsed().as_millis(), top.as_string());
    Ok(())
}

Now create the problem which holds the target and actually scores the solvers. Note that the target data isn't being copied for each solver.

pub struct World { target: Vec<char> }

impl World {
    pub fn new() -> Self {
        World {
            target: vec!['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '!']
        }
    }
}

impl Problem<Hello> for World {

    fn empty() -> Self { World::new() }

    fn solve(&self, model: &mut Hello) -> f32 {
        let mut total = 0.0;
        for (index, letter) in self.target.iter().enumerate() {
            if letter == &model.data[index] {
                total += 1.0;
            }
        }
        total        
    }
}

Now define an environment to hold global data for crossover and distance, things like record/stat keeping, crossover probabilities, really anything that is needed globally is held in this.

#[derive(Debug, Clone)]
pub struct HelloEnv {
    pub alph: Vec<char>,
}

impl HelloEnv {
    pub fn new() -> Self {
        HelloEnv {
            alph: vec!['!', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'], // now i know my abcs..
        }
    }
}

/// implement Environment and Default for the HelloEnv, Environment is there in case you want the environment to be dynamic
impl Envionment for HelloEnv {}
impl Default for HelloEnv {
    fn default() -> Self {
        Self::new()
    }
}

Finally, define a solver. This is type 'Genome' in the evolutionary process and makes up the population of each generation.

#[derive(Debug, Clone, PartialEq)]
pub struct Hello {
    pub data: Vec<char>
}

impl Hello {
    pub fn new(alph: &[char]) -> Self {
        let mut r = rand::thread_rng();
        Hello { 
            data: (0..12)
                .map(|_| alph[r.gen_range(0, alph.len())])
                .collect() 
        }
    }

    pub fn as_string(&self) -> String {
        self.data
            .iter()
            .map(|x| String::from(x.to_string()))
            .collect::<Vec<_>>()
            .join("")
    }
}

/// implement genome for Hello
impl Genome<Hello, HelloEnv> for Hello {

    // the first parent is always going to be the most fit parent
    fn crossover(parent_one: &Hello, parent_two: &Hello, env: &Arc<RwLock<HelloEnv>>, crossover_rate: f32) -> Option<Hello> {
        let params = env.read().unwrap();
        let mut r = rand::thread_rng();
        let mut new_data = Vec::new();
        
        if r.gen::<f32>() < crossover_rate {
            for (one, two) in parent_one.data.iter().zip(parent_two.data.iter()) {
                if one != two {
                    new_data.push(*one);
                } else {
                    new_data.push(*two);
                }
            }
        } else {
            new_data = parent_one.data.clone();
            let swap_index = r.gen_range(0, new_data.len());
            new_data[swap_index] = params.alph[r.gen_range(0, params.alph.len())];
        }
        Some(Hello { data: new_data })
    }

    fn distance(one: &Hello, two: &Hello, _: &Arc<RwLock<HelloEnv>>) -> f32 {
        let mut total = 0_f32;
        for (i, j) in one.data.iter().zip(two.data.iter()) {
            if i == j {
                total += 1_f32;
            }
        }
        one.data.len() as f32 / total
    }

    fn base(env: &mut HelloEnv) -> Hello {
        Hello::new(&env.alph)
    }
}

The result looks something like this when running on the command line:

Generation: 100 score: 8.000    "!eulozworlde"
Generation: 101 score: 8.000    "!eulozworlde"
Generation: 102 score: 8.000    "!eulozworlde"
Generation: 103 score: 8.000    "!eulozworlde"
Generation: 104 score: 8.000    "!eulozworlde"
Generation: 105 score: 9.000    "heulozworlde"
Generation: 106 score: 9.000    "heulozworlde"
Generation: 107 score: 9.000    "heulozworlde"
Generation: 108 score: 9.000    "heulozworlde"
Generation: 109 score: 9.000    "heulozworlde"
Generation: 110 score: 9.000    "heulozworlde"
Generation: 111 score: 9.000    "heulozworlde"
Generation: 112 score: 10.000   "heulo worlde"
Generation: 113 score: 10.000   "heulo worlde"
Generation: 114 score: 10.000   "heulo worlde"
Generation: 115 score: 10.000   "heulo worlde"
Generation: 116 score: 10.000   "heulo worlde"
Generation: 117 score: 10.000   "heulo worlde"
Generation: 118 score: 10.000   "heulo worlde"
Generation: 119 score: 10.000   "heulo worlde"
Generation: 120 score: 11.000   "hello worlde"
Generation: 121 score: 11.000   "hello worlde"
Generation: 122 score: 11.000   "hello worlde"
Generation: 123 score: 11.000   "hello worlde"
Generation: 124 score: 11.000   "hello worlde"
Generation: 125 score: 11.000   "hello worlde"
Generation: 126 score: 12.000   "hello world!"

Time in millis: 349, solution: "hello world!"

Right now there are four examples, just run "cargo run --bin (desired example name)" to run any of them

  1. xor-neat
  2. xor-neat-backprop
  3. lstm-neat
  4. helloworld

Create a Population

The initial generation in the population can be created in four different ways depending on the user's use case. The examples show different ways of using them.

  1. populate_gen - Give the population an already constructed Generation struct.
  2. populate_base - Create a generation of Genomes from the Genome's base function.
  3. populate_vec - Take a vec and populate the generation from the Genomes in the vec.
  4. populate_clone - Given a single Genome, clone it size times and create a generation from the clones.

Speciation

Because the engine is meant to evolve Genomes through speciation, the Config struct is meant to hold parameters for the speciation of the population, adjusting these will change the way the Genomes are split up within the population and thus drive the discovery of new Genomes through crossover and mutation.

Genocide

During evolution it can be common for either the population or specific species to become stagnant or stuck at a certain point in the problem space. To break out of this, population allows the user to define a number of stagnant generations until a 'genocide' will occur. These genocide options can be found in genocide.rs and are simply ways to clean the population to give the genomes an opportunity to breathe and evolve down a new path in the problem space.

pub enum Genocide {
    KeepTop(usize),
    KillWorst(f32),
    KillRandom(f32),
    KillOldestSpecies(usize)
}

This is definitely an area which can be improved in the algorithm.

Versions

1.5.57 - Major improvements to the Dense/DensePool layers. Before the improvement the benchmark took about 1.5 minutes to run. With the improvements it finishes in about 1.5 seconds.

1.1.55 - Removed unsafe code and fixed memory leak in evtree. Refactored Evtree to be generic, moving neural network logic to be separate. Cleaned up send/sync impls.

1.1.52 - Added recurrent neurons for NEAT. Note - this is also only viable for evolution (I will focus on implementing backprop for recurrent neurons and GRU layers next - I'm working on some other projects that require recurrent evolution neurons as of now). This can be configured in the NeatEnvironment settings where the % change of adding a recurrent neuron can be added. 0.0 would mean no recurrent neurons are added, where 1.0 would mean every new neuron is recurrent. Example in radiate/src/models/.

1.1.5 - Added minimal support for GRU layer (Gated Recurrent Unit). GRU is only viable for evolution, NOT backprop, yet. Your program will panic! if a network with a gru layer is used during backprop, if a memory cell is needed for backprop purposes use the LSTM option for now. Also, cleaned up some code and optimized certain points to run a bit quicker. Evtree has been moved to it's own separate crate called radiate_matrix_tree and is available on crates.io.

1.1.3 - Adding support for Radiate Web so training Radiate can be done on a different machine.

1.1.2 - For forward and backward passes of NEAT, gated propagation in LSTM layers is now run in parallel which cuts training times in half. Changed the readme to be a full implementation of the engine which is a little more helpful for setting everything up. Added another readme file to radiate/src/models/ which gives examples of setting up a NEAT neural network.

1.1.1 - Fixed dumb bug in NEAT which was causing a error in backprop.

1.0.9 - As of 1/10/2020 all versions after 1.0.9 require the nightly toolchain Added serialization and deserialization to NEAT model through serde integration - serializing trait objects requires nightly crates for now.

Comments
  • Make population training more flexible and idea for a more powerful GA server.

    Make population training more flexible and idea for a more powerful GA server.

    Right now the Population has full control over training/testing each member in a generation. I would like to have more control over how each member of a generation is tested against the problem.

    The reason is to be able to make a server that just manages the genomes/populations with many worker computers doing the testing of each generation's members against the problem. The workers would request a member/problem pair from the server, evaluate that member against the problem and return the fitness score back to the server. The server could keep a track of Genomes & Problems in a database. Similar problems (same basic code but different inputs) could be trained faster by re-using genes from high scoring Genomes.

    The current logic is like this:

    1. Create Population for a set of Genome, Environment and Problem.
    2. Set evolution parameters.
    3. Run evolution over population with callback for when each generation is finished.

    I would like to split the Population::run() and Population::train() methods so an application can do the following:

    1. Create/setup population like steps 1 & 2 above.
    2. Instead of calling run() get the current list of members from the population.
    3. Process those members against the Problem (this might include offloading the work to workers over the network).
    4. Once all members have been evaluated and a fitness score has been collected, call into the Population with the fitness scores to end the current generation. This would be like the Population::train() method, just skipping the call to Generation::optimize() and setting each members fitness.
    5. Get the end of generation results and decide if another generation needs to be tested (loop to step 2).
    opened by Neopallium 12
  • Linear Algebra

    Linear Algebra

    Was it an active decision to not use linear algebra for neural network forward-propagation and the like? I would assume it would speed up the computations significantly. Crates like nalgebra would present themselves as good candidates for such an implementation.

    If it was a decision, what was the motivation? Could it be that you can't really use linear algebra for NEAT (I'm not really familiar with how NEAT works)?

    opened by LU15W1R7H 7
  • What does Lstm mean for this crate?

    What does Lstm mean for this crate?

    I know Lstm is a variant of RNN in the context of neural network of machine learning. And in the original NEAT paper, the author did mention a kind of RNN, with which the game double pole is solved----the RNN here is not what we refer to in the context of machine learning, right?

    But what does lstm mean in the context of NEAT for this crate? Does it mean that NEAT could generate lstm structure (like in this paper), and with which could solve non-Markov decision problem?

    opened by dbsxdbsx 6
  • NEAT Autoencoder / embedding?

    NEAT Autoencoder / embedding?

    Hello,

    I'd like to evolve a network with a topological constraint for it's hidden layers.

    In a dense network this would be some middle layer that forces the reduction of the dimensionality of the information.

    In NEAT I'm not sure what this would mean, as the network topology has so much more freedom.

    Is this possible in general? If so, can this be accomplished using radiate? I'm not very familiar with the library, just only getting started.

    Thank you!

    opened by wbrickner 3
  • Documentation for Config fields

    Documentation for Config fields

    I'm playing around with radiate, and I'm a bit confused as to what the population config means. E.g. how does distance impact my performance? Where is it used? What does species_target mean during an optimization?

    Thanks for the library, it was really easy to get started and get some results!

    opened by rsdy 2
  • 26x - 100x performance improvement

    26x - 100x performance improvement

    I have made major improvements to the Dense/DensePool layers.

    The first commit add a benchmark for NEAT network with Dense/DensePool layers.

    Before the improvement the benchmark takes about 1.5 minutes to run. With the improvements it finishes in about 1.5 seconds.

    opened by Neopallium 2
  • Meaning of `.reset()`?

    Meaning of `.reset()`?

    What does .reset() method do on Neat struct?

    I'd like to ensure my understanding is correct, as the documentation is a little unclear.

    My real goal is to remove any previous state that may be retained in the network from previous evaluations / forward passes. This ensures there is no chance of information leakage between successive trials (fitness measurements).

    Will the .reset() method do this?

    Thank you!

    opened by wbrickner 1
  • NEAT : function solve

    NEAT : function solve

    Hi,

    I would perform a simple regression using NEAT. So, NEAT do maximization (i.e preserves genomes with high fitness) or the opposite ?

    Kind regards.

    opened by SaadDAHMANI 1
  • Fix docs, refactor

    Fix docs, refactor

    I went through everything quickly and fixed most of the many spelling errors, I believe, plus some other smaller doc improvements.

    Misspelled parts of the API have been renamed (with the old one left over as deprecated to keep backwards compatibility).

    There's also a refactoring in here: Using slices (&[]) instead of &Vec for input values, which is a general convention in Rust and more general since &Vec derefs to a slice automatically. Sadly I couldn't change this in the Layer trait as well since that would be a breaking change for users. I can add that as well if you like, though, the commit is done already.

    There should be no breaking changes in this PR.

    opened by rkarp 1
  • Remove almost all unsafe code and fixed a memory leak in `Evtree`

    Remove almost all unsafe code and fixed a memory leak in `Evtree`

    The only unsafe left is in the IterMut and the parent references. Down to only 7 unsafe usages in radiate_matrix_evtree crate and no unsafe in the other crates.

    Split Evtree so that the tree code is now generic and separate from the NeuralNetwork & Genome logic.

    Fixed the level order iterator (it was returning all left node first) and added some unit tests to test the iterators.

    The only way to remove the remaining unsafe code would be to use something like Rc<RefCell<>> and Weak references for the parent.

    opened by Neopallium 1
  • Cleanups, Formatting, updated dependencies

    Cleanups, Formatting, updated dependencies

    These are some more changes which do not change the functionality but the code is cleaner. Some are questions of aesthetics and readability(for example return vs leaving out the ';' at the end of the line). So some edits may be necessary to suit the style of the project.

    opened by Nereuxofficial 0
Owner
kalivas
kalivas
Rust implementation of real-coded GA for solving optimization problems and training of neural networks

revonet Rust implementation of real-coded genetic algorithm for solving optimization problems and training of neural networks. The latter is also know

Yury Tsoy 19 Aug 11, 2022
A browser app that evolves vehicles using genetic algorithms, written in Rust and Bevy

Vehicle Evolver Deluxe This is a simulation that uses AI (to be specific: genetic algorithms) to try to build better and better vehicles. The vehicles

null 95 Dec 26, 2022
Genetic Algorithms Library

genx genx provides modular building blocks to run simulations of optimization and search problems using Genetic Algorithms (GA). The vision for genx i

Lakshya Singh 29 Aug 9, 2022
This library provides implementations of many algorithms and data structures that are useful for bioinformatics.

This library provides implementations of many algorithms and data structures that are useful for bioinformatics. All provided implementations are rigorously tested via continuous integration.

Rust-Bio 1.2k Dec 26, 2022
Linear Programming for Rust, with an user-friendly API. This crate allows modeling LP problems, and let's you solve them with various solvers.

good_lp A Linear Programming modeler that is easy to use, performant with large problems, and well-typed. use good_lp::{variables, variable, coin_cbc,

Rust Operations Research 101 Dec 27, 2022
Execute genetic algorithm (GA) simulations in a customizable and extensible way.

genevo genevo provides building blocks to run simulations of optimization and search problems using genetic algorithms (GA). The vision for genevo is

Innoave 110 Dec 21, 2022
Genetic Algorithm library in Rust

RsGenetic Summary and Features RsGenetic is a framework for executing genetic algorithms in Rust. It is designed to have a simple but modular API. Exa

Mathieu De Coster 74 Dec 27, 2022
Example of a genetic algorithm in Rust and Python

Example of a genetic algorithm in Rust and Python Monkey typewriter Finding the phrase 'To be or not to be. That is the question.' Inspired by the exa

sotrh 2 Jan 27, 2022
nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm)

nsga nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm), a multi-objective genetic optimization algorithm.

Max Kuznetsov 8 Oct 1, 2022
Common data structures and algorithms for competitive programming in Rust

algorithm-rs algorithm-rs is common data structures and algorithms for competitive programming in Rust. Contents TBA How To Contribute Contributions a

Chris Ohk 16 Dec 21, 2022
darwin-rs, evolutionary algorithms with rust

darwin-rs This library allows you to write evolutionary algorithms (EA) using the Rust programming language. Written by Willi Kappler, License: MIT -

Willi Kappler 95 Jan 1, 2023
Compare binary files using alignment algorithms

biodiff Compare binary files using alignment algorithms. What is this This is a tool for binary diffing. The tool is able to show two binary files sid

null 483 Dec 22, 2022
A tool used to evaluate the output of retrieval algorithms. Written in Rust.

Rusteval A tool used to evaluate the output of retrieval algorithms. Written in Rust. Building Install Rust with curl -sSf https://static.rust-lang.or

Giorgos Sfikas 17 Mar 22, 2022
This crate implements fast route planning algorithms in Rust.

This crate implements fast route planning algorithms in Rust. Algorithms Currently implemented: Contraction Hierarchies: The implementat

Payas Rajan 4 Aug 15, 2021
DSP algorithms for embedded. Often integer math.

This crate contains some tuned DSP algorithms for general and especially embedded use.

QUARTIQ 12 Nov 3, 2022
ECFFT algorithms on the BN254 base field

ECFFT algorithms on the BN254 base field This crate implements structs and traits for the ECFFT algorithms from the paper Elliptic Curve Fast Fourier

null 36 Nov 28, 2022
A library that can be used as a building block for high-performant graph algorithms.

graph A library that can be used as a building block for high-performant graph algorithms. Graph provides implementations for directed and undirected

Martin Junghanns 222 Jan 1, 2023
"Algorithms for approximate string matching" in Rust, with Python bindings.

ukkonen Implementation of a bounded Levenshtein distance by Esko Ukkonen in "Algorithms for approximate string matching" in Rust, with Python bindings

Ethan Smith 1 Dec 1, 2021