適宜暇を見て更新していきます。
1. 群知能(Swarm Intelligence)とは？
そもそも群知能とは何でしょうか？というお話です。
1-1. 群知能とは？
群知能とは、「生物の個体がシンプルなルールで行動を行うことにより、群れとして集合的振る舞いが創発し、結果的に利益を生み出す」といった人工知能の技術の学問・事柄を指します。
上の言葉だとよく分からないので簡単に言い換えると
群知能とは、「各生物の個体は、非常に単純なルールで動いている。それぞれの個体はみんな大した能力を持たない。しかし、いっぱい集まるとすごく強い。なので、この群れの強さをプログラミングの世界に持ってきて、最適化を行おう！」というものです。
人間も「群れ」で行動を行い、より良い結果を出します。
例えば、昔の研究で「専門家一人の意見よりも、ある程度知識のある人間１０人が話し合った意見のほうが正確である。」みたいなのが出てます。
これは、集団のほうが各個人のエラー・間違いが集団の中でかき消されて、より良い結果のみが抽出されるからなんですね。（すごい）
逆に、「群れ」で行動をすると、生物界でも人間界でも、悪い結果が行ることがあります。
蟻はフェロモンを頼りに餌を探しますが、円形にフェロモンを出してしまい、全員が全員のフェロモンを永遠に円形のまま追いかけて死んでしまうことがあります。これも単純なルールしか知らない結果、起きてしまう悲劇です。（複雑なルールを持つ人間なら、視野があるので避けれますね）
人間も、集団で行動すると失敗することもあります（想像しやすいと思います）。
1-2. 群知能で扱われる生物は？
群知能は、「生物の群れの行動」を「モデル化」して、「プログラミング世界のフレームワーク」として落とし込む。
というのが主な流れです。
よって、最適化問題に利用できる、モデル化しやすい・人間の役に立ちやすい生物がよく利用されます。（どんな生物も利用されるわけではありません。）
群知能で扱われる生物の共通点としては、
- 群れで行動する（群知能なので）
- 個体はシンプルなルールで動く
- 各個体間で情報を共有する手段を持っている
などがあります。
1-2-1. 蟻
蟻は、群知能のフレームワークワークで1, 2を争う有名度であると思います。
蟻の群れの動きを利用したアルゴリズムは**Ant Colony Optimization(ACO)**と呼ばれます。
自然界の蟻の群れは、巣から餌を探しに行きますが、餌までのかなり理論的な最短経路を発見します。
この蟻たちは、目を利用して最短経路を発見できません。
どのように最短経路を発見しているのか？というとフェロモンという物質を分泌することで最短経路を群れとして発見しています。
Wikiがとてもわかりやすいです。
蟻コロニー最適化の特徴としては
- 解きたい問題を、グラフネットワークに落とし込む。
- これは、フェロモンをエッジに蓄積するため、グラフに落とし込む必要があります。
- 各エージェント（蟻）は、一つの解を構築する。
- 蟻の行動自体が一つの解になります。
- 直接情報共有をエージェントたちはしない。
- 環境（グラフネットワーク上のフェロモン）を介して情報共有を行います。
- 環境と相互作用する。
- PSOなどはエージェント同士で相互作用しますが、ACOでは環境（グラフネットワーク）にフェロモンを蓄積し、環境からフェロモンを近くすることで移動経路を作成します。
などがあります。
蟻コロニー最適化の難しい点として
- 離散的アルゴリズムである
- 連続的問題は解きづらい（$ACO_R$という連続的ACOはあるみたいです）
- グラフネットワーク問題に落とし込まないといけない
- フェロモンをエッジに累積するため、落とし込むのが面倒ではあります。
などがあります。
1-2-2. 鳥
鳥や魚の群れも群知能としてよく利用されます。
フレームワークの名前としては**Particle Swarm Optimization(PSO)**であり、今回の記事のメインテーマです。
1-2-3. ネコ
かわいいネコのアルゴリズムもあります。（まだ自分自身では触ったことはないです）
Cat Swarm Intelligenceと言うらしいです。
自分でも触ってみたいですね。
1-3. 群知能の利用分野は？
群知能という技術・分野があることがわかりましたが、例えばどういうことに使われているのでしょうか？
1-3-1. 巡回セールスマン問題
巡回セールスマン問題は、みなさんご存知の通り、NP困難な問題です。
$N =50$頂点を超えたあたりで、もうどうしようもなくなります。
すると、我々は最適解ではなく、優良解(現実的に求められる中でできるだけ良い解)を見つける必要があります。
このとき、群知能は非常に良い結果を残します。
例えば、ACOを利用すると、たくさんのエージェントがシンプルなルールを元に巡回セールスマン問題の最短経路を探します。
ACOは、グラフネットワークの問題を解くので、巡回セールスマン問題自体が得意分野なんですね。
ACOを使えば、$N=50$で限界な数理最適化とは対象的に、$N=1000$でも頑張れば解くことができます。
1-3-2. 組合せ最適化問題
組合せ最適化問題も、NP困難な問題です。
$N$が大きくなるとすぐにプログラムは、計算量の著しい増加に伴って動作しなくなります。
そこで、群知能を用いると、組合せ最適化問題の優良解は求めることができます。（最適解は得られないことに注意です。）
1-3-3. ほかにもいろいろ
他にもたくさんあります。
「Swarm Intelligence Applications」で調べると、多くの適用事例を見ることができます。
1-4. 群知能のメリット・デメリットは？
1-4-1. 群知能のメリット
群知能は、確率的にシミュレーションを行って、最適化を行います。
そのため、以下のようなメリットがあります。
- 問題のスケーリングに強い
- 問題サイズが大きくなっても、数理最適化よりもより高速に解くことができます
- 継続的に解を求められる
- 数理最適化・アニーリング法などは、問題が動的に設定が変わると対処しずらいです。群知能は、生物のリアルタイム性などから、問題設定が変わってもリアルタイムに対応しやすいです。
- 生物の恩恵が預かれる
- 生物の特徴を利用する群知能は、まだまだ活路があると考えています。
1-4-2. 群知能のデメリット
群知能のデメリットは、以下のようなものがあります。
- 解が一つに定まらない
- 数理最適化は「確定的な」最適化ですが、群知能は確率的なシミュレーション最適化です。そのため、解は毎回実行タイミングによって変化します。
- 初期解・パラメータ設定に依存しやすい
- 群知能では、エージェントの数などのパラメータや、初期解のランダム配置で大きく解が異なります。
- 理論的な証明がしづらい
- 論文でも、他の数理最適化などの解析的手法と比較すると、「実行したらこれくらい上手くいった」というほうが多いです。