.png){kind=icon}
.png){kind=icon}
Return
An Efficient Memetic Algorithm for the Max-Bisection Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2013.7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The max-bisection problem consists in partitioning the vertices of a weighted undirected graph into two equally sized subsets so as to maximize the sum of the weights of crossing edges. It is an NP-hard combinatorial optimization problem that arises in many applications. In this paper, we present a memetic algorithm for the max-bisection problem, which integrates a new fast local search procedure, a crossover operator, and a pool updating strategy. These strategies achieve a balance between intensification and diversification. Extensive experiments were performed on a number of benchmark instances with 800 to 10,000 vertices from the literature. The proposed memetic algorithm improved the best known solutions for all benchmark instances tested in this paper. The improvement in terms of cut value over the CirCut by Burer et al. [34] ranging from 0.02 to 4.15 percent, and the average time of our proposed memetic algorithm is much lower than that of CirCut. It shows that the proposed memetic algorithm can find high quality solutions in an acceptable running time.
Keywords:
The max-bisection problem
local search
memetic algorithm
combinatorial optimization
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.8
Papers:
5.3K
Citations:
9.8K