論文の概要: Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values
- arxiv url: http://arxiv.org/abs/2606.17731v1
- Date: Tue, 16 Jun 2026 09:47:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-17 17:15:32.382826
- Title: Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values
- Title（参考訳）: 相対重み値に制限のある進化的アルゴリズムと多目的最小スパンニング木
- Authors: Narges Tavassoli Kejani, Andrew M. Sutton, Frank Neumann,
- Abstract要約: 実用的成功にもかかわらず、多目的問題に対する進化的アルゴリズムのランタイムに関する理論的結果は比較的限られている。
進化的多目的アルゴリズムの新たな実行時結果を導出し、理論的結果を実験により補完する。
- 参考スコア（独自算出の注目度）: 6.387555054340123
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.
- Abstract（参考訳）: 進化的アルゴリズムは、様々な多目的組合せ最適化問題に使われている。
実用的成功にもかかわらず、多目的組合せ問題に対する進化的アルゴリズムのランタイムに関する理論的結果は比較的限られている。
古典的な問題の1つは、パレートフロントのすべての極小角点を計算するために実行時境界が得られた多目的最小スパンニングツリー問題である。
本稿では, エッジウェイトが少数の異なる値を持つ場合のパレートフロントの構造について, より詳細な知見を提供する。
これらの知見に基づき、進化的多目的アルゴリズムの新しい実行時結果を導出し、理論的結果と実験的研究を補完する。
関連論文リスト
- Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation [49.86232017439639]
マルチ出力拡張行動クローン(MA-BC)について紹介する。
MA-BCは、振る舞いの衝突が観測されない状態-動作ペアをプールしながら、専門家データを分離する。
我々は,MA-BCが極小であることを示す,多目的模倣学習のための新しい下位境界を確立する。
論文 参考訳（メタデータ） (2026-05-12T11:49:08Z) - Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum
Weight Base Problems [16.803653908913514]
本稿では,多目的最小重み付け木問題などの古典的NPハード問題を抽象化した多目的最小重み付け木問題について検討する。
極点数に対する近似品質や上限値など,非支配面の凸殻のいくつかの重要な性質を証明した。
適切な設定でMOEA/Dアルゴリズムは、オラクルモデルにおいて期待される固定対象時間内の全ての極端点を求める。
論文 参考訳（メタデータ） (2023-06-06T05:13:29Z) - 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) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - A Pareto-optimal compositional energy-based model for sampling and
optimization of protein sequences [55.25331349436895]
深層生成モデルは、生命科学における逆問題に対する一般的な機械学習ベースのアプローチとして登場した。
これらの問題は、データ分布の学習に加えて、興味のある複数の特性を満たす新しい設計をサンプリングする必要があることが多い。
論文 参考訳（メタデータ） (2022-10-19T19:04:45Z) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳（メタデータ） (2022-05-03T07:54:56Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。
確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。
また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
論文 参考訳（メタデータ） (2020-12-14T03:07:39Z) - Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem [13.264683014487376]
多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。
単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
論文 参考訳（メタデータ） (2020-10-21T11:50:49Z) - Specific Single- and Multi-Objective Evolutionary Algorithms for the
Chance-Constrained Knapsack Problem [14.352521012951865]
我々は、チャンス制約付きknapsack問題に対して、新しい効果的な多目的モデルを提案する。
実験結果から, 進化的多目的アルゴリズムを用いた場合, 性能が大幅に向上することが示唆された。
論文 参考訳（メタデータ） (2020-04-07T08:46:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。