群知能＋Pythonを使って新宿駅近くのラーメン店を巡る最短経路を探してみた

こんにちは。ラーメン好き技術者の伊藤彰彦です。

皆さんは「アリの穴から堤も崩れる」ということわざをご存知でしょうか？ほんの小さな不注意や油断が大事につながることのたとえとして、中国の戦国時代から伝わる言葉です。この言葉は大切な教訓であると同時に、アリという非常に小さな生物が、群をなすことによって大きな出来事を引き起こすことができるということを表しています。

生物の群がまるで知能を持っているかのように振る舞う様子は「群知能」（英：Swarm Intelligence）として知られています。アリやハチによる巨大な巣の構築や、鳥や魚の群れの一糸乱れぬ美しい動きは、群知能の働きによって実現されると考えられています。

群知能は、近年の人工知能の発展と結びついて、ビジネスや様々な課題解決に応用できるものとして注目を集めており、指数関数的な進化が予想されるエクスポネンシャルテクノロジーの一つにも選ばれています（参考：2045年に来たるシンギュラリティとエクスポネンシャルテクノロジー）。

今回は群知能を使った有名なアルゴリズムの一つである「蟻コロニー最適化」を用いて、新宿駅近くにあるラーメン屋を効率的に巡る最短経路を探すという、ラーメン好きにとって興味深い（かもしれない）課題にチャレンジしてみました。

群知能はどのようにして実現されるか

「蟻コロニー最適化」のアルゴリズムを理解するにあたり、まずそもそも群知能がどのように成り立っているかについて触れておきたいと思います。

アリやハチといった生物の社会的活動は、全体を取り仕切るリーダーによって管理されているように見えて、実際は一つ一つの個体が他の個体と相互作用することによって成り立っています。相互作用は単純で、例えばアリの場合「別のアリが残したにおいを追いかける」といった程度のものです。このような単純な相互作用が集団の中で働くことによって、巣から餌場までの無数の経路の中から最短経路を探し出すといった難しい問題に対する答えを出します。

一つ一つの個体が行っている行動は単純であるにも関わらず、それらが群れをなすことによって高度な課題を解決できるというところがポイントです。これをコンピュータや人工知能に組み込むことにより、少ない開発コストで難しい問題を解決できることが期待されています。

アリの巣から餌場までの最適な経路の見つけ方

アリの行動をもう少し詳しく見ていきましょう。アリが巣から餌場までの経路を見つける際、アリ達はまずランダムに巣の周辺をうろつきます。そして餌場を見つけるとフェロモン（におい物質）を残しながらコロニーへと戻ります。他のアリがフェロモンを嗅ぎつけると「別のアリが残したにおいを追いかける」というルールに則り、フェロモンの跡を辿って餌場を見つけ、経路のフェロモンを補強しつつ巣へと戻っていきます。

フェロモンは時間とともに蒸発していき、吸引力が弱くなっていきます。餌場までの経路が長いほどフェロモンは蒸発しやすく濃度が薄くなっていきます。経路が短ければフェロモンが蒸発するよりも早く他のアリによって補強されるため、フェロモン濃度が高く保たれます。このようにして、より短い経路により多くのアリが集まり、最終的に一つの最短経路にすべてのアリが集まるようになります。

こうしてアリは餌場までの最適な経路を見つけます。このようなフェロモンとアリの行動を模したシミュレーションを行うことによって、グラフの最適な経路を見つける手法を「蟻コロニー最適化（英：Ant Colony Optimization）」と呼んでいます。

一見単純だけど難しい巡回セールスマン問題

蟻コロニー最適化の応用例の一つに、巡回セールスマン問題の近似解を導くというものがあります。巡回セールスマン問題とは、セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求めるという問題です。

一見単純な問題に見えますが、この問題はNP（Non-deterministic Polynomial time）困難と呼ばれる問題のクラスに属しており、都市数が増えていくと爆発的に計算量が増えて解決が困難となることが知られています。この問題を、蟻コロニー最適化を用いることにより、都市数が増えたとしても（あくまで近似的にですが）少ない計算量で解くことが可能になります。

