論文の概要: Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem
- arxiv url: http://arxiv.org/abs/2409.18157v1
- Date: Thu, 26 Sep 2024 12:50:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-06 15:41:17.990716
- Title: Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem
- Title（参考訳）: 組換えと確率性:最大斜め問題の比較研究
- Authors: Michael Vella, John Abela, Kristian Guillaumier,
- Abstract要約: 最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。
様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。
以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
- 参考スコア（独自算出の注目度）: 0.393259574660092
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The maximum clique problem (MCP) is a fundamental problem in graph theory and in computational complexity. Given a graph G, the problem is that of finding the largest clique (complete subgraph) in G. The MCP has many important applications in different domains and has been much studied. The problem has been shown to be NP-Hard and the corresponding decision problem to be NP-Complete. All exact (optimal) algorithms discovered so far run in exponential time. Various meta-heuristics have been used to approximate the MCP. These include genetic and memetic algorithms, ant colony optimization, greedy algorithms, Tabu algorithms, and simulated annealing. This study presents a critical examination of the effectiveness of applying genetic algorithms (GAs) to the MCP compared to a purely stochastic approach. Our results indicate that Monte Carlo algorithms, which employ random searches to generate and then refine sub-graphs into cliques, often surpass genetic algorithms in both speed and capability, particularly in less dense graphs. This observation challenges the conventional reliance on genetic algorithms, suggesting a reevaluation of the roles of the crossover and mutation operators in exploring the solution space. We observe that, in some of the denser graphs, the recombination strategy of genetic algorithms shows unexpected efficacy, hinting at the untapped potential of genetic methods under specific conditions. This work not only questions established paradigms but also opens avenues for exploring algorithmic efficiency in solving the MCP and other NP-Hard problems, inviting further research into the conditions that favor purely stochastic methods over genetic recombination and vice versa.
- Abstract（参考訳）: 最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論および計算複雑性における基本的な問題である。
グラフ G が与えられたとき、問題は G において最大の傾き(完全部分グラフ)を見つけることである。
この問題はNP-Hardであり、それに対応する決定問題はNP-Completeであることが示されている。
これまでに発見された全ての正確な(最適)アルゴリズムは指数時間で実行されている。
MCPを近似するために様々なメタヒューリスティックが用いられている。
その中には、遺伝子およびメメティックアルゴリズム、アリコロニー最適化、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングが含まれる。
本研究は, 遺伝的アルゴリズム(GA)をMSPに適用することの有効性について, 純粋確率的アプローチと比較した。
以上の結果からモンテカルロのアルゴリズムは, 高速・高密度なグラフ, 特に低密度グラフにおいて, 遺伝的アルゴリズムを超越していることがわかった。
この観察は、従来の遺伝的アルゴリズムへの依存に挑戦し、解空間の探索におけるクロスオーバーと突然変異演算子の役割の再評価を示唆している。
より高密度なグラフでは、遺伝的アルゴリズムの組換え戦略が予期せぬ有効性を示し、特定の条件下での遺伝的手法の未発見の可能性を示している。
この研究は、パラダイムを確立しただけでなく、MPPや他のNP-Hard問題の解法におけるアルゴリズム効率を探求するための道を開き、遺伝的組換えよりも純粋に確率的手法を好む条件についてさらなる研究を促している。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Modified Multiple Sequence Alignment Algorithm on Quantum Annealers (MAQ) [0.0]
本稿では,生物情報学と遺伝的シークエンシングの分野に応用した量子アニールに対する改良型MSAアルゴリズムを提案する。
我々は、アルゴリズムにより多くの量子複素数を導入しながら、スピン使用率の線形化を達成するために、プログレッシブアライメント手法を適用した。
論文 参考訳（メタデータ） (2024-03-24T01:57:38Z) - Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文 参考訳（メタデータ） (2024-02-01T09:18:34Z) - CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。
この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
論文 参考訳（メタデータ） (2022-08-01T17:34:07Z) - An Application of a Multivariate Estimation of Distribution Algorithm to
Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。
より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。
我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文 参考訳（メタデータ） (2022-05-17T15:28:46Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳（メタデータ） (2020-11-06T21:56:41Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Performance Analysis of Meta-heuristic Algorithms for a Quadratic
Assignment Problem [6.555180412600522]
二次代入問題 (QAP) はNPハード問題に属する最適化問題である。
ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。
本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
論文 参考訳（メタデータ） (2020-07-29T15:02:07Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。