論文の概要: Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models

• arxiv url: http://arxiv.org/abs/2505.12627v1
• Date: Mon, 19 May 2025 02:20:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.35552
• Title: Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models
• Title（参考訳）: 大規模言語モデルを用いた組合せ最適化問題の解法のための効率的なヒューリスティックス生成
• Authors: Xuan Wu, Di Wang, Chunguo Wu, Lijie Wen, Chunyan Miao, Yubin Xiao, You Zhou,
• Abstract要約: 近年のLarge Language Models (LLMs) を用いた組合せ最適化問題の解法に関する研究 プロンプトにおけるタスク固有の知識の欠如は、LLMが不特定な探索方向を提供し、良好なパフォーマンスの導出を妨げることがしばしばある。 本稿では,Herculesアルゴリズムを提案する。このアルゴリズムは設計したコア抽象化プロンプティング(CAP)法を利用して,コアコンポーネントをエリートHGから抽象化し,プリミティブに事前知識として組み込む。
• 参考スコア（独自算出の注目度）: 52.538586230181814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent studies exploited Large Language Models (LLMs) to autonomously generate heuristics for solving Combinatorial Optimization Problems (COPs), by prompting LLMs to first provide search directions and then derive heuristics accordingly. However, the absence of task-specific knowledge in prompts often leads LLMs to provide unspecific search directions, obstructing the derivation of well-performing heuristics. Moreover, evaluating the derived heuristics remains resource-intensive, especially for those semantically equivalent ones, often requiring omissible resource expenditure. To enable LLMs to provide specific search directions, we propose the Hercules algorithm, which leverages our designed Core Abstraction Prompting (CAP) method to abstract the core components from elite heuristics and incorporate them as prior knowledge in prompts. We theoretically prove the effectiveness of CAP in reducing unspecificity and provide empirical results in this work. To reduce computing resources required for evaluating the derived heuristics, we propose few-shot Performance Prediction Prompting (PPP), a first-of-its-kind method for the Heuristic Generation (HG) task. PPP leverages LLMs to predict the fitness values of newly derived heuristics by analyzing their semantic similarity to previously evaluated ones. We further develop two tailored mechanisms for PPP to enhance predictive accuracy and determine unreliable predictions, respectively. The use of PPP makes Hercules more resource-efficient and we name this variant Hercules-P. Extensive experiments across four HG tasks, five COPs, and eight LLMs demonstrate that Hercules outperforms the state-of-the-art LLM-based HG algorithms, while Hercules-P excels at minimizing required computing resources. In addition, we illustrate the effectiveness of CAP, PPP, and the other proposed mechanisms by conducting relevant ablation studies.
• Abstract（参考訳）: 近年の研究では、LLMがまず探索方向を提供し、それに従ってヒューリスティックを導出するように促すことで、組合せ最適化問題(COP)を解決するためのヒューリスティックを自律的に生成するために、Large Language Models (LLMs)を活用している。 しかし、プロンプトにおけるタスク固有の知識の欠如は、LLMが不特定な探索方向を提供し、優れたヒューリスティックスの導出を妨げることがしばしばある。 さらに、派生したヒューリスティックスの評価は、特に意味論的に等価なものに対しては、リソースの消費を減らしがちである。 LLMが特定の探索方向を提供するために、設計したコア抽象プロンプティング(CAP)法を利用して、エリートヒューリスティックからコアコンポーネントを抽象化し、プロンプトに事前知識として組み込むHerculesアルゴリズムを提案する。 本研究は, CAPの非特異性低減効果を理論的に証明し, 実験結果を提供する。 得られたヒューリスティックスを評価するのに必要な計算資源を削減するために,ヒューリスティックジェネレーション(HG)タスクのファースト・オブ・イズ・イズ・ライクな手法であるPPP ( few-shot Performance Prediction Prompting) を提案する。 PPP は LLM を利用して、新たに導出したヒューリスティックスの適合値を予測し、その意味的類似性を以前に評価したものと分析する。 さらに,予測精度を向上し,信頼できない予測を決定するために,PPPに適した2つのメカニズムを開発した。 PPP を用いることで、Hercules はより資源効率が良くなり、この変種Hercules-P を命名する。 4つのHGタスク、5つのCOP、8つのLCMからなる大規模な実験により、Herculesは最先端のLLMベースのHGアルゴリズムよりも優れており、Hercules-Pは必要となる計算リソースを最小化することに優れていた。 さらに, CAP, PPP, および他のメカニズムの有効性について検討し, 関連するアブレーション研究を行った。

