論文の概要: On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem

• arxiv url: http://arxiv.org/abs/2306.00222v1
• Date: Wed, 31 May 2023 22:35:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-02 19:09:28.158676
• Title: On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem
• Title（参考訳）: 単目的部分グラフに基づく二目的最小スパンニングツリー問題の解法について
• Authors: Jakob Bossek, Christian Grimme
• Abstract要約: 我々は、進化的計算を取り入れた$mathcalNP$-hard multi-objective least- spanning tree problem (moMST)の効率的な近似に寄与する。 得られた知見に基づいて、高バイアスのサブグラフベースの突然変異演算子を設計する。 その結果,サブグラフベースの演算子が文献のベースラインアルゴリズムに勝っていることを確認した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We contribute to the efficient approximation of the Pareto-set for the classical $\mathcal{NP}$-hard multi-objective minimum spanning tree problem (moMST) adopting evolutionary computation. More precisely, by building upon preliminary work, we analyse the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph. We prove runtime complexity results for the introduced operators and investigate the desirable Pareto-beneficial property. This property states that mutants cannot be dominated by their parent. Moreover, we perform an extensive experimental benchmark study to showcase the operator's practical suitability. Our results confirm that the sub-graph based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs with different shapes of the Pareto-front.
• Abstract（参考訳）: 我々は、進化計算を取り入れた古典的な$\mathcal{NP}$-hard multi-objective minimum spaning tree problem (moMST)に対するパレート集合の効率的な近似に寄与する。 より正確には、予備的な作業に基づいて、パレート最適スパンディングツリーの近傍構造を分析し、得られた知見に基づいて、高度に偏りのあるサブグラフベースの突然変異演算子を設計する。 一言で言えば、これらの演算子は候補解の(未)連結部分木を局所最適部分木に置き換える。 後者(バイアス)ステップは、Kruskalの単目的MSTアルゴリズムを部分グラフの重み付き和スカラー化に適用することにより実現される。 導入した演算子のランタイム複雑性を実証し,pareto-beneficial特性について検討する。 この性質は、変異体が親によって支配されないことを示している。 さらに,操作者の実用性を示すために,広範な実験ベンチマークを行った。 本結果は,パレートフロントの異なる4種類の完全グラフの関数評価において,計算予算が厳しく制限されても,サブグラフベースの演算子が文献からベースラインアルゴリズムを破ることを確認する。

関連論文リスト

• Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing [23.091613114955543]
  予測木を平均化することにより,既存の不連続な動作の異なるアンサンブルを構築することを提案する。 次に、タスクに取り組むための効率的な正確なアルゴリズムを開発し、全てのサンプルに対して妥当な時間で実行します。 3つのデータセットの結果は、我々のメソッドがすべてのメトリクスですべてのベースラインを上回っていることを示している。
  論文  参考訳（メタデータ） (2024-02-29T21:49:31Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems [16.803653908913514]
  本稿では,多目的最小重み付け木問題などの古典的NPハード問題を抽象化した多目的最小重み付け木問題について検討する。 極点数に対する近似品質や上限値など,非支配面の凸殻のいくつかの重要な性質を証明した。 適切な設定でMOEA/Dアルゴリズムは、オラクルモデルにおいて期待される固定対象時間内の全ての極端点を求める。
  論文  参考訳（メタデータ） (2023-06-06T05:13:29Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• On graph-based reentrancy-free semantic parsing [5.228711636020665]
  本論文では,2つの課題を解消する意味解析のためのグラフベースの手法を提案する。 MAP推論と潜在タグアンカリング(弱教師付き学習が要求される)の両方がNPハード問題であることを示す。 本稿では,制約平滑化と条件勾配に基づく2つの最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-15T14:14:09Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• Measure Inducing Classification and Regression Trees for Functional Data [0.0]
  機能的データ分析の文脈における分類と回帰問題に対する木に基づくアルゴリズムを提案する。 これは、制約付き凸最適化により重み付き汎函数 L2$ 空間を学習することで達成される。
  論文  参考訳（メタデータ） (2020-10-30T18:49:53Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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