群知能(<人工生命)

トップページ研究分野と周辺

群知能(swarm intelligence)は、例えば鳥や昆虫の群れに見られるように、個体間の局所的な簡単なやり取りを通じて、集団として高度な動きを見せる現象(創発、等と呼ばれる)を模倣した計算手法として近年、研究が盛んになっている。
全体を統御する指導者は無く、平等な立場の個体の相互作用が全体を決めるボトムアップな方法となる。
進化型計算のうち、遺伝的アルゴリズムは交叉という個体間の相互作用があるので、群知能の一種と言える。
群知能は進化型計算を行なうものも多いが、鳥の運動のシミュレーション等は、進化型計算ではない。
両者は共に人工生命の一種として、共通部分を持つ関係と言える。

蟻コロニー最適化(ACO)

蟻(アリ)の群れは、各個体が以下のたった2つを行なう事で、エサのある場所から巣までの最短経路を群れ全体として見つけ出すという。
・自分が通るときに「フェロモン」という化学物質を道に落とす(フェロモンは時間とともに蒸発していく)。
・仲間のフェロモンが残っている所を通ろうとする。
図のように、エサの場所から巣まで障害物がある場合、最初は二つの経路に分かれて運ぶかもしれない。
しかし、長い経路の方が時間当たりの個体の通行量は少なくなり、フェロモンの蒸発も進んでいく。
自然と短い経路の方ばかりを全ての個体が通るようになっていく。
或る種の最短経路探索問題はNP困難問題という、現在の最先端の数学でも解法が分からない非常な難問として知られている。その準最適解を蟻の群れが見つけ出す事があるのは、まさに自然の驚異の一つと言えるだろう。

蟻コロニー最適化の図解

ACOのアルゴリズム(初期化)

巡回セールスマン問題(TSP)は、多数の場所(ここでは都市とする)を全て一回ずつ訪問(同じところに二回行ってはいけない)する場合の最短経路を求める問題である。問題自体は非常に簡単だが、正確な解は全ての順番を調べなければ分からない(今のところもっと簡単な計算方法が分かっていない)NP困難問題というタイプの問題となる。
ACOでこの問題を解く場合、まず、任意の二つの都市間のフェロモンは、最初は全て同じ値で初期化する。その値は、蟻の数/Greedy法による平均経路長、がよく用いられる。
Greedy法とは或る都市からスタートして、今いる都市から最も近い都市を順に辿り、スタート地点に戻る(全都市を回るが、各都市一回ずつしか訪問しないようにする)経路決定法だ。
最後が伸びるので、最短経路にはならない場合が多い。Greedy法で、全ての別の都市をスタート地点とした経路を都市の数だけ作り、その平均を取る。
次に、都市数(m)と同数の蟻を用意して、其々ランダムに都市を割当て配置する。t(繰返し回数)=0とする。

ACOのアルゴリズム(繰返し1:各蟻の経路生成)

其々の蟻は、全ての都市を一回ずつ訪問する。其々の蟻が、次にどこへ行くかは以下の式による。

ここで、左辺のpは繰返し回数tに於いて、k番目の蟻が都市iにいるときに、都市jに移る確率を表す。
N_i^kは、都市iにいる蟻kがまだ訪問していない都市の集合となる。そこに属する全ての都市jについて、pを計算する。
右辺の分子のτijは、繰返し回数tに於ける都市ij間のフェロモンの量、ηijは都市ij間の距離の逆数となる。αとβはフェロモン量と都市間距離の重要度を決めるパラメータだが、α=1.0、β=0.5が良いとされている。
右辺の分母は、蟻kがまだ訪問していない全ての都市について、今いる都市iとのフェロモン量、都市間距離の逆数等を使った分子と同じ量を求めたものの総和となる。
結局、今いる都市iから見て、間のフェロモン量が多く、距離が短い都市ほど、移る確率は高くなる。これらの確率に基づいてサイコロを振り、どれか一つの都市に移り(確率の低い都市に移る場合もある)、全ての都市を一回ずつ訪問するまで、上記の式に基づく遷移を繰り返す。
全ての蟻が、全ての都市を訪問する事を終えたら、一回の繰返しが終了したとして、最も短い経路を記録する。

ACOのアルゴリズム(繰返し2:フェロモン量の更新)