関連論文リスト

• R1-Searcher: Incentivizing the Search Capability in LLMs via Reinforcement Learning [87.30285670315334]
  textbfR1-Searcherは、大規模言語モデルの検索能力を高めるために設計された、2段階の結果に基づく新しいRLアプローチである。 本フレームワークは, コールドスタート時に, プロセス報酬や蒸留を必要とせず, RLのみに依存している。 提案手法は, クローズドソースGPT-4o-miniと比較して, 従来の強力なRAG法よりも有意に優れていた。
  論文  参考訳（メタデータ） (2025-03-07T17:14:44Z)
• Efficient Reinforcement Learning with Large Language Model Priors [18.72288751305885]
  大規模言語モデル(LLM)は、最近、強力な汎用ツールとして登場した。 本稿では,従来の行動分布としてLLMを扱い,それらをRLフレームワークに統合することを提案する。 LLMに基づくアクションの事前処理を取り入れることで、探索と複雑性の最適化が大幅に削減されることを示す。
  論文  参考訳（メタデータ） (2024-10-10T13:54:11Z)
• VinePPO: Unlocking RL Potential For LLM Reasoning Through Refined Credit Assignment [66.80143024475635]
  VinePPOは不偏のモンテカルロ推定を計算するための簡単な手法である。 我々は、VinePPOが、MATHおよびGSM8Kデータセット間でPPOや他のRLフリーベースラインを一貫して上回ることを示す。
  論文  参考訳（メタデータ） (2024-10-02T15:49:30Z)
• A Training Data Recipe to Accelerate A* Search with Language Models [3.037409201025504]
  A*のような検索アルゴリズムを備えた大規模言語モデル(LLM)は、拡張された推論とスケーラブルな推論の約束を持っている。 我々は,A*探索アルゴリズムの要件を LLM の要件から実験的に切り離して,この課題を一般化する。 提案手法は,解を見つけるのに要する反復回数を最大15倍に削減し,壁面通過速度を最大5倍に向上させる。
  論文  参考訳（メタデータ） (2024-07-13T19:21:44Z)
• Extracting Heuristics from Large Language Models for Reward Shaping in Reinforcement Learning [28.077228879886402]
  強化学習(Reinforcement Learning, RL)は、報酬領域におけるサンプルの非効率性に悩まされ、移行時にはさらにその問題が顕著になる。 サンプル効率を改善するために、報酬形成はRLエージェントが最適なポリシーに迅速に収束するのに役立つ本質的な報酬を導入するためのよく研究されたアプローチである。
  論文  参考訳（メタデータ） (2024-05-24T03:53:57Z)
• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  強化学習(Reinforcement Learning, RL)は、将来の行動方針をフィードバックで改善することにより、シーケンシャルな意思決定問題の事実上の標準的実践となった。 大規模言語モデル(LLM)の最近の発展は、言語理解と生成において印象的な能力を示したが、探索と自己改善能力に欠けていた。 我々はLINVITというアルゴリズムを開発し、LLMガイダンスを値ベースRLの正規化因子として組み込んで学習に必要なデータ量を大幅に削減する。
  論文  参考訳（メタデータ） (2024-02-25T20:07:13Z)
• LLM Performance Predictors are good initializers for Architecture Search [28.251129134057035]
  我々は、下流タスクにおける特定のディープニューラルネットワークアーキテクチャの性能を推定するパフォーマンス予測器(PP)を構築した。 機械翻訳 (MT) タスクでは, PPプロンプト (LLM-PP) を用いた GPT-4 は SoTA 平均絶対誤差と, ベースライン予測器と比較してランク相関係数がわずかに低下する。 ニューラルネットワーク探索 (NAS) では, LLM-Distill-PP を用いたハイブリッド探索アルゴリズム (HS-NAS) を導入する。
  論文  参考訳（メタデータ） (2023-10-25T15:34:30Z)
• Secrets of RLHF in Large Language Models Part I: PPO [81.01936993929127]
  大規模言語モデル (LLMs) は、人工知能の進歩のためのブループリントを定式化した。 人間のフィードバックによる強化学習(RLHF)がこの追求を支える重要な技術パラダイムとして出現する。 本稿では、RLHFの枠組みを解明し、PPOの内部構造を再評価し、PPOアルゴリズムを構成する部分が政策エージェントの訓練にどのように影響するかを考察する。
  論文  参考訳（メタデータ） (2023-07-11T01:55:24Z)

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

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