論文の概要: FIMP-HGA: A Novel Approach to Addressing the Partitioning Min-Max Weighted Matching Problem
- arxiv url: http://arxiv.org/abs/2405.03176v1
- Date: Mon, 6 May 2024 05:57:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-07 14:45:09.790793
- Title: FIMP-HGA: A Novel Approach to Addressing the Partitioning Min-Max Weighted Matching Problem
- Title（参考訳）: FIMP-HGA:Min-Max Weighted Matching問題への新たなアプローチ
- Authors: Yuxuan Wang, Jiongzhi Zheng, Jinyao Xie, Kun He,
- Abstract要約: 本稿では,PMMWM に対する高速反復マッチング分割ハイブリッド遺伝的アルゴリズム (FIMP-HGA) を提案する。
マッチング段階では、漸進的な調整によりマッチング複雑性を低減するKM-Mアルゴリズムを提案する。
分割段階では、エリート戦略を取り入れたHybrid Genetic Algorithm (HGA)を導入し、Greedy Partition Crossover (GPX) 演算子を設計する。
- 参考スコア（独自算出の注目度）: 13.431192456490987
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Partitioning Min-Max Weighted Matching (PMMWM) problem, being a practical NP-hard problem, integrates the task of partitioning the vertices of a bipartite graph into disjoint sets of limited size with the classical Maximum-Weight Perfect Matching (MPWM) problem. Initially introduced in 2015, the state-of-the-art method for addressing PMMWM is the MP$_{\text{LS}}$. In this paper, we present a novel approach, the Fast Iterative Match-Partition Hybrid Genetic Algorithm (FIMP-HGA), for addressing PMMWM. Similar to MP$_{\text{LS}}$, FIMP-HGA divides the solving into match and partition stages, iteratively refining the solution. In the match stage, we propose the KM-M algorithm, which reduces matching complexity through incremental adjustments, significantly enhancing runtime efficiency. For the partition stage, we introduce a Hybrid Genetic Algorithm (HGA) incorporating an elite strategy and design a Greedy Partition Crossover (GPX) operator alongside a Multilevel Local Search (MLS) to optimize individuals in the population. Population initialization employs various methods, including the multi-way Karmarkar-Karp (KK) algorithm, ensuring both quality and diversity. At each iteration, the bipartite graph is adjusted based on the current solution, aiming for continuous improvement. To conduct comprehensive experiments, we develop a new instance generation method compatible with existing approaches, resulting in four benchmark groups. Extensive experiments evaluate various algorithm modules, accurately assessing each module's impact on improvement. Evaluation results on our benchmarks demonstrate that the proposed FIMP-HGA significantly enhances solution quality compared to MP$_{\text{LS}}$, meanwhile reducing runtime by 3 to 20 times.
- Abstract（参考訳）: 実践的なNPハード問題であるPMMWM問題は、二部グラフの頂点を、古典的な最大度完全マッチング(MPWM)問題と、限られた大きさの非連結集合に分割するタスクを統合する。
2015年に初めて導入され、PMMWMに対処する最先端のメソッドはMP$_{\text{LS}}$である。
本稿では,PMMWM に対する高速反復マッチング分割ハイブリッド遺伝的アルゴリズム (FIMP-HGA) を提案する。
MP$_{\text{LS}}$と同様、FIMP-HGAは解をマッチとパーティションのステージに分割し、反復的に解を精製する。
マッチング段階では,漸進的な調整によってマッチング複雑性を低減し,実行効率を大幅に向上するKM-Mアルゴリズムを提案する。
分割段階では,エリート戦略を取り入れたHybrid Genetic Algorithm (HGA)を導入し,多段階局所探索(MLS)と共にGreedy Partition Crossover (GPX)演算子を設計し,人口の個人を最適化する。
人口初期化には、マルチウェイカーマーカーカルプ(KK)アルゴリズムなど、様々な手法が使われており、品質と多様性が保証されている。
各イテレーションにおいて、二部グラフは現在のソリューションに基づいて調整され、継続的な改善を目指している。
総合的な実験を行うため,既存手法と互換性のある新しいインスタンス生成手法を開発し,その結果,4つのベンチマーク群が得られた。
大規模な実験は様々なアルゴリズムモジュールを評価し、各モジュールが改善に与える影響を正確に評価する。
ベンチマークの結果,提案したFIMP-HGAはMP$_{\text{LS}}$に比べてソリューションの品質を著しく向上する一方で,ランタイムを3～20倍削減することが示された。
関連論文リスト
- Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。
我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
論文 参考訳（メタデータ） (2024-09-06T17:17:52Z) - Modified CMA-ES Algorithm for Multi-Modal Optimization: Incorporating Niching Strategies and Dynamic Adaptation Mechanism [0.03495246564946555]
本研究では,多モード最適化問題に対する共分散行列適応進化戦略 (CMA-ES) アルゴリズムを改良する。
この拡張は、複数のグローバルミニマの課題への対処、多様性の維持と複雑なフィットネスランドスケープを探索するアルゴリズムの能力の改善に焦点を当てている。
ニッチ戦略と動的適応機構を取り入れて,複数のグローバル最適化を識別・最適化するアルゴリズムの性能を向上する。
論文 参考訳（メタデータ） (2024-07-01T03:41:39Z) - Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization [19.631213689157995]
多目的多様性最適化(MOCO)問題は、様々な現実世界の応用で広く用いられている。
既存のほとんどのニューラルMOCO法は、MOCO問題を一連のSinge-Objective diversity enhancement (SOCO)問題に変換するために問題に依存する。
これらの手法はしばしば、不明瞭で時間を要する正確な超体積計算のため、前面の部分領域を近似する。
論文 参考訳（メタデータ） (2024-05-14T13:42:19Z) - ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳（メタデータ） (2023-12-04T19:00:07Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳（メタデータ） (2022-08-02T01:49:31Z) - Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic
Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
本稿ではHenry Gas Solubility Optimization(HGSO)アルゴリズムの新しい変種であるHGSO(Hybrid HGSO)について述べる。
前者とは異なり、HHGSOは異なるメタヒューリスティックアルゴリズムを提供する複数のクラスタを同じ集団内で共存させることができる。
HHGSOは、適応的な切替係数を持つペナル化および報酬モデルによる動的クラスタ-アルゴリズムマッピングを発明し、メタヒューリスティックなハイブリダイゼーションのための新しいアプローチを提供する。
論文 参考訳（メタデータ） (2021-05-31T12:42:15Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Planning in Markov Decision Processes with Gap-Dependent Sample
Complexity [48.98199700043158]
マルコフ決定過程における計画のための新しいトラジェクトリに基づくモンテカルロ木探索アルゴリズム MDP-GapE を提案する。
我々は, MDP-GapE に要求される生成モデルに対する呼び出し回数の上限を証明し, 確率の高い準最適動作を同定する。
論文 参考訳（メタデータ） (2020-06-10T15:05:51Z) - Generalized Self-Adapting Particle Swarm Optimization algorithm with
archive of samples [0.0]
本稿では,M-GAPSOと呼ばれるアルゴリズムの新バージョンを紹介する。
GAPSOの当初の定式化と比較すると、グローバル再起動管理スキーム、R-Treeベースインデックス内のサンプル収集、グローバルな粒子性能に基づくサンプリング動作の適応、ローカル検索への具体的なアプローチの4つの特徴がある。
論文 参考訳（メタデータ） (2020-02-28T00:03:17Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳（メタデータ） (2020-02-17T20:21:20Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。