蟻に巡回セールスマン問題を解かせてみる

群れのルール 群衆の叡智を賢く活用する方法

群れのルール 群衆の叡智を賢く活用する方法

「群れのルール 群衆の叡智を賢く活用する方法」を読んでいたら、昆虫の知性を模倣して、情報科学の問題を解くという興味深い問題があったので、自分でも手を動かしてみました。

この書籍の中では、一匹一匹は賢いとは思えない生き物(蟻や蜂、鳥)が、群れとして活動した途端に見せる素晴らしい知性と、そうした知性が生まれる理由を紹介しています。

蟻が餌までの最短経路を見つけることができる理由

書籍の第1章では、蟻がどうやって餌までの最短経路を見つけるのかについて説明しています。最初は各々の蟻がランダムに餌を探しているように見えたのに、徐々に餌までの経路ができ、最終的には餌までの最短経路を、ほとんどの蟻がたどるようになります。

この現象のポイントとなるのは、「フェロモン」です。蟻は餌を探して巣に持ち帰るまでに、経路にフェロモンを残します。多くのフェロモンが残っている経路の方が、より選ばれる可能性が高くなります。

フェロモンは揮発性です。より短い経路の方が、単位時間あたりに通過する蟻が多いため、結果として多くのフェロモンが残ることになり、最終的に最短経路が選択されます。

以下の図*1が、上記の状況を説明しています。1匹の蟻が餌までを辿り初め(1)、そのフェロモンを辿って(多少のランダム性を持ちながら)多くの蟻が餌を運び(2)、最終的には最短経路にフェロモンが蓄積し、ほとんどの蟻がその経路を辿ります(3)。

巡回セールスマン問題への応用

このような、蟻の「餌までの最短経路をみつけようとする」という性質を、情報科学の分野で応用したのが、Marco Dorigoです。1992年、巡回セールスマン問題をヒューリスティックな手法で解く「蟻コロニー最適化」を提案しました。

ちなみに、巡回セールスマン問題とは、「都市の集合と各2都市間の移動コストが与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の、総移動距離が最小のものを求める」問題です(wikipediaのページ)。巡回セールスマン問題は、NP困難と呼ばれるクラスに属し、効率よく解く(つまり、多項式時間の)アルゴリズムが見つかっていません。よって、最適解でなくても良いので、できるだけ良い解を得るためのヒューリスティックな手法が研究されてきました。

蟻コロニー最適化のアルゴリズム

巡回セールスマン問題を解くための、蟻コロニー最適化アルゴリズムの概要は、以下のとおりです。

蟻を生成する
フェロモン情報を初期化する
while(解が収束するまで){
各蟻に対し、フェロモンとヒューリスティックな情報から、解(巡回路)を選択させる
フェロモン情報を更新する
}
解を出力する

また、巡回路の選択と、フェロモン情報の更新に燗するアルゴリズムの詳細は、wikipediaの蟻コロニー最適化を参照。

実験結果

以下、実際に30都市で実験してみた結果です。線の太さが、相対的なフェロモンの強さを表します。

初期状態。フェロモンは色々な経路につけられています。

f:id:GOLEM-XIV:20110109153809p:image

途中状態。徐々に、特定の経路(つまり、全体として距離が短い経路)に、フェロモンが溜まってきます。

f:id:GOLEM-XIV:20110109153810p:image

最終的な解は、以下のとおりです。この例では、最適解が見つかっています。

f:id:GOLEM-XIV:20110109153812p:image

まとめ

ありさんすごい。

というわけで、蟻コロニー最適化を使用して、巡回セールスマン問題を解く方法を紹介しました。半日弱で実装できちゃう単純なアルゴリズムで、かなり良い解が出せるのはびっくりです。

こういう風に、全然違う領域の知識を活用して、新しい解法が生まれることってよくありますよね。やはり、専門分野だけではなく、色々な方向にアンテナはっておくのは大事ですね。そもそも、違う分野の話って、単純に楽しいし。

*1wikipediaより引用

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です