論文の概要: Bi-objective Search with Bi-directional A*
- arxiv url: http://arxiv.org/abs/2105.11888v1
- Date: Tue, 25 May 2021 12:46:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-26 13:56:44.980317
- Title: Bi-objective Search with Bi-directional A*
- Title(参考訳): 双方向A*を用いた双方向探索
- Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby
- Abstract要約: Bi-objective A*-based search (BOA*) は大規模ネットワークにおいて最先端の性能を示す。
本稿では, BOA* の双方向変種を開発し, 高速化を行った。
1000のベンチマークケースに対する実験結果から,BBI(bi-jective search)のための双方向A*アルゴリズムが,ベンチマークケースの全てをタイムリミットで最適に解くことができることがわかった。
- 参考スコア(独自算出の注目度): 8.140473195463905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bi-objective search is a well-known algorithmic problem, concerned with
finding a set of optimal solutions in a two-dimensional domain. This problem
has a wide variety of applications such as planning in transport systems or
optimal control in energy systems. Recently, bi-objective A*-based search
(BOA*) has shown state-of-the-art performance in large networks. This paper
develops a bi-directional variant of BOA*, enriched with several speed-up
heuristics. Our experimental results on 1,000 benchmark cases show that our
bi-directional A* algorithm for bi-objective search (BOBA*) can optimally solve
all of the benchmark cases within the time limit, outperforming the state of
the art BOA*, bi-objective Dijkstra and bi-directional bi-objective Dijkstra by
an average runtime improvement of a factor of five over all of the benchmark
instances.
- Abstract(参考訳): 双目的探索は、2次元領域における最適解の集合を見つけることに関わるよく知られたアルゴリズム問題である。
この問題には、輸送システムの計画やエネルギーシステムの最適制御など、幅広い応用がある。
近年,二目的A*検索 (BOA*) は大規模ネットワークにおいて最先端の性能を示している。
本稿では,数種類のスピードアップヒューリスティックスに富んだBOA*の双方向変種を開発する。
実験結果から,二目的探索(boba*)のための双方向a*アルゴリズムは,全ベンチマークインスタンスに対して平均5倍の改善により,boa*,bi-objective dijkstraおよびbi-directional bi-objective dijkstraの状態を上回って,すべてのベンチマークケースをタイムリミット内で最適に解くことができることが示された。
関連論文リスト
- Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。
本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
論文 参考訳(メタデータ) (2024-01-19T07:40:24Z) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳(メタデータ) (2022-09-27T17:51:31Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。
バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文 参考訳(メタデータ) (2022-02-18T02:54:58Z) - B2EA: An Evolutionary Algorithm Assisted by Two Bayesian Optimization
Modules for Neural Architecture Search [3.126118485851773]
Btextsuperscript2EAは2つのBO代理モデルと2つの変異ステップを持つ補助的EAである。
Btextsuperscript2EAは、目標パフォーマンスの3つの困難レベルに対して、14ベンチマークよりも堅牢で効率的である。
論文 参考訳(メタデータ) (2022-02-07T08:50:21Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳(メタデータ) (2021-12-06T20:34:55Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳(メタデータ) (2021-10-18T14:00:22Z) - ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。
既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。
本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
論文 参考訳(メタデータ) (2021-10-13T19:36:50Z) - A binary variant of gravitational search algorithm and its application
to windfarm layout optimization problem [0.7734726150561088]
本稿では, 2次探索空間 (BNAGGSA) のための GSA 内に, 重力定数を埋め込んだ新しい近傍アーカイブ (A novel neighborhood Archives embedded gravity constants) を提案する。
提案アルゴリズムは、エージェントが最適なステップサイズで最適な方向に移動する自己適応的なステップサイズ機構を生成する。
実世界の応用における提案アルゴリズムの適用性を確認するために,風向配置最適化の問題を検討する。
論文 参考訳(メタデータ) (2021-07-25T16:56:19Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z) - Multi-objective beetle antennae search algorithm [4.847470451539327]
提案する多目的ビートルアンテナ探索アルゴリズムは,4つのよく選択されたベンチマーク関数を用いて検証する。
その結果,提案した多目的ビートルアンテナ探索アルゴリズムは計算効率が良く,精度も良好であることが示唆された。
論文 参考訳(メタデータ) (2020-02-24T06:34:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。