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

Source Code for Module Bio.GA.Selection.RouletteWheel

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