論文の概要: A Reinforcement Learning Approach to the Orienteering Problem with Time
Windows
- arxiv url: http://arxiv.org/abs/2011.03647v2
- Date: Tue, 29 Jun 2021 18:37:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 22:42:39.517734
- Title: A Reinforcement Learning Approach to the Orienteering Problem with Time
Windows
- Title（参考訳）: 時間窓によるオリエンテーリング問題に対する強化学習アプローチ
- Authors: Ricardo Gama and Hugo L. Fernandes
- Abstract要約: Orienteering Problem with Time Windows (OPTW) は、異なる訪問場所から収集した総得点を最大化する最適化問題である。
本研究では,強化学習を用いて学習したポインタネットワークモデルを用いて,OPTW問題の解法を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Orienteering Problem with Time Windows (OPTW) is a combinatorial
optimization problem where the goal is to maximize the total score collected
from different visited locations. The application of neural network models to
combinatorial optimization has recently shown promising results in dealing with
similar problems, like the Travelling Salesman Problem. A neural network allows
learning solutions using reinforcement learning or supervised learning,
depending on the available data. After the learning stage, it can be
generalized and quickly fine-tuned to further improve performance and
personalization. The advantages are evident since, for real-world applications,
solution quality, personalization, and execution times are all important
factors that should be taken into account.
This study explores the use of Pointer Network models trained using
reinforcement learning to solve the OPTW problem. We propose a modified
architecture that leverages Pointer Networks to better address problems related
with dynamic time-dependent constraints. Among its various applications, the
OPTW can be used to model the Tourist Trip Design Problem (TTDP). We train the
Pointer Network with the TTDP problem in mind, by sampling variables that can
change across tourists visiting a particular instance-region: starting
position, starting time, available time, and the scores given to each point of
interest. Once a model-region is trained, it can infer a solution for a
particular tourist using beam search. We based the assessment of our approach
on several existing benchmark OPTW instances. We show that it generalizes
across different tourists that visit each region and that it generally
outperforms the most commonly used heuristic, while computing the solution in
realistic times.
- Abstract（参考訳）: Orienteering Problem with Time Windows (OPTW)は、異なる訪問場所から収集した総得点を最大化することを目的とする組合せ最適化問題である。
ニューラルネットワークモデルの組合せ最適化への応用は、最近、トラベルセールスマン問題のような同様の問題に対処する上で有望な結果を示している。
ニューラルネットワークは、利用可能なデータに応じて強化学習や教師付き学習を用いた学習ソリューションを可能にする。
学習段階の後、パフォーマンスとパーソナライゼーションをさらに向上させるために、一般化し、迅速に微調整することができる。
実世界のアプリケーションでは、ソリューションの品質、パーソナライゼーション、実行時間が考慮すべき重要な要素であることから、メリットは明らかです。
本研究では,強化学習を用いて学習したポインタネットワークモデルを用いて OPTW 問題を解く。
本稿では,動的時間依存制約に係わる問題に対して,ポインタネットワークを活用するアーキテクチャを提案する。
様々な応用の中で、OPTWはツーリストトリップデザイン問題(TTDP)をモデル化することができる。
我々は,ttdp問題を念頭に置いてポインタネットワークを訓練し,特定のインスタンス地域を訪れる観光客間で変化する変数をサンプリングし,開始位置,開始時間,利用可能な時間,各ポイントに与えられるスコアを学習する。
モデルリージョンがトレーニングされると、ビームサーチを使って特定の観光客のソリューションを推測する。
我々は,既存のベンチマークオプティマイザを用いたアプローチの評価を行った。
各地域を訪れる異なる観光客にまたがって一般化し、最も一般的に使用されるヒューリスティックを上回っており、現実的な時間にソリューションを計算している。
関連論文リスト
- Federated Gradient Matching Pursuit [17.695717854068715]
従来の機械学習技術では、1つのサーバまたはデータハブ上のすべてのトレーニングデータを集中化する必要がある。
特に、FL(Federated Learning)は、ローカルクライアントでトレーニングデータを保持しながら、共有モデルを学習するためのソリューションを提供する。
本稿では,FL設定における分散制約最小化問題を解くために,新しいアルゴリズムフレームワークFedGradMPを提案する。
論文 参考訳（メタデータ） (2023-02-20T16:26:29Z) - Revisit the Algorithm Selection Problem for TSP with Spatial Information
Enhanced Graph Neural Networks [4.084365114504618]
本稿では,ユークリッド旅行セールスマン問題(TSP)のアルゴリズム選択問題を再検討する。
我々はGINESと呼ばれる新しいグラフニューラルネットワーク(GNN)を提案する。
GINESは都市の座標と都市間の距離を入力として取ります。
これは、1つのデータセットにおける従来の手作りの機能ベースのアプローチよりも優れている。
論文 参考訳（メタデータ） (2023-02-08T13:14:20Z) - 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) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
我々は、必要に応じて適切な選択を行う決定論的アルゴリズムを支援する模倣学習フレームワークについて検討する。
我々は、模倣学習フレームワークの下で訓練されたグラフニューラルネットワークの強力な一般化能力を示す。
論文 参考訳（メタデータ） (2022-10-12T03:56:37Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - On the Difficulty of Generalizing Reinforcement Learning Framework for
Combinatorial Optimization [6.935838847004389]
現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。
このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。
我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
論文 参考訳（メタデータ） (2021-08-08T19:12:04Z) - Generalization Guarantees for Neural Architecture Search with
Train-Validation Split [48.265305046655996]
本稿では,列車検証分割の統計的側面について検討する。
リスクや高度勾配などの検証損失の洗練された特性は、真のテスト損失の指標であることを示す。
また、NAS、マルチカーネル学習、低ランク行列学習の厳密な接続も強調する。
論文 参考訳（メタデータ） (2021-04-29T06:11:00Z) - Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。
私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
論文 参考訳（メタデータ） (2021-04-19T14:35:14Z) - Exploiting Shared Representations for Personalized Federated Learning [54.65133770989836]
本稿では,クライアント間の共有データ表現と,クライアント毎のユニークなローカルヘッダを学習するための,新しいフェデレーション学習フレームワークとアルゴリズムを提案する。
提案アルゴリズムは, クライアント間の分散計算能力を利用して, 表現の更新毎に低次元の局所パラメータに対して, 多数の局所更新を行う。
この結果は、データ分布間の共有低次元表現を学習することを目的とした、幅広い種類の問題に対するフェデレーション学習以上の関心を持っている。
論文 参考訳（メタデータ） (2021-02-14T05:36:25Z) - A Flexible Framework for Designing Trainable Priors with Adaptive
Smoothing and Game Encoding [57.1077544780653]
我々は、前方通過を非滑らかな凸最適化問題として解釈できるニューラルネットワーク層の設計とトレーニングのための一般的なフレームワークを紹介する。
グラフのノードに代表されるローカルエージェントによって解決され、正規化関数を介して相互作用する凸ゲームに焦点を当てる。
このアプローチは、訓練可能なエンドツーエンドのディープモデル内で、古典的な画像の事前使用を可能にするため、画像の問題を解決するために魅力的である。
論文 参考訳（メタデータ） (2020-06-26T08:34:54Z) - Connecting the Dots: Multivariate Time Series Forecasting with Graph
Neural Networks [91.65637773358347]
多変量時系列データに特化して設計された汎用グラフニューラルネットワークフレームワークを提案する。
グラフ学習モジュールを用いて,変数間の一方向関係を自動的に抽出する。
提案手法は,4つのベンチマークデータセットのうち3つにおいて,最先端のベースライン手法よりも優れている。
論文 参考訳（メタデータ） (2020-05-24T04:02:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。