Package Bio :: Package GA :: Package Selection :: Module RouletteWheel
[hide private]
[frames] | no frames]

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