論文の概要: Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum
Weight Base Problems
- arxiv url: http://arxiv.org/abs/2306.03409v1
- Date: Tue, 6 Jun 2023 05:13:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 17:11:56.747442
- Title: Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum
Weight Base Problems
- Title（参考訳）: 多目的最小重み問題に対するMOEA/Dの剛性解析
- Authors: Anh Viet Do, Aneta Neumann, Frank Neumann, Andrew M. Sutton
- Abstract要約: 本稿では,多目的最小重み付け木問題などの古典的NPハード問題を抽象化した多目的最小重み付け木問題について検討する。
極点数に対する近似品質や上限値など,非支配面の凸殻のいくつかの重要な性質を証明した。
適切な設定でMOEA/Dアルゴリズムは、オラクルモデルにおいて期待される固定対象時間内の全ての極端点を求める。
- 参考スコア（独自算出の注目度）: 16.803653908913514
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the multi-objective minimum weight base problem, an abstraction of
classical NP-hard combinatorial problems such as the multi-objective minimum
spanning tree problem. We prove some important properties of the convex hull of
the non-dominated front, such as its approximation quality and an upper bound
on the number of extreme points. Using these properties, we give the first
run-time analysis of the MOEA/D algorithm for this problem, an evolutionary
algorithm that effectively optimizes by decomposing the objectives into
single-objective components. We show that the MOEA/D, given an appropriate
decomposition setting, finds all extreme points within expected fixed-parameter
polynomial time in the oracle model, the parameter being the number of
objectives. Experiments are conducted on random bi-objective minimum spanning
tree instances, and the results agree with our theoretical findings.
Furthermore, compared with a previously studied evolutionary algorithm for the
problem GSEMO, MOEA/D finds all extreme points much faster across all
instances.
- Abstract（参考訳）: 多目的最小重みベース問題(multi-objective minimum weight base problem)は、多目的最小スパンディングツリー問題のような古典的なnp-ハードコンビネート問題(np-hard combinatorial problem)の抽象化である。
我々は非支配的前線の凸包のいくつかの重要な性質を証明し、その近似的品質や極点数の上限などについて証明する。
これらの特性を用いて,MOEA/Dアルゴリズムを初めて実行時解析し,目的を単一目的成分に分解することで効率よく最適化する進化的アルゴリズムを提案する。
適切な分解条件が与えられたMOEA/Dは、オラクルモデルにおいて、期待される固定パラメータ多項式時間内の全ての極端点、すなわちパラメータが目的数であることを示す。
実験はランダムな二目的最小スパンディングツリーインスタンス上で行われ,実験結果は理論値と一致した。
さらに、以前に研究されたGSEMO問題に対する進化的アルゴリズムと比較すると、MOEA/Dは全てのインスタンスにおいて極端な点をはるかに高速に見つける。
関連論文リスト
- A Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem [0.0]
本稿では,最小連結支配問題の変種に対処するための欲求に基づくシミュレーションアルゴリズムを提案する。
近年の研究では,本手法の優位性について検討した。
論文 参考訳（メタデータ） (2023-12-13T13:36:04Z) - On Single-Objective Sub-Graph-Based Mutation for Solving the
Bi-Objective Minimum Spanning Tree Problem [0.0]
我々は、進化的計算を取り入れた$mathcalNP$-hard multi-objective least- spanning tree problem (moMST)の効率的な近似に寄与する。
得られた知見に基づいて、高バイアスのサブグラフベースの突然変異演算子を設計する。
その結果,サブグラフベースの演算子が文献のベースラインアルゴリズムに勝っていることを確認した。
論文 参考訳（メタデータ） (2023-05-31T22:35:17Z) - Finite-Sum Coupled Compositional Stochastic Optimization: Theory and
Applications [43.48388050033774]
本稿では,非凸目的と凸目標の両方に対して単純なアルゴリズムを包括的に解析する。
また,外層と内層に等しい大きさのバッチをサンプリングすることで,実用的実装を改善するための新たな知見も提示した。
論文 参考訳（メタデータ） (2022-02-24T22:39:35Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳（メタデータ） (2021-10-21T07:28:11Z) - 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) - Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector
Problems [78.95866278697777]
本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。
次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
論文 参考訳（メタデータ） (2021-03-24T23:11:32Z) - Provable Multi-Objective Reinforcement Learning with Generative Models [98.19879408649848]
目的の選好から最適な政策を学習する単一政策 MORL の問題について検討する。
既存の方法は、多目的決定プロセスの正確な知識のような強い仮定を必要とする。
モデルベースエンベロップ値 (EVI) と呼ばれる新しいアルゴリズムを提案し, 包含された多目的$Q$学習アルゴリズムを一般化する。
論文 参考訳（メタデータ） (2020-11-19T22:35:31Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。
GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。
実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
論文 参考訳（メタデータ） (2020-06-20T00:17:44Z) - Convergence of Meta-Learning with Task-Specific Adaptation over Partial
Parameters [152.03852111442114]
モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。
本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
論文 参考訳（メタデータ） (2020-06-16T19:57:48Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。