/usr/lib/python2.7/dist-packages/deap/tools/selection.py is in python-deap 1.0.2.post2-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 | from __future__ import division
import random
from functools import partial
from operator import attrgetter
######################################
# Selections #
######################################
def selRandom(individuals, k):
"""Select *k* individuals at random from the input *individuals* with
replacement. 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.
:returns: A list of selected individuals.
This function uses the :func:`~random.choice` function from the
python base :mod:`random` module.
"""
return [random.choice(individuals) for i in xrange(k)]
def selBest(individuals, k):
"""Select the *k* best individuals among the input *individuals*. 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.
:returns: A list containing the k best individuals.
"""
return sorted(individuals, key=attrgetter("fitness"), reverse=True)[:k]
def selWorst(individuals, k):
"""Select the *k* worst individuals among the input *individuals*. 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.
:returns: A list containing the k worst individuals.
"""
return sorted(individuals, key=attrgetter("fitness"))[:k]
def selTournament(individuals, k, tournsize):
"""Select *k* individuals from the input *individuals* using *k*
tournaments of *tournsize* individuals. 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 tournsize: The number of individuals participating in each tournament.
:returns: A list of selected individuals.
This function uses the :func:`~random.choice` function from the python base
:mod:`random` module.
"""
chosen = []
for i in xrange(k):
aspirants = selRandom(individuals, tournsize)
chosen.append(max(aspirants, key=attrgetter("fitness")))
return chosen
def selRoulette(individuals, k):
"""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.
:returns: A list of selected individuals.
This function uses the :func:`~random.random` function from the python base
:mod:`random` module.
.. warning::
The roulette selection by definition cannot be used for minimization
or when the fitness can be smaller or equal to 0.
"""
s_inds = sorted(individuals, key=attrgetter("fitness"), reverse=True)
sum_fits = sum(ind.fitness.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_ += ind.fitness.values[0]
if sum_ > u:
chosen.append(ind)
break
return chosen
def selDoubleTournament(individuals, k, fitness_size, parsimony_size, fitness_first):
"""Tournament selection which use the size of the individuals in order
to discriminate good solutions. This kind of tournament is obviously
useless with fixed-length representation, but has been shown to
significantly reduce excessive growth of individuals, especially in GP,
where it can be used as a bloat control technique (see
[Luke2002fighting]_). This selection operator implements the double
tournament technique presented in this paper.
The core principle is to use a normal tournament selection, but using a
special sample function to select aspirants, which is another tournament
based on the size of the individuals. To ensure that the selection
pressure is not too high, the size of the size tournament (the number
of candidates evaluated) can be a real number between 1 and 2. In this
case, the smaller individual among two will be selected with a probability
*size_tourn_size*/2. For instance, if *size_tourn_size* is set to 1.4,
then the smaller individual will have a 0.7 probability to be selected.
.. note::
In GP, it has been shown that this operator produces better results
when it is combined with some kind of a depth limit.
:param individuals: A list of individuals to select from.
:param k: The number of individuals to select.
:param fitness_size: The number of individuals participating in each \
fitness tournament
:param parsimony_size: The number of individuals participating in each \
size tournament. This value has to be a real number\
in the range [1,2], see above for details.
:param fitness_first: Set this to True if the first tournament done should \
be the fitness one (i.e. the fitness tournament producing aspirants for \
the size tournament). Setting it to False will behaves as the opposite \
(size tournament feeding fitness tournaments with candidates). It has been \
shown that this parameter does not have a significant effect in most cases\
(see [Luke2002fighting]_).
:returns: A list of selected individuals.
.. [Luke2002fighting] Luke and Panait, 2002, Fighting bloat with
nonparametric parsimony pressure
"""
assert (1 <= parsimony_size <= 2), "Parsimony tournament size has to be in the range [1, 2]."
def _sizeTournament(individuals, k, select):
chosen = []
for i in xrange(k):
# Select two individuals from the population
# The first individual has to be the shortest
prob = parsimony_size / 2.
ind1, ind2 = select(individuals, k=2)
if len(ind1) > len(ind2):
ind1, ind2 = ind2, ind1
elif len(ind1) == len(ind2):
# random selection in case of a tie
prob = 0.5
# Since size1 <= size2 then ind1 is selected
# with a probability prob
chosen.append(ind1 if random.random() < prob else ind2)
return chosen
def _fitTournament(individuals, k, select):
chosen = []
for i in xrange(k):
aspirants = select(individuals, k=fitness_size)
chosen.append(max(aspirants, key=attrgetter("fitness")))
return chosen
if fitness_first:
tfit = partial(_fitTournament, select=selRandom)
return _sizeTournament(individuals, k, tfit)
else:
tsize = partial(_sizeTournament, select=selRandom)
return _fitTournament(individuals, k, tsize)
__all__ = ['selRandom', 'selBest', 'selWorst', 'selRoulette',
'selTournament', 'selDoubleTournament']
|