今回はこの巡回セールスマン問題の実例として、新宿駅周辺のラーメン店を巡る経路の最適化について考えていきたいと思います。「一度にそんなたくさんのラーメン店行かないよ！！」というツッコミが聞こえてきそうですが、何か皆さんの中で実用的な例に置き換えて読んでいただけたらと思います。

開発環境

ラーメン店巡回経路の最適化を実装するにあたり、コードがシンプルで扱いやすいPythonを用いてプログラミングを行いました。開発環境としてMicrosoft社が無料で提供しているVisual Studio Community 2017を利用しています。

新宿駅周辺のラーメン店の情報や店舗間の移動距離を取得するため、今回2種類のWeb APIを使用しました。1つはGoogle LLCが提供しているGoogle Maps Platformで、地点間の距離（所要時間）取得や経路作成、地図の表示に使用しています。もう1つは株式会社ぐるなびが提供するぐるなびAPIで、新宿駅近傍のラーメン店の検索に使用しています。

Google Maps PlatformとぐるなびAPIは利用者登録すれば誰でも無料で使用することが可能です。どちらも利用回数に制限がありますが、個人で利用する範囲では利用制限に引っ掛かることはほとんどありません。利用開始方法については、こちらのサイトを参考にしてください。

計算の流れ

プログラムの流れは以下のようになります。
新宿駅の地理座標（緯度と経度）を取得（Google Maps Platform Geocoding API使用）
上記で取得した地理座標を中心とするラーメン店を検索（ぐるなびレストラン検索API使用）
各店舗間の距離を取得（Google Maps Platform Matrix Distance API使用）
蟻コロニー最適化を用いて巡回セールスマン問題を解き、最適経路を計算
得られた最適経路をfolium（Google Map描画用モジュール）により表示

巡回セールスマン問題の解き方

蟻コロニー最適化を用いて巡回セールスマン問題を解く方法として、Marco DorigoのAnt Systemと呼ばれるモデルを用いた手法を採用しました。この手法では各地点間にフェロモン密度というパラメータを持たせます。アリはフェロモン密度が高い経路をより高い確率で選ぶようになっています。アリが通った経路に応じてフェロモンが分泌され、フェロモン密度の分布が変化します。フェロモンは巡回経路の合計距離が短いほど強く分泌されます。

実際のプログラミングにあたってはこちらのサイトを参考にしました。

計算条件

Google Maps PlatformのDistance Matrix APIのアクセス数制限の都合上、店舗数は20店舗程度に制限しました。店舗の検索範囲を新宿駅から500 m圏内とし、筆者の好みにより検索キーワードを「豚骨ラーメン」としました。この時の検索ヒット数は18件となりました。

計算時間的には店舗数が増えても問題ありませんが、店舗数が100件を超えてくると数回プログラムを走らせただけでDistance Matrix APIの月間アクセス制限数に到達してしまうため、今回このような制限を設けました。

蟻コロニー最適化アルゴリズムで1回の巡回で同時に放たれるアリの数を100匹とし、時間経過数（フェロモンが更新される回数）を50回としました。他にも細かいパラメータがありますが、ここでは割愛します。詳しくはコードをご覧ください。

計算結果

100匹のアリを50回巡回させた後に得られた最適巡回経路は下図のようになりました。移動距離の総和は3.5 km、所要時間は徒歩44分でした。これで無駄なくラーメン店を回れます

フェロモンの更新を重ねるごとに100匹のアリの移動距離の平均値がだんだん短くなっていくことから（下図）、確かにアリの行動が最適化されていくことが確認できました。導き出された経路は実は最短ではなく（これまで確認できた最短距離は3.1 km）、この方法ではアリ達が局所的な最適解にトラップされてしまうようです。厳密な最短経路を求めるには至りませんでしたが、実用的な近似解を求める上では十分な結果を得ることができました。