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
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
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
54
55 prob_wheel = self._set_up_wheel(population)
56 probs = sorted(prob_wheel)
57
58
59 new_population = []
60
61 for pair_spin in range(len(population) // 2):
62
63 choice_num_1 = random.random()
64 choice_num_2 = random.random()
65
66
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
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
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
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