genevo

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:

• knapsack: tries to solve the 0-1 knapsack problem
• monkeys: explores the idea of Shakespeare's monkeys, also known as the infinite monkey theorem
• queens: searches for solutions of the N Queens Problem

Usage

Add this to your Cargo.toml:

[dependencies]
genevo = "0.7"

Crate Features

genevo provides additional data types to be used as genotypes through optional crate features:

• fixedbitset: provides Fixedbitset to be used as genotype
• Smallvec: provides Smallvec to be used as genotype

since version 0.7.0 genevo supports wasm targets. To use genevo for target wasm32-unknown-unknown enable the crate feature wasm-bindgen. Note: on wasm32 targets multithreading (implemented using rayon) is disabled!

[dependencies]
genevo = { version = "0.7", features = ["wasm-bindgen"] }

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-2022, Innoave.com and contributors