論文の概要: An island-parallel ensemble metaheuristic algorithm for large graph coloring problems

• arxiv url: http://arxiv.org/abs/2504.15082v1
• Date: Mon, 21 Apr 2025 13:15:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-29 16:28:27.136238
• Title: An island-parallel ensemble metaheuristic algorithm for large graph coloring problems
• Title（参考訳）: 大規模グラフ着色問題に対する島並列アンサンブルメタヒューリスティックアルゴリズム
• Authors: Tansel Dokeroglu, Tayfun Kucukyilmaz, Ahmet Cosar,
• Abstract要約: 大規模GCPインスタンスを解決するために,島並列アンサンブルメタヒューリスティックアルゴリズム(PEM-Color)を提案する。 私たちの知る限りでは、これはメタヒューリスティックスを組み合わせて、アンサンブルアプローチを使用してGCPに適用する最初の研究です。
• 参考スコア（独自算出の注目度）: 0.4915744683251149
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Coloring Problem (GCP) is an NP-Hard vertex labeling problem in graphs such that no two adjacent vertices can have the same color. Large instances of GCP cannot be solved in reasonable execution times by exact algorithms. Therefore, soft computing approaches, such as metaheuristics, have proven to be very efficient for solving large instances of GCP. In this study, we propose a new island-parallel ensemble metaheuristic algorithm (PEM-Color) to solve large GCP instances. Ensemble learning is a new machine learning approach based on combining the output of multiple models instead of using a single one. We use Message Passing Interface (MPI) parallel computation libraries to combine recent state-of-the-art metaheuristics: Harris Hawk Optimization (HHO), Artificial Bee Colony (ABC), and Teaching Learning Based (TLBO) to improve the quality of their solutions further. To the best of our knowledge, this is the first study that combines metaheuristics and applies to the GCP using an ensemble approach. We conducted experiments on large graph instances from the well-known DIMACS benchmark using 64 processors and achieved significant improvements in execution times. The experiments also indicate an almost linear speed-up with a strong scalability potential. The solution quality of the instances is promising, as our algorithm outperforms 13 state-of-the-art algorithms.
• Abstract（参考訳）: グラフ色問題 (GCP) は、隣接する2つの頂点が同じ色を持つことができないようなグラフにおけるNP-ハード頂点ラベル問題である。 GCPの大規模なインスタンスは、正確なアルゴリズムで適切な実行時間では解決できない。 したがって、メタヒューリスティックスのようなソフトコンピューティングアプローチは、GCPの大規模インスタンスを解くのに非常に効率的であることが証明されている。 本研究では,大規模なGCPインスタンスを解決するために,島並列アンサンブルメタヒューリスティックアルゴリズム(PEM-Color)を提案する。 Ensemble Learningは、単一のモデルではなく、複数のモデルの出力を組み合わせることに基づく、新しい機械学習アプローチである。 我々は、最近の最先端メタヒューリスティック(HHO)、人工ビーコロニー(ABC)、教育学習ベース(TLBO)を結合するために、メッセージパッシングインタフェース(MPI)並列計算ライブラリを使用し、そのソリューションの質をさらに向上させる。 私たちの知る限りでは、これはメタヒューリスティックスを組み合わせて、アンサンブルアプローチを使用してGCPに適用する最初の研究です。 我々は64プロセッサを用いて、よく知られたDIMACSベンチマークから大規模グラフインスタンスの実験を行い、実行時間を大幅に改善した。 実験はまた、スケーラビリティの強いほぼ直線的なスピードアップを示す。 私たちのアルゴリズムは13の最先端のアルゴリズムより優れているので、インスタンスのソリューションの品質は有望です。

関連論文リスト

• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines [1.1970409518725493]
  ソフトウェア製品ライン(SPL)では、多数の有効な機能の組み合わせが存在するため、家族のすべての製品をテストするのは難しい、あるいは不可能かもしれない。 本研究では,Construct, Merge, Solve & Adapt というハイブリッド・メピエリスト的アプローチに基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2024-02-07T05:43:57Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

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

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