巡回セールスマン問題にみる実践と学習のギャップ

概要

組合せ最適化問題の代表的な問題は?と聞かれると、「巡回セールスマン問題」と答える人が多いかもしれません。一方、アニーリングマシンが組合せ最適化問題に適していると言いますが、実世界にある巡回セールスマン問題をアニーリングマシンで解くことが必ずしも有効とは限りません。

今回は巡回セールスマン問題を例に、アニーリングマシンの学習と実践にどのようなギャップがあるのかを解説したいと思います。

巡回セールスマン問題がアニーリングマシンの教育によく使われる理由

巡回セールスマン問題は、数学的にも解き甲斐があり数多くの数学者を魅了してきました。

一般的な巡回セールスマン問題は、「都市数$n$を各1回ずつ訪問し全都市を巡回する最も距離が短くて済む経路を求める」問題で、全ての経路を探索する大変さが一言で言える点で、組合せ最適化問題の難しさを説明するのに好まれています。

例えば、都市数を$n$とすると$n!/2n$回の計算が必要になりますが、このような数式は解の候補が爆発的に増えることが容易に想像できます。

解くのに非常に時間がかかる、つまり「多項式時間に解けない問題」を『NP問題』といい、巡回セールスマン問題は、「NP問題と同等あるいはそれ以上に難しい」という意味の『NP困難』に分類される問題と言われています。問題を現実的な時間で解けるコンピュータがあることを説明するのに巡回セールスマン問題がよく使われるのです。

巡回セールスマン問題解法の数学的な探求

巡回セールスマン問題(以降TSP)は「数学的に解く」という意味では様々な解法が研究されてきました。

例えば

  • 1962年にはP&G社がTSPの最も良い解を出した人には賞金1万ドルを贈るというキャンペーンを出したことがある※1
  • 1960年代に解き明かされたTSPは49都市の問題だったが、別の手法を加える工夫により1980年代に2,392地点のTSPという記録がもたらされた。2006年には「コンコルド」というプログラムで85,900都市のTSPを解けるようになった※1,※2

などのムーブメントがあり、他にもヒューリスティックと呼ばれる必ずしも最適な答えが見つかるわけではないがある程度正しい答えが早く求まる手法(貪欲法や局所探索法、焼きなまし法など)が様々検討されています。

アニーリングマシンは焼きなまし法の理論を量子スピンやCMOSスピンで実装された手法であるため、TSPを解くことが試みられているのも自然な流れというわけです。

実践とのギャップ

しかし実課題の解法として、数学的な解法のまま問題を解く必要はありません。

数学の世界におけるTSPは厳密な問題であり、与えられた制約(各都市を1回廻る)を守らなければならないから解き甲斐があり、解ける都市数が増えることにより学術的進歩が人々に感動をもたらしている側面があります。

一方で、実社会の課題を考えると「同じ場所を2回廻っても良い」など制約がゆるくなることもあれば逆に「廻る順番に制約がある」などと部分的に細かく複雑に制約が入ることもあり、TSPの計算式がそのまま適用できないことが多くなります。

そのため、現実的な「最適経路の探索」を行うにあたっては、制約の数・複雑さ・問題の規模によって、数学的な手法と、課題に応じた個別の工夫(解法)を組み合わせることによって解決しています。

実践に適した手段を知る

このように「学習」と「実践」にギャップがあるケースがあります。

熟練した技術者は解きたい問題に対して、「適切な手段」を探して取捨選択し、知識と経験を常にアップデートすることで問題解決の確度を高めます。そして問題が複雑になればなるほど、より一層日々の技術探求が求められることになります。

Annealing Cloud Webでは「問題解決」にあたる技術者の方々に対し、このようなアニーリングマシンや最適化問題の解決について学習段階ではなかなか先回りして気づくことができないような情報も積極的に発信していきます。

参考文献

※1:驚きの数学 巡回セールスマン問題 ウィリアム・J・クック著 松浦俊輔訳 青土社より
※2:Traveling Salesman Problem (uwaterloo.ca)

組合せ最適化問題をアニーリングマシンで解決する具体的な事例を知りたい人は

組合せ最適化問題とは

組合せ最適化を身近な組合せ最適化問題として分かりやすい2つの例を用いて解説します。また、IoT社会における組合せ最適化処理の高速解法の重要性について述べます。

COVID-19感染対策を考慮し研究員シフトを最適化する

COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。

保険会社の再保険ポートフォリオを最適化する

自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。

アニーリングマシンの使い方が知りたい人は

易しく学ぶ最適化フロー

初級者向けに、アニーリングマシンで最適化問題を解く工程を、「課題整理と要件定義」「定式化」「入力データ作成」「アニーリングマシン実行」の4段階に分けて手順やポイントを解説します。

アニーリングマシンのための数学

アニーリングマシンが得意とする問題の特徴である「二次」「離散」を中心に、知っておくべき数学的前提を易しく解説します。