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.
class evoalgos.niching.NearestBetterClustering(edge_length_factor=2.0, used_rules=(1, 2), dist_matrix_function=None, use_edge_lengths_for_threshold=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, 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.
  • 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
cluster(population)

Construct spanning tree from the population and prune it.

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 – 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().
Return type:list
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