論文の概要: RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models

• arxiv url: http://arxiv.org/abs/2505.20242v1
• Date: Mon, 26 May 2025 17:21:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 19:27:27.041886
• Title: RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models
• Title（参考訳）: RedAHD:大規模言語モデルを用いたエンド・ツー・エンド自動ヒューリスティック設計
• Authors: Nguyen Thach, Aida Riahifar, Nathan Huynh, Hau Chan,
• Abstract要約: 我々は,これらのLCMに基づく設計手法を人間を必要とせずに動作させることができる,RedAHDという新しいエンドツーエンドフレームワークを提案する。 より具体的には、RedAHD は LLM を用いて還元プロセスの自動化、すなわち手元のCOPをよりよく理解された類似のCOPに変換する。 6つのCOPで評価した実験結果から,RedAHDは人間の関与を最小限に抑えた最先端の手法よりも設計や改善が可能であることが示された。
• 参考スコア（独自算出の注目度）: 14.544461392180668
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving NP-hard combinatorial optimization problems (COPs) (e.g., traveling salesman problems (TSPs) and capacitated vehicle routing problems (CVRPs)) in practice traditionally involves handcrafting heuristics or specifying a search space for finding effective heuristics. The main challenges from these approaches, however, are the sheer amount of domain knowledge and implementation efforts required from human experts. Recently, significant progress has been made to address these challenges, particularly by using large language models (LLMs) to design heuristics within some predetermined generalized algorithmic framework (GAF, e.g., ant colony optimization and guided local search) for building key functions/components (e.g., a priori information on how promising it is to include each edge in a solution for TSP and CVRP). Although existing methods leveraging this idea have shown to yield impressive optimization performance, they are not fully end-to-end and still require considerable manual interventions. In this paper, we propose a novel end-to-end framework, named RedAHD, that enables these LLM-based heuristic design methods to operate without the need of GAFs. More specifically, RedAHD employs LLMs to automate the process of reduction, i.e., transforming the COP at hand into similar COPs that are better-understood, from which LLM-based heuristic design methods can design effective heuristics for directly solving the transformed COPs and, in turn, indirectly solving the original COP. Our experimental results, evaluated on six COPs, show that RedAHD is capable of designing heuristics with competitive or improved results over the state-of-the-art methods with minimal human involvement.
• Abstract（参考訳）: NP-hard combinatorial optimization problem (COPs) (例:旅行セールスマン問題 (TSPs) とキャパシタ付き車両ルーティング問題 (CVRPs) ) の解決は、伝統的にヒューリスティックを手作りしたり、効果的なヒューリスティックを見つけるための探索空間を指定したりする。 しかし、これらのアプローチの主な課題は、多くのドメイン知識と人間の専門家が必要とする実装の取り組みです。 近年、これらの課題に対処するために、特に、特定の一般化アルゴリズムフレームワーク(GAF, eg, ant colony optimization and guided local search)内でヒューリスティックを設計するために、大きな言語モデル(LLM)を使用して鍵関数/コンポーネント(例えば、TSPとCVRPのソリューションに各エッジをどの程度含めるかの事前情報)を構築することで、大きな進歩を遂げている。 このアイデアを利用する既存の手法では、優れた最適化性能が得られることが示されているが、完全なエンドツーエンドではなく、手作業による介入がかなり必要である。 本稿では,これらのLCMに基づくヒューリスティック設計手法をGAFを必要とせずに動作させる,RedAHDという新しいエンドツーエンドフレームワークを提案する。 より具体的には、RedAHD は LLM を用いて減算プロセスの自動化、すなわち、手元のCOPをよりよく理解された類似のCOPに変換し、LLM ベースのヒューリスティック設計手法は変換されたCOPを直接解決し、また、元のCOPを間接的に解決する効果的なヒューリスティックを設計することができる。 6つのCOPで評価した実験結果から,RedAHDは人間の関与を最小限に抑えた最先端の手法よりも,競争力のあるヒューリスティックを設計できることが示された。

関連論文リスト

• REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems [3.067143391336441]
  離散変数と有限探索空間を持つ組合せ最適化問題(COP)は、多くの分野において重要な問題である。 リソース中心モデリングおよび問題解決フレームワーク(REMS)を初めて紹介する。 REMSはこれらのCOPを統一パラダイム内でモデル化し、設計したメタヒューリスティックアルゴリズムで効果的に解決することができる。
  論文  参考訳（メタデータ） (2025-05-21T11:21:58Z)
• Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models [52.538586230181814]
  近年のLarge Language Models (LLMs) を用いた組合せ最適化問題の解法に関する研究 プロンプトにおけるタスク固有の知識の欠如は、LLMが不特定な探索方向を提供し、良好なパフォーマンスの導出を妨げることがしばしばある。 本稿では,Herculesアルゴリズムを提案する。このアルゴリズムは設計したコア抽象化プロンプティング(CAP)法を利用して,コアコンポーネントをエリートHGから抽象化し,プリミティブに事前知識として組み込む。
  論文  参考訳（メタデータ） (2025-05-19T02:20:46Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Deep Insights into Automated Optimization with Large Language Models and Evolutionary Algorithms [3.833708891059351]
  大きな言語モデル(LLM)と進化的アルゴリズム(EA)は、制限を克服し、最適化をより自動化するための有望な新しいアプローチを提供する。 LLMは最適化戦略の生成、洗練、解釈が可能な動的エージェントとして機能する。 EAは進化作用素を通して、複雑な解空間を効率的に探索する。
  論文  参考訳（メタデータ） (2024-10-28T09:04:49Z)
• Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization [7.85458999849461]
  我々は,拡散モデルをゼロから直接訓練する,教師なしCOフレームワークであるIC/DCを提案する。 私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。 並列マシンスケジューリング問題(PMSP)と非対称トラベリングセールスマン問題(ATSP)における既存のNCO手法と比較して、IC/DCは最先端の性能を達成する
  論文  参考訳（メタデータ） (2024-10-15T06:53:30Z)
• Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment [58.049113055986375]
  我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。 提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。 本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-06-11T01:20:53Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。