論文の概要: Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems

• arxiv url: http://arxiv.org/abs/2210.00672v1
• Date: Mon, 3 Oct 2022 01:25:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 15:17:12.830253
• Title: Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
• Title（参考訳）: 進化はまだ良い:一般被覆問題における進化アルゴリズムの理論解析
• Authors: Yaoyao Zhang, Chaojie Zhu, Shaojie Tang, Ringli Ran, Ding-Zhu Du, Zhao Zhang
• Abstract要約: いくつかの近似機構は本質的に多くの進化的アルゴリズムに埋め込まれているようである。 我々は、一般化された単純多目的進化アルゴリズムのための統合分析フレームワークを提案することにより、そのような関係を同定する。
• 参考スコア（独自算出の注目度）: 16.98107289469868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.
• Abstract（参考訳）: 進化アルゴリズムに関する理論的研究は近年活発に進展している。 このようなアルゴリズムの多くは、実行時間と近似比の両方において理論的保証を持っている。 いくつかの近似機構は本質的に多くの進化アルゴリズムに埋め込まれているようである。 本稿では,一般化された多目的進化アルゴリズム(gsemo)のための統一解析フレームワークを提案し,その関係を最小重み一般被覆問題に適用する。 幅広い問題(部分モジュラー関数が実数値であるような最小部分モジュラー被覆問題やポテンシャル関数が非劣モジュラーである最小連結支配集合問題を含む)に対して、gsemoは期待される多項式時間で漸近的に密接な近似比を与える。

関連論文リスト

• A Generalized Evolutionary Metaheuristic (GEM) Algorithm for Engineering Optimization [1.6589012298747952]
  近年の大きなトレンドは、自然に着想を得たメタヒュースティックアルゴリズム(NIMA)の利用である。 文献には540以上のアルゴリズムがあり、異なるアルゴリズムの探索機構を理解するための統一的なフレームワークはない。 20以上の異なるアルゴリズムを統一する一般化された進化的メタヒューリスティックアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-02T09:55:15Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。 本研究は,D-SGDAの一般化における各因子の影響を解析した。 また、最適凸凹設定を得るために一般化とバランスをとる。
  論文  参考訳（メタデータ） (2023-10-31T11:27:01Z)
• Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function [1.3053649021965603]
  共進化的アルゴリズムには、ハードウェア設計、ボードゲーム戦略の進化、ソフトウェアバグのパッチなど、幅広い応用がある。 共進化的アルゴリズムが解を効率的にかつ確実に見つけることを予測できる理論を開発することは、オープンな挑戦である。 本稿では,人口ベース競争共進化型アルゴリズムのランタイム解析開発における第一歩について述べる。
  論文  参考訳（メタデータ） (2022-06-30T12:35:36Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。 このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
  論文  参考訳（メタデータ） (2022-01-07T13:33:28Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Evolving Evolutionary Algorithms with Patterns [0.0]
  このモデルは、MEP(Multi Expression Programming)技術に基づいている。 関数最適化のためのいくつかの進化的アルゴリズムは、考慮されたモデルを用いて進化する。
  論文  参考訳（メタデータ） (2021-10-10T16:26:20Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms [16.691265882753346]
  GSEMOと呼ばれる単純な進化的アルゴリズムは、部分モジュラ函数の近似を効率的に行うことが示されている。 我々は理論結果を拡張し、濃度制約を一般化するマトロイド制約を分割する。
  論文  参考訳（メタデータ） (2020-06-23T05:37:29Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  本稿では、進化的遺伝的アルゴリズムを特徴付けるとともに、最小ラベル付けスタイナーツリー(MLST)問題を解く際の性能を評価する。 我々は、進化的アルゴリズムを、時間とともに超最適で実現不可能な解の集団を進化させることによって実現可能な解に到達する過程として定義する。 我々は, 交叉, 突然変異, 適合性などの古典的進化的概念が, 最適解, 最適解に到達するためにどのように適応できるかを示す。
  論文  参考訳（メタデータ） (2020-04-18T13:27:28Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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