.png){kind=icon}
Return
An Improved Memetic Algorithm for the Partial Vertex Cover Problem
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2019.2895738.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
As a generalized form of the classical minimum vertex cover problem (MVCP), the minimum partial vertex cover problem not only inherits the value of MVCP in both theoretical and practical research but also extends the application scenarios under the current era of big data. In order to solve such a classical NP-hard combinatorial optimization problem, we propose an efficient memetic algorithm called MAPVC, the whose motivation behind the idea is a balance between exploitation and exploration. Specifically, the evolutionary process with a powerful backbone crossover and an adaptive mutation is adopted mainly for skipping the local optimum, and the local search with a three-layer encoding, promotive and inhibitory factor interaction is integrated into the framework to ameliorate the solutions. The experimental results on DIMACS and BHOSLIB benchmarks verify the efficiency of MAPVC through comparisons with an exact solver Gurobi and state-of-the-art local search GRASP-PVC. In addition, we also conduct the experiments on parameters setting and strategies validation to provide a comprehensive analysis of MAPVC.
Keywords:
Adaptive mutation
memetic algorithm
minimum partial vertex cover
powerful backbone crossover
promotive and inhibitory factor interaction
three-layer encoding
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.6
Papers:
9.8W
Citations:
29.4W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSaveShareSave
View more