全ての蟻が、全ての都市を一回ずつ訪問したら、各都市間のフェロモンの量を更新する。
都市iと都市j間のフェロモン量の更新は、以下の式に基づく(繰返し回数tのときのフェロモン量からt+1のときの量を決める)。

ここで、上の式の右辺第1項は、フェロモンの蒸発を表す。pは蒸発率で、0~1の固定した値を用いる。
上の式の右辺第2項は、全ての蟻が、都市ij間に、繰返し回数tのときに落としたフェロモンの総和を表している。
蟻kが、繰返し回数tのときに落とすフェロモンは⊿τij^k(t)で示されるが、その蟻が繰返し回数tのときに作った経路Tの中に都市iと都市jを直接結ぶ線が無い場合は(通過していないので)、落とすフェロモン量は0となる。
通過している場合は、その蟻kが作った経路長Lで一定値Qを割った値とする。Qは簡単に1を用いる場合も多い。
つまり、経路の総距離が短い程、(そこに長くいるとも考えられ)フェロモンの分泌量が増える。

ACOのアルゴリズム(終了)

初期化の後、繰返し(全ての蟻の経路生成+フェロモン量更新)を一定数繰り返す。繰返し回数tが予め定められた値に達すれば、終了とし、最後のtに置ける最も短い経路を、最終解とする。
繰り返すにつれ、繰返し毎の最短経路はだんだん短くなっていくが、ある所で停滞する(局所解収束)場合もある。

粒子群最適化(PSO)

鳥や昆虫をはじめ、多くの動物の群れは、仲間の誰かが良い場所(エサがある、安全など)を見つけると、次第にそこに集まって周辺を探索する。
同時に、各個体が探索した良い場所も覚えていて、その周辺に戻る動きを見せる場合もある。
最も良い場所(最適解)は一箇所しかないが、比較的良い場所(準最適解、優良解、局所解)は多数存在する場合もある。また良い場所の近くも良い場所である可能性は高い。
この動物の探索方法は、優良解の周囲を重点的に探索する方法と言えるだろう。
これをアルゴリズム(計算手順)化したのが、粒子群最適化(Particle swarm optimization)である。

PSOのアルゴリズム(初期化)

まず探索空間内にm匹の魚をランダムな位置(Xi)に配置する。各魚の速度(Vi)は全て0とする。ここでXiはi番目の魚の位置(N次元空間の座標)、Viはi番目の魚の単位時間当たりの各座標の変化量となる。繰返し回数(この一回が単位時間となる)tを0とする。
各魚は今まで自分が行った場所のうち、最も評価値の高い場所の位置データ(Pi)を持つ。これは、最初はランダムに置かれた場所とする。
全ての魚がこれまで訪問した場所のうち、最も良い場所(評価値の高い場所)の座標データをPgとし、最初はランダムに魚が置かれた位置の中で最も良い場所とする。

PSOのアルゴリズム(繰返し1:位置の更新)

各魚は、以下の式に基づいて、次の時間における速度を決め、自分の位置を決める。

ここで、wは以前の速度をどれだけ保持するか決める「慣性重み」で通常、0~1の値を設定する。c1とc2は自身に履歴の中で最良の場所に重きを置くか、群れの履歴の最良の場所に重きを置くかを決める調節パラメータで、適当に設定する(c1=c2としてもよい)。rは多様性を維持するための乱数で、0~1の範囲でその都度サイコロを振って決める。
上記の式は、i番目の魚の位置と速度の次元毎に別個に行なう。例えば、2次元空間を探索している場合は、x座標成分、y座標成分ごとに、上記の位置、速度を計算する。
これらの計算を全ての魚について行なう。

PSOのアルゴリズム(繰返し2:最良値の更新)

各魚について、現在の評価値(f(Xi))と過去最高の評価値(Pi)を比較し(ここでfは、位置から評価値を算出する評価関数)、f(Xi)>Piであれば、Piにf(Xi)を代入して更新する。
そのtに置ける最良のP(t)(群れの位置の中で最高の評価値)をPgと比較し、P(t)>Pgであれば、PgにP(t)を代入して更新する。
tを1増やす。

PSOのアルゴリズム(終了)

初期化の後、繰返し(全ての魚の位置更新+最良値更新)を一定数繰り返す。繰返し回数tが予め定められた値に達すれば、終了とし、最後のtに置ける最も良い評価値の位置を最終解とする。
繰り返すにつれ、繰返し毎の最良位置は良くなっていくが、ある所で停滞する(局所解収束)場合もある。