論文の概要: Learning to Control Local Search for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2206.13181v1
• Date: Mon, 27 Jun 2022 10:48:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-28 22:32:22.240238
• Title: Learning to Control Local Search for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための局所探索制御の学習
• Authors: Jonas K. Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thieme
• Abstract要約: 一般化の動物園と問題固有の局所探索の変種は、近似解を計算するのによく用いられる。 本稿では,そのような局所探索アルゴリズムの3つの独立したアルゴリズム的側面を同定し,最適化プロセス上でのシーケンシャルな選択を形式化する。 我々は、NeuroLSがオペレーティングリサーチの汎用ローカルサーチコントローラと最新の機械学習ベースのアプローチの両方より優れていることを示す。
• 参考スコア（独自算出の注目度）: 4.243592852049962
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems are encountered in many practical contexts such as logistics and production, but exact solutions are particularly difficult to find and usually NP-hard for considerable problem sizes. To compute approximate solutions, a zoo of generic as well as problem-specific variants of local search is commonly used. However, which variant to apply to which particular problem is difficult to decide even for experts. In this paper we identify three independent algorithmic aspects of such local search algorithms and formalize their sequential selection over an optimization process as Markov Decision Process (MDP). We design a deep graph neural network as policy model for this MDP, yielding a learned controller for local search called NeuroLS. Ample experimental evidence shows that NeuroLS is able to outperform both, well-known general purpose local search controllers from Operations Research as well as latest machine learning-based approaches.
• Abstract（参考訳）: 組合せ最適化問題はロジスティクスや生産といった多くの実践的な文脈で遭遇するが、厳密な解を見つけることは特に困難であり、問題のサイズではnp困難である。 近似解を計算するために、一般の動物園や局所探索の問題を特定できる変種が一般的に用いられる。 しかしながら、特定の問題に適用すべきバリエーションは、専門家であっても決定が難しい。 本稿では,これらの局所探索アルゴリズムの3つの独立したアルゴリズム的側面を同定し,マルコフ決定プロセス(MDP)として最適化プロセス上での逐次選択を形式化する。 我々は、このMDPのポリシーモデルとしてディープグラフニューラルネットワークを設計し、NeuroLSと呼ばれるローカルサーチのための学習コントローラを得る。 実験的な証拠は、NeuroLSがOperations Researchの一般的なローカルサーチコントローラと最新の機械学習ベースのアプローチの両方より優れていることを示している。

関連論文リスト

• Modeling Local Search Metaheuristics Using Markov Decision Processes [0.0]
  局所探索メタヒューリスティック解析のためのマルコフ決定過程(MDP)に基づく理論的枠組みを提案する。 このフレームワークは、個々のアルゴリズムに収束結果を提供するのに役立つだけでなく、探索-探索トレードオフの明示的な特徴も提供する。
  論文  参考訳（メタデータ） (2024-07-29T11:28:30Z)
• Moco: A Learnable Meta Optimizer for Combinatorial Optimization [5.359176539960004]
  Mocoは、現在の検索状態から抽出された特徴に基づいて、ソリューション構築手順を更新するグラフニューラルネットワークを学習する。 このメタトレーニング手順は、検索予算などの情報を得た探索手順中に見つかった全体的なベストソリューションをターゲットにしている。 Mocoは完全に学習可能なメタで、特定のローカル検索や分解の問題を一切利用しない。
  論文  参考訳（メタデータ） (2024-02-07T14:41:17Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。 そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。 MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
  論文  参考訳（メタデータ） (2023-04-29T07:22:07Z)
• RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization [11.269582666887324]
  本稿では,DQNフレームワークのRELS-DQNを紹介する。 1つのアプリケーションでトレーニングされたRELS-DQNモデルを使用することで、ローカル検索アルゴリズムと既存のDQNモデルの両方に等しい解値を提供することで、様々なアプリケーションに一般化することができる。
  論文  参考訳（メタデータ） (2023-04-11T18:01:49Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
  離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。 オンライン強化学習のための木に基づく階層分割手法の統一的理論的解析を行う。 我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明示的な境界を与える。
  論文  参考訳（メタデータ） (2021-10-29T15:06:15Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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