pythonbiopython
1.60

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