論文の概要: Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem

• arxiv url: http://arxiv.org/abs/2001.08903v1
• Date: Fri, 24 Jan 2020 07:10:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-07 04:57:24.335203
• Title: Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
• Title（参考訳）: 動的重み付き頂点被覆問題に対するランダム探索ヒューリスティックのランタイム性能
• Authors: Feng Shi, Frank Neumann, Jianxin Wang
• Abstract要約: 古典的重み付き頂点被覆問題の動的モデルを提案する。 本研究では,Randomized Local Search と (1+1) EA の性能解析を行った。
• 参考スコア（独自算出の注目度）: 20.624629608537894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic Weighted Vertex Cover problem and analyze the runtime performances of the well-studied algorithms Randomized Local Search and (1+1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual form of the Linear Programming formulation for the problem and study the expected runtime that the adapted algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated, with or without the 1/5-th rule that is employed to control the increasing/decreasing rate of the step size. Our results show that three of the four algorithms presented in the paper can recompute 2-approximate solutions for the studied dynamic changes in polynomial expected runtime, but the (1+1) EA with 1/5-th Rule requires pseudo-polynomial expected runtime.
• Abstract（参考訳）: 進化アルゴリズムのようなランダム化探索ヒューリスティックは動的組合せ最適化問題にしばしば適用される。 本稿では,古典的重み付き頂点被覆問題の動的モデルを提示し,よく研究されているアルゴリズムのランダム化局所探索と (1+1) eaのランタイム性能を分析し,動的変化を伴う問題に対する進化的計算の理論的理解に寄与する。 本研究では,線形計画定式化の双対形式に基づくエッジベース表現を用いて,与えられた重み付きグラフをエッジ編集や重み付け操作で修正する場合に,適応アルゴリズムが2次解を維持する必要があることを想定した実行時間について検討する。 頂点上の重みがグラフのサイズに対して指数関数的に大きいことを考えると、ステップサイズの増大/減少率を制御するために使用される第1/5規則を取り入れたステップサイズ適応戦略が組み込まれている。 本研究の結果から,多項式予測実行時の動的変化に対する2-近似解を3つのアルゴリズムで再計算できることが示されているが,1/5ルールのEAは擬似多項式予測実行を必要とする。

関連論文リスト

• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。 妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。 このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
  論文  参考訳（メタデータ） (2023-05-17T06:22:11Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Analysis of Quality Diversity Algorithms for the Knapsack Problem [14.12876643502492]
  我々は,knapsack問題における動的プログラミング動作のシミュレーションにQDパラダイムを適用した。 予測された擬似ポリノミカル時間内に最適解を計算することができることを示す。
  論文  参考訳（メタデータ） (2022-07-28T12:15:33Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• 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)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。 この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
  論文  参考訳（メタデータ） (2020-04-27T03:50:24Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  本稿では,この問題クラスにおける近位アルゴリズムの適応型事前条件付け手法を提案する。 不活性エッジのネスト・フォレスト分解により局所収束速度が保証されることを示す。 この結果から,局所収束解析は近似アルゴリズムにおける可変指標選択の指針となることが示唆された。
  論文  参考訳（メタデータ） (2020-02-27T16:33:09Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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