Populations

Overview

The Population class contains all of the functionality needed to create an initial group of program trees, assess their individual fitnesses, select members for reproduction, and create a new generation using crossover. Information such as the set of operators and variables, fitness function, and reproduction rate are provided by the application module; the class takes care of all general routines needed. The class definition:

class Population {
  private:
    Binary_Func **b_funcs;      // the list of available binary functions
    int num_b_funcs;            // number of available binary functions
    Unary_Func **u_funcs;       // the list of unary functions
    int num_u_funcs;            // number of unary functions
    Variable **vars;            // list of variables
    int num_vars;               // number of variables
    Val (*const_rand)(void);    // function for generating random constants

    Binary_Node **trees;        // list of trees in the population
    int size;                   // size of the population
    // these 3 are used to generate random subtrees recursively from
    // either a binary or unary operator node
    Node *new_node(Node *);
    void build_tree(Binary_Node *);
    void build_tree(Unary_Node *);

    // these are used when spawning a new generation
    void crossover(Binary_Node *,Binary_Node *,Binary_Node **,Binary_Node **);

  public:
    // constructor takes the initial size, number and list of binary funcs,
    // number and list of unary funcs, number and list of variables,
    // and a function for finding random constants
    Population(int,Binary_Func **,int,Unary_Func **,int,Variable **,int,
               Val (*)(void));
    ~Population(void);          // destructor cleans up memory

    void sort(void);            // sort population by fitness
    void spawn(float);          // spawns a new generation
    void evaluate(double (*)(Node *)); // sets the fitness on each member
    int members(void) {return size;}; // returns the current size of population
    char *print(int);             // returns the expression of a member
    // returns the fitness of a member
    double fitness(int i) {return trees[i]->fitness;};
};

Creating a New Population

As listed above, the constructor takes parameters that define the number of trees in the population, lists of operators and variables, and a function for producing random constants. It then creates a list of Binary_Node's that represent the root nodes of each tree in the population. A random tree builder is then called on each of these nodes to create the initial population. (See section iv-F.3).

Spawning New Generations

There are two steps needed to spawn a new generation: first, the current population must be evaluated to determine the fitness of each member; then, the members that are most fit are allowed to reproduce.

The application module is responsible for providing the fitness function. An example fitness function can be seen in section iv-G. In the cart centering example listed, the fitness of each tree is determined by the average time it takes for it to center the cart over several trials. The function is applied to the population by using evaluate().

Once this has been done, the spawn() function is used to create the new generation. This function does the following (see section iv-F.3 for more details):

1. Sort the population by fitness value (assigned during the evaluate phase).
2. Choose parent trees, based on the birth rate supplied by the application module. These are picked sequentially from the top of the sorted population.
3. Delete the trees that will be replaced by the children. These are picked sequentially from the bottom of the sorted population.
4. Create the children by using the crossover function.

The crossover function performs the real work of tree reproduction. It basically takes the two parents, selects a node in each, and swaps the subtrees rooted at those nodes. The code for this function is also in section iv-F.3. The steps used are:

1. Copy the two parents to the children (so the parents themselves do not get altered).
2. Select random nodes in each tree. The root node will not be selected.
3. Delete the appropriate subtree from child 1, and replace with a copy of the crossover section from child 2.
4. Repeat the above for the opposite case.