論文の概要: Matrix Domination: Convergence of a Genetic Algorithm Metaheuristic with the Wisdom of Crowds to Solve the NP-Complete Problem
- arxiv url: http://arxiv.org/abs/2403.17939v1
- Date: Thu, 14 Dec 2023 00:42:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-01 02:34:48.505146
- Title: Matrix Domination: Convergence of a Genetic Algorithm Metaheuristic with the Wisdom of Crowds to Solve the NP-Complete Problem
- Title（参考訳）: 行列支配:NP-Complete問題を解決するための集団の知恵と遺伝的アルゴリズムメタヒューリスティックの収束
- Authors: Shane Storm Strachan,
- Abstract要約: マトリックス支配は、細胞のサブセットをマトリックスに配置し、残りの細胞を支配させることが目的である。
この研究は、遺伝的アルゴリズムの探索的性質と群衆の知恵を統合し、より最適な解を見つける。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This research explores the application of a genetic algorithm metaheuristic enriched by the wisdom of crowds in order to address the NP-Complete matrix domination problem (henceforth: TMDP) which is itself a constraint on related problems applied in graphs. Matrix domination involves accurately placing a subset of cells, referred to as dominators, within a matrix with the goal of their dominating the remainder of the cells. This research integrates the exploratory nature of a genetic algorithm with the wisdom of crowds to find more optimal solutions with user-defined parameters to work within computational complexity considerations and gauge performance mainly with a fitness evaluation function and a constraining function to combat the stochastic nature of genetic algorithms. With this, I propose a novel approach to MDP with a genetic algorithm that incorporates the wisdom of crowds, emphasizing collective decision-making in the selection process, and by exploring concepts of matrix permutations and their relevance in finding optimal solutions. Results demonstrate the potential of this convergence to generate efficient solutions, optimizing the trade-off between the number of dominators and their strategic placements within the matrices while efficiently ensuring consistent and complete matrix domination.
- Abstract（参考訳）: 本研究では,NP-Complete行列支配問題(以下TMDP)に対処するために,群集の知恵に富んだ遺伝的アルゴリズムのメタヒューリスティックの適用について検討する。
マトリックス支配は、ドミネーターと呼ばれる細胞のサブセットを正確にマトリックスに配置し、残りの細胞を支配することを目的としている。
本研究は, 遺伝的アルゴリズムの探索的性質と, 群集の知恵を融合して, 計算複雑性を考慮した最適解を求めるとともに, 適応性評価関数と遺伝的アルゴリズムの確率的性質に対処する制約関数を主とする評価性能を求める。
そこで我々は,群集の知恵を取り入れた遺伝的アルゴリズムによるMDPへの新たなアプローチを提案し,選択過程における集団的意思決定を強調するとともに,行列置換の概念と最適解の発見との関連性を探究する。
結果は, ドミネータ数と行列内の戦略配置とのトレードオフを最適化し, 整合性および完全行列支配を効率よく確保し, 効率的な解を生成するためのこの収束の可能性を示す。
関連論文リスト
- Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。
様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。
以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
論文 参考訳（メタデータ） (2024-09-26T12:50:00Z) - Regularized Projection Matrix Approximation with Applications to Community Detection [1.3761665705201904]
本稿では,アフィニティ行列からクラスタ情報を復元するための正規化プロジェクション行列近似フレームワークを提案する。
3つの異なるペナルティ関数について検討し, それぞれが有界, 正, スパースシナリオに対応するように調整した。
合成および実世界の両方のデータセットで行った数値実験により、我々の正規化射影行列近似アプローチはクラスタリング性能において最先端の手法を著しく上回っていることが明らかとなった。
論文 参考訳（メタデータ） (2024-05-26T15:18:22Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
我々はロバスト成分分析のためのアルゴリズムを設計する(A)
行列を低主行列とスパース主行列の和に分解する。
論文 参考訳（メタデータ） (2023-07-12T03:48:26Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - Matrix Reordering for Noisy Disordered Matrices: Optimality and
Computationally Efficient Algorithms [9.245687221460654]
単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。
我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。
そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-01-17T14:53:52Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
非負行列ファクタリゼーションの逆学習版を検討する。
我々の定式化では、攻撃者は与えられたデータ行列に有界ノルムの任意の行列を追加する。
辞書と係数行列を最適化するために, 逆学習に触発された効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-04-10T13:13:17Z) - Epistocracy Algorithm: A Novel Hyper-heuristic Optimization Strategy for
Solving Complex Optimization Problems [1.471992435706872]
本稿では,人間の社会・政治行動と知性を組み込んで複雑な最適化問題を解く,エピストクラシーという新しい進化的アルゴリズムを提案する。
エピストクラシーのアルゴリズムのインスピレーションは、教育を受けた人々が教育を受けていない人や教育を受けていない人よりも投票力を持つ政治体制に端を発する。
実験結果から, エピストクラシーアルゴリズムは, 性能, 精度, 堅牢性の観点から, 最先端の進化的, 群知能アルゴリズムよりも優れていることがわかった。
論文 参考訳（メタデータ） (2021-01-30T19:07:09Z) - Multi-View Spectral Clustering with High-Order Optimal Neighborhood
Laplacian Matrix [57.11971786407279]
マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。
本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。
提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
論文 参考訳（メタデータ） (2020-08-31T12:28:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。