はじめに
Fable 5(以下、Fable)と「CPUで動くAI」について語るとこのような反応がありました。
自ら「最適化系は最も苦手な領域」と語ってくれました。
生成AIが何でもできるように見える今、Falbeは自ら「苦手」と語りました。理由として生成AIと古典アルゴリズムは競合ではなく、得意領域がまったく違うということを訴えています。それはそうだろ……と思う方もいますが、意外に健闘したり、確かに「苦手」だと思う資料ができたので記事にします。
まとめると
- LLM:汎用。重い・遅い・確率的(同じ入力でも毎回違う答え)・正しさの保証なし
- 古典アルゴリズム:特化型。高速・決定的・完全オフライン・(厳密解法なら)最適性を保証
確かに、Fableを代表するLLMは、ハルシネーションを起こしたり、毎回出力が違うなど厳密解法とは真逆のアプローチです。Fableは本当に「苦手」なのか、本記事ではその差が最も鮮明に出る組合せ最適化の一つである巡回セールスマン問題を舞台に、実際にFableと古典アルゴリズムを戦わせてみました。
今回Fableはやり取りの間に解いてしまったので、裏で本当にやったか確認する方法がありませんでした。しかし、Fableと古典アルゴリズムには目視可能なレベルで実行速度の差が出ているのでそのまま採用します。APIキーがあるサービスであればある程度何を起ったか予想は立てられると思います。
本記事の対象
- 生成AIの得意なことと苦手なことを知り、設計に役立てたい方
- 生成AIの時代だが枯れた技術に価値を見出したい方
- Fableでもできないことがあることを知りたい方
巡回セールスマン問題とは
本記事ではFableがどのような結果になるかに焦点を当てるため、概要に留め厳密な数式を説明しません。シリーズ【配送最適化入門】に非常に詳しく書かれているため、そちらを参考にしていただければ幸いです。また、後述のアルゴリズムについてもリンクを設けています。
概要
巡回セールスマン問題とは
都市の集合および 2 都市間の移動コストが与えられているものとする． この時，セールスマンが全ての都市を 1 >回ずつ通って最初の都市に戻ることができるルートのうち， 総コストが最小になるルートを求める問題が巡回セー>ルスマン問題である．
NTTデータ数理システムより
図は15地点を赤い出発点からスタートし、全ての地点を一度ずつ訪れて出発点に戻ります。これは、配送ルート・巡回点検・部品の加工順など、現実業務そのものです。歴史が長く「枯れた」解法が多数存在し、普通のPCでも解くことができます。さらに、地点が増えると組合せが爆発します。例えば15地点で約436億通りになります。
実験設計
ルール
- 問題：2次元平面上の巡回セールスマン問題。座標は一様乱数(シード固定、再現可能)
- Fable設定：座標リストを読み、コード実行なし・純粋な推論のみで巡回順序を出力。あわせて自分の経路長を自己推定させる。コード実行はソルバーを書いて勝ってしまうので禁止。本実験が測るのは「LLMの素の推論による最適化能力」である
- 古典側：最近傍法（Nearest Neighbor: NN）、2-opt局所探索、焼きなまし法（Simulated Annealing: SA）+2-opt。すべて純Python・標準ライブラリのみ、ノートPCのCPUで実行。計算方法と解説リンクは以下の通り
| 解法 | 計算方法 |
|---|---|
| 最近傍法 | 今いる都市から最も近い未訪問の都市へ移動する |
| 2-opt | 交差する2本の辺を削除し、別の形で再接続することでルートを短くする |
| 焼きなまし | あえて悪化を許容することで局所最適から脱出する |
-
古典アルゴリズムの目安となる計算時間は以下の通り
(11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz)
-
基準：15都市は動的計画法（Held-Karp）による厳密解。30・50都市はSA+2-opt×10試行のベストを best known とする
Round 1：15都市
| 解法 | 経路長 | 最適比 | 計算時間 |
|---|---|---|---|
| 最近傍法 | 3,623 | +8.4% | 0.000秒 |
| Falbe（推論） | 3,347 | +0.2% | 数十秒・数千トークン |
| 2-opt | 3,341 | 最適 | 0.000秒 |
| 焼きなまし | 3,341 | 最適 | 1.0秒 |
| 厳密解（DP） | 3,341 | — | 0.52秒 |
苦手と語るFableですが意外と健闘しました。しかし、実行時間を見ると圧倒的に遅く、確率的なので今回のルールである乱数シード固定ではなく、乱数を変えた10回の平均誤差、標準偏差などの指標だったら全く違う結果であることから、現実問題でこの解に対する保証は何もありません。
Round 2：30都市
| 解法 | 経路長 | best known比 | 計算時間 |
|---|---|---|---|
| 最近傍法 | 6,246 | +28.1% | 0.000秒 |
| Fable(推論) | 5,355 | +9.8% | 数分・数千トークン |
| 2-opt | 5,268 | +8.0% | 0.000秒 |
| SA+2-opt ×10 | 4,877 | best known | 5.0秒 |
急に解が悪くなりました。15都市のFableは自身も語るように苦手だという部分が出てきて、15都市の結果はフロックの可能性が出てくる結果となりました。それでも最近傍法より精度が20ポイントほど精度が良い点は驚きに値します。焼きなまし法は時間がかかりますが、最適化完了し、Fableよりも早く解答できました。この辺りから時間とトークンがもったいなくなります。
Round 3：50都市
| 解法 | 経路長 | best known比 | 計算時間 |
|---|---|---|---|
| 最近傍法 | 6,283 | +13.4% | 0.000秒 |
| Fable(推論) | 6,055 | +9.3% | 数分・数千トークン |
| 2-opt | 5,812 | +4.9% | 0.001秒 |
| SA+2-opt ×10 | 5,541 | best known | 5.0秒 |
他のアルゴリズムが30都市と比べ良い結果になりましたが、Fableだけはあまり変わりませんでした。30都市に比べ明らかにルートが異なる結果になりました。2026年7月現在の最新LLMでは15都市程度なら準最適解レベルはたどれる結論になりました。
驚く結果は、交差するルートがFableにもほとんどないという点(N=50の真ん中が交差している？)です。解の精度ばかり目に行きがちですが、純粋な推論でも2-optは実現しているということになります。
まとめ
Fableでの完全な最適化計算の推論は古典アルゴリズムに勝てず良い結果とは言えませんでしたが、自然言語から最適化という計算自体はできました。計算不能にならず、走り切ったことは称賛に値します。
ではLLMと古典アルゴリズムは手を取り合えることは可能でしょうか？キーワードとして自動定式化(Autoformulation)があります。例えば、『障害物を通行不能なハード制約とするのではなく、移動コストが跳ね上がるソフト制約（ペナルティコスト課金）として処理する』といった要求に対し、LLMがソルバーの解読可能なコードや数式に動的変換するシステムは、すでに論文や解説があります。お互いの得意分野を活かしたアプローチは今後様々な分野で活用されると予想されます。この実験中にそのようなものがあってもおかしくないと思い調べた結果、自動定式化にたどり着きました。
この記事のレビューをしていただいた際、AIは自動定式化に留め、ソルバーという電卓を使うように外部リソースに任せるのは直観的であるということでした。また、Fableに特に制約を課すことなくフルパワーで挑んでもらって、より早く最適解を導き出すアルゴリズムを発見できるのか？みたいなのが面白そうという意見もいただきました。特に、制約なしのFable(もしくは将来のモデル)に純粋に目的関数・制約条件が求められるのであれば。業務として大きな変化になると思います。
依然としてLLMの不確実性を抑えることは難しく、いかに計算効率・性能を上げていけるかは今後に筆者も含めた様々なエンジニアが取り組んで改善されていくことを期待していきたいと思います。また、機会があれば自動定式化について記事が書けたらと思います。