Lévy flight foraging hypothesis

The Lévy flight foraging hypothesis is a hypothesis in the field of biology that may be stated as follows:

Since Lévy flights and walks can optimize search efficiencies, therefore natural selection should have led to adaptations for Lévy flight foraging.^[1]

Background

The movement of animals closely resembles in many ways the random walks of dust particles in a fluid.^[2] This similarity led to interest in trying to understand how animals move via the analogy to Brownian motion. This conventional wisdom held until the early 1990s. However, starting in the late 1980s, evidence began to accumulate that did not fit the theoretical predictions.^[2]

In 1999, a theoretical investigation of the properties of Lévy flights showed that an inverse square distribution of flight times or distances could optimize the search efficiency under certain circumstances.^[3] Specifically, a search based on an inverse-square Lévy walk, consisting of a constant velocity search following a path whose length is distributed over an inverse square Levy stable distribution, is optimal for searching sparsely and randomly distributed revisitable targets in the absence of memory. These results have been published in 1999 in the journal Nature.^[3]

Controversy on empirical support

There has been some controversy about the reality of Lévy flight foraging. Early studies were limited to a small range of movement, and thus the type of motion could not be unequivocally determined; and in 2007 flaws were found in a study of wandering albatrosses which was the first empirical example of such a strategy.^[4] There are however many new studies backing the Lévy flight foraging hypothesis.^[5][6][7][8]

Recent studies use newer statistical methods^[9] and larger data sets showing longer movement paths.^[10] Studies published in 2012 and 2013 re-analysed wandering albatross foraging paths and concluded strong support for truncated Lévy flights and Brownian walks consistently with predictions of the Lévy flight foraging hypothesis.^[11][12]

Debate on the optimality of a specific exponent

From the theoretical point of view, a recent study^[13] disputes the validity of the optimality result published in 1999, by concluding that for bi- or tri-dimensional random walks, this result is only valid for very specific conditions: (i) once a target has been foraged, it has to reappear infinitely fast, (ii) the typical scale of the animal displacement has to be very small compared to the typical size of the targets, (iii) after a target is found, the animal has to start a new random walk infinitely close to the border of this target. If any of these conditions is not valid, the optimality result does not hold: inverse-square Levy walks are not optimal, and the gain of any optimal Levy walk over others is necessarily marginal (in the sense that it does not diverge when the density of targets is low).

In contrast, assuming that the search is intermittent^[14](i.e., detection is possible only at the short pauses between jumps), a different argument for the optimality of the inverse-square Lévy walk has been given.^[15] Mathematical arguments show that in finite two-dimensional domains the intermittent inverse-square Lévy walk is optimal when the goal is to minimize the search time until finding a target of unpredictable size. In contrast, any intermittent Lévy walks other than the inverse-square walk fail to efficiently find either small or large targets. In other words, the inverse-square Lévy walk stands out as the only intermittent Lévy process that is highly efficient with respect to all target scales without the need for any adaptation. This result highlights the relationships between the detection ability of the searcher and the robustness and speed of the search.^[15]

Another mathematical argument which shows that inverse-square Lévy walks are not generally optimal has been subsequently provided by studying the search efficiency of a group of individuals that have to find a single target in the infinite two-dimensional grid ${\displaystyle \mathbb {Z} ^{2}}$.^[16] In particular, it has been considered a setting with ${\displaystyle k}$ individuals that start performing a Lévy walk at the origin of the grid (a nest-site), and where there is a target at some fixed (Manhattan) distance ${\displaystyle D}$ from the origin; ${\displaystyle D}$ must be at most some exponential function in ${\displaystyle k}$, which is a reasonable assumption since otherwise the target might not be found with non-negligible probability. It can then be proven that the target is found in almost-optimal time with high probability if the exponent of the power-law density distribution is ${\displaystyle \alpha ^{\star }\sim 3-\log k/\log D}$. Any constant deviation from ${\displaystyle \alpha ^{\star }}$ results in sub-optimal hitting time. However, such a choice for the power-law exponent requires the knowledge, by the individuals, of both the number of individuals ${\displaystyle k}$ and the target distance ${\displaystyle D}$, which may be a very strong assumption in living societies. For this reason, it has been provided a simple almost-optimal search strategy without such requirements: if each individual samples uniformly at random the power-law exponent from the interval ${\displaystyle (2,3)}$ and then performs the corresponding Lévy walk, the target is still found in almost-optimal time with high probability. This strategy surprisingly achieves near-optimal search efficiency for all distance scales, and implies that different members of the same group follow different search patterns. The existence of such variation in the search patterns among individuals of the same species requires empirical validation.^[16] These results highlight that Lévy walks are indeed optimal search strategies, but there isn't any power-law exponent playing a universal role; instead, in the latter setting, any exponent between ${\displaystyle 2}$ and ${\displaystyle 3}$ might be employed depending on the number of individuals ${\displaystyle k}$ and the target distance ${\displaystyle D}$.

