TIDE：LLMを用いた自動ヒューリスティック設計のための調整統合型動的進化フレームワーク

TL;DR（結論）

TIDEは、大規模言語モデル（LLM）を用いた自動ヒューリスティック設計（AHD）において、離散的なアルゴリズム構造と連続的な数値パラメータの最適化を分離して扱う「調整統合型動的進化フレームワーク」である。 外部ループでは抽象構文木に基づく構造的類似性指標（TSED）を用いた島モデルにより、表面的なコードの差異に惑わされない真の多様性を維持し、内部ループではUCBアルゴリズムによる戦略選択と差分進化による精密なパラメータ調整を統合している。 9つの組合せ最適化問題を用いた実験では、既存の最先端手法を解の質と探索効率の両面で大幅に上回り、LLMの数値的精度の低さを補いながら優れたアルゴリズム骨格を発見できることが実証された。

なぜこの問題か

ヒューリスティックアルゴリズムの設計は、物流、スケジューリング、資源配分など、様々な領域におけるNP困難な組合せ最適化問題（COP）を解決するために極めて重要である。従来、このプロセスは人間の専門家の直感と経験に依存しており、多大な労力と時間を要する作業であった。近年、大規模言語モデル（LLM）の進歩により、アルゴリズム生成をコード空間における探索問題として捉える「言語ハイパーヒューリスティック（LHH）」という新たなパラダイムが登場した。これにより、人間が設計したベースラインを超えるアルゴリズムを自動的に生成することが可能になりつつある。しかし、既存の自動ヒューリスティック設計（AHD）手法には、解決すべき重大な課題がいくつか存在している。 第一の課題は、アルゴリズムの進化を単一のテキスト生成タスクとして過度に簡略化して扱っている点である。ヒューリスティックアルゴリズムの本質は、離散的な論理構造（シンボリックな論理フロー）と、連続的な数値パラメータの組み合わせにある。LLMは記号的な推論には優れているものの、数値的な精度が低い「数値的盲目性」という問題を抱えている。…

核心：何を提案したのか

本研究では、アルゴリズムの構造的推論とパラメータ最適化を分離し、動的な進化を実現する「TIDE（Tuning-Integrated Dynamic Evolution）」フレームワークを提案している。TIDEの最大の特徴は、外部ループと内部ループからなる入れ子状のアーキテクチャを採用している点にある。この設計により、LLMが得意とする「論理の構築」と、LLMが苦手とする「数値の微調整」をそれぞれの専門モジュールに分担させ、相乗効果を生み出すことに成功している。 外部ループでは、抽象構文木（AST）レベルでの構造的類似性を定量化する「TSED（Tree Similarity Edit Distance）」に基づいた島モデルを導入している。このモデルは、複数の独立した「島（サブポピュレーション）」を管理し、島同士の構造的な距離に応じて適応的な移動やリセットを行う。…

続きはログイン/プランで閲覧できます。