MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design
本論文は、大規模言語モデルを活用して、品質多様性（Quality-Diversity）アーカイブ内で特化型ヒューリスティックと識別的な問題インスタンスを同時に進化させることで、スカラー値によるフィードバックや固定されたデータセットの限界を克服し、最先端の自動設計手法を凌駕する堅牢かつ相補的なヒューリスティック・ポートフォリオを生成する、グリッドベースの敵対的共進化フレームワークであるMOSAICを導入するものである。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
膨大な、そして混沌としたパズルを解こうとしている場面を想像してみてください。例えば、数百もの停留所がある配送トラックのルートを整理したり、最も価値のあるアイテムを詰め込めるようにスーツケースに荷物を詰め込んだりするような作業です。これらは「組合せ最適化問題」と呼ばれ、非常に困難なことで知られています。なぜなら、ピースを並べる方法の総数が膨大すぎて、最速のスーパーコンピュータであってもそのすべてをチェックすることはできないからです。何十年もの間、人間はこれらのパズルを素早く解くために、特別な「経験則」（ヒューリスティックと呼ばれます）を書こうと試みてきました。しかし、ここに落とし穴があります。格子状の街路を持つ都市で完璧に機能するルールが、曲がりくねった円形の道路を持つ都市では惨めに失敗してしまうことがあるのです。これが「ノーフリーランチ（無料の昼食はない）」という現実です。あらゆる状況に通用する単一のマジックルールなど存在しないのです。
最近、科学者たちは「大規模言語モデル（LLM）」――物語を書いたり質問に答えたりする、あの種のAI――を使用して、これらのルールを自動的に発明させる実験を始めました。しかし、ほとんどのAI実験は、たった一つの小さな教科書だけで学生を訓練しているようなものでした。そのAIはその特定の教科書にある問題を解くことには非常に長けてなりますが、少し異なるパズルを与えられると混乱してしまいます。それは、ある特定の農場の卵を使って完璧なオムレツを作る方法をシェフに教えるようなものです。もし別の農場の卵を与えられたら、オムレツは崩れてしまうかもしれません。従来のAIの訓練方法は、「よくできました」や「ダメでした」といった非常に単純なフィードバックに頼っており、「なぜ」あるいは「どこで」間違いが起きたのかを説明することはありませんでした。
そこで登場したのが、ジョージア工科大学の研究者たちによって開発された新しいフレームワーク「MOSAIC」です。MOSAICを、単一の教科書を暗記しようとする一人の学生としてではなく、異なる種類のパズルに合わせて訓練された様々な「専門家」のルールが集まる、巨大で生きた図書館として考えてみてください。AIに対して単に「より良いルールを作れ」と指示する代わりに、MOSAICは高度な「いたちごっこ」のゲームを設定します。AIが現在持っているルールを、一連の「敵対的」なパズル作成者チームと対決させるのです。これらのパズル作成者もまたAIであり、その唯一の任務は、現在のルールを打破するために特別に設計された、最も難解で混乱を招くパズルを作り出すことです。ルールが失敗したとき、システムは単に「負けました」と言うだけではありません。スマートな決定木を使用して、具体的にどのような種類のパズルがルールを壊したのかを特定し、そのパズルと学んだ教訓を巨大なグリッドの特定の「セル」に保存します。時間が経つにつれ、このグリッドは多様な専門家のコレクションで満たされていきます。格子状の街のためのルール、集落型の近隣地域のためのルール、そして長く曲がりくねったルートのためのルールといった具合です。システムはこれらの蓄積された教訓を使用して、さらに優れたルールへと進化させ、それぞれの専門領域において達人となるエキスパートのチームを作り上げます。
研究者たちは、このアイデアを3つの古典的な問題、すなわち「巡回セールスマン問題」（最短ルートを見つける）、「ナップサック問題」（最も価値のあるものを詰め込む）、「容量制限付き車両配送問題」（限られたトラックのスペースで荷物を配送する）でテストしました。その結果、MOSAICは他の最先端のAI手法を一貫して上回る性能を示しました。他の手法がパズルが少し変わると苦戦する一方で、MOSAICの「専門家チーム」はその変化を容易に処理し、しばしば完璧な答えに極めて近い解を見つけ出しました。例えば、巡回セールスマン問題において、MOSAICの最高のルールチームは、次に優れた手法よりも最大22%高い精度を叩き出しました。
さらに刺激的なことに、MOSAICが作り出した「敵対的」なパズルは、従来の手法が作るものよりもはるかに多様で挑戦的なものでした。このシステムは、従来のメソッドよりも33%多くの「特徴空間」（パズルの構造の異なる種類）をカバーしており、これは、より幅広い現実世界のシナリオに対処することを学習したことを意味しています。この研究は、問題を「共進化するバトル」として捉えること――つまり、弱点を露呈させるためにパズルがより難しくなり、それを修正するためにルールがより賢くなるというプロセス――によって、AIに単にいくつかの例を暗記させるのではなく、問題の全体像を真に理解させることができるということを示唆しています。それは、一つのことをすべて知っている単独の天才を育てることから、あらゆることを少しずつ知り、かつ自分の担当領域については深く知っている、多様な専門家のコミュニティを構築することへの転換なのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。