Variation (Crossover/Mutation)

class MutationBase

Subclassed by Brush::Var::DeleteMutation, Brush::Var::InsertMutation, Brush::Var::PointMutation, Brush::Var::SplitMutation, Brush::Var::SubtreeMutation, Brush::Var::ToggleWeightOffMutation, Brush::Var::ToggleWeightOnMutation

Public Types

using Iter = tree<Node>::pre_order_iterator

Public Static Functions

template<Brush::ProgramType T>
static inline auto find_spots(Program<T> &program, Variation<T> &variator, const Parameters &params)
template<Brush::ProgramType T>
static auto mutate(Program<T> &program, Iter spot, Variation<T> &variator, const Parameters &params)
template<ProgramType T>
class Variation

Class representing the variation operators in Brush.

The Variation class is responsible for performing individual-level variations and handling the variation of a population in Brush. It contains methods for crossing individuals, mutating individuals, and varying a population.

Public Functions

Variation() = default

Default constructor.

inline Variation(Parameters &params, SearchSpace &ss, Dataset &d)

Constructor that initializes the Variation object with parameters and search space.

Parameters:

  • params – The parameters for the variation operator.

  • ss – The search space for the variation operator.

inline ~Variation()

Destructor.

inline void init()

Initializes the Variation object with parameters and search space.

Parameters:

  • params – The parameters for the variation operator.

  • ss – The search space for the variation operator.

std::optional<Individual<T>> cross(const Individual<T> &mom, const Individual<T> &dad)

Performs croearch_spaceover operation on two individuals.

Stochastically swaps subtrees between root and other, returning a new program.

The spot where the cross will take place in the root parent is sampled based on attribute get_prob_change of each node in the tree. After selecting the cross spot, the program will iterate through the other parent searching for all compatible sub-trees to replace.

Due to the stochastic behavior, it may come to a case where there is no candidate to replace the spot node. In this case, the method returns std::nullopt (and has overloads so it can be used in a boolean context).

If the cross succeeds, the child program can be accessed through the .value() attribute of the std::optional. TODO: update this documentation (it doesnt take the program but the individual. also update mutation documentation) This means that, if you use the cross as auto opt = mutate(parent, SS), either opt==false or opt.value() contains the child.

Parameters:

  • mom – The first parent individual.

  • dad – The second parent individual.

  • root – the root parent

  • other – the donating parent

Returns:

An optional containing the offspring individual if the crossover is successful, or an empty optional otherwise.

Template Parameters:

T – the program type

Returns:

std::optional that may contain the child program of type T

std::optional<Individual<T>> mutate(const Individual<T> &parent, string choice = "")

Performs mutation operation on an individual.

Stochastically mutate a program.

Types of mutation:

  • point mutation changes a single node.

  • insertion mutation inserts a node as the parent of an existing node, and fills in the other arguments.

  • deletion mutation deletes a node.

  • subtree mutation inserts a new subtree into the program.

  • toggle_weight_on mutation turns a node’s weight ON.

  • toggle_weight_off mutation turns a node’s weight OFF.

Every mutation has a probability (weight) based on global parameters. The spot where the mutation will take place is sampled based on attribute get_prob_change of each node in the tree. Inside each type of mutation, when a new node is inserted, it is sampled based on terminal_weights.

Due to the stochastic behavior, and the several sampling steps, it may come to a case where the search space does not hold any possible modification to do in the program. In this case, the method returns std::nullopt (and has overloads so it can be used in a boolean context).

If the mutation succeeds, the mutated program can be accessed through the .value() attribute of the std::optional. This method will try to generate a child that is within size and depth constraints. If ater three attempts it failed to generate a solution under these conditions, then the last model is returned regardless of it’s size and depth. This loosens the size and depth constraints by a small factor (the final program will have at most 3*max_arity extra nodes), and it is better than the alternatives of just replicating the parent or generating a new random solution to add to the population.

This means that, if you use the mutation as auto opt = mutate(parent, SS), either opt==false or opt.value() contains the child program.

Parameters:

  • parent – The parent individual.

  • parent – the program to be mutated

  • SS – a search space

Returns:

An optional containing the mutated individual if the mutation is successful, or an empty optional otherwise.

Template Parameters:

T – program type

Returns:

std::optional that may contain the child program of type T

void vary(Population<T> &pop, int island, const vector<size_t> &parents)

Handles variation of a population.

Parameters:

  • pop – The population to be varied.

  • island – The island index.

  • parents – The indices of the parent individuals.

  • p – The parameters for the variation operator.

void update_ss()

Updates the probability distribution sampling for variation and nodes based on the given rewards.

Parameters:

  • pop – The population to update the selection strategy for.

  • rewards – The rewards obtained from the evaluation of individuals.

inline void vary_and_update(Population<T> &pop, int island, const vector<size_t> &parents, const Dataset &data, Evaluation<T> &evaluator, bool do_simplification)

Varies a population and updates the selection strategy based on rewards.

This function performs variation on a population, calculates rewards, and updates the selection strategy based on the obtained rewards.

Parameters:

  • pop – The population to be varied and updated.

  • island – The island index.

  • parents – The indices of the parent individuals.

inline std::optional<Node> bandit_sample_terminal(DataType R)
inline std::optional<Node> bandit_get_node_like(Node node)
inline std::optional<Node> bandit_sample_op_with_arg(DataType ret, DataType arg, int max_args = 0)
inline std::optional<Node> bandit_sample_op(DataType ret)
inline void log_simplification_table(std::ofstream &log)

Public Members

SearchSpace search_space
Dataset &data
Parameters parameters