I am implementing a genetic algorithm in numpy and I'm trying to figure out how to correctly implement selection via roulette wheel and stochastic universal sampling. The examples I've seen on stackoverflow or elsewhere use a python loop rather than vectorized numpy code.
For example, here are the implementations of both algorithms in DEAP.
def selRoulette(individuals, k, fit_attr="fitness"):
"""Select *k* individuals from the input *individuals* using *k*
spins of a roulette. The selection is made by looking only at the first
objective of each individual. The list returned contains references to
the input *individuals*.
:param individuals: A list of individuals to select from.
:param k: The number of individuals to select.
:param fit_attr: The attribute of individuals to use as selection criterion
:returns: A list of selected individuals.
This function uses the :func:`~random.random` function from the python base
"""
s_inds = sorted(individuals, key=attrgetter(fit_attr), reverse=True)
sum_fits = sum(getattr(ind, fit_attr).values[0] for ind in individuals)
chosen = []
for i in xrange(k):
u = random.random() * sum_fits
sum_ = 0
for ind in s_inds:
sum_ += getattr(ind, fit_attr).values[0]
if sum_ > u:
chosen.append(ind)
break
return chosen
def selStochasticUniversalSampling(individuals, k, fit_attr="fitness"):
"""Select the *k* individuals among the input *individuals*.
The selection is made by using a single random value to sample all of the
individuals by choosing them at evenly spaced intervals. The list returned
contains references to the input *individuals*.
:param individuals: A list of individuals to select from.
:param k: The number of individuals to select.
:param fit_attr: The attribute of individuals to use as selection criterion
:return: A list of selected individuals.
"""
s_inds = sorted(individuals, key=attrgetter(fit_attr), reverse=True)
sum_fits = sum(getattr(ind, fit_attr).values[0] for ind in individuals)
distance = sum_fits / float(k)
start = random.uniform(0, distance)
points = [start + i*distance for i in xrange(k)]
chosen = []
for p in points:
i = 0
sum_ = getattr(s_inds[i], fit_attr).values[0]
while sum_ < p:
i += 1
sum_ += getattr(s_inds[i], fit_attr).values[0]
chosen.append(s_inds[i])
return chosen
Here is my implementation of roulette wheel, which seems to be weighted sampling with replacement, but I'm not sure about the replacement parameter.
# population is a 2D array of integers
# population_fitness is a 1D array of float of same length as population
weights = population_fitness / population_fitness.sum()
selected = population[np.random.choice(len(population), size=n, replace=True, p=weights)]
And here is my implementation of SUS selection. Am I correct that, when implemented in numpy, the only thing I have to change is that sampling is without replacement, or should I also remove the weights?
weights = population_fitness / population_fitness.sum()
selected = population[np.random.choice(len(population), size=n, replace=False, p=weights)]
Thanks for any suggestions!
from numpy genetic algorithm selection: roulette wheel vs. stochastic universal sampling
No comments:
Post a Comment