Emergence of Lévy walks from second order stochastic optimization

Abstract

In natural foraging, many organisms seem to perform two different types of motile search: directed search (taxis) and random search. The former is observed when the environment provides cues to guide motion towards a target. The latter involves no apparent memory or information processing and can be mathematically modeled by random walks. We show that both types of search can be generated by a common mechanism in which Lévy flights or Lévy walks emerge from a second-order gradient-based search with noisy observations. No explicit switching mechanism is required -- instead, continuous transitions between the directed and random motions emerge depending on the Hessian matrix of the cost function. For a wide range of scenarios the Lévy tail index is $\alpha =1$, consistent with previous observations in foraging organisms. These results suggest that adopting a second-order optimization method can be a useful strategy to combine efficient features of directed and random search.

arXiv comment6 pages, 1 figure

References in corpus (14)

• Understanding individual human mobility patterns
• The origin of bursts and heavy tails in human dynamics
• The scaling laws of human travel
• Lévy walks
• First order transition for the optimal search time of Lévy flights with resetting
• Functional Analysis of Spontaneous Cell Movement under Different Physiological Conditions
• Modeling the Searching Behavior of Social Monkeys
• Optimal first arrival times in Lévy flights with resetting
• Average Time Spent by Levy Flights and Walks on an Interval with Absorbing Boundaries
• Power-law tails from multiplicative noise
• Universality of Wigner random matrices: a Survey of Recent Results
• The origin of power-law distributions in deterministic walks: the influence of landscape geometry
• Escape from bounded domains driven by multi-variate $\alpha$-stable noises
• Stationary states in 2D systems driven by bi-variate Lévy noises

Cited by in corpus (2)

• Search with home returns provides advantage under high uncertainty
• Gradient dynamics in reinforcement learning