The evolutionary origins of Lévy walk foraging

Abstract

We study through a reaction-diffusion algorithm the influence of landscape diversity on the efficiency of search dynamics. Remarkably, the identical optimal search strategy arises in a wide variety of environments, provided the target density is sparse and the searcher's information is restricted to its close vicinity. Our results strongly impact the current debate on the emergentist vs. evolutionary origins of animal foraging. The inherent character of the optimal solution (i.e., independent on the landscape for the broad scenarios assumed here) suggests an interpretation favoring the evolutionary view, as originally implied by the Lévy flight foraging hypothesis. The latter states that, under conditions of scarcity of information and sparse resources, some organisms must have evolved to exploit optimal strategies characterized by heavy-tailed truncated power-law distributions of move lengths. These results strongly suggest that Lévy strategies-and hence the selection pressure for the relevant adaptations-are robust with respect to large changes in habitat. In contrast, the usual emergentist explanation seems not able to explain how very similar Lévy walks can emerge from all the distinct non-Lévy foraging strategies that are needed for the observed large variety of specific environments. We also report that deviations from Lévy can take place in plentiful ecosystems, where locomotion truncation is very frequent due to high encounter rates. So, in this case normal diffusion strategies-performing as effectively as the optimal one-can naturally emerge from Lévy. Our results constitute the strongest theoretical evidence to date supporting the evolutionary origins of experimentally observed Lévy walks.

Fig 1. Heterogeneous search landscapes with representative trajectories of different strategies.

Fragmented search landscapes containing N_t = 10⁴ targets placed in N_p = 10 heterogeneous patches (gray regions) with: (A) same average distance between inner targets, $l_t^{\left(p\right)}=100$, and radii uniformly distributed in the range 0.03M ≤ R^(p) ≤ 0.3M, M = 10⁴; (B) same radius, R^(p) = 0.1M, and $l_t^{\left(p\right)}$ uniformly distributed in the range $5\le l_t^{\left(p\right)}\le 350$; and (C) distinct sizes uniformly distributed in the range 0.03M ≤ R^(p) ≤ 0.3M, but fixed number (10³) of inner targets per patch, so that $17\le l_t^{\left(p\right)}\le 170$. The darker the patch, the higher its homogeneous density of inner targets. We also show typical paths of a searcher with power-law (Lévy-like) distributions of step lengths displaying different degrees of diffusivity: nearly ballistic (μ = 1.1), superdiffusive (μ = 2.0), and Brownian (μ = 3.0). In this illustrative example the search ends upon the finding of only 10 targets.

Fig 2. Lévy dust distribution of targets.

Search landscapes containing Lévy dust distributions of N_t = 10⁴ targets (see main text), drawn from Eq (1) with d₀ = 1, d_max = M = 10⁴, and (A) β = 1.1, (B) β = 2.0, (C) β = 2.5, and (D) β = 3.0. Larger values of β increase the degree of clustering of targets. The bouncing of coordinates technique applied to the β = 1.1 case results in a nearly homogeneous targets distribution.

Fig 3. Construction of a fractal patch environment.

Illustration of a search landscape with N_p = 3 patches and N_t = 15000 targets (5000 targets per patch), forming Lévy dust distributions (see main text). Here, β = 2.5, d₀ = 2, d_max = M/10 in Eq (1), and γ = 2.0, r₀ = 500, r_max = M = 10⁴ in Eq (2). The parameters are chosen so that the patches do not overlap. Dotted lines are only a guide to visually delimit the patches regions.

Fig 4. Fractal patches obtained by combining two Lévy dust distributions.

Search landscapes containing Lévy dust distributions located in N_p = 50 patches. Here, N_t = 50000 (1000 targets per patch), β = 3.0, d₀ = 2, d_max = M/10 in Eq (1), and r₀ = 100, r_max = M = 10⁴, (A) γ = 1.1, (B) γ = 2.0, (C) γ = 2.5, (D) γ = 3.0, in Eq (2). For large γ the patches are so close that one cannot distinguish them only by visual inspection.

Fig 5. Search efficiency η vs. power-law exponent μ of Lévy searches for 10⁴ targets in fragmented landscapes.

In the simulations, N_p = 10 (circles) and N_p = 5 (squares) heterogeneous patches contain a total of N_t = 10⁴ inner targets (see Methods section). In (A)-(C) the parameters determining the radii and average distances between inner targets are respectively set as in Fig 1(A)–1(C). Ballistic and Brownian limits correspond to μ → 1 and μ = 3, respectively. In all cases, the efficiency η is maximized for the superdiffusive dynamics with μ_opt ≈ 2.

Fig 6. Search efficiency η vs. power-law exponent μ in Lévy dust distributions.

The searcher detected 10⁴ targets in a landscape with Lévy dust distributions of N_t = 10⁴ targets (see Methods section). Parameters are set as in Fig 2. High clustering of targets and nearly homogeneous landscapes correspond to β = 3 and β = 1.1, respectively. In all cases, η is maximized for μ_opt ≈ 2, with a slight decrease in the optimal value (i.e. enhanced superdiffusion) observed as β → 3.

Fig 7. Search efficiency η vs. power-law exponent μ in fractal patches.

The searcher detected 10⁴ targets in a landscape with Lévy dust distributions of N_t = 50000 targets in N_p = 50 patches (see Methods section). Parameters are set as in Fig 4. In all cases, η is maximized for μ_opt ≈ 2.

Fig 8. Search efficiency η vs. power-law exponent μ in a super-dense landscape.

The simulations lasted for 10⁴ detected targets in a landscape with l_t = 5 and homogeneous distribution of N_t = 50000 targets. Note that μ_opt ≈ 2 is still the optimal value. However, in contrast with the sparse regime (see previous η vs. μ plots), less superdiffusive search walks (2 < μ < 3) and even diffusive ones (μ = 3) perform nearly as efficient as the optimal superdiffusive strategy.

Fig 9. Output distribution of step lengths for a μ = 2.0 Lévy searcher in a super-dense landscape.

In the simulations, l_t = 2.5 with N_t = 50000 targets homogeneously placed. The distribution takes into account the first 10⁴ search steps, including non-truncated moves that end up without detecting a target and also a relatively large number of truncated steps due to targets encounters. Numerical simulation data are represented by circles. Dashed and dotted lines are, respectively, best fits to Brownian-like exponential and truncated power-law pdfs. The inset details the large-steps regime. Statistical data inference (MLE and AIC methods) indicates that the output distribution of step lengths in the super-dense regime is not properly described by a superdiffusive power-law (Lévy-like) pdf. Instead, it shows the signature of a Brownian motion.

Fig 10. Output distribution of step lengths for a μ = 2.0 Lévy searcher in a low-dense landscape (l_t = 100).

In the sparse regime, the number of truncated moves due to targets encounters is relatively low and long steps are much more frequent, if compared to the super-dense limit (see inset). Statistical data inference (MLE and AIC methods) indicates that the output distribution of step lengths in the low-dense regime is actually a power-law (Lévy-like), with best-fit exponent μ = 2.19 close to the original one.