Execute genetic algorithm (GA) simulations in a customizable and extensible way.

Overview

genevo

Crates.io Docs.rs Linux Build Status Windows Build Status codevoc.io MIT/Apache Join the chat

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

The vision for genevo is to be a flexible and greatly extensible framework for implementing genetic algorithm applications.

genevo is written in Rust. The library's API utilizes lots of traits and types for modelling the domain of genetic algorithms.

Documentation

Features

This crate provides a default implementation of the genetic algorithm to be used to find solutions for a wide variety of search and optimization problems.

The implementation is split into building blocks which are all represented by traits. This crate provides most common implementation for all building blocks. So it can be used for many problems out of the box.

Anyway if one wants to use different implementations for one or the other building block it can be extended by implementing any of the traits in a more sophisticated and customized way.

The building blocks (defined as traits) are:

  • Simulation
  • Algorithm
  • Termination
  • Operator
  • Population
  • Phenotype and Genotype
  • FitnessFunction

The simulation can run an algorithm that is executed in a loop. An algorithm implements the steps to be done for each iteration of the loop. The provided implementation of the genetic algorithm implements the Algorithm trait and can therefore be executed by the Simulator which is the provided implementation of the Simulation trait.

The Simulator holds state about the simulation and tracks statistics about the execution of the algorithm, such as number of iterations and processing time.

The simulation runs until the termination criteria are met. The termination criteria can be a single one such as max number of iterations or a logical combination of multiple termination criteria, e.g. max number of iterations OR a minimum fitness value has been reached. Of coarse Termination is a trait as well and one can implement any termination criteria he/she can think of.

The algorithm can make use of operators that perform different stages of the algorithm. E.g. the basic genetic algorithm defines the stages: selection, crossover, mutation and accepting. These stages are performed by the appropriate operators: SelectionOp, CrossoverOp, MutationOp, RecombinationOp and ReinsertionOp.

This crate provides multiple implementations for each one of those operators. So one can experiment with combining the different implementations to compose the best algorithm for a specific search or optimization problem. Now you may have guessed that the defined operators are traits as well and you are free to implement any of these operators in a way that suits best for your problem and plug them into the provided implementation of the genetic algorithm.

The genetic algorithm needs a population that it evolves with each iteration. A population contains a number of individuals. Each individual represents a possible candidate solution for an optimization problem for which the best solution is searched for. This crate provides a PopulationBuilder to build population of genomes. To run the population builder it needs an implementation of the GenomeBuilder trait. A GenomeBuilder defines how to create one individual (or genome) within the population.

Last but maybe most important are the traits Phenotype, Genotype and FitnessFunction. These are the traits which define the domain of the optimization problem. They must be implemented individually for each application of the genetic algorithm.

Enough words about the building blocks. Show me some concrete examples. Have a look at the examples in the examples folder to find out how to use this crate:

Usage

Add this to your Cargo.toml:

[dependencies]
genevo = "0.5"

If you are not using Rust 2018 edition add this to your crate root:

extern crate genevo;

References

I started this project mainly to learn about genetic algorithms (GAs). During this journey I searched a lot for information about GA. Here are the links to sources of information about GA that I found most useful for me.

[JFGA]: Jeremy Fisher: Genetic Algorithms

[OBI98]: Marek Obitko: Genetic Algorithms Tutorial

[GEAT]: GEATbx: Evolutionary Algorithms

[IGAYT]: Noureddin Sadawi: A Practical Introduction to Genetic Algorithms

[CT9YT]: The Coding Train: 9: Genetic Algorithms - The Nature of Code

[BT95]: Tobias Blickle, Lothar Thiele, 1995: A Comparison of Selection Schemes used in Genetic Algorithms.

[RRCGH]: StefanoD: Rust_Random_Choice Rust library.

[TSP95]: TSPLIB95: library of sample instances for the TSP (and related problems)


Copyright ยฉ 2017-2019, Innoave.com and contributors

