Trait programinduction::GP

pub trait GP<Observation: ?Sized> {
    type Expression: Clone;
    type Params;

    // Required methods
    fn genesis<R: Rng>(
        &self,
        params: &Self::Params,
        rng: &mut R,
        pop_size: usize,
        tp: &TypeScheme
    ) -> Vec<Self::Expression>;
    fn mutate<R: Rng>(
        &self,
        params: &Self::Params,
        rng: &mut R,
        prog: &Self::Expression,
        obs: &Observation
    ) -> Vec<Self::Expression>;
    fn crossover<R: Rng>(
        &self,
        params: &Self::Params,
        rng: &mut R,
        parent1: &Self::Expression,
        parent2: &Self::Expression,
        obs: &Observation
    ) -> Vec<Self::Expression>;

    // Provided methods
    fn tournament<'a, R: Rng>(
        &self,
        rng: &mut R,
        tournament_size: usize,
        population: &'a [(Self::Expression, f64)]
    ) -> &'a Self::Expression { ... }
    fn init<R: Rng>(
        &self,
        params: &Self::Params,
        rng: &mut R,
        gpparams: &GPParams,
        task: &impl Task<Observation, Representation = Self, Expression = Self::Expression>
    ) -> Vec<(Self::Expression, f64)> { ... }
    fn validate_offspring(
        &self,
        _params: &Self::Params,
        _population: &[(Self::Expression, f64)],
        _children: &[Self::Expression],
        _offspring: &mut Vec<Self::Expression>
    ) { ... }
    fn evolve<R: Rng>(
        &self,
        params: &Self::Params,
        rng: &mut R,
        gpparams: &GPParams,
        task: &impl Task<Observation, Representation = Self, Expression = Self::Expression>,
        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.

use polytype::{ptp, tp};
use programinduction::{
    simple_task, GP, GPParams, GPSelection,
    pcfg::{self, Grammar, Rule}
};
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!(),
    }
}

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 = simple_task(|g: &Grammar, expr| {
    if let Ok(n) = g.eval(expr, &evaluator) {
        (n - target).abs() as f64 // numbers close to target
    } else {
        f64::INFINITY
    }
}, ptp!(EXPR));

let gpparams = GPParams {
    selection: GPSelection::Deterministic,
    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; 32]);

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 (winner, score) = &pop[0];
assert_eq!(6, g.eval(winner, &evaluator).unwrap());
assert_eq!(0.0, *score);

Required Associated Types

type Expression: Clone

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

type Params

Extra parameters for a representation go here.

Required Methods

fn genesis<R: Rng>( &self, params: &Self::Params, rng: &mut R, pop_size: usize, tp: &TypeScheme ) -> Vec<Self::Expression>

Create an initial population for a particular requesting type.

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

Mutate a single program, potentially producing multiple offspring

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

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

Provided Methods

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

A tournament selects an individual from a population.

fn init<R: Rng>( &self, params: &Self::Params, rng: &mut R, gpparams: &GPParams, task: &impl Task<Observation, Representation = Self, Expression = Self::Expression> ) -> Vec<(Self::Expression, f64)>

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.

fn validate_offspring( &self, _params: &Self::Params, _population: &[(Self::Expression, f64)], _children: &[Self::Expression], _offspring: &mut Vec<Self::Expression> )

This should be a filter-like operation on offspring. The intended semantics is that validate_offspring reduces the set of newly created individuals in offspring to just those viable for consideration as part of the total population, taking into account other children that are part of the current generation. This allows you to do things like ensure a population of unique individuals.

fn evolve<R: Rng>( &self, params: &Self::Params, rng: &mut R, gpparams: &GPParams, task: &impl Task<Observation, Representation = Self, Expression = Self::Expression>, population: &mut Vec<(Self::Expression, f64)> )

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.

Object Safety

This trait is not object safe.

Implementors

impl GP<()> for Grammar

type Expression = AppliedRule

type Params = GeneticParams

impl GP<[Rule]> for Lexicon

type Expression = TRS

type Params = GeneticParams