Genetic Algorithms Library

Overview

genx

crb dcb build size downloads license

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

The vision for genx is to be a flexible and greatly extensible library for implementing genetic algorithm applications. genx is written in Rust. The library's API utilizes functional programming paradigm and exposes it's API in that manner only.

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

Documentation

Basic Example

Selection

Here's a trivial example that returns back individual selected using stochastic universal sampling

use genx::selection::stochastic_universal::stochastic_universal_selection;

let num_parents:usize = 10;
let fitness_values = vec![2.4,8.4,3.2,9.4,9.0,11.0,4.5,0.6,4.4,2.3,5.6,10.0,0.2,9.0,4.8,7.7];

let result = stochastic_universal_selection(&fitness_values, num_parents, None)
                .iter()
                .map(|&a| fitness_values[a])
                .collect::<Vec<f32>>();

stochastic_universal_selection takes in the fitness_value vector, number of parents it needs to select and a seed value which is Option<u64>. It returns back the indices of selected individuals which we map to actual fitness values.

Mutation

Mutation function takes in a single individual, distribution index and returns in the mutated individual using polynomial mutation for real valued individual.

use genx::mutation::polynomial::polynomial_mutation;
let individual = 29.11;
let result = polynomial_mutation(individual, 4.2, 4.0, None);

The returned value may or may not be equal as is mutated based on a randomly generated value, which for deterministic results can be seeded.

Building Blocks

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.

A Genetic Algorithm proceeds through following operations:

  • Encoding: Binary, Real Values, Order, Tree, etc.
  • Selection: Selecting individuals after fitness evaluation.
  • Crossover: Creating new individuals from selected pool of individuals.
  • Mutation: Making stark changes in generated individual for diversification.
  • Convergence: Test for goal accomplishment or convergence.

The building blocks currently available (defined as traits) are:

  • Selection
  • Mutation

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.

Usage

Add this to your Cargo.toml:

[dependencies]
genx = "0.3.0"

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

extern crate genx;

Why Genetic Algorithms

Genetic Algorithms are at the core of soft computing which is a branch of computing that comes to rescue when problem at hand is not feasible to be solved using hard computing. There are several advantages of genetic algorithms:

  • Algorithms are adaptive and can adjust to the change of dynamic environment​
  • The approach makes use of approximate solutions to solve problems that may be either unsolvable or too time-consuming to solve with current hardware.​
  • Imprecise but usable solutions to complex computational problems allowing researchers to approach some problems that traditional computing cannot process.​

Inspiration

I started this project mainly to learn about genetic algorithms (GAs) as part of my college curriculum where am studying severals methods for soft computing. I found myself looking for simple easy to use modular functions that I can use to learn more about each step of GA.

Issues
  • Function Level Documentation

    Function Level Documentation

    Add in the following for each function:

    • Description
    • Working
    • Additional Notes
    • Return type
    • Example
    opened by king-11 1
  • Refactor Module Schema

    Refactor Module Schema

    Add in re-exports so that users can use the API and have a better experience without making long use chains

    opened by king-11 1
  • Module Level Documentation added in v0.2.2

    Module Level Documentation added in v0.2.2

    Documentation for the following

    • Main Module
    • Mutation Module
    • Selection Module
    opened by king-11 1
  • Create CODE_OF_CONDUCT.md

    Create CODE_OF_CONDUCT.md

    null

    opened by king-11 0
  • Update issue templates

    Update issue templates

    null

    opened by king-11 0
  • Crossover Methods

    Crossover Methods

    Add in the following crossover methods

    Binary Encoding

    • [ ] Single Point Crossover
    • [ ] Two Point Crossover
    • [ ] Multi Point Crossover
    • [ ] Shuffle Crossover
    • [ ] Uniform Crossover
    • [ ] Uniform Crossover with Mask
    • [ ] Half Uniform Crossover
    • [ ] Three Parent Crossover
    • [ ] Matrix Crossover

    Order Encoding:

    • [ ] Davis' Order Crossover
    • [ ] Order Based Crossover (OBX)
    • [ ] Modified Order Crossover (MOC)
    • [ ] Partially-Mapped Crossover (PMX)
    • [ ] Order Crossover Operator (OX1)
    • [ ] Order-based Crossover (OX2)

    Value Encoding:

    • [ ] Linear Crossover
    • [ ] Blend Crossover
    • [ ] Simulated Binary Crossover

    Reference

    v1.0.0 module 
    opened by king-11 0
  • Optimize Selection Methods

    Optimize Selection Methods

    Improve time complexity and memory requirements of all the selection methods.

    Some know improvements include:

    • [ ] Use prefix array and binary search for roulette Wheel and rank based selection.
    enhancement 
    opened by king-11 0