Comments
  • This crate can run on wasm32 with a little modification.

    This crate can run on wasm32 with a little modification.

    I wrote a traveling salesman problem in rust and build it with wasm bindgen.

    1. rayon::join doesn't work on wasm32, so I limit the population under 50.
    2. time::get_time is unimplemented!. so I stub the time crate return value with 0.

    demo https://warycat.github.io/ga_wasm/ src https://github.com/warycat/ga_wasm

    Thank you for making this awesome crate.

    opened by warycat 5
  • Disable GA parallelism

    Disable GA parallelism

    I'm currently implementing a genetic algorithm that runs a circuit simulation to evaluate a circuits fitness. To perform the simulation, I use a third party C API. This API is called from within the fitness_of() function of the FitnessFunction trait I defined.

    The third party C API I use cannot be used in a multi-threaded fashion. so I'm wondering if it's possible to disable the parallelism in the ga module; or if there is a less performant, sequential version of genevo.

    opened by keegit 3
  • Add default mutation operators for binary, value and permutation encoding

    Add default mutation operators for binary, value and permutation encoding

    Default mutation operators for basic encoding types are helpful to use the library for simulations with basic genotypes.

    With this issue mutation operators for the following 3 encoding types will be supported:

    • binary encoding
    • value encoding
    • permutation encoding
    feature 
    opened by haraldmaida 2
  • Add default crossover operators for binary, value and permutation encoding

    Add default crossover operators for binary, value and permutation encoding

    Default crossover operators for basic encoding types are helpful to use the library for simulations with basic genotypes.

    With this issue crossover operators for the following 3 encoding types will be supported:

    • binary encoding
    • value encoding
    • permutation encoding
    feature 
    opened by haraldmaida 2
  • Add default types for binary encoding, value encoding and permutation encoding

    Add default types for binary encoding, value encoding and permutation encoding

    Without knowing anything about the encoding of gene it is impossible to provide default implementations for crossover and mutation operator. Therefore it would make sense to implement the basic types of gene encodings, which are:

    • binary encoding
    • value encoding
    • permutation encoding
    • tree encoding

    the implementation will be split up into 2 parts. with this feature request only the first 3 encoding types:

    • binary encoding
    • value encoding
    • permutation encoding

    will be implemented. For tree encoding a separate issue will be created.

    feature 
    opened by haraldmaida 1
  • Future compile error on Rust beta 1.60 in `types/tests.rs`

    Future compile error on Rust beta 1.60 in `types/tests.rs`

    A crater run found that this crate's tests no longer compile with rust 1.60 beta (see https://github.com/rust-lang/rust/issues/94504) due to a newly added method causing conflicts in method resolution.

    The regression has been deemed an acceptable minor change per RFC 1105. It can be fixed by using fully qualified function call syntax to unambiguously call the extension trait that previously provided abs_diff or by switching to the new std API once 1.60 is released.

    opened by the8472 0
  • [fix] index comparison with correct collection size

    [fix] index comparison with correct collection size

    I received an index out of bounds error when using an OrderOneCrossover operator: index out of bounds: the len is 2 but the index is 2. I believe, this is due to the second index p2_index in the cyclic crossover function being compared to the wrong vector's size.

    opened by dariogoetz 0
  • [fix] index comparison with correct collection size

    [fix] index comparison with correct collection size

    I received an index out of bounds error when using an OrderOneCrossover operator: index out of bounds: the len is 2 but the index is 2. I believe, this is due to the second index p2_index in the cyclic crossover function being compared to the wrong vector's size.

    opened by dariogoetz 0
  • impl RandomValueMutator for bool type

    impl RandomValueMutator for bool type

    this PR is for the case when using Vec<bool> as the Genotype in combination with RandomValueMutator.

    As a result, we can use the built-in Vec<bool> instead of the fixedbitset crate for binary encoded individual.

    sample codes:

        let algorithm = genetic_algorithm()
            .with_evaluation(MagFitnessEvaluator)
            .with_selection(RouletteWheelSelector::new(0.7, 2))
            .with_crossover(MultiPointCrossBreeder::new(3))
            .with_mutation(RandomValueMutator::new(0.1, false, true))
            .with_reinsertion(ElitistReinserter::new(MagFitnessEvaluator, false, 0.7))
            .with_initial_population(initial_population)
            .build();
    
    opened by ybyygu 0
  • Processing time is not meassured correctly

    Processing time is not meassured correctly

    Since execution of crossover and mutation is done in parallel, the processing time is no longer correct. The processing time should be meassured in each thread separately.

    bug 
    opened by haraldmaida 0
  • Add a Gitter chat badge to README.md

    Add a Gitter chat badge to README.md

    innoave/genevo now has a Chat Room on Gitter

    @haraldmaida has just created a chat room. You can visit it here: https://gitter.im/innoave/genevo.

    This pull-request adds this badge to your README.md:

    Gitter

    If my aim is a little off, please let me know.

    Happy chatting.

    PS: Click here if you would prefer not to receive automatic pull-requests from Gitter in future.

    opened by gitter-badger 0
  • GenomeBuilder -> GenotypeBuilder?

    GenomeBuilder -> GenotypeBuilder?

    I'm no biologist, but reading definitions, should structs/traits/fns with GenomeBuilder be rather called GenotypeBuilder? Also Evaluated::genome should be a genotype?

    opened by KoltesDigital 0
  • Getting the current population after calling step()?

    Getting the current population after calling step()?

    Quick question, is it possible to get the current population after calling Simulator::step()?

    It seems step() returns an EvaluatedPopulation, which you can query using EvaluatedPopulation::individuals(), but this is the population before applying selection. I want to get the population after applying selection (so after selecting the best parents and cross-breeding them). Is this possible at all?

    (Basically I'm looking for a way to access GeneticAlgorithm.population directly, which is not possible at the moment since it's private)

    opened by Bauxitedev 1
  • How to use `f32` / `f64` as fitness scores?

    How to use `f32` / `f64` as fitness scores?

    Hello,

    I am currently stuck using a janky float discretization technique because I can't use floats directly.

    Is there a better workaround? Is there some truly compelling reason we cannot implement the Fitness trait for floats internally like is done for the signed and unsigned integers?

    Thank you.

    opened by wbrickner 2
  • add genotype fixer

    add genotype fixer

    Hello! I'm working under a handler that will help us fix the genotype after mutation, if necessary. Iโ€™m very interested in your opinion about this, maybe I'm doing something wrong.

    opened by GoWebProd 0
  • Advertise features in README

    Advertise features in README

    Hi, I'm doing my first experiments in the field of GAs. After looking at all crates matching "genetic", genevo looked to me as the most promising library. Great work! For others doing the same evaluation, a list of features in the README would help a lot. And for a beginner like me, more documentation would be immensely helpful. Ideal would be an exerpt of OBI98 with included code examples. Maybe you would get the permission for copying parts of it (see FAQ)? But anyway, this issue is mostly to thank you for your work! Gruss, Pirmin

    opened by pka 1
  • Trait based impl. of OrderOneCrossover and PartiallyMappedCrossover

    Trait based impl. of OrderOneCrossover and PartiallyMappedCrossover

    Hi, I've changed OrderOneCrossover and PartiallyMappedCossover to a trait based implemenation, because I wanted to have my permutation encoding in something different than Vec<usize>. Since I'm an absolute beginner in the field of GAs, I don't know whether my approach makes sense though. Thanks for your great work! Pirmin

    opened by pka 2
