論文の概要: Run Time Analysis for Random Local Search on Generalized Majority Functions

• arxiv url: http://arxiv.org/abs/2204.12770v3
• Date: Mon, 26 Sep 2022 07:43:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-15 09:26:08.972749
• Title: Run Time Analysis for Random Local Search on Generalized Majority Functions
• Title（参考訳）: 一般化多数関数のランダム局所探索のための実行時間解析
• Authors: Carola Doerr and Martin S. Krejca
• Abstract要約: 我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。 我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
• 参考スコア（独自算出の注目度）: 1.0965065178451106
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Run time analysis of evolutionary algorithms recently makes significant progress in linking algorithm performance to algorithm parameters. However, settings that study the impact of problem parameters are rare. The recently proposed W-model provides a good framework for such analyses, generating pseudo-Boolean optimization problems with tunable properties. We initiate theoretical research of the W-model by studying how one of its properties -- neutrality -- influences the run time of random local search. Neutrality creates plateaus in the search space by first performing a majority vote for subsets of the solution candidate and then evaluating the smaller-dimensional string via a low-level fitness function. We prove upper bounds for the expected run time of random local search on this MAJORITY problem for its entire parameter spectrum. To this end, we provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY, where a sufficient majority is needed to optimize the subset. We also introduce a generalized version of classic drift theorems as well as a generalized version of Wald's equation, both of which we believe to be of independent interest.
• Abstract（参考訳）: 進化的アルゴリズムの実行時間解析はアルゴリズム性能をアルゴリズムパラメータにリンクする上で大きな進歩を遂げている。 しかし、問題パラメータの影響を研究する設定は稀である。 最近提案されたW-モデルはそのような分析のための優れたフレームワークを提供し、チューナブルな特性を持つ擬似ブール最適化問題を生成する。 我々は、w-モデルの理論的研究を開始し、その特性である中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。 中立性は、まずソリューション候補のサブセットに対して過半数の投票を行い、次に低レベルフィットネス関数を介してより小さな次元の文字列を評価することによって、検索空間の高原を生み出す。 我々は、この多数問題に対するランダム局所探索の期待実行時間の上限をパラメータスペクトル全体に対して証明する。 この目的のために、多くの最適化アルゴリズムに適用可能な定理を提供し、実行時間とその対称バージョンhas majorityをリンクし、サブセットを最適化するのに十分な過半数が必要となる。 また、古典的ドリフト定理の一般化版や、ウォルド方程式の一般化版も導入し、どちらも独立な関心を持つと考えている。

関連論文リスト

• Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
  本稿ではHastingsが最初に提案したショートパスフレームワークに基づいてアルゴリズムの一般化を分析する。 一般的に満たされているいくつかの技術的条件の下では、適切な一般化は超4次スピードアップを達成することができる。 本論文は,短経路アルゴリズムのパラメータ選択を導く数値解析で締めくくった。
  論文  参考訳（メタデータ） (2024-10-30T17:52:56Z)
• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  一般化されたOneMax関数の最初のランタイム解析を提供する。 r-cGAはこのr値のOneMax問題を効率的に解くことを示す。 実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
  論文  参考訳（メタデータ） (2024-04-17T10:40:12Z)
• DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
  PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。 我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
  論文  参考訳（メタデータ） (2023-01-28T17:03:56Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Fast Perturbative Algorithm Configurators [0.0]
  ParamRLS と ParamILS のパラメータ問題を最適化するために,期待時間に線形な下界を証明した。 本研究では, 摂動アルゴリズムのための高調波突然変異演算子を, 対数時間, 対数時間, ほぼ対数時間で提案する。 実験的な分析により、いくつかの構成シナリオにおいて、実際にアプローチの優位性を確認することができる。
  論文  参考訳（メタデータ） (2020-07-07T10:48:32Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Parameterized Complexity Analysis of Randomized Search Heuristics [16.759797540118665]
  この章では、ランダム化アルゴリズムのパラメータ化実行時間解析の理論を適用した多数の結果をまとめた。 NP-hard最適化問題の解法を課題とするランダム化検索の集合に対する主な結果と証明手法について概説する。
  論文  参考訳（メタデータ） (2020-01-15T03:43:56Z)

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

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