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