References

1. Viswanathan, G.M.; Raposo, E.P.; da Luz, M.G.E. (September 2008). "Lévy flights and superdiffusion in the context of biological encounters and random searches". Physics of Life Reviews. 5 (3): 133–150. Bibcode:2008PhLRv...5..133V. doi:10.1016/j.plrev.2008.03.002.
2. Buchanan, Mark (5 June 2008). "Ecological modelling: The mathematical mirror to animal nature". Nature. 453 (7196). Springer Nature: 714–716. doi:10.1038/453714a. ISSN 0028-0836. PMID 18528368.
3. Viswanathan, G. M.; Buldyrev, Sergey V.; Havlin, Shlomo; da Luz, M. G. E.; Raposo, E. P.; et al. (1999). "Optimizing the success of random searches". Nature. 401 (6756). Springer Nature: 911–914. Bibcode:1999Natur.401..911V. doi:10.1038/44831. ISSN 0028-0836. PMID 10553906. S2CID 4419834.
4. Edwards, Andrew M.; Phillips, Richard A.; Watkins, Nicholas W.; Freeman, Mervyn P.; Murphy, Eugene J.; et al. (25 October 2007). "Revisiting Lévy flight search patterns of wandering albatrosses, bumblebees and deer" (PDF). Nature. 449 (7165). Springer Nature: 1044–1048. Bibcode:2007Natur.449.1044E. doi:10.1038/nature06199. ISSN 0028-0836. PMID 17960243. S2CID 4393885.
5. Sims, David W.; Southall, Emily J.; Humphries, Nicolas E.; Hays, Graeme C.; Bradshaw, Corey J. A.; et al. (2008). "Scaling laws of marine predator search behaviour". Nature. 451 (7182). Springer Nature: 1098–1102. Bibcode:2008Natur.451.1098S. doi:10.1038/nature06518. ISSN 0028-0836. PMID 18305542. S2CID 4412923.
6. Humphries, Nicolas E.; Queiroz, Nuno; Dyer, Jennifer R. M.; Pade, Nicolas G.; Musyl, Michael K.; et al. (2010). "Environmental context explains Lévy and Brownian movement patterns of marine predators" (PDF). Nature. 465 (7301). Springer Nature: 1066–1069. Bibcode:2010Natur.465.1066H. doi:10.1038/nature09116. ISSN 0028-0836. PMID 20531470. S2CID 4316766.
7. Raichlen, D. A.; Wood, B. M.; Gordon, A. D.; Mabulla, A. Z. P.; Marlowe, F. W.; et al. (23 December 2013). "Evidence of Levy walk foraging patterns in human hunter-gatherers". Proceedings of the National Academy of Sciences. 111 (2): 728–733. Bibcode:2014PNAS..111..728R. doi:10.1073/pnas.1318616111. ISSN 0027-8424. PMC 3896191. PMID 24367098.
8. Sims, D. W.; Reynolds, A. M.; Humphries, N. E.; Southall, E. J.; Wearmouth, V. J.; et al. (14 July 2014). "Hierarchical random walks in trace fossils and the origin of optimal search behavior". Proceedings of the National Academy of Sciences. 111 (30): 11073–11078. Bibcode:2014PNAS..11111073S. doi:10.1073/pnas.1405966111. ISSN 0027-8424. PMC 4121825. PMID 25024221.
9. Clauset, Aaron; Shalizi, Cosma Rohilla; Newman, M. E. J. (4 November 2009). "Power-Law Distributions in Empirical Data". SIAM Review. 51 (4): 661–703. arXiv:0706.1062. Bibcode:2009SIAMR..51..661C. doi:10.1137/070710111. ISSN 0036-1445. S2CID 9155618.
10. Sims, David W.; Humphries, Nicolas E.; Bradford, Russell W.; Bruce, Barry D. (17 October 2011). "Lévy flight and Brownian search patterns of a free-ranging predator reflect different prey field characteristics". Journal of Animal Ecology. 81 (2). Wiley: 432–442. doi:10.1111/j.1365-2656.2011.01914.x. ISSN 0021-8790. PMID 22004140.
11. Humphries, N. E.; Weimerskirch, H.; Queiroz, N.; Southall, E. J.; Sims, D. W. (23 April 2012). "Foraging success of biological Levy flights recorded in situ". Proceedings of the National Academy of Sciences. 109 (19): 7169–7174. Bibcode:2012PNAS..109.7169H. doi:10.1073/pnas.1121201109. ISSN 0027-8424. PMC 3358854. PMID 22529349.
12. Humphries, Nicolas E.; Weimerskirch, Henri; Sims, David W. (2013). Freckleton, Robert (ed.). "A new approach for objective identification of turns and steps in organism movement data relevant to random walk modelling" (PDF). Methods in Ecology and Evolution. Wiley: 480–490. doi:10.1111/2041-210x.12096. ISSN 2041-210X.
13. Levernier, Nicolas; Textor, Johannes; Bénichou, Olivier; Voituriez, Raphaël (2020-02-26). "Inverse Square L\'evy Walks are not Optimal Search Strategies for $d\ensuremath{\ge}2$". Physical Review Letters. 124 (8): 080601. arXiv:2002.00278. doi:10.1103/PhysRevLett.124.080601. hdl:2066/217203. PMID 32167352. S2CID 211011297.
14. Bénichou, Olivier; Loverdo, Claude; Moreau, Michel; Voituriez, Raphael (2011). "Intermittent search strategies". Reviews of Modern Physics. 83 (1): 81–129. arXiv:1104.0639. Bibcode:2011RvMP...83...81B. doi:10.1103/RevModPhys.83.81. S2CID 55004463.
15. Guinard, Brieuc; Korman, Amos (2021). "Intermittent inverse-square Lévy walks are optimal for finding targets of all sizes". Science Advances. 7 (15): eabe8211. arXiv:2003.13041. Bibcode:2021SciA....7.8211G. doi:10.1126/sciadv.abe8211. PMC 8034848. PMID 33837080.
16. Clementi, Andrea; d'Amore, Francesco; Giakkoupis, George; Natale, Emanuele (2021). "Search via Parallel Lévy Walks on ${\displaystyle \mathbb {Z} ^{2}}$". Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC'21). arXiv:2004.01562. doi:10.1145/3465084.3467921.

Further reading

• Viswanathan, Gandhimohan. M.; Luz, Marcos G. E. da; Raposo, Ernesto P.; Stanley, H. Eugene (2011). The Physics of Foraging: An Introduction to Random Searches and Biological Encounters. Cambridge University Press. ISBN 9781139497558.
• Kagan, Eugene; Ben-Gal, Irad (2015). Search and foraging : individual motion and swarm dynamics. CRC Press. ISBN 9781482242102.
• Reynolds, Andy (September 2015). "Liberating Lévy walk research from the shackles of optimal foraging". Physics of Life Reviews. 14: 59–83. Bibcode:2015PhLRv..14...59R. doi:10.1016/j.plrev.2015.03.002. PMID 25835600.