mod diversity

module diversity

Annealing the distance at which two solutions count as one. Annealing the distance that decides when two solutions are the same.

Every basin-keyed mechanism in this crate compares a distance against a threshold held fixed for the run. That threshold is not a constant of the problem, and treating it as one is why three separate calibrations of it failed to find a value that transferred.

Lee, Lee and Scheraga make the case directly (Conformational space annealing, arXiv cond-mat/0307690). Their Dcut “plays the role of the temperature in simulated annealing”: the diversity of sampling is controlled by comparing a distance between two configurations against it, and “the value of Dcut is slowly reduced just as in SA, hence the name conformational space annealing”. It is a schedule, not a setting, and it is the mechanism behind the only published method that solves the hard Lennard-Jones sizes reliably: ten independent runs finding every known global minimum up to 183 atoms, against 4 runs in 1000 for a basin-hopping variant at 75 atoms.

Two details from that paper are load-bearing and are kept here.

The initial value is taken from the data, as half the average distance among the first population, not chosen in advance. A threshold in a shape metric has units of length and the right length depends on the system, which is exactly what a hand-set radius cannot know.

The reduction is slow. The threshold starts wide, so distinct-looking solutions are held apart and the search stays diverse, and narrows, so finer distinctions are resolved as the budget runs down. Annealing it the other way, or holding it at the narrow end, collapses the population early.

What this module supplies is the schedule. The distance measure is the caller’s, which for clusters is the shape distance in crate::shape.

What this must not be applied to

Dcut decides which new solutions are admitted to a population. A merge radius decides which structures count as the same basin for a bias. They are different parameters and only one of them can be annealed downwards freely.

A basin threshold is bounded below by the distance a single accepted hop covers. Measured on 75-point minima that is 0.4766, against 0.9212 between independent minima, so a threshold below roughly a half stops recognising a structure the chain has already visited. Driving it there makes every hop open a new basin and the well-tempered bias never accumulates.

That is not hypothetical. Annealing the merge radius from 0.7 to a tenth of it took an LJ75 run from about 250 basins at 25 revisits each to 4423 basins at 2.6, and the best structure found from -396.282 to -394.629. The schedule was correct and the quantity was wrong.

Structs and Unions

struct DiversityAnnealer

A distance threshold annealed from wide to narrow over a budget.

The threshold is a length in whatever metric the caller uses. It is not constructed with a value: DiversityAnnealer::from_population takes it from the spread of an initial population, which is what makes it a property of the system rather than of this file.

anneal_fraction: f64

Fraction of the budget over which the threshold reaches its floor.

queries: usize

Times the threshold was queried.

Implementations

impl DiversityAnnealer

Functions

fn current(&self) -> f64

Most recently returned threshold, without advancing anything.

fn from_initial(initial: f64) -> Self

Threshold starting at a stated value, for callers with their own scale.

fn from_population<D>(members: &[usize], mut distance: D) -> Option<Self>
where
    D: FnMut(usize, usize) -> f64

Threshold starting at half the mean pairwise distance of a population.

The factor of one half is the paper’s: Dcut starts at Dave / 2 where Dave is the average distance among the first bank.

Returns None when fewer than two members are supplied, or when every pair is at zero distance, since neither gives a scale and a threshold invented at that point would be the hand-set constant this replaces.

fn initial(&self) -> f64

Threshold the schedule started from.

fn threshold(&mut self, progress: f64) -> f64

Threshold at progress through the budget, in [0, 1].

Geometric rather than linear, because the threshold is a scale: halving it matters equally wherever it starts, and a linear schedule spends most of the run near the wide end and then collapses.

fn with_final_fraction(mut self, fraction: f64) -> Self

Sets the floor as a fraction of the initial threshold.