Source Code for Module Bio.GA.Selection.RouletteWheel

  1  """Implement Roulette Wheel selection on a population. 
  2   
  3  This implements Roulette Wheel selection in which individuals are 
  4  selected from a population randomly, with their proportion of selection 
  5  based on their relative fitness in the population. 
  6  """ 
  7  # standard modules 
  8  import random 
  9  import copy 
 10   
 11  # local modules 
 12  from Abstract import AbstractSelection 
 13   
 14   
 15 -class RouletteWheelSelection(AbstractSelection): 
 16      """Roulette wheel selection proportional to individuals fitness. 
 17   
 18      The implements a roulette wheel selector that selects individuals 
 19      from the population, and performs mutation and crossover on 
 20      the selected individuals. 
 21      """ 
 22 -    def __init__(self, mutator, crossover, repairer = None): 
 23          """Initialize the selector. 
 24   
 25          Arguments: 
 26   
 27          o mutator -- A Mutation object which will perform mutation 
 28          on an individual. 
 29   
 30          o crossover -- A Crossover object which will take two 
 31          individuals and produce two new individuals which may 
 32          have had crossover occur. 
 33   
 34          o repairer -- A class which can do repair on rearranged genomes 
 35          to eliminate infeasible individuals. If set at None, so repair 
 36          will be done. 
 37          """ 
 38          AbstractSelection.__init__(self, mutator, crossover, repairer) 
 39   
 40 -    def select(self, population): 
 41          """Perform selection on the population based using a Roulette model. 
 42   
 43          Arguments: 
 44   
 45          o population -- A population of organisms on which we will perform 
 46          selection. The individuals are assumed to have fitness values which 
 47          are due to their current genome. 
 48          """ 
 49          # set up the current probabilities for selecting organisms 
 50          # from the population 
 51          prob_wheel = self._set_up_wheel(population) 
 52          probs = prob_wheel.keys() 
 53          probs.sort() 
 54   
 55          # now create the new population with the same size as the original 
 56          new_population = [] 
 57   
 58          for pair_spin in range(len(population) // 2): 
 59              # select two individuals using roulette wheel selection 
 60              choice_num_1 = random.random() 
 61              choice_num_2 = random.random() 
 62   
 63              # now grab the two organisms from the probabilities 
 64              chosen_org_1 = None 
 65              chosen_org_2 = None 
 66              prev_prob = 0 
 67              for cur_prob in probs: 
 68                  if choice_num_1 > prev_prob and choice_num_1 <= cur_prob: 
 69                      chosen_org_1 = prob_wheel[cur_prob] 
 70                  if choice_num_2 > prev_prob and choice_num_2 <= cur_prob: 
 71                      chosen_org_2 = prob_wheel[cur_prob] 
 72   
 73                  prev_prob = cur_prob 
 74   
 75              assert chosen_org_1 is not None, "Didn't select organism one" 
 76              assert chosen_org_2 is not None, "Didn't select organism two" 
 77   
 78              # do mutation and crossover to get the new organisms 
 79              new_org_1, new_org_2 = self.mutate_and_crossover(chosen_org_1, 
 80                                                               chosen_org_2) 
 81   
 82              new_population.extend([new_org_1, new_org_2]) 
 83   
 84          return new_population 
 85   
 86 -    def _set_up_wheel(self, population): 
 87          """Set up the roulette wheel based on the fitnesses. 
 88   
 89          This creates a fitness proportional 'wheel' that will be used for 
 90          selecting based on random numbers. 
 91   
 92          Returns: 
 93   
 94          o A dictionary where the keys are the 'high' value that an 
 95          individual will be selected. The low value is determined by 
 96          the previous key in a sorted list of keys. For instance, if we 
 97          have a sorted list of keys like: 
 98   
 99          [.1, .3, .7, 1] 
100   
101          Then the individual whose key is .1 will be selected if a number 
102          between 0 and .1 is chosen, the individual whose key is .3 will 
103          be selected if the number is between .1 and .3, and so on. 
104   
105          The values of the dictionary are the organism instances. 
106          """ 
107          # first sum up the total fitness in the population 
108          total_fitness = 0 
109          for org in population: 
110              total_fitness += org.fitness 
111   
112          # now create the wheel dictionary for all of the individuals 
113          wheel_dict = {} 
114          total_percentage = 0 
115          for org in population: 
116              org_percentage = float(org.fitness) / float(total_fitness) 
117   
118              # the organisms chance of being picked goes from the previous 
119              # percentage (total_percentage) to the previous percentage 
120              # plus the organisms specific fitness percentage 
121              wheel_dict[total_percentage + org_percentage] = copy.copy(org) 
122   
123              # keep a running total of where we are at in the percentages 
124              total_percentage += org_percentage 
125   
126          return wheel_dict 
127