Releases(v0.7.1)
Owner
Innoave
Innoave
Rust library for genetic algorithms

Spiril Spiril is an implementation of a genetic algorithm for obtaining optimum variables (genetics) for a task through mutation and natural selection

Ashley Jeffs 25 Apr 29, 2022
NEATeRS is a library for training a genetic neural net through reinforcement learning.

NEATeRS NEATeRS is a library for training a genetic neural net through reinforcement learning. It uses the NEAT algorithm developed by Ken Stanley whi

TecTrixer 3 Nov 28, 2022
Label Propagation Algorithm by Rust. Label propagation (LP) is graph-based semi-supervised learning (SSL). LGC and CAMLP have been implemented.

label-propagation-rs Label Propagation Algorithm by Rust. Label propagation (LP) is graph-based semi-supervised learning (SSL). A simple LGC and a mor

vaaaaanquish 4 Sep 15, 2021
๐Ÿš€ efficient approximate nearest neighbor search algorithm collections library written in Rust ๐Ÿฆ€ .

?? efficient approximate nearest neighbor search algorithm collections library written in Rust ?? .

Hora-Search 2.3k Jan 3, 2023
An implementation of the Pair Adjacent Violators algorithm for isotonic regression in Rust

Pair Adjacent Violators for Rust Overview An implementation of the Pair Adjacent Violators algorithm for isotonic regression. Note this algorithm is a

Ian Clarke 3 Dec 25, 2021
A naive density-based clustering algorithm written in Rust

