Fitness Module

This module implements the fitness components for grammatical evolution.

FitnessList Class

This class maintains a list of fitness values per generation. It is a subclassed list to maintain information regarding whether fitness values should be maximized, minimized or centered around zero. By holding that information, when the fitness list is given to a fitness evaluation or replacement object, it can configure itself automatically to conform to the appropropriate characteristics for the class.

def __init__(self, fitness_type, target_value=0.0):

This function initializes and accepts the fitness type. Optionally it accepts the target value. The target value is the value where execution of the evolutionary process halts upon attaining the goal.

def set_fitness_type(self, fitness_type):

This function sets the fitness type.

Accepted fitness types are 'min', 'max', or 'center'.

def get_fitness_type(self):

This function returns the fitness type, such as 'min', 'max', or 'center'.

def set_target_value(self, target_value):

This function sets the target value.

def get_target_value(self):

This function returns the target value.

def min_value(self):

This function returns the minimum value in the list.

def max_value(self):

This function returns the maximum value in the list.

def best_value(self):

This function returns the best value in the list on the basis of the objective of the fitness list. For example, when trying to maximize a fitness value, it would return the maximum value.

def worst_value(self):

This function returns the worst value in the list on the basis of the objective of the fitness list. For example, when trying to maximize a fitness value, it would return the minimum value.

def min_member(self):

This function returns the member with the minimum value.

def max_member(self):

This function returns the member with the maximum value.

def best_member(self):

This function returns the member with the best value based upon the criteria of the fitness type.

def worst_member(self):

This function returns the member with the worst value based upon the criteria of the fitness type.

def mean(self):

This function returns the mean fitness value.

def median(self):

This function returns the median fitness value.

def stddev(self):

This function returns the standard deviation of fitness values.

def sorted(self):

This function returns the fitness list sorted in fitness order according to the fitness type.

Selection Class

This is the base class for methods appropriate for assessing the fitness landscape. _selection_type refers to the technique associated with the selection method that is subclassed.

The selection_list used in this class is an ordinary list of values, not a fitness list, the fitness list being a list of tuples.

It is the responsibility of the derived classes to adjust the selection list values as needed.

def __init__(self, selection_list=None):

def set_selection_list(self, selection_list):

This function accepts the selection list. This is the list of fitness values that may have been transformed for the selection process.

def set_selection_type(self, selection_type):

This function accepts the selection type, which must be either 'min' or 'max'. The selection type is used by the subclass to know how to manipulate the list to achieve the fitness goals.

def _roulette_wheel(scale_list):

This function receives a list that has been scaled so that the sum total of the list is 1.0. This enables a fair use of probability. This is a generator that yields a random selection from the list.

def _make_sort_list(self):

This function sorts the _selection list making it similar to the original fitness list, except the the fitness values have been adjusted.

Tournament Class

Selects random tuples and returns either the minimum or maximum. To speed up the rate of selection, use larger tournament sizes, and smaller to slow down the process.

def __init__(self, selection_list=None, tournament_size=None):

def set_tournament_size(self, tournament_size):

This function accepts the tournament size, which is the number of members that will be selected per tournament.

def _set_minmax(self, minmax):

This function sets whether the selection should minimize or maximize.

def select(self):

The select function provides all the members based upon the class algorithm.

Fitness Class

This class is the prototype for the fitness functions. The primary job of a fitness function is to deal with the list of [fitness value, member no] pairs that are generated as a result of a run.

It also scales and configures the fitness values to be consistent with the fitness functions characteristics. For example, if the fitness strategy is to minimize values and the Fitness selection strategy maximizes, then the fitness values will be converted to -value. If the fitness strategy centers on a value, such as zero, then the values will be converted to the absolute distance from that value.

def __init__(self, fitness_list):

def set_fitness_list(self, fitness_list):

This function accepts the fitness list. It is the list of fitness values by member number for a population.

def _invert(value):

This method returns the reciprocal of the value.

def _scale_list(self):

This function scales the list to convert for example min to max where the selection type warrants it.

def _make_prob_list(selection_list):

This function aids in calculating probability lists. It scales the values to add up to 1.0.

FitnessProportionate Class

The probability of selection is based upon the fitness value of the individual relative to the rest of the population.

Pr(G_i) = f(G_i)/ sum(1 to pop) f(G_i)

This is the total probability. Roulette wheel selects individuals randomly, highest fitness more likely to be included.

Note that inherent in this approach is the assumption that the fitness value should be as large as possible. Consequently, if the fitness type is MIN or CENTER, a modification is made. In the case of MIN, inverse of the fitness values are used. For the CENTER fitness type, the inverse of the absolute difference between the target value and the fitness values are used.

