概要
Sakana AIは、AIの長期的な推論能力、つまり「考え続ける力」を要する挑戦的な課題として「組合せ最適化」分野に着目し、世界最大級のコーディングコンテスト運営会社のAtCoder株式会社（以下、「AtCoder社」）との共同でベンチマーク「ALE-Bench (ALgorithm Engineering Benchmark)」を作成しました。同時にこの分野に特化したAIエージェント「ALE-Agent」を開発。ALE-Agentは、AtCoder社の許諾のもと2025年5月18日に開催されたプログラミングコンテストにリアルタイムで参加し、1000人以上の人間の参加者の中で21位の成績を達成しました。
はじめに
物流の効率化、工場の生産計画、電力供給網の安定化など、社会に不可欠な仕組みの背後には「組合せ最適化問題」があります。組合せ最適化とは、与えられた制約条件を満たす複数の組合せの中から最適解を探す数学的な問題です。問題の設定ごとに性質や有効な手法が異なるため、人間の専門家が多大な時間と労力をかけ、試行錯誤しつつ独自のアルゴリズムを構築する必要があります。こうした最適化アルゴリズムの発見は、どこまでAIで自動化できるでしょうか。最適化問題をAIで解くことができれば、さまざまな産業を効率化でき、大きなインパクトをもたらすはずです。
これはまた、「AIの汎用的な推論能力をどう測るか」という、AI分野全体にまたがるより大きな課題にも通じます。AIの実力を測る上で従来よく用いられてきた指標に、正解/不正解を問う形のプログラミング課題における正答率があります。プログラミングコンテストサイト「Codeforces」などにおける過去の出題を用いたベンチマークはその代表例です。しかし最新のAIはこれらの課題で人間のトップ層を上回りつつあり、スコアが頭打ちになりつつあります。既存のベンチマークでは測りきれていない創造性、継続的な思考、試行錯誤による知見の蓄積などが、今後のAIの発展における鍵となるはずです。これらのより高度な推論能力を客観的に測定することは可能でしょうか。
こうした問題意識のもと、このたびベンチマーク「ALE-Bench（ALgorithm Engineering Benchmark）」およびAIエージェント「ALE-Agent」を作成しました。ALE-BenchはAtCoder社の協力のもと、組合せ最適化分野における世界最大級のコーディングコンテストの過去の出題にAIが取り組めるようにしたものです。ALE-Agentは、Sakana AIがこの分野のため設計した特化型のAIエージェントで、同ベンチマークで高い性能を得たほか、実際のAtCoder社のコンテストにリアルタイムに参加し、1000人以上の人間が参加する中で21位の成績を収めました。一方で、ALE-BenchとALE-Agentの研究を通じて見えてきた、現在のAIの強みと課題から、今後のAI研究に対する洞察を得ることができました。
ALE-Bench：長期的推論と創造性を問う次世代のコーディングベンチマーク
ベンチマークを適切に設計し、AIによるその結果を分析・解釈するには、良質なデータや問題や当該領域の専門家との連携が不可欠です。Sakana AIでは最近でも、段階的な創造的推論の能力を測るSudoku-Benchや、実応用にフォーカスした日本語金融タスクベンチマークEDINET-Benchを開発してきました。そしてこの度、組合せ最適化分野で世界最大級のコーディングコンテストを運営するAtCoder社の協力のもと、最適化問題のアルゴリズムエンジニアリング課題のベンチマーク「ALE-Bench（ALgorithm Engineering Benchmark）」を開発しました。
ALE-Benchは、過去にAtCoder社が主催したAtCoder Heuristic Contest（以下AHC）を元に作成されています。AHCでは、物流の最適化や工場生産計画といった、現実社会の産業課題に直結する最適化問題が主に扱われています。数時間から数週間をかけて取り組まれるような、良質で難しい問題が出題されており、最適化アルゴリズムの専門家や実務で産業応用に携わっている人を含め、多い時には1000人を超える参加者がしのぎを削るコンテストです。
以下は出題された問題の一例です。これは、「できるだけ移動距離が短くなるように1000個の配達注文の中から50個を選んで配達順序を決める」という問題で、組合せ最適化問題の代表格である「巡回セールスマン問題」を発展させたものです。こうした問題では全ての組合せを網羅的に調べることは不可能なことがよく知られており、この問題の例では組合せの総数はおおよそ10200という天文学的な数に上ります。このような問題では、最適解を計算することは難しいため、少しでも良い解を見つけるために「焼きなまし法」などのアルゴリズムが用いられます。
AHC006（2021年11月開催）での「Food Delivery」は、できるだけ移動距離が短くなるように1000個の配達注文の中から50個を選んで配達順序を決める問題。（AtCoder社提供ツールに基づき描画）
ALE-BenchはAHCで出題された多種多様な最適化問題40問から構成されています（下図左）。また本ベンチマークでは、問題文や可視化ツール、コード実行環境、順位算出のためのソフトウェアを提供しています（下図右）。これにより、AIが人間の参加者と同様にコンテストに参加する状況をシミュレートでき、人間や他AIと公平な条件で競い合うことが可能です。詳細は論文やGitHub上のコードをご確認ください。
ALE-Bench概要
これまで組合せ最適化問題におけるAIによる自動化の試みは限定的でしたが、実社会応用のポテンシャルに照らして、取り組む価値のある領域です。また、既存のベンチマークは正解／不正解を問うものが多く、最適化問題のような近似解の「スコア」を競う問題に対するベンチマークは少数でした。未知の最適解を追究し続けるオープンエンドな性質を持つALE-Benchのタスクには、長時間にわたる推論能力や創造性、継続的な改善能力が求められます。これは、最適化問題にとどまらず、AI分野全体の発展にも寄与するベンチマークだといえます。
ALE-Agent：アルゴリズムエンジニアリングに特化したAIエージェント
Sakana AIは、アルゴリズムエンジニアリング能力に特化したAIエージェント「ALE-Agent」を開発しました。これは、自然言語で記述された最適化問題を受け取ると、全自動で試行錯誤を行い、その最適化問題を解くための優れたプログラムを開発するエージェントです。現在の最先端のAIであるGemini 2.5 Proをベースに、1）頻繁に使用されるアルゴリズムやテクニックなどのドメイン知識をプロンプトとして与える、2）推論時に複数の回答を生成することで性能を向上させる推論時スケーリングの一手法を用いる、という二つのアプローチを組み合わせています。技術の詳細は論文を参照ください。
今回、AtCoder社に許可をいただき、ALE-Agentを用いて実際のコンテスト（AHC046、AHC047の2回）にリアルタイムに参加し、同一のルール下で約1000人の参加者と競いました。その結果、AHC046で154位（上位16%）、AHC047では21位（上位2%）にランクインする結果となりました。
AHC047での順位表。21位の「fishylene」がSakana AIのAIエージェント「ALE-Agent」のアカウント。AtCoder社の許諾のもと実際のコンテストにリアルタイムに参加し、同一のルール下で1000人以上の人間の参加者と競った。
また、ALE-Benchを用いてより広範な組合せ最適化問題で評価を行いました。ALE-Agentに加え、様々な最先端AIの性能を、4時間にわたって回答を改良させ続ける設定で評価しました（下図）。標準的な手法を用いた各AIのパフォーマンスは人間の参加者の上位50%前後となりましたが、ALE-Agentでは上位6.8%にまで到達し、性能を大幅に引き上げられていることが分かります。実験の設定および結果の詳細は論文をご覧ください。
ALE-Benchにおける評価の結果。標準的な手法で解かせ続けたAIと比較して、ALE-Agentは高い性能を発揮した。
ALE-Agentの分析と得られた知見
ALE-Agentが回答を更新していくプロセスを見てみると、ドメイン知識を反映した探索アルゴリズムの高速化やハイパーパラメータの調整などを行っており、スコアを向上させる回答を出していることが分かりました。AHC047では、スコア計算を高速化のためにポアソン分布を用いて近似したり、焼きなまし法における近傍解の探索パターンを工夫していたりといった例が見られます。一方で、バグをなかなか修正しきれなかったり、計算量解析がうまくいかずに実行時間制限を何度も超過してしまったり、スコア向上への寄与が少ない部分の改善に固執したりするケースも見られました。
ポアソン近似によるスコア算出の高速化。AHC047で上位のスコアを取るために必須の戦略となっている。実際の回答はこちら（254行目から276行目）
焼きなまし法における近傍解の探索パターンの成長。初期回答（304行目から342行目）および最終回答（492行目から771行目）の部分を編集した概要を記載している。より多様な近傍解候補をより効率的に探索できるようにしたことで、スコアが増加した。
なぜ、ALE-AgentはAHC047で上位2％の性能を発揮できたのでしょうか。一つは、人間とAIの問題の解き方の違いがあります。たとえば4時間制のコンテストにおいて、人間のコンテスト参加者が回答を修正するのは多くて十数回である一方、現在のAIでは100回前後の修正が可能です。さらに私たちのAIエージェントでは、並列実行により数百から千を超える回答を作成しています。こうしたAIの高速かつ並列に回答を生成できるアドバンテージのために、人間の解答時間が数時間程度のコンテストでより高いパフォーマンスを発揮できることがわかりました。また現在のAIが得意にするのは「焼きなまし法」というAHCでしばしば使用されるアルゴリズムだということも判明しました（エージェントによるスコアの高い解答例：AHC039、本番5位相当）。
他方、ALE-Agentの課題も見えてきました。上述したように、ALE-Agentは4時間制の短いコンテストや焼きなまし法が有効な問題では高い性能を示したものの、2週間制の長いコンテストや焼きなまし法以外のアルゴリズムが効果を発揮する問題では苦戦しました。さらに、回答プログラムの挙動を確認しながら実験的な試行錯誤を元にアルゴリズムを構築することが苦手という傾向も見られました。
今後は、熟練した人間のテクニックやツールをより多く取り入れたり、詳細な実行結果の分析ができるようフィードバックを強化したりといった、確度の高い改善ができるようなエージェントを開発することが考えられます。加えて、エージェントに自分自身を改良させるアプローチを組み合わせるといった、エージェントそのものの技術を発展させていく方向性も考えられます。そうした工夫を通した、人間のトップレベル並み、さらには人間を越えるアルゴリズムエンジニアリングのスキル獲得が次の大きな挑戦となります。
AtCoder社はこの度、AIによるアルゴリズム開発の能力の現在地を知る目的で、ALE-Benchの構築にご協力頂き、またALE-Agentのコンテストへの参加を許可して下さいました。今回の実験結果を踏まえ、人間が今後も有意義にアルゴリズムやプログラミングのスキルを競い学び続けられる環境を維持するため、AtCoder社はSakana AIの協力の元で今後のコンテストにおけるAI利用の新ルールを策定しました。Sakana AIとしても、こうした取り組みは日進月歩するAIと人間が協働していくための重要なステップだと考えています。
おわりに
本研究では、組合せ最適化問題におけるAIのアルゴリズムエンジニアリング能力を測るベンチマーク「ALE-Bench」を構築すると同時に、分野特化型のAIエージェント「ALE-Agent」を開発し、ALE-Benchやリアルタイムのコンテストで良好な成績を得ました。今後、さらに性能が向上し、AIによる最適化問題のアルゴリズム発見の自動化が実現すれば、各産業を効率化させるパラダイムシフトとなります。Sakana AIは、本研究で得た知見をもとに、更なるアルゴリズムエンジニアリング能力を持ったAIの開発に挑戦していきます。
本研究はAtCoder株式会社との共同で行われました。組合せ最適化問題およびアルゴリズムにおいて卓越した知見と実績を持つ同社に、データの提供や分析、AIエージェントの実際のコンテストへの参加まで、様々な面でご助力いただきました。
本研究の詳細は論文をご覧ください。
Sakana AI
日本でのAIの未来を、Sakana AIと一緒に切り拓いてくださる方を募集しています。当社の募集要項をご覧ください。