Related papers: FIMP-HGA: A Novel Approach to Addressing the Partitioning Min-Max Weighted Matching Problem

FIMP-HGA: A Novel Approach to Addressing the Partitioning Min-Max Weighted Matching Problem

URL: http://arxiv.org/abs/2405.03176v1
Date: Mon, 6 May 2024 05:57:46 GMT
Title: FIMP-HGA: A Novel Approach to Addressing the Partitioning Min-Max Weighted Matching Problem
Authors: Yuxuan Wang, Jiongzhi Zheng, Jinyao Xie, Kun He,
Abstract summary: We present a novel approach, the Fast Iterative Match-Partition Hybrid Genetic Algorithm (FIMP-HGA) for addressing PMMWM. In the match stage, we propose the KM-M algorithm, which reduces matching complexity through incremental adjustments. For the partition stage, we introduce a Hybrid Genetic Algorithm (HGA) incorporating an elite strategy and design a Greedy Partition Crossover (GPX) operator.
Score: 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.

Related papers

A Greedy Strategy for Graph Cut [95.2841574410968]
We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
arXiv Detail & Related papers (2024-12-28T05:49:42Z)
Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
This work proposes an efficient parallel algorithm for non-monomodular size under a knapsack constraint. Our algorithm improves the existing parallel one from $8+epsilon$ to $7+epsilon$ with $O(log n)$ adaptive complexity.
arXiv Detail & Related papers (2024-09-06T17:17:52Z)
Modified CMA-ES Algorithm for Multi-Modal Optimization: Incorporating Niching Strategies and Dynamic Adaptation Mechanism [0.03495246564946555]
This study modifies the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) algorithm for multi-modal optimization problems. The enhancements focus on addressing the challenges of multiple global minima, improving the algorithm's ability to maintain diversity and explore complex fitness landscapes. We incorporate niching strategies and dynamic adaptation mechanisms to refine the algorithm's performance in identifying and optimizing multiple global optima.
arXiv Detail & Related papers (2024-07-01T03:41:39Z)
ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
We introduce an efficient single-loop primal-dual block-coordinate algorithm, dubbed ALEXR. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions. We present lower complexity bounds to demonstrate that the convergence rates of ALEXR are optimal among first-order block-coordinate algorithms for the considered class of cFCCO problems.
arXiv Detail & Related papers (2023-12-04T19:00:07Z)
Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
arXiv Detail & Related papers (2022-08-02T01:49:31Z)
A novel multiobjective evolutionary algorithm based on decomposition and multi-reference points strategy [14.102326122777475]
Multiobjective evolutionary algorithm based on decomposition (MOEA/D) has been regarded as a significantly promising approach for solving multiobjective optimization problems (MOPs) We propose an improved MOEA/D algorithm by virtue of the well-known Pascoletti-Serafini scalarization method and a new strategy of multi-reference points.
arXiv Detail & Related papers (2021-10-27T02:07:08Z)
Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
This paper discusses a new variant of the Henry Gas Solubility Optimization (HGSO) Algorithm, called Hybrid HGSO (HHGSO) Unlike its predecessor, HHGSO allows multiple clusters serving different individual meta-heuristic algorithms to coexist within the same population. Exploiting the dynamic cluster-to-algorithm mapping via penalized and reward model with adaptive switching factor, HHGSO offers a novel approach for meta-heuristic hybridization.
arXiv Detail & Related papers (2021-05-31T12:42:15Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z)
Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability.
arXiv Detail & Related papers (2020-06-10T15:05:51Z)
Generalized Self-Adapting Particle Swarm Optimization algorithm with archive of samples [0.0]
The paper introduces a new version of the algorithm, abbreviated as M-GAPSO. In comparison with the original GAPSO formulation it includes the following four features: a global restart management scheme, samples gathering within an R-Tree based index, adaptation of a sampling behavior based on a global particle performance, and a specific approach to local search.
arXiv Detail & Related papers (2020-02-28T00:03:17Z)
Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
arXiv Detail & Related papers (2020-02-13T05:42:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.