niching — Basin Identification Methods

Basin identification methods.

This module contains two different approaches to identify different attraction basins of a multimodal, real-valued function from a finite sample of points in its domain.

class evoalgos.niching.TopographicalSelection(num_neighbors, dist_matrix_function=None, use_all_distances=True, sort_key=None)

Basin identification via a k-nearest-neighbors graph.

This implementation is based on the description in [Toern1992].

References

[Toern1992](1, 2) Törn, A. and Viitanen, S. (1992). Topographical global optimization. In: C.A. Floudas and P.M. Pardalos (Eds.), Recent Advances in Global Optimization, Princeton University Press, pp. 384-398.
[Wessing2016](1, 2) Simon Wessing, Günter Rudolph, Mike Preuss (2016). Assessing Basin Identification Methods for Locating Multiple Optima. In Panos M. Pardalos, Anatoly Zhigljavsky, and Julius Zilinskas (eds.): Advances in Stochastic and Deterministic Global Optimization, Springer.
__init__(num_neighbors, dist_matrix_function=None, use_all_distances=True, sort_key=None)

Constructor.

Parameters:
  • num_neighbors (int) – The number of neighbors to consider in the graph.
  • dist_matrix_function (callable, optional) – A callable producing a distance matrix from two sequences of individuals. Default is Euclidean distance.
  • use_all_distances (bool, optional) – [Wessing2016] recommended to use all distances in the computations. In [Toern1992], only half the distances were considered to avoid problems caused by an inefficient graph data structure.
  • sort_key (callable, optional) – A sort key for determining which individual is better. Default is lexicographic ordering of objective values.
select(population)

Return individuals corresponding to different local optima.

Note that population is not modified. The number of selected individuals is dependent on the used number of neighbors and cannot be controlled directly.

Parameters:population (iterable) – The individuals to select from.
Returns:selected – Selected individuals from the population.
Return type:list of Individual
class evoalgos.niching.NearestBetterClustering(edge_length_factor=2.0, used_rules=(1, 2), dist_matrix_function=None, use_edge_lengths_for_threshold=False, require_incoming_edge=False, sort_key=None)

Basin identification via nearest-better distances.

This is a hierarchical clustering method introduced in [Preuss2012]. In a first step, the method constructs a spanning tree, which is divided into several connected components in a second step.

References

[Preuss2012](1, 2) Mike Preuss (2012). Improved Topological Niching for Real-Valued Global Optimization. In: Applications of Evolutionary Computation, Volume 7248 of the series Lecture Notes in Computer Science, pp. 386-395, Springer. https://dx.doi.org/10.1007/978-3-642-29178-4_39
__init__(edge_length_factor=2.0, used_rules=(1, 2), dist_matrix_function=None, use_edge_lengths_for_threshold=False, require_incoming_edge=False, sort_key=None)

Constructor.

Parameters:
  • edge_length_factor (float, optional) – This factor is multiplied with the reference distance, which is estimated from the data. The result is a threshold for separating long and short edges.
  • used_rules (iterable, optional) – The set of used pruning rules. This must be either (1,), (2,), or (1, 2).
  • dist_matrix_function (callable, optional) – A callable producing a distance matrix from two sequences of individuals. Default is Euclidean distance.
  • use_edge_lengths_for_threshold (bool, optional) – Setting this value to True recovers the original behavior of rule 1 as used in [Preuss2012]. The other variant was proposed in [Wessing2016] to eliminate the influence of the actual number of attraction basins on the threshold calculation.
  • require_incoming_edge (bool, optional) – Setting this value to True tightens rule 1 to that effect that only solutions with an incoming edge can be selected (rule 1b). This may help to prevent the accidental selection of outliers.
  • sort_key (callable, optional) – A sort key for determining which individual is better. Default is lexicographic ordering of objective values.
build_spanning_tree(population)

Build the spanning tree using nearest-better distances.

Returns:edges – A list of edges. Each edge is a three-tuple (tail, weight, head).
Return type:list
calc_reference_distance(population, spanning_tree)

Calculate the reference distance required for the threshold.

Returns:
  • population (list of Individual) – The individuals that shall be clustered.
  • spanning_tree (list) – A list of edges. Each edge is a three-tuple (tail, weight, head).
cluster(population, spanning_tree=None)

Prune the spanning tree of the population.

The returned edges represent a disconnected graph. However, the edges are not grouped into connected components. The number of connected components is dependent on the edge-length factor and cannot be controlled directly.

Returns:
  • edges (list) – A list of edges. Each edge is a three-tuple (tail, weight, head). The returned edges are a subset of those returned by build_spanning_tree().
  • spanning_tree (list, optional) – Optionally, the precomputed spanning tree can be provided as a list of edges. Each edge is a three-tuple (tail, weight, head).
static connected_components(edges)

Identify weakly connected components from a list of edges.

This method is geared for application to the output of cluster().

Parameters:edges (list) – A list of edges. Each edge is a three-tuple (tail, weight, head).
Returns:components – Each set in this list corresponds to a connected component.
Return type:list of set
static median(data)

Return the median (middle value) of numeric data.

When the number of data points is odd, return the middle data point. When the number of data points is even, the median is interpolated by taking the average of the two middle values.

This function is needed as a helper function for rule 2 and included here for compatibility with Python 2.

select(population)

Build spanning tree, prune, and select sink of each component.

The number of selected individuals is dependent on the edge-length factor and cannot be controlled directly.

Returns:graph_minima – A list of individuals. They are the only nodes in the graph without outgoing edges.
Return type:list of Individual