Releases(v0.3.0)
  • v0.3.0(Sep 3, 2021)

    Documentation

    • documentation added at module and sub-module level #3
    • individual function documentation with examples added #1

    Issues Fixed

    • fix issues with stochastic universal selection

    Refactor

    • polynomial mutation implementation was wrong is now corrected to use user-defined maximum perturbation
    • typo in the name of scramble_mutation function
    • Better experience for library users by fixing #2 added in re-exports
    Source code(tar.gz)
    Source code(zip)
  • v0.2.0(Sep 2, 2021)

    Mutations

    Added in mutation functions for both binary encoded ( boolean vec ) and real values.

    Binary Encoded Mutation

    • Flipping/Toin Coss
    • Inversion
    • Swap
    • Scramble

    Real Encoded Mutation

    • Random Linear
    • Polynomial

    Fix possible panic in tournament selection 5947944f9ed9a1e0f9cb7ff5aa19e4021aba2ed6

    Source code(tar.gz)
    Source code(zip)
  • first(Aug 31, 2021)

    Selection Algorithms

    A variety of selection algorithms added 🥇 covering all general purpose and specialized needs.

    • Steady State
    • Stochastic Universal Sampling
    • Roulette Wheel
    • Rank proportionate
    • Tournament Selection
    • Random Selection

    Test Coverage at 100% 🚀

    Source code(tar.gz)
    Source code(zip)
Owner
Lakshya Singh
My Reactive Vue Flutters. LFX'21 @cncf GSOC'21 @chapel-lang
Lakshya Singh
Fast, parallel, extensible and adaptable genetic algorithms framework written in Rust

oxigen Oxigen is a parallel genetic algorithm framework implemented in Rust. The name comes from the merge of OXIdación (Rust translated to Spanish) a

Martín Pozo 121 Aug 26, 2021
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 79 Sep 1, 2021
Radiate is a parallel genetic programming engine capable of evolving solutions to many problems as well as training learning algorithms.

Radiate Coming from Evolutionary Radiation. Evolutionary radiation is a rapid increase in the number of species with a common ancestor, characterized

kalivas 84 Sep 1, 2021
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 17 Jun 28, 2021
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 75 Sep 2, 2021
DSP algorithms for embedded. Often integer math.

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

QUARTIQ 3 Sep 17, 2021
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 66 Jul 2, 2021
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
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 171 Sep 14, 2021
A Trig-less Line of Sight Algorithm in Two Dimensions

In many examples of 2D line-of-sight algorithms, expensive operations like trigonometry are used. Additionally, some methods have intentional inaccuracies in them for the sake of simplicity. Here, we give an algorithm which does not fudge the numbers, and uses only basic arithmetic: addition, subtraction, multiplication, and division. This is not intended to replace the existing algorithms, or even be more efficient in practice.

null 21 Sep 7, 2021
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 18 Jul 16, 2021
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 48 Sep 9, 2021
A SIMD-accelerated Adler-32 rolling hash algorithm implementation.

simd-adler32 A SIMD-accelerated Adler-32 rolling hash algorithm implementation. Features No dependencies Support no_std (with default-features = false

Marvin Countryman 16 Apr 14, 2021