論文の概要: On Solving Close Enough Orienteering Problem with Overlapped Neighborhoods

• arxiv url: http://arxiv.org/abs/2310.04257v2
• Date: Tue, 12 Mar 2024 17:16:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-14 01:33:47.908543
• Title: On Solving Close Enough Orienteering Problem with Overlapped Neighborhoods
• Title（参考訳）: 重なり合う近傍での十分に近いオリエンテーリング問題の解法について
• Authors: Qiuchen Qian, Yanran Wang, David Boyle
• Abstract要約: Close Enough Traveling Salesman Problem (CETSP) は、Close Enough Orienteering Problem (CEOP) のよく知られた変種である。 シュタイナーゾーン(Steiner Zones, SZ)と呼ばれる重なり合う地区に基づくヒューリスティックスは、CETSPに対処する上で注目されている。 ここでは、重複する地区に賞品を集約することで、このような制限が、親密な配向問題(CEOP)の利点にどのように変換できるかを示す。
• 参考スコア（独自算出の注目度）: 3.360922672565235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Close Enough Traveling Salesman Problem (CETSP) is a well-known variant of TSP whereby the agent may complete its mission at any point within a target neighborhood. Heuristics based on overlapped neighborhoods, known as Steiner Zones (SZ), have gained attention in addressing CETSP. While SZs offer effective approximations to the original graph, their inherent overlap imposes constraints on search space, potentially conflicting with global optimization objectives. Here we show how such limitations can be converted into advantages in a Close Enough Orienteering Problem (CEOP) by aggregating prizes across overlapped neighborhoods. We further extend classic CEOP with Non-uniform Neighborhoods (CEOP-N) by introducing non-uniform costs for prize collection. To tackle CEOP and CEOP-N, we develop a new approach featuring a Randomized Steiner Zone Discretization (RSZD) scheme coupled with a hybrid algorithm based on Particle Swarm Optimization (PSO) and Ant Colony System (ACS), CRaSZe-AntS. The RSZD scheme identifies sub-regions for PSO exploration, and ACS determines the discrete visiting sequence. We evaluate the RSZD's discretization performance on CEOP instances derived from established CETSP instances and compare CRaSZe-AntS against the most relevant state-of-the-art heuristic focused on single-neighborhood optimization for CEOP instances. We also compare the performance of the interior search within SZs and the boundary search on individual neighborhoods in the context of CEOP-N. Our experimental results show that CRaSZe-AntS can yield comparable solution quality with significantly reduced computation time compared to the single neighborhood strategy, where we observe an average 140.44% increase in prize collection and a 55.18% reduction in algorithm execution time. CRaSZe-AntS is thus highly effective in solving emerging CEOP-N, examples of which include truck-and-drone delivery scenarios.
• Abstract（参考訳）: CETSP(Close Enough Traveling Salesman Problem)は、TSPのよく知られた変種であり、エージェントはターゲット地区内の任意の地点でミッションを完了することができる。 シュタイナーゾーン(Steiner Zones, SZ)と呼ばれる重なり合う地区に基づくヒューリスティックスは、CETSPに対処する上で注目されている。 szsは元のグラフに効果的な近似を提供するが、それらの固有の重複は探索空間に制約を課し、潜在的にグローバル最適化の目的と矛盾する。 ここでは,これらの制限を,重複する近傍の賞品を集約することで,十分に近いオリエンテーリング問題(ceop)の利点に転換できることを示す。 古典的CEOPを非一様隣人 (CEOP-N) に拡張し, 賞品収集に非一様コストを導入する。 CEOP と CEOP-N に対処するため, 粒子群最適化 (PSO) と Ant Colony System (ACS), CRaSZe-AntS に基づくハイブリッドアルゴリズムを併用したランダム化されたスタイナーゾーン離散化 (RSZD) 方式の新たなアプローチを開発した。 RSZDスキームはPSO探索のサブリージョンを特定し、ACSは個別の訪問シーケンスを決定する。 CETSP インスタンスから派生した CEOP インスタンス上での RSZD の離散化性能を評価し,CRaSZe-AntS と CRaSZe-AntS を比較した。 また,SZの内部探索と各地区の境界探索の性能を,CEOP-Nの文脈で比較した。 実験結果から,crasze-antsは1つの近傍戦略に比べて計算時間を大幅に削減し,平均140.44%の賞金獲得率と55.18%のアルゴリズム実行時間を短縮できることがわかった。 CRaSZe-AntSは、トラックとドローンの配送シナリオを含む、新たなCEOP-Nの解決に非常に効果的である。

関連論文リスト

• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Parameter optimization comparison in QAOA using Stochastic Hill Climbing with Random Re-starts and Local Search with entangled and non-entangled mixing operators [0.0]
  本研究では,Hill Climbing with Random Restarts (SHC-RR) の有効性を検討した。 以上の結果から,SHC-RRはLSアプローチよりも優れており,より単純な最適化機構にもかかわらず優れた有効性を示した。
  論文  参考訳（メタデータ） (2024-05-14T20:12:17Z)
• Personalized Federated X -armed Bandit [44.7483638955294]
  我々は、フェデレートされた$mathcalX$-armed bandit問題について検討し、フェデレート学習パラダイムにおいて、クライアントの異種局所目的を同時に最適化する。 本手法では,非最適領域を安全に除去すると同時に,非最適領域の偏りはあるが効果的な局所目的評価を通じて協調を奨励する。
  論文  参考訳（メタデータ） (2023-10-25T03:11:32Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。 我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。 本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T15:29:32Z)
• High-Similarity-Pass Attention for Single Image Super-Resolution [81.56822938033118]
  非局所的注意(NLA)分野における最近の進歩は、自己相似性に基づく単一画像超解像(SISR)への新たな関心につながっている。 高相似性パスアテンション(HSPA)を得るための簡潔で効果的なソフトしきい値設定操作を導入する。 HSPAの有効性を実証するため,我々はHSPAN(Deep High-Similarity-pass attention network)を構築した。
  論文  参考訳（メタデータ） (2023-05-25T06:24:14Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。 関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。 我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
  論文  参考訳（メタデータ） (2021-10-19T07:26:33Z)
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks [59.419152768018506]
  最適ポリシーは必ずk-SP制約を満たすことを示す。 本研究では,SP制約に違反するポリシーを完全に排除する代わりに,新たなコスト関数を提案する。 また,MiniGrid,DeepMind Lab,Atari,Fetchを用いた実験の結果,提案手法はPPOを著しく改善することが示された。
  論文  参考訳（メタデータ） (2021-07-13T21:39:21Z)
• An Improved Approach for Estimating Social POI Boundaries With Textual Attributes on Social Media [3.590202054885437]
  ソーシャルメディア上のテキスト属性を利用して、密度ベースのクラスタリングを実行する方法が不十分に検討されている。 我々は、社会POI境界推定(SoBEst)に関する初期の研究に基づいて、新しいアプローチとアルゴリズムを提案する。 SoBEstが基本的に想定している各POIの固定された代表座標は、特定のPOIに対して推定された社会的POI境界の遠心点から遠く離れている可能性がある。
  論文  参考訳（メタデータ） (2020-12-18T00:41:44Z)
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
  安全強化学習(SRL)問題では、エージェントは期待される全報酬を最大化し、一定の制約の違反を避けるために環境を探索する。 これは、大域的最適ポリシーを持つSRLアルゴリズムの最初の分析である。
  論文  参考訳（メタデータ） (2020-11-11T16:05:14Z)

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

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