利用者:Fridericusgauss/sandbox

ここはFridericusgaussさんの利用者サンドボックスです。編集を試したり下書きを置いておいたりするための場所であり、百科事典の記事ではありません。ただし、公開の場ですので、許諾されていない文章の転載はご遠慮ください。

登録利用者は自分用の利用者サンドボックスを作成できます（サンドボックスを作成する、解説）。

その他のサンドボックス: 共用サンドボックス | モジュールサンドボックス

記事がある程度できあがったら、編集方針を確認して、新規ページを作成しましょう。

カッコウ探索（英語版）（Cuckoo Search：CS）は、2009年にXin-she YangとSuash Debによって開発された^[1]、カッコウの托卵行動をアナロジーとする発見的な最適化アルゴリズム(メタヒューリスティクス)である。さらにCSは、メタヒューリスティクスの中でも、群知能に分類される。群知能に分類される代表的なアルゴリズムとして、粒子群最適化(Particle Swarm Optimization：PSO)、差分進化(Differential Evolution：DE)、人工蜂コロニーアルゴリズム(Artificial Bee Colony Algorithm：ABC)などが挙げられる。最近の研究によれば、CSは他の群知能のアルゴリズムと同等の性能を持つとされる。CS、PSO、DE、ABCの比較において、PSOやABCに比べ、CSとDEのほうが頑健だという結果が得られた^[2]。

基本原理

カッコウの托卵

自然界におけるカッコウの托卵とは、他の鳥の巣に卵を植え付け、卵及び雛の世話を他の個体に托す習性のことである。このとき、卵を植え付けられる巣の親鳥を仮親と呼ぶ。仮親は巣内の雛が仮親の雛と全く似ていない場合や、仮親よりも大きく育つ場合でも、巣内の雛に鳴かれると本能的に世話をする習性を持つため、カッコウの雛を育ててしまう。

さらに、仮親はカッコウに托卵されないように、自らの卵とは異なる卵を見つけると、雛が孵る前に巣から弾き出したり、新たな巣を作りカッコウの卵を巣ごと見捨てるようになる。すると、その一方でカッコウは、卵の色や柄を仮親の卵に似せて産むようになる。このように、托卵における様々な進化、生存競争が確認されている。

レヴィ分布とレヴィフライト

レヴィ分布は安定分布の一つであり、確率密度関数が

$Levy(x;\mu ,c)={\begin{cases}{\sqrt {\frac {c}{2\pi }}}\mathrm {exp} [{\frac {-c}{2(x-\mu )}}](x-\mu )^{-3/2}&\mathrm {if} ~x\geq \mu \\0&\mathrm {otherwise} \end{cases}}$
$v\leftarrow ({\hat {x}}_{g}-x)$

として与えられる。ここで、 $x$ は確率変数、 $\mu$ は最小値を決めるパラメータ、 $c$ はスケールパラメータである。レヴィ分布は、動物の飛行パターンや採餌行動など、様々な自然現象や物理現象における確率的変動を表現できるとされている。

レヴィフライト（英語版）は、ステップ幅がレヴィ分布に従うランダムウォークの一つである。ランダムウォークは、現在位置する点からのステップ幅をある確率分布に従う乱数とし、次の点を生成する方法である。ランダムウォークでは、次の点 $x'$ を

$x'=x+r$

より生成する。ここで、 $x$ は現在位置する点、 $r$ は確率分布により決定されるステップ幅である。レヴィフライト（英語版）ではステップ幅 $r$ がレヴィ分布に従う。最適化において、未知でより広い範囲の探索を行う場合、レヴィフライト（英語版）を用いることで、正規分布によるランダムウォーク（Gaussian random walk（英語版））を用いる場合に比べ、効率的な探索を行うことができるとされている^[3]。

レヴィフライトを数値計算上で行う方法として、要素ごとのステップ幅を、安定分布に従う乱数の生成法Mantegna's Algorithmにより決定する方法が提案されている。Mantegna' s Algorithmは乱数 $L(\beta )$ を

$L(\beta )={\frac {u}{{|v|}^{1/\beta }}}$

として作成する。ここで、 $u,v$ は以下の式で表される正規分布に従う乱数である。( $\Gamma$ はガンマ関数)

$u;N(0,{\sigma _{u}}^{2})$
$v;N(0,1)$
${\sigma _{u}}^{2}={\frac {\Gamma (1+\beta )\sin(\pi \beta /2)}{\Gamma [(1+\beta )/2]2^{(\beta -1)/2}\beta }}^{1/\beta }$