Density-based clustering This a pure Rust implementation of a naive density-based clustering algorithm similar to DBSCAN. Here, 50 points are located

chris m 0 Mar 19, 2020
A rust library inspired by kDDBSCAN clustering algorithm

kddbscan-rs Rust implementation of the kddbscan clustering algorithm. From the authors of kDDBSCAN algorithm. Due to the adoption of global parameters

WhizSid 2 Apr 28, 2021
Rust implementation for DBSCANSD, a trajectory clustering algorithm.

DBSCANSD Rust implementation for DBSCANSD, a trajectory clustering algorithm. Brief Introduction DBSCANSD (Density-Based Spatial Clustering of Applica

Nick Gu 2 Mar 14, 2021
k-Medoids clustering in Rust with the FasterPAM algorithm

k-Medoids Clustering in Rust with FasterPAM This Rust crate implements k-medoids clustering with PAM. It can be used with arbitrary dissimilarites, as

Erich Schubert 11 Oct 16, 2022
Rust port of the extended isolation forest algorithm for anomaly detection

Extended Isolation Forest This is a rust port of the anomaly detection algorithm described in Extended Isolation Forest and implemented in https://git

Nico Mandery 6 Oct 21, 2022
An Implementation of the Context Tree Weighting (CTW) Sequence Prediction Algorithm

Context Tree Weighting (CTW) CTW is a lightweight, practical and well performing sequence prediction algorithm discovered by Frans Willems, Yuri Shtar

null 7 Dec 23, 2022
A neural network model that can approximate any non-linear function by using the random search algorithm for the optimization of the loss function.

random_search A neural network model that can approximate any non-linear function by using the random search algorithm for the optimization of the los

ph04 2 Apr 1, 2022
TopK algorithm implementation in Rust (Filtered Space-Saving)

TopK TopK algorithm implementation in Rust. This crate currently provides the Filtered Space-Saving algorithm. Version numbers follow the semver conve

null 6 Feb 24, 2023
m2cgen (Model 2 Code Generator) - is a lightweight library which provides an easy way to transpile trained statistical models into a native code

Transform ML models into a native code (Java, C, Python, Go, JavaScript, Visual Basic, C#, R, PowerShell, PHP, Dart, Haskell, Ruby, F#, Rust) with zero dependencies

Bayes' Witnesses 2.3k Dec 31, 2022
A programming language written in an "easy to understand" way

Trees Trees ใฏใ€ใƒ–ใƒญใƒƒใ‚ฏใƒ—ใƒญใ‚ฐใƒฉใƒŸใƒณใ‚ฐ่จ€่ชžใงใ€ไปฅไธ‹ใฎ็‰นๅพดใ‚’ๅ‚™ใˆใฆใ„ใพใ™๏ผ ๅˆ†ใ‹ใ‚Šใ‚„ใ™ใ„ (easy to understand) ่ชญใฟใ‚„ใ™ใ„ (readable) ๆ›–ๆ˜งๆ€งใŒใชใ„ (clear) โ”Œโ”€โ”€โ”€โ”€โ”€โ” โ”‚printโ”‚ โ””โ”€โ”€โ”€โ”ฌโ”€โ”˜

Snowman-s 34 Jul 5, 2024
Narwhal and Tusk A DAG-based Mempool and Efficient BFT Consensus.

This repo contains a prototype of Narwhal and Tusk. It supplements the paper Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus.

Facebook Research 134 Dec 8, 2022
MesaTEE GBDT-RS : a fast and secure GBDT library, supporting TEEs such as Intel SGX and ARM TrustZone

MesaTEE GBDT-RS : a fast and secure GBDT library, supporting TEEs such as Intel SGX and ARM TrustZone MesaTEE GBDT-RS is a gradient boost decision tre

MesaLock Linux 179 Nov 18, 2022
Ecosystem of libraries and tools for writing and executing extremely fast GPU code fully in Rust.

Ecosystem of libraries and tools for writing and executing extremely fast GPU code fully in Rust.

Riccardo D'Ambrosio 2.1k Jan 5, 2023
Ecosystem of libraries and tools for writing and executing fast GPU code fully in Rust.

The Rust CUDA Project An ecosystem of libraries and tools for writing and executing extremely fast GPU code fully in Rust Guide | Getting Started | Fe

Rust GPU 2.1k Dec 30, 2022