メタヒューリスティクスとアリ:人工生命の基礎知識3

人工生命の基礎知識

更新日:2022年12月1日(初回投稿)
著者:東京大学 情報理工学系研究科 電子情報学専攻 教授 伊庭 斉志

前回は、進化論的手法と創造性について紹介しました。人工生命の応用として知られているメタヒューリスティクスは、生物や物理現象を基に構成された探索手法・AI技法です。前回説明した進化計算も、進化論に基づくという意味ではメタヒューリスティクスです。今回はその代表例である、アリの群知能とその応用であるACOについて説明します。ACOは、ロジスティックスの最適化、ネットワークのルーティング、クラスタリングなど、さまざまな実問題に応用されています。

1. メタヒューリスティクスとは

ヒューリスティクスとは、ある程度正解に近い解を見つけ出すための経験則や発見方法のことであり、メタヒューリスティクスとは、組み合わせ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことです。要するに、あらゆる組み合わせ最適化問題に適用できる近似解法といえます。

メタヒューリスティクスは、生物や物理現象をもとに構成された探索手法・AI技法に用いられています。GA(Genetic Algorithm:遺伝的アルゴリズム)、GP(Genetic Programming:遺伝的プログラミング)、SA(Simulated Annealing:焼きなまし法)、ニューラルネットワーク、強化学習なども、広い意味ではメタヒューリスティクスです。それは、進化論、物理現象、脳の可塑性、行動主義などをもとにしているためです。

図1に、メタヒューリスティクスの分類を示します。前述のGA、GPなどは、進化計算に入ります。今回と次回では、図中の2番目の項目である群知能に基づくメタヒューリスティクスについて説明します。

図1:メタヒューリスティクスの分類
図1:メタヒューリスティクスの分類

2. アリの知恵

アリという昆虫は、人間が地球上に現れる1億年以上前から、コロニーという集団による生態を確立しています。そして、原始的なコミュニケーションによって、餌の採集、営巣、分業などの複雑なタスクをこなす社会を形成しています。その結果、アリは生物の中でも適合度が高く、過酷な環境にも適応できる生物となりました。アリの行動モデルから、ルーティング(経路制御)やエージェント、ロボティクスの分散制御に関する新しいアイデアが生まれています。

アリの種類のうち多くは、餌の採集が終わって巣に戻るときに、自分の通った道筋の痕跡を、揮発性の物質フェロモンを分泌することで残します。そして、餌の探索中に他のアリの残した道筋(フェロモントレイル)があれば、それをたどります。アリはフェロモンによる情報交換を用いて、効率的な探索、特に最短経路探索を実現しています。

1匹のアリは以下のように単純なことしかしません。

  • 通常はランダムに餌を探す。
  • 餌を見つければ巣に持ち帰る。そのとき帰り道にフェロモンを落とす。
  • フェロモンが近くにあれば、そちらに導かれる。

アリの餌集めは、一見非常に簡単な問題に思えます。しかし、アリはほとんど盲目なので分岐の認知すら難しく、個体間で餌の位置を伝達する複雑なコミュニケーションは取れません。それにもかかわらず、アリはフェロモンを介した誘導によって、集団としての効率を高める探索を実現します。

図2~5は、上記の仕組みでアリの餌の探索をシミュレートしたものです。図2の中心部分(紫)には巣があり、その周りに3か所の餌(青)があります。

図2:アリの巣と餌
図2:アリの巣と餌

初めのうちは、アリ(赤)はランダムに餌を探し回り、餌を見つけると巣に持ち帰ります(図3)。その際にフェロモンを落とします。フェロモンは揮発性なので、遠くの餌よりも近くの餌からのフェロモントレイル(白は濃度が高く、緑は低い)が強くなりがちです。

図3:アリの分布とフェロモン
図3:アリの分布とフェロモン

結果的に、アリは巣の近くの餌に集中することになり、近い方の餌が最初に探索し尽くされます(図4)。 この図では、遠くの餌(左上)からのフェロモントレイルは薄くなっていて、まだあまり探索されていないことが分かります。一方、近い餌(右と左下)に関し、フェロモントレイルが現れています。

図4:アリから近い方の餌の消失とフェロモントレイルの痕跡
図4:アリから近い方の餌の消失とフェロモントレイルの痕跡

これらの餌がなくなるとフェロモンは消散し、その後、残った左上の餌場の探索が本格的に始まります(図5)。

図5:アリから近い方の餌とフェロモントレイルの消失
図5:アリから近い方の餌とフェロモントレイルの消失

3. ACOと巡回セールスマン

続きは、保管用PDFに掲載中。ぜひ、下記よりダウンロードして、ご覧ください。