論文の概要: Time Complexity Analysis of Evolutionary Algorithms for 2-Hop
(1,2)-Minimum Spanning Tree Problem
- arxiv url: http://arxiv.org/abs/2110.04701v1
- Date: Sun, 10 Oct 2021 04:35:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 21:24:24.281929
- Title: Time Complexity Analysis of Evolutionary Algorithms for 2-Hop
(1,2)-Minimum Spanning Tree Problem
- Title（参考訳）: 2-hop(1,2)-minimum spanning tree問題に対する進化アルゴリズムの時間複雑性解析
- Authors: Feng Shi, Frank Neumann, Jianxin Wang
- Abstract要約: 2-Hop (1,2)-Minimum Spanning Tree problem (略MSTP) の制約付きバージョンを進化アルゴリズムの文脈で検討し、NPハードであることが示されている。
2-ホップスパンニングツリーの特別な構造に着想を得て、(1+1) EA はエッジベース表現の探索点を持ち、これは問題にはあまり自然とは思えず、期待する時間に上限を与えて$frac32$-approximate の解を得る。
- 参考スコア（独自算出の注目度）: 20.624629608537894
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial
optimization problem that has been extensively studied by the researchers in
the field of evolutionary computing to theoretically analyze the optimization
performance of evolutionary algorithms. Within the paper, we consider a
constrained version of the problem named 2-Hop (1,2)-Minimum Spanning Tree
problem (abbr. 2H-(1,2)-MSTP) in the context of evolutionary algorithms, which
has been shown to be NP-hard. Following how evolutionary algorithms are applied
to solve the MSTP, we first consider the evolutionary algorithms with search
points in edge-based representation adapted to the 2H-(1,2)-MSTP (including the
(1+1) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two
variants). More specifically, we separately investigate the upper bounds on
their expected time (i.e., the expected number of fitness evaluations) to
obtain a $\frac{3}{2}$-approximate solution with respect to different fitness
functions. Inspired by the special structure of 2-hop spanning trees, we also
consider the (1+1) EA with search points in vertex-based representation that
seems not so natural for the problem and give an upper bound on its expected
time to obtain a $\frac{3}{2}$-approximate solution, which is better than the
above mentioned ones.
- Abstract（参考訳）: 最小スパンニングツリー問題(英: Minimum Spanning Tree problem、略称MSTP)は、進化的アルゴリズムの最適化性能を理論的に解析する進化コンピューティングの分野で研究者によって広く研究されている、よく知られた組合せ最適化問題である。
本稿では,2-Hop (1,2)-Minimum Spanning Tree problem (abbr) という問題の制約版を検討する。
2H-(1,2)-MSTPは進化アルゴリズムの文脈においてNPハードであることが示されている。
まず,2h-(1,2)-mstp( (1+1) ea, global simple evolutionary multi-objective optimizerとその2つの変種を含む)に適応したエッジベース表現における探索点を持つ進化的アルゴリズムを考える。
より具体的には、異なるフィットネス機能に関して$\frac{3}{2}$-approximate の解を得るために、期待される時間(つまり、期待されるフィットネス評価の数)の上限を別々に調査する。
2-ホップスパンディングツリーの特別な構造に触発されて、(1+1) ea が頂点ベースの表現で探索点を持ち、問題に対してそれほど自然なものではなく、期待された時間上の上限を与えて、上記の解よりもよい$\frac{3}{2}$-approximate 解を得る。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。
GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。
これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
論文 参考訳（メタデータ） (2024-07-11T09:37:21Z) - The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
論文 参考訳（メタデータ） (2023-05-22T19:59:19Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on
Clustered Shortest-Path Tree problem [2.578242050187029]
CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。
探索処理の性能を向上させるために,2つの手法を提案する。
論文 参考訳（メタデータ） (2020-10-19T08:37:18Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - 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) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Analysis of Evolutionary Algorithms on Fitness Function with
Time-linkage Property [27.660240128423176]
実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。
本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
論文 参考訳（メタデータ） (2020-04-26T07:56:40Z) - Devolutionary genetic algorithms with application to the minimum
labeling Steiner tree problem [0.0]
本稿では、進化的遺伝的アルゴリズムを特徴付けるとともに、最小ラベル付けスタイナーツリー(MLST)問題を解く際の性能を評価する。
我々は、進化的アルゴリズムを、時間とともに超最適で実現不可能な解の集団を進化させることによって実現可能な解に到達する過程として定義する。
我々は, 交叉, 突然変異, 適合性などの古典的進化的概念が, 最適解, 最適解に到達するためにどのように適応できるかを示す。
論文 参考訳（メタデータ） (2020-04-18T13:27:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。