Title: A memetic algorithm for the max-cut problem

Authors: Geng Lin; Wenxing Zhu

Addresses: Department of Mathematics, Minjiang University, Fuzhou, China ' Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou, China

Abstract: Given an undirected graph G = (V, E) with a set V of vertices, and a set E of edges with weights, the max-cut problem consists of partitioning all vertices into two independent sets such that the sum of the weights of the edges between different sets is maximised. The max-cut problem is an NP-hard problem. An efficient memetic algorithm is proposed in this paper for the problem. The proposed memetic algorithm uses a local search procedure and a new crossover operator based on the encoding characteristic of the max-cut problem to generate new offsprings. Then the algorithm uses a function, which takes into account both the solution quality and the diversity of population, to control the population updating. Experiments were performed on three sets of benchmark instances of size up to 10,000 vertices. Experiment results and comparisons demonstrate the effectiveness of the proposed algorithm in both solution quality and computational time.

Keywords: max-cut problem; local search; memetic algorithm; combinatorial optimisation; computing science; memetics.

DOI: 10.1504/IJCSM.2015.067544

International Journal of Computing Science and Mathematics, 2015 Vol.6 No.1, pp.69 - 77

Received: 11 Jul 2014
Accepted: 26 Aug 2014
Published online: 19 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article