論文の概要: More Effective Randomized Search Heuristics for Graph Coloring Through
Dynamic Optimization
- arxiv url: http://arxiv.org/abs/2005.13825v1
- Date: Thu, 28 May 2020 07:55:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-27 04:44:07.954472
- Title: More Effective Randomized Search Heuristics for Graph Coloring Through
Dynamic Optimization
- Title（参考訳）: 動的最適化によるグラフカラー化のためのより効率的なランダム化探索ヒューリスティックス
- Authors: Jakob Bossek, Frank Neumann, Pan Peng, Dirk Sudholt
- Abstract要約: 進化的アルゴリズムは、動的最適化を用いて、二部グラフのグラフ彩色問題をより効率的に解くことができることを示す。
3つの島を用いた島式は、すべての$m$-edge二部グラフ上で$Theta(m)$の最適時間で成功し、子孫より優れている。
- 参考スコア（独自算出の注目度）: 15.45783225341009
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dynamic optimization problems have gained significant attention in
evolutionary computation as evolutionary algorithms (EAs) can easily adapt to
changing environments. We show that EAs can solve the graph coloring problem
for bipartite graphs more efficiently by using dynamic optimization. In our
approach the graph instance is given incrementally such that the EA can
reoptimize its coloring when a new edge introduces a conflict. We show that,
when edges are inserted in a way that preserves graph connectivity, Randomized
Local Search (RLS) efficiently finds a proper 2-coloring for all bipartite
graphs. This includes graphs for which RLS and other EAs need exponential
expected time in a static optimization scenario. We investigate different ways
of building up the graph by popular graph traversals such as
breadth-first-search and depth-first-search and analyse the resulting runtime
behavior. We further show that offspring populations (e. g. a (1+$\lambda$)
RLS) lead to an exponential speedup in $\lambda$. Finally, an island model
using 3 islands succeeds in an optimal time of $\Theta(m)$ on every $m$-edge
bipartite graph, outperforming offspring populations. This is the first example
where an island model guarantees a speedup that is not bounded in the number of
islands.
- Abstract（参考訳）: 進化アルゴリズム(EA)は変化する環境に容易に適応できるため、動的最適化問題は進化計算において大きな注目を集めている。
両部グラフのグラフカラー化問題を動的最適化によりより効率的に解けることを示す。
このアプローチでは、グラフインスタンスは段階的に与えられ、新しいエッジが競合を起こすと、eaは色付けを再最適化できます。
グラフ接続性を維持する方法としてエッジを挿入した場合、ランダム化局所探索(RLS)は、すべての二部グラフに対して適切な2色付けを効率的に見つける。
これには、静的最適化シナリオにおいてRSSや他のEAが指数関数的な期待時間を必要とするグラフが含まれる。
本研究では,広帯域探索や奥行き優先探索などの一般的なグラフトラバーサルによるグラフ構築方法を調査し,実行時の動作解析を行う。
また、子孫の個体数(例)も示す。
g.
1+$\lambda$) rls) は、$\lambda$ で指数関数的な高速化をもたらす。
最後に、3つの島を使った島モデルは、1つの$m$-edge二分グラフで$\theta(m)$という最適な時間に成功し、子孫の個体数を上回っている。
これは、島数に制限されないスピードアップを島モデルが保証する最初の例である。
関連論文リスト
- Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。
最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。
我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
論文 参考訳（メタデータ） (2023-10-23T01:25:44Z) - Hierarchical cycle-tree packing model for $K$-core attack problem [0.0]
ここでは、この挑戦的な最適化問題に対して、階層的なサイクルツリーパッキングモデルを導入している。
統計物理学のレプリカ対称キャビティ法を用いて,このモデルを解析する。
関連する階層的サイクルツリー誘導攻撃(tt hCTGA)は、通常のランダムグラフに対するほぼ最適な攻撃解を構築することができる。
論文 参考訳（メタデータ） (2023-03-02T06:47:33Z) - Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。
我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。
特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
論文 参考訳（メタデータ） (2022-06-15T18:20:01Z) - 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) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Time Complexity Analysis of Randomized Search Heuristics for the Dynamic
Graph Coloring Problem [15.45783225341009]
エッジを現在のグラフに追加する動的設定について検討する。
次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
論文 参考訳（メタデータ） (2021-05-26T13:00:31Z) - Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for
Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。
本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
論文 参考訳（メタデータ） (2020-08-03T08:48:41Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z) - Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time [12.43303621344215]
専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。
本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。
最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
論文 参考訳（メタデータ） (2020-06-06T01:35:45Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳（メタデータ） (2020-05-18T14:23:09Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。