論文の概要: Stalling in Space: Attractor Analysis for any Algorithm

• arxiv url: http://arxiv.org/abs/2412.15848v1
• Date: Fri, 20 Dec 2024 12:44:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 16:21:43.823630
• Title: Stalling in Space: Attractor Analysis for any Algorithm
• Title（参考訳）: 宇宙でのストール:任意のアルゴリズムのためのトラクター解析
• Authors: Sarah L. Thomson, Quentin Renau, Diederick Vermetten, Emma Hart, Niki van Stein, Anna V. Kononova,
• Abstract要約: 我々は、CMA-ES、微分進化、24のノイズレスブラックボックス最適化ベンチマーク問題に対するランダム検索のためのアトラクタネットワークを構築した。 我々は,他のモデルでは不可能なアルゴリズム動作の洞察を促進するために,局所探索を含まないアルゴリズムに対しても,アトラクタ解析の考慮を提唱する。
• 参考スコア（独自算出の注目度）: 0.14843690728081999
• License:
• Abstract: Network-based representations of fitness landscapes have grown in popularity in the past decade; this is probably because of growing interest in explainability for optimisation algorithms. Local optima networks (LONs) have been especially dominant in the literature and capture an approximation of local optima and their connectivity in the landscape. However, thus far, LONs have been constructed according to a strict definition of what a local optimum is: the result of local search. Many evolutionary approaches do not include this, however. Popular algorithms such as CMA-ES have therefore never been subject to LON analysis. Search trajectory networks (STNs) offer a possible alternative: nodes can be any search space location. However, STNs are not typically modelled in such a way that models temporal stalls: that is, a region in the search space where an algorithm fails to find a better solution over a defined period of time. In this work, we approach this by systematically analysing a special case of STN which we name attractor networks. These offer a coarse-grained view of algorithm behaviour with a singular focus on stall locations. We construct attractor networks for CMA-ES, differential evolution, and random search for 24 noiseless black-box optimisation benchmark problems. The properties of attractor networks are systematically explored. They are also visualised and compared to traditional LONs and STN models. We find that attractor networks facilitate insights into algorithm behaviour which other models cannot, and we advocate for the consideration of attractor analysis even for algorithms which do not include local search.
• Abstract（参考訳）: ネットワークベースのフィットネスランドスケープの表現は、過去10年間に人気が高まってきたが、これはおそらく最適化アルゴリズムの説明可能性への関心が高まったためだろう。 ローカルオプティマネットワーク(LON)は文学において特に支配的であり、ローカルオプティマの近似とランドスケープにおけるそれらの接続性を捉えている。 しかし、これまでのところ、LONは局所探索の結果である局所最適値の厳密な定義に従って構築されている。 しかし、多くの進化的アプローチは、これを含まない。 そのため、CMA-ESのような一般的なアルゴリズムはLON解析の対象にはなっていない。 サーチトラジェクトリーネットワーク(STN)は、任意の検索空間にノードを配置できるという選択肢を提供する。 しかし、STNは通常、時間的ストールをモデル化する方法ではモデル化されない:すなわち、アルゴリズムが一定期間にわたってより良い解を見つけられなかった検索空間の領域である。 そこで,本研究では,アトラクタネットワークと呼ばれるSTNの特殊なケースを体系的に解析することで,この問題に対処する。 これらはアルゴリズムの振る舞いを粗い粒度の粗いビューで表現し、屋台に特化して焦点をあてる。 我々は、CMA-ES、微分進化、24のノイズレスブラックボックス最適化ベンチマーク問題に対するランダム探索のためのアトラクタネットワークを構築した。 トラクタネットワークの特性を体系的に検討する。 また、従来のLONやSTNモデルと比較される。 我々は,他のモデルでは不可能なアルゴリズム動作の洞察を促進するために,局所探索を含まないアルゴリズムに対しても,アトラクタ解析の考慮を提唱する。

関連論文リスト

• Optimisation via encodings: a renormalisation group perspective [0.0]
  最適化問題の解法として被覆符号化マップをどのように利用できるかを示す。 カバーエンコーディングマップに係わる粗粒化は、再正規化グループスキームで遭遇した粗粒化と強く類似していることが示される。
  論文  参考訳（メタデータ） (2023-03-28T19:07:33Z)
• Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! [100.19080749267316]
  Sparsity May Cry"ベンチマーク(SMC-Bench)は、慎重に計算された4つのタスクと10のデータセットのコレクションである。 SMC-Benchは、よりスケーラブルで一般化可能なスパースアルゴリズムの開発を奨励するように設計されている。
  論文  参考訳（メタデータ） (2023-03-03T18:47:21Z)
• Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
  我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。 我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
  論文  参考訳（メタデータ） (2022-04-27T08:40:33Z)
• CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems [0.0]
  本稿では、マルコフ連鎖からSAに基づく奥行き制限木への探索空間の拡大による探索アルゴリズムを提案する。 それぞれのイテレーションにおいて、このアルゴリズムは、先を見据えて、木に沿って探索することで、実現可能な探索空間内で最高の準最適解を選択する」。 以上の結果から,IsingのNP最適化問題に対する高次木探索戦略は,より少ないエポックの範囲で解決可能であることが示唆された。
  論文  参考訳（メタデータ） (2022-03-09T10:07:26Z)
• Flipping the switch on local exploration: Genetic Algorithms with Reversals [0.0]
  著者らは、勾配のない探索手法が離散領域における最適解を提供するのに適していることを示した。 また、複数のローカル検索を使用することで、ローカル検索のパフォーマンスが向上することを示した。 提案したGA変種は,提案した問題を含む全てのベンチマークにおいて,最小平均コストであり,ICが構成成分よりも優れた性能を発揮することが観察された。
  論文  参考訳（メタデータ） (2022-02-02T08:27:11Z)
• Waypoint Planning Networks [66.72790309889432]
  本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。 我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
  論文  参考訳（メタデータ） (2021-05-01T18:02:01Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• 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)
• Multi-layer local optima networks for the analysis of advanced local search-based algorithms [0.6299766708197881]
  ローカルオプティマスネットワーク(Local Optima Network, LON)は、特定の近傍演算子と局所探索アルゴリズムに基づいて、特定の最適化問題のフィットネスランドスケープを圧縮するグラフモデルである。 本稿では、多層LONの概念と、フィットネスランドスケープ分析のためのメトリクス抽出を目的としたこれらのモデルを探索するための方法論を提案する。
  論文  参考訳（メタデータ） (2020-04-29T03:20:01Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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