BETA

Swarm Intelligence: Concepts, Models, and Applications読み 【一日目】

投稿日:2019-08-13
最終更新:2019-08-13

経緯

自分が勉強していきたい4ジャンル
「群知能」
「ディープラーニング」
「AI」
「アルゴリズム(競プロ)」

のうち、「群知能」だとACOしかしらないので
Swarm Ingelligenceのまとめ論文を読む。

本当は、本を読んだほうがいいんだろうけど、本が少なすぎて、そもそも日本語の本はない(かなしい)。
よって、英語の論文を読んでいく。

先生に聞いたところ「英語の長い本を読むよりは、どんどん気になる論文読んで、駄目なところ見つけて書いたほうが伸びる」ということなので論文を週に一本読んでいく。

論文タイトル「Swarm Intelligence: Concepts, Models, and Applications」

論文リンク

1. Introduction

Swarm Intelligence(SI)は、最近発達してきた、生物の動きを利用した最適化のフレームワーク
生物は非常に単純な動きをするが、群れ全体としてはなにか一つの目的を達成する。
これによって、より環境の変化に強く、より計算量を軽くできる。

Stigmergyという単語が良く群知能に出てくるが、これは
「生物が環境を媒介として他の生物とコミュニケーションを取ること」を指す。
例えば、蟻はフェロモンを利用して、他の環境を知り、環境に影響を与え、その環境への影響を、他の生物は受託する。
よって、環境がすべてを支配している。

本書では、特に
Ant Colony Optimization(ACO)と
Swarm Intelligence(SI)
を中心に扱っている。

2. SI Models

SIは多くの成功を納めており、まず、ACOについてまとめていく。

2-1. ACO Model

ACOは、蟻の群れが何も前が見えない状態で、環境に散布されるフェロモンを元に最短経路を発見しさらにフェロモンを分泌するアルゴリズム(フレームワーク)である。

2-1.1 Ants in Nature

自然における蟻についてまとめる。

2.1.1.1 Stigmergic behaviour

自然界の蟻はフェロモンを分泌して巣から餌までの最短経路を発見する。
フェロモンを利用することで餌がなくなったら、蒸発していき、負のフィードバックによってまた新しい経路を探すことができる。
このように、フェロモンを介すことで、自然界との相互作用を果たし、個レベル、そして郡レベルで環境を介して情報を共有し、目的を果たす。
よって、ロバスト性に強い特徴がある。

2.1.1.2 橋実験

自然界の橋で実験をする。

1つ目の実験は短い経路と長い経路を用意し、餌までの経路を求めさせると
自然界の蟻は多くの場合において、短い経路を発見できる。

2つ目の実験は先に長い経路のみを用意しフェロモンをつけさせた後、あとから短い経路を用意する場合である。
このときは、多くの場合長い経路をそのまま使ってしまっている。
この理由として、フェロモンが自然界の場合は多く残り、他の経路を発見しづらいからである。

よって、フェロモンの蒸発の速度は、収束の速度である、フェロモンが蒸発しづらいとすぐ収束するがロバスト性がなくなる。
よって、フェロモンはある程度蒸発しやすいほうがよい。

2.1.1.3 現実の蟻 vs 人工蟻

現実の蟻をモデル化する上で人工蟻は多くの他の要素を持つ。

以下のようなものである。

  • 人工の蟻は、帰る、つまり解を一つ構築したあとにフェロモンを分泌する。
  • パスの長さでフェロモンを調節する。
    • つまり現実の蟻には見れないヒューリスティックを人間が与えられる。
  • メモリーを持つ
  • 蒸発率を変更できる。

よって、モデリングの流れとしては

  1. 人間が自然にInspireされて、それを観察として発展させる。
  2. これらの観察から、とある検証モデルを作る
  3. この検証モデルを繰り返し利用し、テスト、改良を重ねる。
  4. これらのモデルから良いものを抽出しメタヒューリスティクスとする。
  5. 最後に再設計を行い、群知能、自然アルゴリズムになる。

明日

明日は、P9~15のACOの部分を紙にまとめながら、読む。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

競プロなどをします。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!