論文の概要: On Parallel External-Memory Bidirectional Search

• arxiv url: http://arxiv.org/abs/2412.21104v1
• Date: Mon, 30 Dec 2024 17:29:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:01:04.821607
• Title: On Parallel External-Memory Bidirectional Search
• Title（参考訳）: 並列外部メモリ双方向探索について
• Authors: ior Siag, Shahaf S. Shperberg, Ariel Felner, Nathan R. Sturtevant,
• Abstract要約: 本稿では,一方向および双方向のベストファースト検索アルゴリズムを統合するフレームワークを提案する。 我々は最先端双方向探索(BiHS)アルゴリズムBAE*(PEM-BAE*)のPEM版を開発する。 PEM-BAE* は A* の PEM 変種と MM アルゴリズム,および IDA* の並列変種より優れていることを示す。
• 参考スコア（独自算出の注目度）: 16.87919636127611
• License:
• Abstract: Parallelization and External Memory (PEM) techniques have significantly enhanced the capabilities of search algorithms when solving large-scale problems. Previous research on PEM has primarily centered on unidirectional algorithms, with only one publication on bidirectional PEM that focuses on the meet-in-the-middle (MM) algorithm. Building upon this foundation, this paper presents a framework that integrates both uni- and bi-directional best-first search algorithms into this framework. We then develop a PEM variant of the state-of-the-art bidirectional heuristic search (\BiHS) algorithm BAE* (PEM-BAE*). As previous work on \BiHS did not focus on scaling problem sizes, this work enables us to evaluate bidirectional algorithms on hard problems. Empirical evaluation shows that PEM-BAE* outperforms the PEM variants of A* and the MM algorithm, as well as a parallel variant of IDA*. These findings mark a significant milestone, revealing that bidirectional search algorithms clearly outperform unidirectional search algorithms across several domains, even when equipped with state-of-the-art heuristics.
• Abstract（参考訳）: 並列化と外部メモリ(PEM)技術は,大規模問題の解法における探索アルゴリズムの能力を大幅に向上させた。 PEMのこれまでの研究は主に一方向のアルゴリズムに焦点をあてており、メット・イン・ザ・ミドル(MM)アルゴリズムに焦点をあてた双方向のPEMに関する出版物は1つだけである。 本稿では,この基盤を基盤として,一方向および双方向のベストファースト検索アルゴリズムをこのフレームワークに統合するフレームワークを提案する。 次に、最先端の双方向ヒューリスティックサーチ(\BiHS)アルゴリズムBAE*(PEM-BAE*)のPEM版を開発する。 これまでの \BiHS では,問題サイズのスケーリングに重点を置いていなかったため,この問題に対する双方向アルゴリズムの評価が可能となった。 PEM-BAE* は A* の PEM 変種と MM アルゴリズム,および IDA* の並列変種より優れていることを示す。 これらの発見は重要なマイルストーンであり、最先端のヒューリスティック技術を装備した場合でも、双方向検索アルゴリズムが複数のドメインで一方向検索アルゴリズムよりも明らかに優れていることが判明した。

関連論文リスト

• A Gold Standard Dataset for the Reviewer Assignment Problem [117.59690218507565]
  類似度スコア(Similarity score)とは、論文のレビューにおいて、レビュアーの専門知識を数値で見積もるものである。 私たちのデータセットは、58人の研究者による477の自己申告された専門知識スコアで構成されています。 2つの論文をレビュアーに関連付けるタスクは、簡単なケースでは12%～30%、ハードケースでは36%～43%である。
  論文  参考訳（メタデータ） (2023-03-23T16:15:03Z)
• Empirical Evaluation of Project Scheduling Algorithms for Maximization of the Net Present Value [0.0]
  本稿では,3つのプロジェクトスケジューリングアルゴリズムの実証的性能解析について述べる。 選択されたアルゴリズムは、Recursive Search (RS)、Steepest Ascent Approach (SAA)、Hybrid Search (HS)である。
  論文  参考訳（メタデータ） (2022-07-05T03:01:33Z)
• A survey on multi-objective hyperparameter optimization algorithms for Machine Learning [62.997667081978825]
  本稿では,多目的HPOアルゴリズムに関する2014年から2020年にかけての文献を体系的に調査する。 メタヒューリスティック・ベース・アルゴリズムとメタモデル・ベース・アルゴリズム,および両者を混合したアプローチを区別する。 また,多目的HPO法と今後の研究方向性を比較するための品質指標についても論じる。
  論文  参考訳（メタデータ） (2021-11-23T10:22:30Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。 既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。 本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
  論文  参考訳（メタデータ） (2021-10-13T19:36:50Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Critical Analysis: Bat Algorithm based Investigation and Application on Several Domains [1.1802674324027231]
  このアルゴリズムのアイデアはコウモリのエコーロケーション能力から取られた。 バットアルゴリズムは、背景、特徴、制限の観点から詳細に与えられる。
  論文  参考訳（メタデータ） (2021-01-18T19:25:12Z)
• On Population-Based Algorithms for Distributed Constraint Optimization Problems [12.21350091202884]
  我々は、人口ベースのアルゴリズムとして広く呼ばれる、新しい不完全アルゴリズムのクラスについて研究する。 最初のアプローチであるAnytime Evolutionary DCOP(AED)は、進化最適化メタヒューリスティックを利用してDCOPを解く。 第2のコントリビューションでは、人口ベースのアプローチと局所的な検索アプローチを組み合わせることができることを示す。
  論文  参考訳（メタデータ） (2020-09-02T06:39:30Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  二次代入問題 (QAP) はNPハード問題に属する最適化問題である。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
  論文  参考訳（メタデータ） (2020-07-29T15:02:07Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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