論文の概要: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem

• arxiv url: http://arxiv.org/abs/2010.10913v2
• Date: Tue, 27 Apr 2021 12:38:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 23:25:31.294712
• Title: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
• Title（参考訳）: 進化的多様性の最適化と最小スパンディングツリー問題
• Authors: Jakob Bossek, Frank Neumann
• Abstract要約: 多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。 単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
• 参考スコア（独自算出の注目度）: 13.264683014487376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of $\mu=2$ fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple $(\mu+1)$-EA can effectively compute a diversified population of spanning trees of high quality.
• Abstract（参考訳）: 進化計算の分野では、与えられた最適化問題に対する様々な高品質な解の計算が、進化的多様性最適化という用語の下で近年勢いを増している。 多様性最適化のためのベースライン進化アルゴリズムの動作原理に関する理論的洞察はまだ稀である。 本稿では,集団の多様性をペアワイズエッジ重なりの和で測定する多様性最適化の文脈において,よく知られた最小スパンディングツリー問題(mst)について検討する。 理論的な結果は、MSTの多様性最適化問題におけるフィットネスランドスケープに関する洞察を与え、もし人口が$\mu=2$のフィットネスプラトー(一定長さ)であっても、多項式時間で様々な集合を計算できることを指摘した。 我々は、全ての解が最小品質のしきい値を満たす必要がある場合、制約のない一連の実験で理論結果を補足する。 以上の結果から, 単純$(\mu+1)$-EAは, 品質の高い木々の多種多様な個体群を効果的に計算できることが示唆された。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax [13.026567958569965]
  両目的のベンチマーク問題であるOneMinにおいて,GSEMOアルゴリズムの多様性向上による人口の多様性の最適化について検討した。 問題サイズ$n$が奇数である場合、期待時間$O(n2)$で最適な多様性を持つ集団が見つかることを証明している。 目標を達成するために、人口のランダムウォークを分析し、人口の変化頻度とその成果を反映する。
  論文  参考訳（メタデータ） (2023-07-14T09:43:29Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
  マルチモーダル最適化は高い適合性ソリューションを生み出し、品質の多様性は遺伝的中立性に敏感ではない。 オートエンコーダは表現型特徴を自動的に発見するために使用され、品質の多様性を備えたさらに多様なソリューションセットを生成する。
  論文  参考訳（メタデータ） (2021-05-10T10:39:03Z)
• Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem [11.590506672325668]
  我々は,高次エントロピー尺度(High-order entropy measure)と呼ばれる集団多様性尺度を進化的アルゴリズムに応用し,トラベリングセールスパーソン問題に対する多様な高品質な解を求める。 最近提案されたエッジベースの多様性最適化アプローチと比較して,多数のソリューションや長いセグメントを扱う場合に比べて,大幅な改善が見られた。
  論文  参考訳（メタデータ） (2021-04-28T02:36:14Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)
• 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)

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

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