Ant Colony Optimization（創発とStigmergy）

　アリの群れが、餌場から巣へと餌を持ち帰っている様子を観察すると、アリどもは同じ1本の経路をたどっているように思われる。これを、アリが他のアリの付置したフェロモンを頼りに移動しているからだ、と説明することは、広く膾炙しているといえよう。
　しかし、アリたちは1本の経路をたどっているだけではなく、最短の経路をたどっているようにも思われる。もしアリが他のアリの付置したフェロモンに頼って移動しているだけだとすると、最初にとんでもない経路に沿ってフェロモンが付置されてしまった場合、アリどもはそれを修正できないはずである。
　アリ個体の認知能力はごく限られており、自分の現在地から遠く離れた餌場の位置を確認することはできないし、先の経路の予測もできない。行動ルールも、フェロモン蒸気を左右の触覚で感知して左右に曲がるという、非常に単純なものでしかない。したがってアリ個体はせいぜい、確率的にフェロモンの濃度に反応して（ときどきフェロモンを無視して経路を外れてみるなどして）移動・餌の探索をする、といった、局所的な能力しか持たないはずである。にも関わらず、アリの群れは大局的な最短経路を発見している。このようなことが可能になる理由の1つは、アリの群れが群れであることに求められるはずだ。個々には高度なレベルの知能を持たない個体が、群をなすことによって、個々の行動パターンからは予測できない複雑な群レベルの行動をみせることから、この働きは群知能swarm intelligenceと呼ばれている。
　では、じっさいにはアリの群れは、どのようにして最短経路を発見するのだろうか。単純化のために、長短2本の経路を選択する場合を考えよう。
　最初、経路にほとんどフェロモンがない状態では、アリは長短の経路をランダムに選択し、フェロモンを付置しながら進んでいく。そして、経路の先にある餌を確認すると、フェロモンを付置しながら、もときた道（に付置されたフェロモン）をたどって巣に戻ってくる。
　アリが1匹の場合はこれで終わりであるが、アリが複数いる場合には事情が違ってくる。複数のアリは、初期段階では長短の経路をランダムに選択するので、どちらの経路にも等しくフェロモンが付置されるはずである。ところが、アリの移動速度は一定であるから（アリは経路長を知らないので、経路によって急いだりのんびりしたりはしない）、短いほうの経路には早く付置が終わり、往路のフェロモンに加え、復路のフェロモンまでもが付置されることになる。
　いま、短い経路と長い経路とに、1匹ずつアリが向かったとしよう。短い経路の長さをSとし、アリの移動速度をS/分とすると、2分後には、短い経路には往復で2回ぶんのフェロモンが付置されていることになる。いっぽう長い経路については、まだ往路のぶんのフェロモンしか付置が終わっていない（アリはそおらく、長い経路の復路の途中にいるので）。出発地点である巣から見ると、短い経路には長い経路の2倍濃いフェロモンが付置されていることになる。アリはフェロモンの濃度が高い経路を選択する傾向があるので、この時点で巣を出発するアリは、長い経路ではなく短い経路を選択するようになる。
　これに加えて、フェロモンは化学物質であるため、付置されつづけなければ蒸発して消滅していく。しばらく利用されなかった経路からはフェロモンが消えてしまうため、アリがその経路（非効率な経路）を選択することはなくなり、アリはますます短い経路にひきつけられるようになるのだ。こうしてアリの群れが短い経路にひきつけられると、その経路にはさらにフェロモンが付置されていくので、アリの経路選択はますます強固なものとなっていく（正のフィードバック）。
　これがアリの群れによる経路探索のあらましである。整理しよう。この探索のためには、アリ個体の行動ルールに加え、アリの群れシステムが置かれた環境の性質と、アリが群れであるということの効果とが関わっていた。まずアリ個体の行動ルールは、

• フェロモンによるマーキングを行いながら移動を行う。
• 一定速度で移動を行う。
• フェロモンの濃度が高い経路ほど、高い確率で選択する。

というものであった。アリの認知能力は低いため、自身の周辺のフェロモンという局所的な情報に基づいてしか行動していないことに注意しておこう。
これに加え、以下のような環境の性質が利用されている。

• アリがマーキングするほどフェロモンは濃くなる。
• フェロモンはじょじょに蒸発していく（負のフィードバック）。

環境にこの性質があるおかげで、フェロモンは最短経路に付置されたものだけに絞られていくのだ。アリ個体は、ほかのアリ個体の行動に影響されて行動するという意味で、ほかのアリ個体とコミュニケーションしていると言えるが、このコミュニケーションはシグナルそのものに意味のある直接的なコミュニケーション（言語や動物の身ぶり）ではなく、環境の修整を媒体とした間接的なコミュニケーション(indirect communication mediated by modifications of the environment)である。このコミュニケーションを、動物学者Grasséはスティグマジー(stigmergy)と名づけた(Grassé, 1959)。
　以上のように、最短経路を探索するアリの群知能とは、スティグマジーに基づく、行動ルール＋環境特性＋群の効果、であるとまとめられる。
　さて、このように多数のモジュールを組み合わせたシステムを、こんどは人工的に設計することを考えよう。アリの群れが最短経路を探索しているのであれば、アリの群れに最短経路を探索させればよいのである、と考えるわけだが、厄介なのは、最短経路探索というアリの群知能が、行動ルールや環境特性やのそれぞれだけを見たのでは、じゅうぶん予想できないものだ、という点である。上述の各ルールのどこにも、"最短経路を探索する"という性質は含まれていないように思われるのだ。
　近年では、コンピュータの計算能力の発展に伴い、多数のモジュールからなるシステムをシミュレートして実験的に設計することが可能になっている。事前に予想できなくとも、実際にいろいろ試してみて結果が出たものを採用する、という方法がとれるようになってきたわけだ。こうして考案されたアルゴリズムが、最初のAnt Colony OptimizationであるAnt Systemであり（Dorigo, et al. 1991）、以後、これの改良アルゴリズムが多数提案されてきた。例をあげれば、一定以上のフェロモンがある経路は確率1で選択するAnt Colony System、付置しうるフェロモンの量に制限を加えるMax-min Ant System, 動的な問題に対応したAntNetなどである。