論文の概要: Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs
- arxiv url: http://arxiv.org/abs/2203.13877v2
- Date: Fri, 20 Jan 2023 22:52:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-20 20:37:42.405766
- Title: Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs
- Title（参考訳）: 固定パラメータトラクタブルグラフ問題に対する局所的ジャンプ・アンド・リペア制約処理
- Authors: Luke Branson and Andrew M. Sutton
- Abstract要約: グラフ問題における不可能な子孫の確率的修復に使用できる調整されたジャンプ・アンド・リペア操作を備えた(1+1)EAについて検討する。
- 参考スコア（独自算出の注目度）: 3.495114525631289
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Repair operators are often used for constraint handling in constrained
combinatorial optimization. We investigate the (1+1)~EA equipped with a
tailored jump-and-repair operation that can be used to probabilistically repair
infeasible offspring in graph problems. Instead of evolving candidate solutions
to the entire graph, we expand the genotype to allow the (1+1)~EA to develop in
parallel a feasible solution together with a growing subset of the instance (an
induced subgraph). With this approach, we prove that the EA is able to
probabilistically simulate an iterative compression process used in classical
fixed-parameter algorithmics to obtain a randomized FPT performance guarantee
on three NP-hard graph problems. For $k$-VertexCover, we prove that the (1+1)
EA using focused jump-and-repair can find a $k$-vertex cover (if one exists) in
$O(2^k n^2\log n)$ iterations in expectation. This leads to an exponential (in
$k$) improvement over the best-known parameterized bound for evolutionary
algorithms on VertexCover. For the $k$-FeedbackVertexSet problem in
tournaments, we prove that the EA finds a feasible feedback set in
$O(2^kk!n^2\log n)$ iterations in expectation, and for OddCycleTransversal, we
prove the optimization time for the EA is $O(3^k k m n^2\log n)$. For the
latter two problems, this constitutes the first parameterized result for any
evolutionary algorithm. We discuss how to generalize the framework to other
parameterized graph problems closed under induced subgraphs and report
experimental results that illustrate the behavior of the algorithm on a
concrete instance class.
- Abstract（参考訳）: 補修演算子は制約付き組合せ最適化の制約処理によく使用される。
グラフ問題における不可能な子孫の確率的修復に使用できる,調整されたジャンプ・アンド・リペア操作を備えた (1+1)~EA について検討する。
グラフ全体の候補解を進化させる代わりに、(1+1)~eaがインスタンスのサブセット(誘導部分グラフ)と並行して実現可能な解を開発できるように遺伝子型を拡張します。
提案手法では,古典的な固定パラメータアルゴリズムで使用される反復圧縮過程を確率論的にシミュレートし,NP-hardグラフ問題に対するランダムなFPT性能保証を得る。
k$-vertexcover について、集中ジャンプ・アンド・リペアを用いて (1+1) ea が$o(2^k n^2\log n)$ の反復で $k$-vertex cover を見つけることができることを証明している。
これにより、VertexCover上の進化的アルゴリズムの最もよく知られたパラメータ化境界よりも指数関数的に($k$で)改善される。
トーナメントにおける$k$-FeedbackVertexSet問題に対して、EAが$O(2^kk!
n^2\log n)$ iterations in expectation, and for OddCycleTransversal, we prove the optimization time for the EA is $O(3^k k m n^2\log n)$。
後者の2つの問題に対して、これは任意の進化的アルゴリズムの最初のパラメータ化結果を構成する。
本稿では,誘導サブグラフの下で閉じた他のパラメータ化グラフ問題に対するフレームワークの一般化と,具体的なインスタンスクラスにおけるアルゴリズムの振る舞いを説明する実験結果について述べる。
関連論文リスト
- 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Improved Runtime Results for Simple Randomised Search Heuristics on
Linear Functions with a Uniform Constraint [11.228244128564512]
均一制約下での線形関数のクラスについて検討し、ランダム化局所探索(RLS)の期待最適時間について検討する。
RLS に対して $Theta(n2)$ の厳密な境界を証明し、(1+1) EA の既知上界を改善する。
論文 参考訳（メタデータ） (2020-10-21T10:42:39Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳（メタデータ） (2020-05-15T21:14:22Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。