Overview - How to use this Framework

If you are making your own evolutionary algorithm, there are several files that you should edit

individual.py

This file defines what an individual is (in a class). Generically, an individual is simply an ordered collection of chromosomes. The original implementation treats each chromosome differently. Therefore, all the chromosomes of an individual are maintained in a list as opposed to a set.

Also implemented in this file are methods to the individual class that help identify an individual, define its hash, test its equality to another individual instance, etc

population.py

This file contains the functions that define population generation. The important function defined here is genPop(), which may be used as an interface to creating unique individuals.

genPop(N, chromGenfuncs, chromGenParams)
Parameters:
  • N (int) – the number of individuals in the population
  • chromGenfuncs (list of tuples) – a list of functions. The ith function is responsible for generating the ith chromosome for the individual. The length of this list is exactly the number of chromosomes in each individual
  • chromGenfuncs – list of params for the functions in chromGenfuncs. The ith function in chromGenfuncs is called with the parameters held in the ith tuple of this list
Return type:

list of unique individuals. Uniqueness is defined by Individual.__eq__

chromGenfuncs

chromGenfuncs is a list of functions. The idea here is that each individual in the population is made up of C chromosomes. These C chromosomes are generated independently of each other for each individual in the initial population. Therefore, there must be exactly C functions listed in chromGenfuncs. The i th function in chromGenfuncs will be used to generate the i th chromosome of each individual

chromGenParams

chromGenParams is a list of tuples. There should be exactly as many tuples in this list, as there are functions in chromGenfuncs. To generate the ith chromosome for each individual in the population, the ith function in chromGenfuncs is called with the parameters in the ith tuple of chromGenParams as follows:

chromGenfuncs[i](*chromGenParams[i])

Though that is the general idea behind how genPop() works, it actually performs this call in a for loop over a zip() of chromGenfuncs and chromGenParams

Note

In order for genPop() to work, Individual must implement __hash__(). This is because genPop() uses a set internally before returning a list of individuals as the generated population. As a result, a meaningful __hash__() must be implemented in Individual.

fitness.py

This file contains all selection functions for evaluating the fitness of any individual of the population. The main function in this file is called score().

score(p, scorefuncs, scorefuncparams, SCORES)
Parameters:
  • p (instance of individual) – the individual being evaluated
  • scorefuncs (list of functions) – a list of functions - one to evaluate each chromosome in the individual
  • scorefuncparams – a list of tuples containing the parameters for each of the functions in scorefuncs. Each function will be called by calling scorefuncs[i](p, *scorefuncparams[i])
  • SCORES (dict {Individual : number}) – a dict mapping instances of Individual to their fitness
Return type:

number (the fitness of the individual)

Note

if the individual being evaluated by this function (p) was not in SCORES before the function is executed, it will be inserted into SCORES by this function. Thus, SCORES is modified in-place by this function as required.

selection.py

This file contains all selection functions for selecting individuals from a population for any purpose.

There are three important functions already implemented:

  1. tournamentSelect()
  2. rouletteWheelSelect()
  3. getRouletteWheel()

tournamentSelect()

tournamentSelect(pop, T, w, n, scorefunc, scoreparams)
Parameters:
  • pop (list of Individuals) – the population to select from
  • T (int) – the number of contestants in each tournament (must be smaller than len(pop))
  • w (int) – the number of winners in each tournament (must be smaller than T)
  • n (int) – the number of Individuals to be selected from the population by Tournament Selection (n%w should be 0)
  • scorefunc (function) – the function used to evaluate the fitness of individuals, to determine the winner(s) of a tournament
  • scoreparams (tuple) – the parameters that scorefunc requires, other than the individual itself. The individual is provided along with the unpacked list of params
Return type:

list of individuals

rouletteWheelSelect()

rouletteWheelSelect(wheel, s=None)
Parameters:
  • wheel (a list of 3-tuples. Each tuple consists of the individual, the lower bound (float) of its section of the roulette wheel, and the upper bound (float) of its section of the roulette wheel.) – a roulette wheel
  • s (float) – the random number on which the roulette ball lands on the roulette wheel. This is not provided when calling the function (though it may be if desired). Using this, a binary search is performed to find the Individual that bet on a section of the roulette wheel containing this number
Return type:

single individual

getRouletteWheel()

getRouletteWheel(pop, SCORES)
Parameters:
  • pop (list of instances of Individual) – the population for which a roulette wheel must be made
  • SCORES (dict {Individual:number}) – a dictionary that maps instances of Individual to their fitnesses
Return type:

list of 3-tuples (Individual, lowerBound, UpperBound)

crossover.py

All functions that have to do with crossing over chromosomes between individuals are defined here. There is no generic driver function here as crossovers are defined per GA.

mutation.py

All functions that have to do with mutating chromosomes between individuals are defined here. There is no generic driver function here as mutations are defined per GA