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(¶ms, rng, &gpparams, &task); for _ in 0..generations { g.evolve(¶ms, 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
type Expression: Clone + Send + Sync
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: &TypeSchema
) -> Vec<Self::Expression>
&self,
params: &Self::Params,
rng: &mut R,
pop_size: usize,
tp: &TypeSchema
) -> 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
) -> Self::Expression
&self,
params: &Self::Params,
rng: &mut R,
prog: &Self::Expression
) -> Self::Expression
Mutate a single program.
fn crossover<R: Rng>(
&self,
params: &Self::Params,
rng: &mut R,
parent1: &Self::Expression,
parent2: &Self::Expression
) -> Vec<Self::Expression>
&self,
params: &Self::Params,
rng: &mut R,
parent1: &Self::Expression,
parent2: &Self::Expression
) -> 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
&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, O: Sync>(
&self,
params: &Self::Params,
rng: &mut R,
gpparams: &GPParams,
task: &Task<Self, Self::Expression, O>
) -> Vec<(Self::Expression, f64)>
&self,
params: &Self::Params,
rng: &mut R,
gpparams: &GPParams,
task: &Task<Self, Self::Expression, O>
) -> 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 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)>
)
&self,
params: &Self::Params,
rng: &mut R,
gpparams: &GPParams,
task: &Task<Self, Self::Expression, O>,
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.
Implementors
impl GP for Grammar type Expression = AppliedRule; type Params = GeneticParams;