論文の概要: Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics

• arxiv url: http://arxiv.org/abs/2404.04018v1
• Date: Fri, 5 Apr 2024 11:02:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-08 16:24:44.827754
• Title: Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics
• Title（参考訳）: 電力線パラメータ選択と簡易グリーディヒューリスティックに基づく目標集合選択問題の上位遺伝的アルゴリズム
• Authors: Benjamin Doerr, Martin S. Krejca, Nguyen Vu,
• Abstract要約: 本稿では,2つの簡単な修正を施したバイアスランダムキー遺伝的アルゴリズム(BRKGA)により,より優れた結果が得られることを示す。 すると、グラフ全体に到達するのに不要な、小さな度合いの頂点を何度も捨てるために、自然な欲求を加える。 結果として得られるアルゴリズムは、最先端の全てのアルゴリズムを一貫して上回る。
• 参考スコア（独自算出の注目度）: 9.044970217182117
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed randomized search heuristics, namely a biased random-key genetic algorithm (BRKGA) obtained from extensive parameter tuning, a max-min ant system (MMAS), and a MMAS using Q-learning with a graph convolutional network. We show that the BRKGA with two simple modifications and without the costly parameter tuning obtains significantly better results. Our first modification is to simply choose all parameters of the BRKGA in each iteration randomly from a power-law distribution. The resulting parameterless BRKGA is already competitive with the tuned BRKGA, as our experiments on the previously used benchmarks show. We then add a natural greedy heuristic, namely to repeatedly discard small-degree vertices that are not necessary for reaching the whole graph. The resulting algorithm consistently outperforms all of the state-of-the-art algorithms. Besides providing a superior algorithm for the TSS problem, this work shows that randomized parameter choices and elementary greedy heuristics can give better results than complex algorithms and costly parameter tuning.
• Abstract（参考訳）: 対象集合選択問題(TSS)は、これらの頂点から始まる影響拡散過程がグラフ全体に到達するように一連の頂点を求める。 このNP-hard問題に対する現在の最先端は、最近提案された3つのランダム化探索ヒューリスティック、すなわち、広範囲なパラメータチューニングから得られるバイアス付きランダムキー遺伝的アルゴリズム(BRKGA)、最大アントシステム(MMAS)、グラフ畳み込みネットワークを用いたQ-ラーニングを用いたMMASである。 BRKGAは2つの簡単な修正を施し,コストのかかるパラメータチューニングを伴わずに,より優れた結果が得られることを示す。 最初の修正は、各反復におけるBRKGAの全てのパラメータを、無作為な分布からランダムに選択することです。 パラメータレスBRKGAは、以前に使用したベンチマークで行った実験から、既に調整されたBRKGAと競合している。 次に、自然な欲求的ヒューリスティック、すなわちグラフ全体に到達するのに不要な小次頂点を何度も破棄する。 結果として得られるアルゴリズムは、最先端の全てのアルゴリズムを一貫して上回る。 この研究は、TSS問題に対して優れたアルゴリズムを提供することに加えて、ランダム化されたパラメータ選択と初等グリーディヒューリスティックスにより、複雑なアルゴリズムや高価なパラメータチューニングよりも優れた結果が得られることを示す。

関連論文リスト

• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。 ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。 本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-05T21:24:11Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulateは、グローバル最適化のための進化的最適化アルゴリズムとソフトウェアパッケージである。 提案アルゴリズムは, 選択, 突然変異, 交叉, 移動の変種を特徴とする。 Propulateは解の精度を犠牲にすることなく、最大で3桁高速であることがわかった。
  論文  参考訳（メタデータ） (2023-01-20T18:17:34Z)
• Iterative-Free Quantum Approximate Optimization Algorithm Using Neural Networks [20.051757447006043]
  そこで本稿では,ニューラルネットワークを用いて与えられた問題に対して,より優れたパラメータを求めるための実践的手法を提案する。 我々の手法は一貫して収束し、最終結果も最高速である。
  論文  参考訳（メタデータ） (2022-08-21T14:05:11Z)
• LAWS: Look Around and Warm-Start Natural Gradient Descent for Quantum Neural Networks [11.844238544360149]
  Vari Quantum Algorithm (VQA) は、ノイズ中間スケール量子コンピュータ (NISQ) における有望な性能のために最近注目されている。 パラメータ化量子回路(PQC)上でランダムなパラメータを持つVQAは、勾配が量子ビット数で指数関数的に消えるバレンプラトー(BP)によって特徴づけられる。 本稿では、古典的な1次最適化点から、VQAでよく使われるアルゴリズムの1つである量子自然勾配(QNG)について述べる。 そして、私たちはアンダーラインAroundアンダーラインを提案しました。
  論文  参考訳（メタデータ） (2022-05-05T14:16:40Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。 本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。 我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-03-15T13:17:53Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution [8.34061303235504]
  ほとんどの進化的アルゴリズムは複数のパラメータを持ち、その値は性能に大きな影響を及ぼす。 そこで本研究では,各繰り返しにおけるパラメータの値を,適切にスケールされたパワー・ロー分布からランダムに選択する,遅延だが効果的な解を提案する。 静的パラメータで知られている最高のパフォーマンスに匹敵する性能を保証する。
  論文  参考訳（メタデータ） (2021-04-14T09:17:18Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22: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)

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

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