論文の概要: Pareto Frontier Approximation Network (PA-Net) to Solve Bi-objective TSP
- arxiv url: http://arxiv.org/abs/2203.01298v1
- Date: Wed, 2 Mar 2022 18:25:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 15:30:36.031657
- Title: Pareto Frontier Approximation Network (PA-Net) to Solve Bi-objective TSP
- Title（参考訳）: Pareto Frontier Approximation Network (PA-Net)による双方向TSPの解法
- Authors: Ishaan Mehta and Sajad Saeedi
- Abstract要約: トラベリングセールスパーソン問題(TSP)は、一連のタスクを行う最適な順序を見つけるために使用される古典的なリソース割り当て問題である。
本研究では,2つの目的に対して,強化学習を用いてTSPを解く。
- 参考スコア（独自算出の注目度）: 1.4884785898657995
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Travelling salesperson problem (TSP) is a classic resource allocation problem
used to find an optimal order of doing a set of tasks while minimizing (or
maximizing) an associated objective function. It is widely used in robotics for
applications such as planning, scheduling etc. In this work, we solve TSP for
two objectives using reinforcement learning. Often in multi objective
optimization problems, the associated objective functions can be conflicting in
nature. In such cases, the optimality is defined in terms of Pareto optimality.
A set of these Pareto Optimal solutions in the objective space form a Pareto
front (or frontier). Each solution has its own trade off. } In this work, we
present PA-Net, a network that generates good approximations of the Pareto
front for the bi-objective travelling salesperson problem (BTSP). Firstly, BTSP
is converted into a constrained optimization problem. We then train our network
to solve this constrained problem using the Lagrangian relaxation and policy
gradient. With PA-Net we are able to generate good quality Pareto fronts with
fast inference times. Finally, we present the application of PA-Net to find
optimal visiting order in a robotic navigation task/coverage planning.
- Abstract（参考訳）: トラベリングセールスパーソン問題(TSP)は、関連する目的関数を最小化(または最大化)しながらタスクセットを実行する最適な順序を見つけるために使用される古典的なリソース割り当て問題である。
ロボット工学において、計画、スケジューリングなどの用途に広く使われている。
本研究では,2つの目的に対して,強化学習を用いてTSPを解く。
しばしば多目的最適化問題において、関連する目的関数は本質的に矛盾することがある。
そのような場合、最適性はパレート最適性の観点から定義される。
対象空間におけるこれらのパレート最適解の組はパレート前線(あるいはフロンティア)を形成する。
各ソリューションには独自のトレードオフがある。
本稿では,btsp(bi-objective traveling salesperson problem)問題に対して,pareto frontの近似値を生成するネットワークpa-netを提案する。
まず、BTSPを制約付き最適化問題に変換する。
そして、ラグランジアン緩和と政策勾配を用いて、この制約のある問題を解決するためにネットワークを訓練します。
PA-Netでは、高速な推論時間で高品質なParetoフロントを生成することができます。
最後に,ロボットナビゲーションタスク/カバレッジ計画において,PA-Netを用いて最適な訪問順序を求める。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Preference-Optimized Pareto Set Learning for Blackbox Optimization [1.9628841617148691]
すべての目的を同時に最適化できる単一のソリューションはありません。
典型的なMOO問題では、目的間の好みを交換する最適解(パレート集合)を見つけることが目的である。
我々の定式化は、例えば微分可能なクロスエントロピー法によって解決できる二段階最適化問題につながる。
論文 参考訳（メタデータ） (2024-08-19T13:23:07Z) - Towards Efficient Pareto Set Approximation via Mixture of Experts Based Model Fusion [53.33473557562837]
大規模深層ニューラルネットワークに対する多目的最適化問題を解くことは、損失ランドスケープの複雑さと高価な計算コストのために難しい課題である。
本稿では,専門家(MoE)をベースとしたモデル融合を用いて,この問題を実用的でスケーラブルに解決する手法を提案する。
特殊な単一タスクモデルの重みをまとめることで、MoEモジュールは複数の目的間のトレードオフを効果的に捉えることができる。
論文 参考訳（メタデータ） (2024-06-14T07:16:18Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。
本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。
メタラーニング戦略を導入することで、大規模なTPPインスタンス上で安定してポリシーネットワークをトレーニングすることができる。
論文 参考訳（メタデータ） (2024-04-03T05:32:10Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Pareto Manifold Learning: Tackling multiple tasks via ensembles of
single-task models [50.33956216274694]
マルチタスク学習(MTL)では、タスクは、ソリューションへの最適化を導くのではなく、互いに達成したパフォーマンスを競い、制限することができる。
重み空間におけるアンサンブル手法であるTextitPareto Manifold Learningを提案する。
論文 参考訳（メタデータ） (2022-10-18T11:20:54Z) - Pareto Conditioned Networks [1.7188280334580197]
本稿では,すべての非支配的ポリシーを包含するために,単一ニューラルネットワークを用いる手法を提案する。
PCNは過去の移行とエピソードのリターンを関連付け、ネットワークをトレーニングする。
提案手法は教師付き方式で学習することで安定しており,移動目標問題を回避することができる。
論文 参考訳（メタデータ） (2022-04-11T12:09:51Z) - Pareto Navigation Gradient Descent: a First-Order Algorithm for
Optimization in Pareto Set [17.617944390196286]
マルチタスク学習のような現代の機械学習アプリケーションは、複数の目的関数をトレードオフするために最適なモデルパラメータを見つける必要がある。
勾配情報のみを用いてOPT-in-Paretoを近似的に解く1次アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-17T04:07:04Z) - Efficient Multi-Objective Optimization for Deep Learning [2.0305676256390934]
マルチオブジェクト最適化(MOO)はディープラーニングの一般的な課題です。
真に深いニューラルネットワークのためのスケーラブルなMOOソリューションはありません。
論文 参考訳（メタデータ） (2021-03-24T17:59:42Z) - A Hybrid 2-stage Neural Optimization for Pareto Front Extraction [3.918940900258555]
最適なトレードオフソリューションに対する大きな障害は、それらが必ずしも互いに収束しないことです。
正確かつ費用対効果の高い二段階アプローチを提案する。
論文 参考訳（メタデータ） (2021-01-27T20:56:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。