Random walks, Lévy walks, and Silly walks

 

捕食者(predator)が空間上に散在する被食者(prey)についての情報がない状態で探索する課題をrandom search problemという*1

捕食者(agent)がランダムに右往左往して,偶然に被食者(対立するagent)に遭遇するまで探索を繰り返す.これをBrownian walksという*2.Brownian walksでは探索の幅(一歩一歩の移動距離)は正規分布する.

f:id:kapibarasenn10:20200517161328p:plain

https://commons.wikimedia.org/wiki/File:BrownianMotion.svg

探索幅の分布が正規分布ではなく,裾が重い分布(heavy-tailed)を取った移動をLévy walksという *3 *4.Lévy walksでは,ときどき遠くにジャンプするように探索する.

f:id:kapibarasenn10:20200517161227p:plain

https://commons.wikimedia.org/wiki/File:LevyFlight.svg

Lévy walks で探索すると成功確率がブラウン運動よりも向上することが理論的に示され*5,Lévy walks パターンは自然界に広く発見され,さまざまな種の動物の移動*6に加えて,体内におけるT細胞の移動 *7や分子の移動などのミクロのレベルでも報告されている.動物がLévy walks で探索することは,自然選択によって動物の捕食確率が最適化されて進化した形質だという仮説をLévy flight foraging hypothesisという*8 *9 *10

Lévy walksという名前を初めてきいたときに,私の頭に浮かんだのは Silly walks *11するジョン・クリーズ*12の姿だった*13 *14 *15


Ministry of Silly Walks

*1:捕食者被食者関係におけるrandam search problemは典型的な例だが,問題の枠組みは広く拡張できる.ソフトウェア的に方法が不明な状態で,目標に辿り着くための最適化に確率的な近似によるrandom searchが取られることがある.

*2:ブラウン運動と同じ

*3:

https://en.wikipedia.org/wiki/Lévy_flight

*4:

en.wikipedia.org

*5:Viswanathan, G., Buldyrev, S., Havlin, S. et al. Optimizing the success of random searches. Nature 401, 911–914 (1999). https://doi.org/10.1038/44831

*6:クモザル,シカ,アホウドリ,ヒト,細菌

*7:Harris, T., Banigan, E., Christian, D. et al. Generalized Lévy walks and the role of chemokines in migration of effector CD8+ T cells. Nature 486, 545–548 (2012). https://doi.org/10.1038/nature11098

*8:

https://en.wikipedia.org/wiki/Lévy_flight_foraging_hypothesis

*9:他方でこれは進化的というよりも物理学的な現象だという考えがある。

*10:Reynolds, Current status and future directions of Lévy walk research. Biology Open (2018) 7, bio030106. http://dx.doi.org/10.1242/bio.030106

*11:https://en.wikipedia.org/wiki/The_Ministry_of_Silly_Walks

*12:https://ja.wikipedia.org/wiki/ジョン・クリーズ

*13:

ja.wikipedia.org

*14:https://en.wikipedia.org/wiki/The_Ministry_of_Silly_Walks

*15:でもなんだか彼の歩き方ってLévy walksっぽい.