The available scaling methods are:

  • SCALING_LINEAR = 'linear'
  • SCALING_TRUNC = 'truncation'
  • SCALING_EXPONENTIAL = 'exponential'
  • SCALING_LOG = 'logarithmic'

Truncation can be selected via ex: self.select(param=). Upon truncation, the fitness values are linearly scaled.

The default value for exponential is 2.0, but that is adjustable via: ex: self.select(param=1.5)

Also, note that because a probability map is derived from the scaled numbers, the fitness values must all be positive or all negative for this approach to be valid. In addition, the logarithmic scaling also requires that the fitness values must be 1 or above, prior to scaling. This is because the log below 1 is a negative number, which then interferes with the calculation of the probabilities.

def __init__(self, fitness_list, scaling_type):

def set_scaling_type(self, scaling_type):

This function accepts the type of scaling that will be performed on the data in preparation of building a probability list for the roulette selection.

def _check_minmax(self):

If selection of fitness is with proportions, then they must all be the same sign. Also, negative numbers do not mix with logs.

def select(self, param=None):

The select function provides all the members based upon the class algorithm.

def _apply_prop_scaling(self, param):

This function scales the values according to the scale type.

FitnessTournament Class

This class selects the fitness based on a tournament. It defaults to a tournament size of 2, but it can be anything up to the size of the population.

def __init__(self, fitness_list, tournament_size=2):

FitnessElites Class

This class selects the highest or lowest fitness depending upon what is desired. The fitness list is put into the selection list in this case so that once the sorting for rank takes place, the member numbers are still available.

def __init__(self, fitness_list, rate):

def set_rate(self, rate):

This function accepts a value greater than 0 and less than or equal to 1.0. It is the percentage of members from a list sorted by best values.

def select(self):

The select function provides all the members based upon the class algorithm.

FitnessLinearRanking Class

This class selects fitness on the basis of rank with other members. Only the position in the ranking matters rather than the fitness value. The probability curve is calculated on that basis. Then, roulette selection takes place.

This uses the formula for the probability curve of: Probability = 1 / population * (worstfactor + (best - worstfactor) * (rank(Member) - 1) / (population - 1))

where best = 2.0 - worstfactor

the best individual produces up to twice the children as the average.

To make sense of this: Suppose that the worst factor is .6 and therefor the best factor is 1.4. That will generate a probability list where the most fit members will be weighted more highly than less fit members.

If the worst factor is 1.0 and therefore the best factor is 1.0 too, the slope of the probability line will flat.

And finally, if the worst factor is 1.6 and the best factor is .4, the slope of the probaility line will cause the less fit members to have a higher probability of being selected than the more fit members.

def __init__(self, fitness_list, worstfactor):

def set_worstfactor(self, worstfactor):

This function sets the worst factor. See the class description for more.

def select(self):

The select function provides all the members based upon the class algorithm.

def _linear_ranking(count, worst):

This applies the best and worst factors and assigns the selection probability to each rank.

This returns a list of those probabilities.

FitnessTruncationRanking Class

This class selects fitness on the basis of rank with other members if above a certain rank. Once above that rank, any member can be selected with an equal probability. The truncation value is entered as a rate and converted to a ranking value. For example, if a population has 100 members and a truncation value of .2, the truncated ranking will be converted to a rank of 20.

def __init__(self, fitness_list, trunc_rate):

def set_trunc_rate(self, trunc_rate):

This function sets the rate, between 0 and 1 that is a hurdle for selection.

def select(self):

The select function provides all the members based upon the class algorithm.

def _calc_prob(length, cutoff_rank):

This function calculates the probability that a member will be selected if it falls within the cutoff rank.

Replacement Class

This is the base class for the classes that identify which members are to be replaced. It is basically the same as a fitness class, but attempts to identify the worst, not the best.

def __init__(self, fitness_list):

ReplacementDeleteWorst Class

This class is the mirror image of FitnessElite. The worst members are returned.

def __init__(self, fitness_list, replacement_count):

This function initializes Replacement and then adds a replacement count for handling the number of members that will be replaced each time.

def set_replacement_count(self, replacement_count):

This function accepts the number of members to be replaced.

def select(self):

select is a generator that yields the members for replacement sorted from worst to best. It halts when the replacemnt count has been reached.

ReplacementTournament Class

This class selects the fitness based on a tournament.

def __init__(self, fitness_list, tournament_size):

This class combines Replacement and Tournament. It inits Replacement first, because both have a select function and the Tournament select function is the one that matters.