Rust-Genevo: genevo — Execute genetic algorithm (GA) simulations in a customizable and extensible way.

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

  • Add default mutation operator for tree encoding
    Add default mutation operator for tree encoding

    Jun 24, 2017

                                                                                                                                                                                                            feature 
    Reply
  • Trait based impl. of OrderOneCrossover and PartiallyMappedCrossover
    Trait based impl. of OrderOneCrossover and PartiallyMappedCrossover

    Nov 5, 2017

    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

    Reply
  • Advertise features in README
    Advertise features in README

    Nov 5, 2017

    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

    Reply
  • fix typos in docs.
    fix typos in docs.

    Jun 28, 2019

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

    Feb 4, 2020

    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.

    Reply
  • add genotype fixer
    add genotype fixer

    Feb 5, 2020

    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.

    Reply
  • Add a Gitter chat badge to README.md
    Add a Gitter chat badge to README.md

    Jun 22, 2017

    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.

    Reply
  • Add prelude module reexporting most common uses
    Add prelude module reexporting most common uses

    Jun 24, 2017

    In order to make using genevo more comfortable a 'prelude' module that reexports most common imports would be helpful.

    feature 
    Reply
  • Add default genotype for tree encoding
    Add default genotype for tree encoding

    Jun 24, 2017

    in order to complete the basic encoding types of genes - see issue #2 - a genotype implementation for tree encoding shall be added.

    feature 
    Reply
  • Add default types for binary encoding, value encoding and permutation encoding
    Add default types for binary encoding, value encoding and permutation encoding

    Jun 24, 2017

    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 
    Reply
  • Add default mutation operators for binary, value and permutation encoding
    Add default mutation operators for binary, value and permutation encoding

    Jun 24, 2017

    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 
    Reply
  • Add default crossover operators for binary, value and permutation encoding
    Add default crossover operators for binary, value and permutation encoding

    Jun 24, 2017

    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 
    Reply