Back to index

python-biopython  1.60
RouletteWheel.py
Go to the documentation of this file.
00001 """Implement Roulette Wheel selection on a population.
00002 
00003 This implements Roulette Wheel selection in which individuals are
00004 selected from a population randomly, with their proportion of selection
00005 based on their relative fitness in the population.
00006 """
00007 # standard modules
00008 import random
00009 import copy
00010 
00011 # local modules
00012 from Abstract import AbstractSelection
00013 
00014 class RouletteWheelSelection(AbstractSelection):
00015     """Roulette wheel selection proportional to individuals fitness.
00016 
00017     The implements a roulette wheel selector that selects individuals
00018     from the population, and performs mutation and crossover on
00019     the selected individuals.
00020     """
00021     def __init__(self, mutator, crossover, repairer = None):
00022         """Initialize the selector.
00023 
00024         Arguments:
00025 
00026         o mutator -- A Mutation object which will perform mutation
00027         on an individual.
00028 
00029         o crossover -- A Crossover object which will take two
00030         individuals and produce two new individuals which may
00031         have had crossover occur.
00032 
00033         o repairer -- A class which can do repair on rearranged genomes
00034         to eliminate infeasible individuals. If set at None, so repair
00035         will be done.
00036         """
00037         AbstractSelection.__init__(self, mutator, crossover, repairer)
00038 
00039     def select(self, population):
00040         """Perform selection on the population based using a Roulette model.
00041 
00042         Arguments:
00043 
00044         o population -- A population of organisms on which we will perform
00045         selection. The individuals are assumed to have fitness values which
00046         are due to their current genome.
00047         """
00048         # set up the current probabilities for selecting organisms
00049         # from the population
00050         prob_wheel = self._set_up_wheel(population)
00051         probs = prob_wheel.keys()
00052         probs.sort()
00053         
00054         # now create the new population with the same size as the original
00055         new_population = []
00056 
00057         for pair_spin in range(len(population) // 2):
00058             # select two individuals using roulette wheel selection
00059             choice_num_1 = random.random()
00060             choice_num_2 = random.random()
00061 
00062             # now grab the two organisms from the probabilities
00063             chosen_org_1 = None
00064             chosen_org_2 = None
00065             prev_prob = 0
00066             for cur_prob in probs:
00067                 if choice_num_1 > prev_prob and choice_num_1 <= cur_prob:
00068                     chosen_org_1 = prob_wheel[cur_prob]
00069                 if choice_num_2 > prev_prob and choice_num_2 <= cur_prob:
00070                     chosen_org_2 = prob_wheel[cur_prob]
00071 
00072                 prev_prob = cur_prob
00073 
00074             assert chosen_org_1 is not None, "Didn't select organism one"
00075             assert chosen_org_2 is not None, "Didn't select organism two"
00076 
00077             # do mutation and crossover to get the new organisms
00078             new_org_1, new_org_2 = self.mutate_and_crossover(chosen_org_1,
00079                                                              chosen_org_2)
00080             
00081             new_population.extend([new_org_1, new_org_2])
00082 
00083         return new_population
00084 
00085     def _set_up_wheel(self, population):
00086         """Set up the roulette wheel based on the fitnesses.
00087 
00088         This creates a fitness proportional 'wheel' that will be used for
00089         selecting based on random numbers.
00090 
00091         Returns:
00092         
00093         o A dictionary where the keys are the 'high' value that an
00094         individual will be selected. The low value is determined by
00095         the previous key in a sorted list of keys. For instance, if we
00096         have a sorted list of keys like:
00097 
00098         [.1, .3, .7, 1]
00099 
00100         Then the individual whose key is .1 will be selected if a number
00101         between 0 and .1 is chosen, the individual whose key is .3 will
00102         be selected if the number is between .1 and .3, and so on.
00103 
00104         The values of the dictionary are the organism instances.
00105         """
00106         # first sum up the total fitness in the population
00107         total_fitness = 0
00108         for org in population:
00109             total_fitness += org.fitness
00110 
00111         # now create the wheel dictionary for all of the individuals
00112         wheel_dict = {}
00113         total_percentage = 0
00114         for org in population:
00115             org_percentage = float(org.fitness) / float(total_fitness)
00116 
00117             # the organisms chance of being picked goes from the previous
00118             # percentage (total_percentage) to the previous percentage
00119             # plus the organisms specific fitness percentage
00120             wheel_dict[total_percentage + org_percentage] = copy.copy(org)
00121 
00122             # keep a running total of where we are at in the percentages
00123             total_percentage += org_percentage
00124 
00125         return wheel_dict