分布調整変数 $\beta$ が $0.3\leq \beta \leq 1.99$ のとき、 $L(\beta )$ が従う確率分布は、確率変数が0.1より十分に大きな値となる範囲においてレヴィ分布を近似する。本稿では以下より、このMantegna's Algorithmによって生成される乱数を、分布調整変数 $\beta$ を用いて $L(\beta )$ 、また $L(\beta )$ が従う分布を近似レヴィ分布と表記する。

CSの概要

カッコウの托卵行動は、大きく次の3つの要素で構成できると解釈できる。

カッコウが他の個体の巣に自らの卵を産む。
仮親が質の悪い卵を巣から弾き出す。

CSはカッコウの托卵行動をアナロジーとしており、大きく分けてレヴィフライト、更新、排斥の3つのステップを繰り返すことで探索を行う。

脚注

^ Yang X.-S. and Deb S. (December 2009). "Cuckoo search via Lévy flights". World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). IEEE Publications. pp. 210–214. arXiv:1003.1594v1.
^ P. Civicioglu and E. Besdok, A conception comparison of the cuckoo search, particle swarm optimization, differential evolution and artificial bee colony algorithms, Artificial Intelligence Review, DOI 10.1007/s10462-011-92760, 6 July (2011).
^ “Novel 'Cuckoo Search Algorithm' Beats Particle Swarm Optimization in Engineering Design”. Science Daily. 2012年5月21日閲覧。

参考文献

Swarm Intelligence: From Natural to Artificial Systems by Eric Bonabeau, Marco Dorigo and Guy Theraulaz. (1999) ISBN 0-19-513159-2
Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds by Mitchel Resnick. ISBN 0-262-18162-2
Swarm Intelligence by James Kennedy and Russell C. Eberhart. ISBN 1-55860-595-9
The Behavioral Self-Organization of Nanorobots Using Local Rules. by Lewis, M. Anthony, and Bekey, George A. (1992) Proceedings of the 1992 IEEE/RSJ International Conference on Intelligent Robots and Systems.
Fundamentals of Computational Swarm Intelligence by Andries Engelbrecht. Wiley & Sons. ISBN 0-470-09191-6
Nanocomputers and Swarm Intelligence by Jean-Baptiste Waldner, ISTE, ISBN 978-1-84704-002-2, 2007.
Miller, Peter (July 2007), “Swarm Theory”, National Geographic Magazine
E. Ridge, D. Kudenko, D. Kazakov, and E. Curry,“Moving Nature-Inspired Algorithms to Parallel, Asynchronous and Decentralised Environments,” in Self-Organization and Autonomic Informatics (I), 2005, vol. 135, pp. 35-49.
Metaheuristic Optimization by Xin-She Yang, Scholarpedia article,cholarpedia, 6(8):11472 (2011)
Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff, Article at IEEE Computer Society
- "From Ants to People: an Instinct to Swarm" - NY Times, 11-13-07
Swarm Intelligence (Journal) Chief Editor: Marco Dorigo. Springer New York. ISSN 1935-3812 (Print) 1935-3820 (Online)
Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004. ISBN 0-262-04219-3
Eva Horn, Lucas Marco Gisi (Ed.): Schwärme – Kollektive ohne Zentrum. Eine Wissensgeschichte zwischen Leben und Information, Bielefeld: transcript 2009. ISBN 978-3-8376-1133-5
L. Fisher, The Perfect Swarm : The Science of Complexity in Everyday Life, Basic Books, 2009.
E. Ridge and E. Curry, “A roadmap of nature-inspired systems research and development,” Multiagent and Grid Systems, vol. 3, no. 1, pp. 3-8, 2007.
"Swarm Intelligence for Analyzing Opinions in Online Communities" by Carolin Kaiser, Johannes Kröckel, Freimut Bodendorf (2010) Proceedings of the 43rd Hawaii International Conference on System Sciences, pp. 1-9

外部リンク

Swarm Intelligence （英語） - スカラーペディア百科事典「Fridericusgauss/sandbox」の項目。

[1] Yang X.-S. and Deb S. (December 2009). "Cuckoo search via Lévy flights". World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). IEEE Publications. pp. 210–214. arXiv:1003.1594v1.

[2] P. Civicioglu and E. Besdok, A conception comparison of the cuckoo search, particle swarm optimization, differential evolution and artificial bee colony algorithms, Artificial Intelligence Review, DOI 10.1007/s10462-011-92760, 6 July (2011).

[3] “Novel 'Cuckoo Search Algorithm' Beats Particle Swarm Optimization in Engineering Design”. Science Daily. 2012年5月21日閲覧。

[1]

[2]

[3]