論文の概要: A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives
- arxiv url: http://arxiv.org/abs/2505.22244v1
- Date: Wed, 28 May 2025 11:26:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-29 17:35:50.57151
- Title: A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives
- Title（参考訳）: 相関対象存在下での効率的な近似的二目的最短パス計算のための前処理フレームワーク
- Authors: Yaron Halle, Ariel Felner, Sven Koenig, Oren Salzman,
- Abstract要約: 本研究は,両目的性短絡(BOSP)問題と相関する目的が存在することを考察する。
BOSPは、探索空間のサイズが目的関数の数とグラフサイズで指数関数的であるため、一般に計算的に困難である。
相関対象が存在する場合の探索労力を削減できる効率的なアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 21.108406629056173
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The bi-objective shortest-path (BOSP) problem seeks to find paths between start and target vertices of a graph while optimizing two conflicting objective functions. We consider the BOSP problem in the presence of correlated objectives. Such correlations often occur in real-world settings such as road networks, where optimizing two positively correlated objectives, such as travel time and fuel consumption, is common. BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size. Bounded sub-optimal BOSP solvers such as A*pex alleviate this complexity by approximating the Pareto-optimal solution set rather than computing it exactly (given a user-provided approximation factor). As the correlation between objective functions increases, smaller approximation factors are sufficient for collapsing the entire Pareto-optimal set into a single solution. We leverage this insight to propose an efficient algorithm that reduces the search effort in the presence of correlated objectives. Our approach for computing approximations of the entire Pareto-optimal set is inspired by graph-clustering algorithms. It uses a preprocessing phase to identify correlated clusters within a graph and to generate a new graph representation. This allows a natural generalization of A*pex to run up to five times faster on DIMACS dataset instances, a standard benchmark in the field. To the best of our knowledge, this is the first algorithm proposed that efficiently and effectively exploits correlations in the context of bi-objective search while providing theoretical guarantees on solution quality.
- Abstract（参考訳）: 単目的短経路(BOSP)問題は、2つの矛盾する目的関数を最適化しながら、グラフの開始点と目標頂点の間の経路を見つけようとするものである。
BOSP問題と相関する目的が存在することを考察する。
このような相関は、旅行時間や燃料消費といった2つの正に相関した目的を最適化することが一般的である道路網などの現実的な環境において発生することが多い。
BOSPは、探索空間のサイズが目的関数の数とグラフサイズで指数関数的であるため、一般に計算的に困難である。
A*pexのような境界付き準最適BOSPソルバは、正確に計算するのではなく、Pareto-Optimalソリューションセットを近似することで、この複雑さを緩和する(ユーザが提供する近似係数を付与する)。
目的関数間の相関が増加するにつれて、より小さな近似因子はパレート最適集合全体を1つの解に折り畳むのに十分である。
我々はこの知見を利用して、相関対象の存在下での探索の労力を削減できる効率的なアルゴリズムを提案する。
パレート最適集合全体の近似計算に対する我々のアプローチは、グラフクラスタリングアルゴリズムに着想を得たものである。
グラフ内の相関クラスタを識別し、新しいグラフ表現を生成するために、前処理フェーズを使用する。
これにより、フィールドの標準ベンチマークであるDIMACSデータセットインスタンス上で、A*pexの自然な一般化が最大5倍高速になる。
我々の知る限り、このアルゴリズムは二目的探索の文脈における相関を効率的に効果的に活用し、解の質に関する理論的保証を提供する最初のアルゴリズムである。
関連論文リスト
- A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。
これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
論文 参考訳（メタデータ） (2024-12-05T10:38:29Z) - BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
本稿では,非支配解と結合累積分布関数の極端量子化との自然な関係を示す。
このリンクにより、我々はPareto対応CDFインジケータと関連する取得関数BOtiedを提案する。
種々の合成および実世界の問題に対する実験により,BOtied は最先端MOBO 取得関数より優れていることが示された。
論文 参考訳（メタデータ） (2023-06-01T04:50:06Z) - End-to-End Pareto Set Prediction with Graph Neural Networks for
Multi-objective Facility Location [10.130342722193204]
施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。
本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。
ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
論文 参考訳（メタデータ） (2022-10-27T07:15:55Z) - Arch-Graph: Acyclic Architecture Relation Predictor for
Task-Transferable Neural Architecture Search [96.31315520244605]
Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。
Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。
わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
論文 参考訳（メタデータ） (2022-04-12T16:46:06Z) - Effective and efficient structure learning with pruning and model
averaging strategies [9.023722579074734]
本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。
アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。
そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
論文 参考訳（メタデータ） (2021-12-01T10:35:34Z) - The Minimax Complexity of Distributed Optimization [0.0]
分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。
私は「間欠的コミュニケーション設定」の具体例に焦点をあてる
コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
論文 参考訳（メタデータ） (2021-09-01T15:18:33Z) - Many Objective Bayesian Optimization [0.0]
マルチオブジェクトベイズ最適化(MOBO)は、ブラックボックスの同時最適化に成功している一連の手法である。
特に、MOBO法は、多目的最適化問題における目的の数が3以上である場合に問題があり、これは多くの目的設定である。
GPが測定値とアルゴリズムの有効性の予測分布を予測できるような,玩具,合成,ベンチマーク,実実験のセットで実証的な証拠を示す。
論文 参考訳（メタデータ） (2021-07-08T21:57:07Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Balanced Order Batching with Task-Oriented Graph Clustering [28.05598654297136]
本稿では,BTOGCN(Ba balanced Task- Clustering Network)というエンドツーエンドの学習・最適化フレームワークを提案する。
BOBPは、中国最大のロジスティクスプラットフォームであるCainiaoの買収プロセスに端を発する。
論文 参考訳（メタデータ） (2020-08-19T08:42:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。