Trait programinduction::GP[−][src]

pub trait GP: Send + Sync + Sized {
    type Expression: Clone + Send + Sync;
    type Params;
    fn genesis<R: Rng>(
        &self, 
        params: &Self::Params, 
        rng: &mut R, 
        pop_size: usize, 
        tp: &TypeSchema
    ) -> Vec<Self::Expression>;

    fn mutate<R: Rng>(
        &self, 
        params: &Self::Params, 
        rng: &mut R, 
        prog: &Self::Expression
    ) -> Self::Expression;

    fn crossover<R: Rng>(
        &self, 
        params: &Self::Params, 
        rng: &mut R, 
        parent1: &Self::Expression, 
        parent2: &Self::Expression
    ) -> Vec<Self::Expression>;

    fn tournament<'a, R: Rng>(
        &self, 
        rng: &mut R, 
        tournament_size: usize, 
        population: &'a [(Self::Expression, f64)]
    ) -> &'a Self::Expression { ... }

    fn init<R: Rng, O: Sync>(
        &self, 
        params: &Self::Params, 
        rng: &mut R, 
        gpparams: &GPParams, 
        task: &Task<Self, Self::Expression, O>
    ) -> Vec<(Self::Expression, f64)> { ... }

    fn evolve<R: Rng, O: Sync>(
        &self, 
        params: &Self::Params, 
        rng: &mut R, 
        gpparams: &GPParams, 
        task: &Task<Self, Self::Expression, O>, 
        population: &mut Vec<(Self::Expression, f64)>
    ) { ... }
}

A kind of representation suitable for genetic programming.

Implementors of GP must provide methods for genesis, mutate, crossover. A Task provides a fitness function via its oracle: we adopt the convention that smaller values are better (so one can think of the oracle as providing a measure of error). To opt out of the default tournament-based selection, implementors may override the tournament method.

Typically, you will interact with this trait using the init and evolve methods on existing implementations, such as pcfg::Grammar.

The provided methods (namely init and evolve) manipulate a population, which is a sorted list of programs according to fitness. If you otherwise modify the population such that it is no longer sorted appropriately, these methods will behave incorrectly.

Examples

This example has a lot of code, but it is quite straightforward. Given a PCFG and an evaluator for sentences, a task is created by measuring proximity of an evaluted sentence to some target. We finally pick some parameters and evolve a population for a few hundred generations.

#[macro_use]
extern crate polytype;
extern crate programinduction;
extern crate rand;
use programinduction::pcfg::{self, Grammar, Rule};
use programinduction::{GPParams, Task, GP};
use rand::{rngs::SmallRng, SeedableRng};

fn evaluator(name: &str, inps: &[i32]) -> Result<i32, ()> {
    match name {
        "0" => Ok(0),
        "1" => Ok(1),
        "plus" => Ok(inps[0] + inps[1]),
        _ => unreachable!(),
    }
}

fn main() {
    let g = Grammar::new(
        tp!(EXPR),
        vec![
            Rule::new("0", tp!(EXPR), 1.0),
            Rule::new("1", tp!(EXPR), 1.0),
            Rule::new("plus", tp!(@arrow[tp!(EXPR), tp!(EXPR), tp!(EXPR)]), 1.0),
        ],
    );
    let target = 6;
    let task = Task {
        oracle: Box::new(|g: &Grammar, expr| {
            if let Ok(n) = g.eval(expr, &evaluator) {
                (n - target).abs() as f64 // numbers close to target
            } else {
                std::f64::INFINITY
            }
        }),
        tp: ptp!(EXPR),
        observation: (),
    };

    let gpparams = GPParams {
        population_size: 10,
        tournament_size: 5,
        mutation_prob: 0.6,
        n_delta: 1,
    };
    let params = pcfg::GeneticParams::default();
    let generations = 1000;
    let rng = &mut SmallRng::from_seed([1u8; 16]);

    let mut pop = g.init(&params, rng, &gpparams, &task);
    for _ in 0..generations {
        g.evolve(&params, rng, &gpparams, &task, &mut pop)
    }

    // perfect winner is found!
    let &(ref winner, score) = &pop[0];
    assert_eq!(6, g.eval(winner, &evaluator).unwrap());
    assert_eq!(0.0, score);
}

Associated Types

An Expression is a sentence in the representation. Tasks are solved by Expressions.

Extra parameters for a representation go here.

Required Methods

ⓘImportant traits for Vec<u8>

Create an initial population for a particular requesting type.

Mutate a single program.

ⓘImportant traits for Vec<u8>

Perform crossover between two programs. There must be at least one child.

Provided Methods

A tournament selects an individual from a population.

ⓘImportant traits for Vec<u8>

Initializes a population, which is a list of programs and their scores sorted by score. The most-fit individual is the first element in the population.

Evolves a population. This will repeatedly run a Bernoulli trial with parameter mutation_prob and perform mutation or crossover depending on the outcome until n_delta expressions are determined.

Implementors