論文の概要: First Steps Towards a Runtime Analysis When Starting With a Good Solution

• arxiv url: http://arxiv.org/abs/2006.12161v2
• Date: Tue, 23 Jun 2020 10:31:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 05:31:16.305239
• Title: First Steps Towards a Runtime Analysis When Starting With a Good Solution
• Title（参考訳）: よいソリューションから始めるとき、ランタイム分析に向かう最初のステップ
• Authors: Denis Antipov, Maxim Buzdalov, Benjamin Doerr
• Abstract要約: 現実的な応用では、ランダムな解よりも優れた解を推測することができる。 我々は、異なるアルゴリズムがより良い初期解と全く異なる程度に利益を得ることを示す。 このことは、進化的アルゴリズムが良い初期解をうまく活用していることがまだ見つからないことを示唆している。
• 参考スコア（独自算出の注目度）: 8.34061303235504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of the algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the $(1+1)$ evolutionary algorithm and the static, self-adjusting, and heavy-tailed $(1 + (\lambda,\lambda))$ GA on the OneMax benchmark, but we are optimistic that the question how to profit from good initial solutions is interesting beyond these first examples.
• Abstract（参考訳）: 進化的アルゴリズムの数学的ランタイム解析は、伝統的にアルゴリズムがランダムな集団で初期化する際に特定の品質の解を見つける必要がある時間を扱う。 現実的な応用では、ランダムな解よりも優れた解を推測することができる。 このような状況に対する数学的ランタイム解析を始める。 我々は、異なるアルゴリズムがより良い初期化から全く異なる程度に利益をもたらすことを観察する。 また,アルゴリズムの最適パラメータ化は初期解の品質に強く依存することを示した。 この困難を克服するために、自己調整およびランダム化された重み付きパラメータ選択は利益を得ることができる。 最後に、最高の進化的アルゴリズムの性能と対応するブラックボックスの複雑さとの間の大きなギャップを観察する。 このことは、進化的アルゴリズムが優れた初期解をうまく活用できることを示唆している。 これらの最初の発見は、onemaxベンチマークで$(1+1)$進化アルゴリズムと静的で自己調整、そして重み付き$(1 + (\lambda,\lambda))$ gaのパフォーマンスを分析することに起因している。

関連論文リスト

• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Fast Re-Optimization of LeadingOnes with Frequent Changes [0.9281671380673306]
  Doerrらによって提案された再最適化アプローチは、問題インスタンスがより頻繁な変更の傾向にある場合に限界に達することを示す。 本稿では,前ベスト周辺における欲求探索と現在ベスト解を補間するアルゴリズムの修正を提案する。
  論文  参考訳（メタデータ） (2022-09-09T16:51:41Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。 同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
  論文  参考訳（メタデータ） (2021-04-14T07:59:53Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property [27.660240128423176]
  実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。 本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
  論文  参考訳（メタデータ） (2020-04-26T07:56:40Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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