selection — Selection Components

Selection components for evolutionary algorithms.

class evoalgos.selection.Selection

Abstract base class for selection operators.

reduce_to(population, number, already_chosen=None)

Reduce population size to number and return the rejected.

This method is abstract. Here, population should be modified in-place.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – Definitely surviving individuals not included in population, but which might influence these ones.
Returns:

rejected – The removed individuals.
Return type:

list
select(population, number, already_chosen=None)

Return number individuals from the population.

Note that population is not modified.

Parameters:
  • population (sequence) – The individuals to select from.
  • number (int) – The number of individuals to select.
  • already_chosen (sequence of Individual, optional) – Definitely surviving individuals not included in population, but which might influence these ones.
class evoalgos.selection.BackwardElimination(selection)

Wrapper for other selection components.

__init__(selection)

Constructor.

Parameters:selection (Selection) – The selection component that is forced to backward elimination by this wrapper.
reduce_to(population, number, already_chosen=None)

Reduce population size to number and return the rejected.

This method iteratively calls the respective method of the selection component, removing one individual per call.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – Definitely surviving individuals not included in population, but which might influence these ones.
Returns:

rejected – The removed individuals.
Return type:

list
class evoalgos.selection.ForwardSelection(selection)

Wrapper for other selection components.

__init__(selection)

Constructor.

Parameters:selection (Selection) – The selection component that is forced to forward selection by this wrapper.
reduce_to(population, number, already_chosen=None)

Reduce population size to number and return the rejected.

This method iteratively calls the respective method of the selection component, selecting the best individual per call.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – Definitely surviving individuals not included in population, but which might influence these ones.
Returns:

rejected – The removed individuals.
Return type:

list
select(population, number, already_chosen=None)

Return number individuals from the population.

Note that population is not modified.

Parameters:
  • population (sequence) – The individuals to select from.
  • number (int) – The number of individuals to select.
  • already_chosen (sequence of Individual, optional) – Definitely surviving individuals not included in population, but which might influence these ones.
class evoalgos.selection.UniformSelection

Choose individuals random uniformly from the population.

reduce_to(population, number, already_chosen=None)

Discard randomly selected members of the population and return them.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – This parameter has no influence for this selection.
Returns:

rejected – The removed individuals.
Return type:

list
select(population, number, already_chosen=None)

Return number randomly drawn individuals from population.

Note that population is not modified.

Parameters:
  • population (sequence) – The individuals to select from.
  • number (int) – The number of individuals to select.
  • already_chosen (sequence of Individual, optional) – This parameter has no influence for this selection.
class evoalgos.selection.TruncationSelection(sorting_component=None)

Choose strictly the best individuals according to sorting component.

The features depend heavily on the used sorting component. In particular, the selection is only deterministic and elitistic if the sorting component is, too.

__init__(sorting_component=None)

Constructor.

Parameters:sorting_component (SortingComponent, optional) – The sorting component that is used to establish a ranking of the individuals. Default is LexicographicSorting.
reduce_to(population, number, already_chosen=None)

Reduce population size to number and return the rejected.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – Definitely surviving individuals not included in population, but which might influence these ones (depending on sorting component).
Returns:

rejected – The removed individuals.
Return type:

list
class evoalgos.selection.HyperVolumeContributionSelection(offsets=None, prefer_boundary_points=True, selection_variant='auto')

Use the individuals’ hypervolume contribution as criterion.

This selection is designed for multi-objective problems. The selection criterion is the individuals’ hypervolume contribution to the dominated hypervolume of the non-dominated front it belongs to.

__init__(offsets=None, prefer_boundary_points=True, selection_variant='auto')

Constructor.

