Source-linked AI summary
Levy Flights, Non-local Search and Simulated Annealing
I. Pavlyukevich
TL;DR
The paper addresses global optimisation of an unknown multi-well potential, where classical diffusion-based annealing faces localisation and cooling-rate constraints. It introduces simulated annealing driven by state-dependent Lévy flights with variable stability index. The method provides non-local search, global-minimum localisation in suitable regimes, and polynomial rather than logarithmic cooling, while optimal parameter selection remains open.
Problem
Global optimisation seeks the global minimum of a non-convex, multi-well potential, while classical annealing requires a critical cooling rate and fixed-index Lévy flights do not settle near the global minimum.
Method
The paper uses simulated annealing with state-dependent stable-like Lévy flights whose stability index α(x) varies with the particle's position.
Results
Suitable choices of α(x) localise the global minimum, while the search remains non-local and the temperature decreases polynomially as ∼t^-θ.
Takeaways & Limitations
Variable stability is crucial for successful global search and enables targeting approximately known wells or local minima below a specified energy.
Takeaways & Limitations
The optimal pair α(x) and θ that minimises search time remains unresolved, with very small α(mi) potentially causing large jumps and slower search in inner wells.
Abstract
from arXiv · showhide
We solve a problem of non-convex stochastic optimisation with help of simulated annealing of Levy flights of a variable stability index. The search of the ground state of an unknown potential is non-local due to big jumps of the Levy flights process. The convergence to the ground state is fast due to a polynomial decrease rate of the temperature.
1 Introduction
The paper frames global optimisation in multi-well potentials as a challenge for simulated annealing, contrasting logarithmic cooling with faster non-local Lévy-flight approaches. It proposes state-dependent Lévy flights whose variable stability index enables global-minimum localisation.
- Problem: Classical simulated annealing seeks a global minimum of a multi-well potential using a diffusion process.The potential has several local minima and increases rapidly at infinity.
- Classical simulated annealing: A critical cooling rate determines whether the diffusion converges to the global minimum.Convergence occurs when θ exceeds the critical value ˆθ; otherwise it fails.
- Classical simulated annealing: The critical cooling rate can be calculated from the heights of potential barriers between wells.The paper also cites rigorous results on optimal cooling rates.
- Non-local search: Fast simulated annealing combines a Metropolis algorithm with heavy-tailed Cauchy visiting distributions and uses power-law temperature decrease σ(t) ∼ t^-1.This introduces non-local search through large jumps.
- Lévy-flight approaches: Earlier continuous-time Lévy-flight annealing with fixed stability index never settles near a global minimum, motivating state-dependent flights.Those processes can instead reveal the spatial structure of the potential.
- Contribution: The present paper uses state-dependent Lévy flights in multi-well potentials and shows that suitable annealing regimes localise the global minimum.The theoretical discussion is one-dimensional, while the numerical example uses a two-dimensional potential with five wells.
2 Results on the cooled down L´evy flights
Cooled Lévy-flight processes exhibit distinct transition regimes, with behavior determined by the stability index and cooling rate. The jump measure and stable-like extensions characterize non-local motion and its well-to-well dynamics.
- Lévy-flight process: Lévy flights are symmetric stable processes with stability index α ∈ (0, 2), governed by a non-local generator.Their jump measure controls jump intensity and sizes, with jump counts on intervals following Poissonian laws with mean tν(J).
- Spatial structure: The potential is partitioned into attraction domains Ω_i around stable points m_i, and estimated occupancies π_i^(α) reveal their spatial structure.The authors identify this structure through quantities estimated from Monte Carlo simulations, including domain sizes.
- Cooling: The temperature decreases polynomially, with θ as the cooling rate and λ determining the initial temperature λ^-θ.The process is studied under σ(t) ∼ t^-θ as t →∞.
- Cooling regimes: θ < 1/α and θ > 1/α define slow- and fast-cooling regimes with different asymptotic well-transition behavior.These regimes organize the subsequent analysis of transition times and probabilities between neighborhoods of local minima.
- Slow cooling: For θ < 1/α, transition probabilities between distinct neighborhoods of local minima determine the process's long-run well occupancy.The occupancy vector π^(α) is obtained from the transition-rate matrix through Q^Tπ^(α) = 0.
- Fast cooling: Under sufficiently fast cooling, the Lévy particle becomes trapped in one well, so convergence to the global minimum fails.This contrasts with the transition-rich regime where well changes remain asymptotically relevant.
3 L´evy flights with variable stability index (stable-like processes)
The paper replaces spatially uniform Lévy flights with a stable-like process whose jump behavior depends on the current position. This process drives both continuous dynamics and a discrete Euler scheme for simulation.
- Position-dependent Lévy flights: The stable-like process H uses a position-dependent jump measure ν_x(dy) = |y|−1−α(x)dy.Its instantaneous jump distribution is governed by the current position x.
- Position-dependent Lévy flights: The variable stability index α(x) takes values in (0, 2), with 0 < a ≤ α(x) ≤ A < 2 excluding degeneration.A constant α(x) reduces H to an ordinary Lévy flight process.
- Simulation scheme: The stochastic differential equation driven by H is approximated by a discrete recurrence with time step h for simulations.The random input uses standard symmetric α(y)-stable variables.
4 One-well dynamics. Transitions and trapping
At low temperature, the process follows deterministic attraction toward local minima while retaining non-local jumps between wells. Its exit and trapping behavior is controlled by the local stability index and cooling rate.
- One-well dynamics: At low temperature, Y rapidly approaches a neighborhood of the local minimum mi within its attraction domain Ωi while still making Lévy jumps.Inside a well, its jumps are approximately governed by ν_mi(dy) = |y|−1−α(mi)dy.
- One-well dynamics: For piecewise-constant α(x), the process Y follows the corresponding Lévy-driven dynamics inside each well until it exits.This makes the approximation of well exit behavior exact away from small saddle neighborhoods.
- Transitions and trapping: The transition and exit-time relations determine whether a Lévy particle leaves a well or becomes trapped as λ increases.The threshold is α(mi)θ < 1 for escape behavior and α(mi)θ > 1 for trapping.
5 Non-local random search and simulated annealing
The search assigns stability indices and cooling rates so non-target wells remain escapable while the target well becomes trapping. The same mechanism extends to unknown global minima and energy-threshold searches.
- Targeted well search: Choosing α(x) with a unique maximum at a target minimum and selecting θ so α(mi)θ > 1 only there traps the particle in that well.Other wells satisfy α(mj)θ < 1 and are left in finite time.
- Unknown global minimum: For an unknown global minimum M, α(x) is constructed from the potential so that M has the largest stability index, and θ is chosen accordingly.The resulting trapping follows from the preceding well-selection argument.
- Energy-threshold search: The method can target a local minimum below an energy threshold E by assigning stability A below E and a below E's complement.With Aθ > 1 and aθ < 1, low-energy wells trap the particle while higher-energy wells are exited.
- Energy-threshold search: If several wells lie below E, the particle settles near one of them; decreasing thresholds can estimate the ground energy E∗ = U(M).The algorithm requires only a, A, θ, the energy level E, and values of U′(x).
6 Numerical example
The numerical example applies the algorithm to a two-dimensional five-well potential using isotropic Lévy flights and only potential values. Across 100 simulations, the global minimum was found in 96 cases.
- Multidimensional implementation: The multidimensional extension uses isotropic d-dimensional Lévy flights with jumping measure ν_x(dy) = |y|−d−α(x)dy.Transition probabilities are recalculated with dimension d replacing one-dimensional integrals.
- Five-well potential: The experiment evaluates a two-dimensional potential with five local minima and targets a minimum satisfying U(mE) ≤ −1.In this example, the target is m4.
- Simulation results: 96 of 100 simulations located the global minimum m4 with U(yn) = −1.46.The remaining outcomes located m3 twice and m1 and m2 once each.
- Simulation results: The simulations used only values of the potential U without additional information about its geometry.This supports the stated unknown-potential setting of the numerical demonstration.
7 Conclusion and discussion
The paper’s stable-like Lévy-flight algorithm uses a spatially varying stability index and polynomial cooling to perform non-local global optimisation. It can localise the global minimum and support targeted well searches, but optimal parameter selection and some jump-related issues remain open.
- Core algorithm: Variable stability α(x) is crucial: unlike spatially homogeneous Lévy flights, it enables the particle to settle near a global minimum.The paper contrasts the successful state-dependent process with prior homogeneous Lévy-flight algorithms, which produced different results.
- Core algorithm: Non-local jumps let the particle move from one potential well to any other with strictly positive probability, rather than only to neighbouring wells.The deepest well is most likely to receive a jump when it is also spatially largest.
- Parameter choice: The cooling rate θ can be selected jointly with α(x), avoiding the need to know potential values required to determine Gaussian simulated annealing’s cooling rate.The paper identifies this parameter freedom as an advantage when the well energies are unknown.
- Parameter choice: The method can target any approximately known well or identify a local minimum below a specified energy, with parameter choices independent of potential geometry.These search regimes are unavailable in the classical setting described by the authors.
- Empirical accuracy: Polynomial cooling, σ(t) ∼t^-θ, improves the accuracy of empirical estimates for local-minimum locations compared with logarithmic cooling.The paper presents polynomial temperature decrease as a final practical advantage of the method.
- Open questions: Optimal choices of α(x) and θ remain unresolved because reducing trapping in false wells can create very large jumps and slow searches in inner global wells.Truncated Lévy flights could limit jump sizes, but simulating their random input may be more complicated.