Rust-RsGenetic: RsGenetic — Genetic Algorithm library in Rust. In maintenance mode.

RsGenetic

Build Status Crates Version License MIT License Apache

Summary and Features

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

Examples and Documentation

Documentation is available here.

Implementing the Fitness trait

Note that, if your fitness type is an integer type, you do not need to write a wrapper struct around this integer. See the types module documentation for more details.

use rsgenetic::pheno::*;
use std::cmp::Ordering;

#[derive(Eq, PartialEq, PartialOrd, Ord)]
struct MyFitness {
    value: i32,
}

impl Fitness for MyFitness {
    // The zero value for our custom type
    fn zero() -> MyFitness {
        MyFitness { value: 0 }
    }

    // The absolute difference between two instances
    fn abs_diff(&self, other: &MyFitness) -> MyFitness {
        MyFitness {
            value: (self.value - other.value).abs()
        }
    }
}

Implementing the Phenotype trait

Note that we use an integer type as the fitness type parameter to make this example more simple. Replace it with your custom type if needed. In this example, we try to find individuals with two integer components that sum to a target value.

This example is far-fetched, but simplified to show how easy it is to define new individuals and implement the Phenotype trait.

use rsgenetic::pheno::*;

const TARGET: i32 = 100;

#[derive(Copy, Clone)]
struct MyPheno {
    x: i32,
    y: i32,
}

impl Phenotype<i32> for MyPheno {
    // How fit is this individual?
    fn fitness(&self) -> i32 {
        TARGET - (self.x + self.y)
    }

    // Have two individuals create a new individual
    fn crossover(&self, other: &MyPheno) -> MyPheno {
        MyPheno {
            x: self.x,
            y: other.y,
        }
    }

    // Mutate an individual, changing its state
    fn mutate(&self) -> MyPheno {
        MyPheno {
            x: self.x + 1,
            y: self.y - 1,
        }
    }
}

Creating and running a Simulator

use rsgenetic::pheno::*;
use rsgenetic::sim::*;
use rsgenetic::sim::seq::Simulator;
use rsgenetic::sim::select::*;

const TARGET: i32 = 100;

#[derive(Copy, Clone)]
struct MyPheno {
    x: i32,
    y: i32,
}

impl Phenotype<i32> for MyPheno {
    // How fit is this individual?
    fn fitness(&self) -> i32 {
        TARGET - (self.x + self.y)
    }

    // Have two individuals create a new individual
    fn crossover(&self, other: &MyPheno) -> MyPheno {
        MyPheno {
            x: self.x,
            y: other.y,
        }
    }

    // Mutate an individual, changing its state
    fn mutate(&self) -> MyPheno {
        MyPheno {
            x: self.x + 1,
            y: self.y - 1,
        }
    }
}

fn main() {
    let mut population = (0..100).map(|i| MyPheno { x: i, y: 100 - i }).collect();
    let mut s = Simulator::builder(&mut population)
                    .set_selector(Box::new(StochasticSelector::new(10)))
                    .set_max_iters(50)
                    .build();
    s.run();
    let result = s.get().unwrap(); // The best individual
}

See the examples directory in the repository for more elaborate examples.

Note