Parameters:
  • offsets (sequence, optional) – For calculating the hypervolume, a reference point is required. The reference point is typically calculated as the worst objective values in the set of individuals plus an offset vector, which can be specified here. Default offset is [1.0, ..., 1.0].
  • prefer_boundary_points (bool, optional) – This flag only pertains to the two-objective case. If it is set to True, the two boundary points (but not their potentially existing duplicates) of a front are guaranteed to be retained.
  • selection_variant (string, optional) – This argument has the possible values ‘forward-greedy’, ‘backward-greedy’, ‘super-greedy’, and ‘auto’. ‘backward-greedy’ means that the worst individuals are iteratively removed one by one (also known as backward elimination). ‘forward-greedy’ means that also iteratively, the individual maximizing the hypervolume together with the already selected ones is chosen. ‘auto’ selects forward selection if \lambda > \mu, and backward elimination otherwise. This rule was devised based on results in [Schendekehl2017]. Finally, ‘super-greedy’ removes the necessary number of individuals without recalculating the fitness of the other ones in between (this is faster, but not recommended). We have to know the variant internally, because the results of the wrapper approach with BackwardElimination or ForwardSelection are not 100% correct (due to reference point construction being triggered in every iteration) and because some time can be saved.

References

[Schendekehl2017]Tim Schendekehl (2017). Vergleich von gieriger Vorwärts- und Rückwärtsselektion bezüglich exaktem und approximiertem Hypervolumen. Master thesis, available as Algorithm engineering report TR17-2-001, Technische Universität Dortmund. (in German) https://ls11-www.cs.tu-dortmund.de/_media/techreports/tr17-01.pdf
construct_ref_point(individuals, offsets=None)

Construct a reference point from the given individuals.

Parameters:
  • individuals (sequence) – The individuals whose objective values are considered. For each objective, the worst value is taken.
  • offsets (sequence, optional) – Non-negative offsets to be added to the worst values. The default is [1.0, ..., 1.0].
reduce_to(population, number, already_chosen=None)

Reduce population size to number and return the rejected.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – Individuals which influence the fitness values for the population, but do not underlie selection themselves. Empty by default.
Returns:

rejected – The removed individuals.
Return type:

list of Individual
class evoalgos.selection.NearestBetterSelection(dist_matrix_function=None, sorting_component=None, use_neighbor_count=False, multiobjective=False)

Selection with information about nearest better neighbors.

__init__(dist_matrix_function=None, sorting_component=None, use_neighbor_count=False, multiobjective=False)

Constructor.

Parameters:
  • dist_matrix_function (callable, optional) – A function which takes two sequences of individuals as input (say, sizes n and m), and returns an (n \times m) matrix of distances as output. Default is Euclidean distance.
  • sorting_component (SortingComponent, optional) – This component is used to determine the fitness levels in the population, by its method identify_groups(). Default is LexicographicSorting.
  • use_neighbor_count (bool, optional) – Indicates which selection criterion is used. If False, the population is ranked descending by nearest-better neighbor distances (called variant SV7 in [Wessing2016a]). If True (default), for each individual the neighbors being closer than the nearest-better neighbor are counted. The ranking is then descending by this number. This approach is the basic concept behind “rule 3” as described on pages 101-103 of [Wessing2015]. In any case, the order of the sorting component is used as secondary criterion to break ties.
  • multiobjective (bool, optional) – Decides if the nearest-better data and objective-related data is combined in a multiobjective fashion (by non-dominated sorting) or by lexicographic sorting. The setting where multiobjective == True and use_neighbor_count == False corresponds to the variant SV4 in [Wessing2016a].

References

[Wessing2015]Wessing, Simon (2015). Two-stage Methods for Multimodal Optimization. PhD Thesis, Technische Universität Dortmund. http://hdl.handle.net/2003/34148
[Wessing2016a](1, 2) Simon Wessing, Mike Preuss (2016). On multiobjective selection for multimodal optimization. Computational Optimization and Applications, Vol. 63, Issue 3, pp. 875-902. https://dx.doi.org/10.1007/s10589-015-9785-x
reduce_to(population, number, already_chosen=None)

Reduce population size to number and return the rejected.

Internally, NearestBetterSorting is used to obtain the necessary ranking. Then, a simple truncation is done for selection.

Parameters:
  • population (sequence) – The population to reduce in size.
  • number (int) – The number of individuals to reduce to.
  • already_chosen (sequence of Individual, optional) – Individuals which influence the distance calculations for the population, but do not underlie selection themselves. Empty by default.
Returns:

rejected – The removed individuals.
Return type:

list of Individual