Fugu-MT 論文翻訳(概要): Efficient Active Search for Combinatorial Optimization Problems

論文の概要: Efficient Active Search for Combinatorial Optimization Problems

arxiv url: http://arxiv.org/abs/2106.05126v1
Date: Wed, 9 Jun 2021 15:08:03 GMT
ステータス: 処理完了
システム内更新日: 2021-06-10 15:18:37.253258
Title: Efficient Active Search for Combinatorial Optimization Problems
Title（参考訳）: 組合せ最適化問題の効率的な能動探索
Authors: Andr\'e Hottung, Yeong-Dae Kwon, Kevin Tierney
Abstract要約: 能動探索により、学習したモデルが、トレーニング中に見られたものよりもはるかに大きいインスタンスを効果的に解決できることが示される。提案手法は、与えられたモデルの探索性能を大幅に向上する簡単な方法を提供し、ルーティング問題に対する最先端の機械学習手法より優れている。
参考スコア（独自算出の注目度）: 1.6543719822033436
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Recently numerous machine learning based methods for combinatorial optimization problems have been proposed that learn to construct solutions in a sequential decision process via reinforcement learning. While these methods can be easily combined with search strategies like sampling and beam search, it is not straightforward to integrate them into a high-level search procedure offering strong search guidance. Bello et al. (2016) propose active search, which adjusts the weights of a (trained) model with respect to a single instance at test time using reinforcement learning. While active search is simple to implement, it is not competitive with state-of-the-art methods because adjusting all model weights for each test instance is very time and memory intensive. Instead of updating all model weights, we propose and evaluate three efficient active search strategies that only update a subset of parameters during the search. The proposed methods offer a simple way to significantly improve the search performance of a given model and outperform state-of-the-art machine learning based methods on combinatorial problems, even surpassing the well-known heuristic solver LKH3 on the capacitated vehicle routing problem. Finally, we show that (efficient) active search enables learned models to effectively solve instances that are much larger than those seen during training.
Abstract（参考訳）: 近年,強化学習による逐次決定過程における解構築を学習する組合せ最適化問題に対する機械学習手法が数多く提案されている。これらの方法は、サンプリングやビーム検索のような検索戦略と簡単に組み合わせることができるが、強力な検索ガイダンスを提供するハイレベルな検索手順に統合するのは簡単ではない。 Belloなど。 (2016) では, 強化学習を用いて, 単インスタンスに対して(訓練された)モデルの重みを調整する能動探索を提案する。アクティブ検索は実装は簡単だが、各テストインスタンスのモデル重みの調整は非常に時間とメモリ集約的であるため、最先端のメソッドと競合しない。モデル重みを更新する代わりに、探索中にパラメータのサブセットだけを更新する3つの効率的なアクティブ検索戦略を提案し、評価する。提案手法は, 与えられたモデルの探索性能を著しく向上し, コンビネート問題に基づく機械学習手法よりも優れており, 容量付き車両経路問題において, 有名なヒューリスティックソルバ lkh3 を上回っている。最後に、(効率的な)アクティブ検索により、学習したモデルが、トレーニング中に見たものよりもずっと大きいインスタンスを効果的に解決できることを示す。

関連論文リスト

Guided Stream of Search: Learning to Better Search with Language Models via Optimal Path Guidance [17.28280896937486]
言語モデルの探索と計画能力を高めるために最適な解をいかに活用するかを示す。提案手法は,単純な数学的推論タスクであるCountdownにおける言語モデルの探索と計画能力を大幅に向上させる。
論文参考訳（メタデータ） (2024-10-03T21:07:59Z)
PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
木探索に基づく推論経路生成手法であるPathFinderを提案する。動的デコードの統合により、多様な分岐とマルチホップ推論を強化する。我々のモデルは、大きな分岐因子を持つビームサーチに類似した複雑さを反映して、よく、長く、目に見えない推論連鎖を一般化する。
論文参考訳（メタデータ） (2023-12-08T17:05:47Z)
Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文参考訳（メタデータ） (2022-10-31T09:46:26Z)
Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文参考訳（メタデータ） (2022-09-27T17:51:31Z)
CorpusBrain: Pre-train a Generative Retrieval Model for Knowledge-Intensive Language Tasks [62.22920673080208]
単一ステップ生成モデルは、検索プロセスを劇的に単純化し、エンドツーエンドで最適化することができる。我々は、事前学習された生成検索モデルをCorpsBrainと名付け、コーパスに関する全ての情報が、追加のインデックスを構築することなく、そのパラメータにエンコードされる。
論文参考訳（メタデータ） (2022-08-16T10:22:49Z)
Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。我々のモデルは様々な経路問題に一般化可能であることを示す。
論文参考訳（メタデータ） (2022-05-31T09:51:48Z)
Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文参考訳（メタデータ） (2021-10-08T07:22:45Z)
Fast Line Search for Multi-Task Learning [0.0]
マルチタスク学習における行探索アルゴリズムの新しいアイデアを提案する。この考え方は、ステップサイズを見つけるためにパラメータ空間の代わりに潜在表現空間を使用することである。本稿では,MNIST,CIFAR-10,Cityscapesタスクの学習速度を一定とする古典的バックトラック法と勾配法を比較した。
論文参考訳（メタデータ） (2021-10-02T21:02:29Z)
A Novel Surrogate-assisted Evolutionary Algorithm Applied to Partition-based Ensemble Learning [0.0]
高価な最適化問題を解決するための新しいサロゲート支援アルゴリズムを提案する。我々は,適応値推定に用いるサロゲートモデルと,進化的遺伝子-進化的最適混合アルゴリズムの最先端p3様変種を統合する。提案したアルゴリズムをアンサンブル学習問題で検証する。
論文参考訳（メタデータ） (2021-04-16T11:51:18Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters [10.279748604797911]
機械学習とデータサイエンスの主な問題は、最適化問題として日常的にモデル化され、最適化アルゴリズムによって解決される。データ量の増加と、これらの不条件最適化タスクを定式化するために使用される統計モデルのサイズと複雑さにより、これらの課題に対処できる新しい効率的なアルゴリズムが必要である。この論文では,これらの課題をそれぞれ異なる方法で処理する。ビッグデータ問題に効率的に対処するために,各イテレーションでトレーニングデータの小さなランダムサブセットのみを検査する新しい手法を開発する。大きなモデル問題に対処するために、イテレーション毎に更新されるメソッドを開発します。
論文参考訳（メタデータ） (2020-08-26T21:15:18Z)

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

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