This library is currently in maintenance mode. There have been some indications that the API needs an update to be more flexible, which would require an incrementation of the major version number (#23, #30). Unfortunately, I currently do not have the time to implement such a redesign. I will however continue to reply to issues and merge pull requests, but features might not be implemented by me, depending on their size.

License

Licensed under either of

at your option.

Contribution

Contributions are always welcome. Take a look at the issues for any enhancements that need to be done or bugs that need to be fixed. If you encounter any bugs while using the library, feel free to open an issue and/or fix the bug, and submit pull requests.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments

  • Built in operator support
    Built in operator support

    Feb 7, 2018

    Hi there. It would be nice to have pluggable crossover and mutation operators and implementations of well known operators.

    feature-request help wanted 
    Reply
  • WASM Support
    WASM Support

    Jun 29, 2018

    Hi! This might be a bit of a weird one, but it would be great to have WASM support for this crate :smile:

    ... which I have gotten to work, but now I am not sure how to contribute back to you guys :) there are two major changes that I had to implement:

    • using rand's PRNG (the OS RNG doesn't work yet...) for here
    • remove/make timing optional here :+1:

    Now I'd be happy to integrate this somehow, but I am not sure how to do this without rewriting half the seq module or removing things like the timing and replacing thread_rng (where I don't know the difference in quality to XorShiftRng). Alternatively it could live as its own compilation unit for the wasm target, but that would duplicate code which is also not great :sweat_smile:

    What are your ideas? I am happy to help :+1:

    enhancement 
    Reply
  • seq WASM compatibility
    seq WASM compatibility

    Jul 3, 2018

    Hi! So these are the (minor) changes to the seq module (incl. the update to the WASM compatible 0.5 rand crate).

    I think there are a few things that are worth doing:

    • the iteration timing is useful for wherever Instant is available, WASM bindgen doesn't support it yet though.
    • the random thread_rng number generator doesn't work with WASM bindgen yet, a good solution would probably be to be able to pass in a custom RNG (like Math.random or XorShiftRng).

    This PR should mostly show the required changes to seq. I am happy to use a completely different approach too!

    Tracked also in #32

    Reply
  • Allow parents with high fitness to have more offspring per generation
    Allow parents with high fitness to have more offspring per generation

    Jan 29, 2020

    Currently, the crossover method can only return one offspring. But often it is desirable to have high fitness parents producing more offspring. And it's not just enough to call the crossover function multiple times, because often the offspring should be generated exhaustively, regarding a certain set of "orthogonal" crossover combinations that makes sense, without repeating the same way of crossover. Simply calling crossover multiple times would potentially produce the same offspring multiple times, if the number of crossover-ways that make sense is low. The same can be said for the mutate method. Often it's desirable to generate multiple "orthogonal" mutations together.

    Reply
  • tournament select requires participants to be >1
    tournament select requires participants to be >1

    Jan 24, 2018

    https://github.com/m-decoster/RsGenetic/blob/master/src/sim/select/tournament.rs#L63-L71

    For tournament selection, line 70 requires that at least there are 2 elements; when 1 participant is specified in user code, it will cause index out of bound panic.

    Reply
  • a few minor refinements
    a few minor refinements

    Jan 26, 2018

    This PR contains some minor refinements.

    • formatting with cargo-fmt
    • asset! -> asset_eq! whenever possible
    • name anonymous function parameter in Trait
    • remove one duplicate map

    See specially e206d07 for details.

    Reply
  • Fixed apparent bug with sorting for best fitness
    Fixed apparent bug with sorting for best fitness

    Oct 11, 2016

    Firstly, thanks for writing this! I love the way you've laid out the Phenotype trait.

    I had difficulty getting my GA to work correctly; the issue appears to be a bug in the MaximizeSelector structure implementation, which sorts elements based on ascending fitness [0]. This should be sorting based on descending fitness ([1] indicates that a better fitness should be > than a lesser fitness).

    An alternative resolution for this issue is to just add cloned.reverse() but this should be more performant, though less obvious.

    [0] - https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_by [1] - http://m-decoster.github.io/RsGenetic/doc/rsgenetic/pheno/trait.Fitness.html

    Reply
  • Avoid boxing.
    Avoid boxing.

    Feb 14, 2016

    There's no need to allocate so much. You only really need to box things when you want runtime polymorphism (trait objects). However, you're using compiletime polymorphism (generics) for everything but selectors.

    Reply
  • Avoid cloning in Selectors
    Avoid cloning in Selectors

    Sep 22, 2017

    Improves performance (amount depending on Phenotype implementation).

    Reply
  • Relicense under dual MIT/Apache-2.0
    Relicense under dual MIT/Apache-2.0

    Jan 10, 2016

    This issue was automatically generated. Feel free to close without ceremony if you do not agree with re-licensing or if it is not possible for other reasons. Respond to @cmr with any questions or concerns, or pop over to #rust-offtopic on IRC to discuss.

    You're receiving this because someone (perhaps the project maintainer) published a crates.io package with the license as "MIT" xor "Apache-2.0" and the repository field pointing here.

    TL;DR the Rust ecosystem is largely Apache-2.0. Being available under that license is good for interoperation. The MIT license as an add-on can be nice for GPLv2 projects to use your code.

    Why?

    The MIT license requires reproducing countless copies of the same copyright header with different names in the copyright field, for every MIT library in use. The Apache license does not have this drawback. However, this is not the primary motivation for me creating these issues. The Apache license also has protections from patent trolls and an explicit contribution licensing clause. However, the Apache license is incompatible with GPLv2. This is why Rust is dual-licensed as MIT/Apache (the "primary" license being Apache, MIT only for GPLv2 compat), and doing so would be wise for this project. This also makes this crate suitable for inclusion and unrestricted sharing in the Rust standard distribution and other projects using dual MIT/Apache, such as my personal ulterior motive, the Robigalia project.

    Some ask, "Does this really apply to binary redistributions? Does MIT really require reproducing the whole thing?" I'm not a lawyer, and I can't give legal advice, but some Google Android apps include open source attributions using this interpretation. Others also agree with it. But, again, the copyright notice redistribution is not the primary motivation for the dual-licensing. It's stronger protections to licensees and better interoperation with the wider Rust ecosystem.

    How?

    To do this, get explicit approval from each contributor of copyrightable work (as not all contributions qualify for copyright, due to not being a "creative work", e.g. a typo fix) and then add the following to your README:

    ## License
    
    Licensed under either of
    
     * Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
     * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
    
    at your option.
    
    ### Contribution
    
    Unless you explicitly state otherwise, any contribution intentionally submitted
    for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
    additional terms or conditions.
    

    and in your license headers, if you have them, use the following boilerplate (based on that used in Rust):

    // Copyright 2016 RsGenetic developers
    //
    // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
    // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
    // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
    // option. This file may not be copied, modified, or distributed
    // except according to those terms.
    

    It's commonly asked whether license headers are required. I'm not comfortable making an official recommendation either way, but the Apache license recommends it in their appendix on how to use the license.

    Be sure to add the relevant LICENSE-{MIT,APACHE} files. You can copy these from the Rust repo for a plain-text version.

    And don't forget to update the license metadata in your Cargo.toml to:

    license = "MIT/Apache-2.0"
    

    I'll be going through projects which agree to be relicensed and have approval by the necessary contributors and doing this changes, so feel free to leave the heavy lifting to me!

    Contributor checkoff

    To agree to relicensing, comment with :

    I license past and future contributions under the dual MIT/Apache-2.0 license, allowing licensees to chose either at their option.
    

    Or, if you're a contributor, you can check the box in this repo next to your name. My scripts will pick this exact phrase up and check your checkbox, but I'll come through and manually review this issue later as well.

    • [x] @m-decoster
    Reply