論文の概要: Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs
- arxiv url: http://arxiv.org/abs/2608.06808v1
- Date: Fri, 07 Aug 2026 05:00:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-10 16:21:25.364437
- Title: Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs
- Title（参考訳）: LLMを用いた電位認識インスタンス生成による並列アルゴリズムポートフォリオの進化
- Abstract要約: 本稿では,確率対応インスタンスとアルゴリズム共進化フレームワークを紹介する。
生成したアルゴリズムを摂動させ、生成した問題インスタンス上でそれらの改善可能性を評価することにより、一般化ゲインを推定する。
PIACは最先端のLCM-ACPベースラインを一貫して上回っている。
- 参考スコア（独自算出の注目度）: 23.8937164783691
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Automatic Construction of Portfolios via Large Language Models (LLM-ACP) suffers from poor generalization in practical few-shot scenarios when solving complex combinatorial optimization problems. Instance and algorithm co-evolution frameworks address this by expanding the training dataset with generated hard instances on which the current algorithm portfolio underperforms, thereby enhancing generalization. However, this paradigm faces two critical limitations: evaluating instance hardness relies on high-quality reference solutions, and single-mode generation patterns limit instance diversity. To overcome these limitations, we introduce the Potential-aware Instance and Algorithm Co-evolution (PIAC) framework. Our core contribution is twofold. First, we propose potential gain, a novel metric that eliminates the need for reference solutions. This metric estimates generalization gain by perturbing the generated algorithms and assessing their improvement potential on generated problem instances. Second, PIAC leverages LLMs to synthesize diverse instance mutators, exploring a broader region of the problem-instance space and thereby enhancing the portfolio's generalization capabilities. Given that perturbation spaces vary across different algorithms, we instantiate our framework on Greedy Constructive, Ant Colony Optimization, and Guided Local Search algorithmic backbones. Comprehensive evaluations on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) across six distinct data distributions demonstrate that PIAC consistently outperforms state-of-the-art LLM-ACP baselines, notably achieving a 19.76% relative improvement for TSP Greedy Constructive portfolios.
- Abstract（参考訳）: 大規模言語モデル(LLM-ACP)によるポートフォリオの自動構築は、複雑な組合せ最適化問題の解決において、現実的な数ショットシナリオでの一般化に苦しむ。
インスタンスとアルゴリズムの共同進化フレームワークは、トレーニングデータセットを、現在のアルゴリズムポートフォリオがパフォーマンスの悪い生成されたハードインスタンスで拡張することで、この問題に対処する。
しかし、このパラダイムは2つの重要な制限に直面している。インスタンスの硬さの評価は高品質な参照ソリューションに依存し、単一モード生成パターンはインスタンスの多様性を制限する。
これらの制限を克服するために、我々は、潜在的に認識されるインスタンスとアルゴリズムの共進化(PIAC)フレームワークを紹介します。
私たちのコアコントリビューションは2倍です。
まず、参照解の必要性を排除した新しい計量であるポテンシャルゲインを提案する。
この計量は、生成したアルゴリズムを摂動させ、生成した問題インスタンス上でそれらの改善ポテンシャルを評価することで一般化ゲインを推定する。
第2に、PIACはLLMを活用し、多様なインスタンスミュータを合成し、問題インスタンス空間の広い領域を探索し、ポートフォリオの一般化能力を向上する。
摂動空間はアルゴリズムによって異なるので、Greedy Constructive、Ant Colony Optimization、Guid Local Searchアルゴリズムのバックボーンに関するフレームワークをインスタンス化する。
トラベリングセールスマン問題(TSP)とCVRP(Capacitated Vehicle Routing Problem)に関する総合的な評価は、PIACが最先端のLCM-ACPベースラインを一貫して上回り、TSPグレディ・コンストラクティブ・ポートフォリオの19.76%の相対的な改善を実現していることを示している。
関連論文リスト
- Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search [27.981714638078966]
信頼性の高いアルゴリズムポートフォリオを構築するための特徴のない構造認識機構を備えたLESフレームワークであるDynamic Instance Clustering and Specialized Algorithm Design (DyCA)を提案する。
DyCAは、インスタンスクラスタリングを検索プロセス内で共進化するコンポーネントとして扱い、評価データを特徴のない信号として再利用する。
実験の結果、DyCAは最先端のLESベースラインを上回り、尾の堅牢性は平均15.2%、全体的な性能は7.1%向上した。
論文 参考訳（メタデータ） (2026-08-04T04:59:48Z) - FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization [61.43300970020897]
大規模言語モデル(LLM)は、最適化モデリングとソルバコード生成にますます使われている。
既存のベンチマークは、実際のスケールと複雑さよりもはるかに低い、小さな、あるいは単純化された例に限られている。
現実的な大規模最適化問題に対して,LLMに基づく効率的なアルゴリズム設計を評価するための最初のベンチマークとしてFrontierORを紹介した。
論文 参考訳（メタデータ） (2026-05-24T20:10:42Z) - Multi-Agent DRL for V2X Resource Allocation: Disentangling Challenges and Benchmarking Solutions [51.22818149833102]
マルチエージェント強化学習(MARL)は、車間通信(C-V2X)ネットワークにおける無線リソース割り当ての有望なアプローチとして登場した。
しかし、MARLに固有の多面的課題はしばしば絡み合っており、車載環境における個々の影響を理解することは困難である。
我々は, C-V2X RRA を, 複雑さが徐々に増大する多エージェント干渉ゲーム列として定式化し, このギャップを埋める。
論文 参考訳（メタデータ） (2026-02-18T14:46:56Z) - LLM Agents for Combinatorial Efficient Frontiers: Investment Portfolio Optimization [0.0]
本研究では,カーディナリティ制約付き平均分散ポートフォリオ最適化問題に対する新しいエージェント・フレームワークを実装した。
ベンチマーク問題では、実装されたエージェントフレームワークは最先端のアルゴリズムと一致する。
複雑なアルゴリズム開発は軽減され、最悪の場合、低いが許容できるエラーが報告される。
論文 参考訳（メタデータ） (2026-01-02T18:02:13Z) - Learning Branching Policies for MILPs with Proximal Policy Optimization [0.0]
混合線形プログラム(MILP)における分岐境界法(B&B)
現在のアプローチはImitation Learning (IL)に依存しており、専門家によるデモンストレーションに過度に適合する傾向にあり、構造的に多様なインスタンスや目に見えないインスタンスに一般化するのに苦労している。
本研究では,RLアルゴリズムであるPPO(Proximal Policy Optimization)を用いて分岐ポリシーの学習を行う新しいフレームワークであるTree-Gate Proximal Policy Optimizationを提案する。
論文 参考訳（メタデータ） (2025-11-17T05:16:14Z) - LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm [0.9214658764451348]
本稿では,Large Language Models (LLMs) と Biased Random-Key Genetic Algorithm (BRKGA) を統合し,NP-hard Longest Run Subsequence 問題の解法を提案する。
我々のアプローチは、計算効率のよいメトリクスセットを共同設計し実装するための人間-LLM協調プロセスを導入することで、インスタンス駆動バイアスパラダイムを拡張します。
その結果, BRKGA+Llama-4-Maverickはベースラインよりも大幅に改良された。
論文 参考訳（メタデータ） (2025-09-05T21:46:41Z) - LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.35609820607923]
大規模言語モデル(LLM)は、アルゴリズム設計を支援する新しい機会を提供する。
LLM4CMOは,2つの人口構成をもつ2段階のフレームワークをベースとした新しいCMOEAである。
LLMは複雑な進化最適化アルゴリズムの開発において効率的な共同設計者として機能する。
論文 参考訳（メタデータ） (2025-08-16T02:00:57Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。
このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - Evolving Generalizable Parallel Algorithm Portfolios via Domain-Agnostic Instance Generation [27.138566940625385]
一般化は、データからトレーニングする際の中核的な目的である。
並列アルゴリズムポートフォリオ(PAP)とインスタンス人口を同時に進化させることによって、共進化的アプローチはこの課題に対処する。
本研究は,パラメタライズドサーチ(DACE)のドメインに依存しない共進化という,汎用的で既成のPAP構築手法を提案する。
論文 参考訳（メタデータ） (2025-01-06T10:29:48Z) - Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。
我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。
車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
論文 参考訳（メタデータ） (2024-07-24T12:00:30Z) - PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
我々は、強化学習におけるポリシーアライメントの最近強調された重要な問題に対処するために、新しい統合された二段階最適化ベースのフレームワーク、textsfPARLを提案する。
本フレームワークは, 上向きの目標(逆設計)の分布を, 下向きの最適変数で明示的にパラメータ化することにより, これらの問題に対処する。
その結果,提案したtextsfPARL が RL のアライメントの懸念に対処できる可能性が示唆された。
論文 参考訳（メタデータ） (2023-08-03T18:03:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。