論文の概要: Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem

• arxiv url: http://arxiv.org/abs/2004.10424v1
• Date: Wed, 22 Apr 2020 07:47:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-10 17:38:13.609335
• Title: Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
• Title（参考訳）: 多目的最小スパンディングツリー問題に対するバイアス付き変異を持つ進化アルゴリズムのランタイム解析
• Authors: Vahid Roostapour, Jakob Bossek, Frank Neumann
• Abstract要約: 我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。 我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。 我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
• 参考スコア（独自算出の注目度）: 12.098400820502635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if heavy edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound -- as unbiased mutation -- in the worst case and benefits from bias if the circumstances are favorable.
• Abstract（参考訳）: 進化的アルゴリズム(EA)は、通常、偏見のない探索を行う汎用的な問題解決法である。 これはブラックボックスのシナリオでは合理的で望ましい。 組合せ最適化問題では、最適解の構造に関するより多くの知識が与えられ、バイアス付き探索演算子によって活用される。 我々は,単目的および多目的バージョンにおける最小スパンディングツリー(mst)問題を考察し,低ドーミネーション数の観点から低ランクのエッジの選択に重点を置いたバイアス付き突然変異を導入する。 バイアス付き突然変異が(pareto-)最適解が見つかるまで、期待されるランタイムを著しくスピードアップできるグラフの例を示す。 一方,重いエッジが最適解の一部である必要のある場合には,バイアスが指数関数的ランタイムにつながることを実証する。 しかし、単目的設定の一般グラフでは、各ステップにおいて等確率で非偏りまたは偏りのエッジ選択を決定する複合突然変異作用素が、最悪の場合において、多項式上界(非偏りの突然変異)を示し、状況が好ましくなければバイアスの恩恵を受けることを示す。

関連論文リスト

• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。 特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
  論文  参考訳（メタデータ） (2024-02-01T09:18:34Z)
• Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima [12.009357100208353]
  本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。 EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
  論文  参考訳（メタデータ） (2023-10-06T06:32:07Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
  我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。 我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
  論文  参考訳（メタデータ） (2022-04-27T08:40:33Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  本稿では,染色体ランクを用いた突然変異確率生成の代替手法を提案する。 単純な遺伝的アルゴリズム(SGA)と一定の突然変異確率と限られた資源制約内での適応的アプローチとの比較実験を行った。
  論文  参考訳（メタデータ） (2021-04-18T12:41:33Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem [13.264683014487376]
  多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。 単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
  論文  参考訳（メタデータ） (2020-10-21T11:50:49Z)
• 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)

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

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