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
8 import random
9 import copy
10
11
12 from Abstract import AbstractSelection
13
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
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
49
50 prob_wheel = self._set_up_wheel(population)
51 probs = prob_wheel.keys()
52 probs.sort()
53
54
55 new_population = []
56
57 for pair_spin in range(len(population) / 2):
58
59 choice_num_1 = random.random()
60 choice_num_2 = random.random()
61
62
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
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
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
107 total_fitness = 0
108 for org in population:
109 total_fitness += org.fitness
110
111
112 wheel_dict = {}
113 total_percentage = 0
114 for org in population:
115 org_percentage = float(org.fitness) / float(total_fitness)
116
117
118
119
120 wheel_dict[total_percentage + org_percentage] = copy.copy(org)
121
122
123 total_percentage += org_percentage
124
125 return wheel_dict
126